這個(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>
2
int data[110000];
3
int mark[110000],n,c;
4
int 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