這個題目是Ulm Local 2007比賽的。
今天我們組隊做了5個小時Ulm Local 2007比賽
在比賽還有半小時AC了6個還差兩個題目
一個是線段數(shù)的感覺沒時間寫了
另一個就是這個了。先開始一直想不出來很好的算法。
聽后面一個全做完的隊再說這個可以用鴿籠原理來證明還說這個題目只要找出連續(xù)的集合就可以了
然后聽到之后仔細想了一下感覺有道理
當(dāng)把所有從第一個開始的部分和對C的余數(shù)統(tǒng)計就可以發(fā)現(xiàn)
要么就是有一個人給的糖果直接就是C的倍數(shù)
要么會出現(xiàn)兩個部分和對C取余后得到相同的值
這就說明相同這兩個之間的部分和就是C的倍數(shù)
然后題目寫起來就很簡單了
寫了沒幾分鐘然后交了就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