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