这个题目是Ulm Local 2007比赛的。
今天我们组队做了5个小时Ulm Local 2007比赛
在比赛还有半小时AC了6个还差两个题目
一个是线段数的感觉没时间写了
另一个就是这个了。先开始一直想不出来很好的算法。
听后面一个全做完的队再说这个可以用鸽笼原理来证明还说这个题目只要找出连续的集合就可以了
然后听到之后仔细想了一下感觉有道理
当把所有从第一个开始的部分和对C的余数统计就可以发现
要么就是有一个人给的糖果直接就是C的倍数
要么会出现两个部分和对C取余后得到相同的值
这就说明相同这两个之间的部分和就是C的倍数
然后题目写起来就很简单了
写了没几分钟然后交了就A了
后来下来听那个队说他们这个想法居然是baidu出来的
然后小鄙视了一下他们。
不过想想我也是听力人家说以后才有了想法的啊
1
#include<stdio.h>
2int data[110000];
3int mark[110000],n,c;
4int main()
5
{
6
int i,a,b,sum;
7
while(scanf("%d%d",&c,&n),c){
8
9 for(i=0;i<n;i++){
10 mark[i]=0;
11 scanf("%d",&data[i]);
12
}
13 sum=0;
14 for (i=0;i<n;++i){
15 sum=(sum+data[i])%c;
16 if (sum==0){
17 a=1;
18 b=i+2;
19 break;
20 }
21 if (mark[sum]){
22 a=mark[sum]+1;
23 b=i+2;
24 break;
25 }
26 mark[sum]=i+1;
27 }
28 for(i=a;i<b-1;i++)printf("%d ",i);printf("%d\n",i);
29 }
30 return 0;
31
}
32
33