欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2015 ACM Amman Collegiate Programming Contest I.Bahosain and Digits【思维+暴力枚举】

程序员文章站 2022-06-02 22:44:52
...

2015 ACM Amman Collegiate Programming Contest I.Bahosain and Digits【思维+暴力枚举】


题目大意:


给你一个数字串(长度最大为250),我们每一次可以选定一个数K,使得我们每次操作可以选一个长度为K的连续区间,使得其整体向上加一(9变0);

如果能够通过若干次操作最终使得序列都是一个数字的话,K就算作一个可行答案,我们要求K的最大值。


思路:

我们O(n)枚举答案,因为我们只关心能否构成答案,而不关心最小步数,所以我们再O(10)枚举最终数字都要变成的答案,然后将数字串从左向右扫,如果遇到一个非答案的数字,那么对应我们将其置为想要变成的答案的数字,然后将身后(包括自己)区间长度为K的部分都整体向上调整当前序列。

如果暴力这样处理下去如果是可行的,那么break掉,就得到了答案。


Ac代码:

#include<stdio.h>
#include<string.h>
using namespace std;
char a[450];
int b[450];
int sum[450];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int ok=-1;
        scanf("%s",a);
        int n=strlen(a);
        for(int i=n;i>=1;i--)
        {
            for(int j=0;j<10;j++)
            {
                int flag=0;
                int summ=0;
                memset(sum,0,sizeof(sum));
                for(int k=0;k<n;k++)b[k]=a[k]-'0';
                for(int k=0;k<n;k++)
                {
                    summ+=sum[k];
                    b[k]+=summ;
                    b[k]%=10;
                    if(b[k]==j)continue;
                    else
                    {
                        if(k+i-1>=n)flag=1;
                        if(j>=b[k])
                        {
                            sum[k+1]+=j-b[k];
                            sum[k+1+i-1]+=-(j-b[k]);
                        }
                        else
                        {
                            sum[k+1]+=j-b[k]+10;
                            sum[k+1+i-1]+=-(j-b[k]+10);
                        }
                    }
                }
                if(flag==0)
                {
                    ok=i;
                    break;
                }
            }
            if(ok!=-1)break;
        }
        printf("%d\n",ok);
    }
}