CF758 D. Ability To Convert 细节处理字符串

题意：给定进制数n及一串数字,问在此进制下这串数能看成最小的数（10进制）是多少（如HEX下 1|13|11 = 475）

思路：此题要仔细思考细节。首先要想使数最小那么必定有个想法是使低位的数尽可能大即位数尽可能多，个人想法是从最后一位开始向前遍历，如果位数没有超过n的位数且数值比n小，那么该数可以加入上一个分隔。如果不符合条件，则说明该数应该作为新的分隔。

那么在此就有一个问题了，如果一个分隔是以0开始的（如：10000）显然我们也将0认定为是分隔的一部分，但如果有前导0了(11进制 10110)显然分隔是这样的（10|1|10）此时这个0属于最前面的那个分隔。

故当某个数判断不符合加入上一个分隔的条件，那么还要判断下上一个遍历的数字是否是0，否则要逐步回退到非0位,并将过程中这些0作为当前分隔的一部分。

/** @Date    : 2017-04-02-18.25

  * @Author  : Lweleth (SoungEarlf@gmail.com)

  * @Link    : https://github.com/

  * @Version :

  */

#include<bits/stdc++.h>

#define LL long long

#define PII pair

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e5+20;

const double eps = 1e-8;

char a[100];

LL ans = 0;

int main()

{

    LL n;

    while(~scanf("%lld%s", &n, a))

    {

        ans = 0;

        int x = strlen(a);

        int y = 0;

        int t = n;

        while(t)

            y++, t /= 10;

        LL cnt = 1;

        int bit = 0;

        int rec = x - 1;

        LL b = 1;

        for(int i = x - 1; i >= 0; i--)

        {

            if(t + cnt * (a[i] - '0') < n && bit < y)

                t = t + cnt * (a[i] - '0'), cnt *= 10, bit++;

            else

            {

                int ct = 0;

                if(a[i + 1] == '0')//考虑到有前导0时回退加值

                {

                    while(a[i + 1] == '0')

                    {

                        ct++;

                        if(i + 1 == rec)

                            break;

                        i++;

                    }

                }

                ans += t * b;

                b = b * n;

                t = a[i] - '0';

                bit = 1;

                cnt = 10;

                rec = i;

            }

        }

        if(t != 0)

            ans += t * b;

        printf("%lld\n", ans);

    }

    return 0;

}

巴特西

CF758 D. Ability To Convert 细节处理字符串

最新文章

热门文章