跟那个博弈题一样，是个没想出来非常狠，想出来又非常水的题。。果断看题解。。
从第一个数开始计算起，如果到第a个数，所有的和mod n的数字已经出现过，上次出现的点和这次的点之间的连续的数的和一定能被n整除（2个余数一样，一减不就是N的倍数么），所以，只要记录连续数的和除以N的余数就行。一旦发现重复的，就输出两个重复的之间的那段数字。因为有n个数，所以总能得到解。
PS：不是说选择性的选不能得到结果，而是题目只要解，没要最优解，而搜索的复杂度又太大，所
#include<stdio.h>
long n,i,j,sum;
long bj[15001];
long v[10001];
int main()
{
scanf("%ld",&n);
for (i=1;i<=n;i++)
{
bj[i]=-1;
scanf("%ld",&v[i]);
}
bj[0]=0;
for (i=1;i<=n;i++)
{
sum+=v[i];
if (bj[sum%n]==-1)
bj[sum%n]=i;
else
{
printf("%ld\n",i-bj[sum%n]);
for (j=bj[sum%n]+1;j<=i;j++)
printf("%ld\n",v[j]);
return 0;
}
}
}
以上述是最好的解法。
posted on 2011-07-05 23:21
梦转千寻 阅读(56)
评论(0) 编辑 收藏 引用