2015 ACM Amman Collegiate Programming Contest I.Bahosain and Digits【思维+暴力枚举】
程序员文章站
2022-06-02 22:44:52
...
题目大意:
给你一个数字串(长度最大为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);
}
}
下一篇: 北极圈远征