Poj 3370 Halloween treats

這道題在集訓(xùn)手冊(cè)上標(biāo)志是“抽屜原理”，老實(shí)說(shuō)，在看到這道題的具體解法之前，我還不知道為什么是抽屜原理，這明明是判斷一些數(shù)的同余嘛，后來(lái)才發(fā)現(xiàn)鴿籠原理的巧妙之處。

 

4 5

1 2 3 7 5

 

例如對(duì)于第一組數(shù)據(jù)，

1 2 3 7 5模上4分別是：

1 2 3 3 1

如果采用同余+dp的方法，難度會(huì)相當(dāng)大，規(guī)則比較復(fù)雜；

 

這時(shí)，我們采用一種巧妙地方法，就是用一個(gè)sum[i]數(shù)組來(lái)記錄前i個(gè)數(shù)之和%4，例如上例中，我們得到：

I	0(該列隱含)	1	2	3	4	5
Sweet[i]	0	1	2	3	7	5
Sum[i]	0	1	3	2	1	2

 

由此，我們?cè)谂龅?/span>1.sum[i] == 0 或者2.sum[i]的值已經(jīng)在前面出現(xiàn)過(guò)的情況時(shí)，就可以知道有解，并且解是從上一個(gè)出現(xiàn)該sum[i]數(shù)值的后一個(gè)位置開(kāi)始→現(xiàn)在sum[i]的位置，這個(gè)貌似可以解出可能的解；但由于加和的順序隨機(jī)，所以還不清楚是否可以在該case有解的情況下一定能夠解出解。這時(shí)候，我們就要用到鴿籠原理了。

 

運(yùn)用《離散數(shù)學(xué)與組合數(shù)學(xué)》書(shū)中的方法，我們可以把sum[1~n=nneighbor](或0~n)看做n+1只鴿子（注意上面的隱含0列），飛入c=nchild個(gè)鴿籠中，再注意到題目中有這樣的數(shù)據(jù)范圍：

The first line of each test case contains two integers c and n (1 ≤ c ≤ n ≤ 100000) （這是本題能用鴿籠原理的最重要的前提）

由此我們可以知道一定有兩只鴿子是飛入同一個(gè)籠子當(dāng)中的，所以加法的順序就自然不用考慮了；而且由這個(gè)我們也可以知道，此題一定不存在無(wú)解的情況。

代碼就不貼了，數(shù)學(xué)題還是要自己想才好