題目連接：http://acm.zju.edu.cn/onlinejudge/showContestPRoblems.do?contestId=347

套題是真TM酸爽。193?47?887?29$193*47*887*29$

A applications

英語題 特別復(fù)雜的模擬 注意細(xì)節(jié) 細(xì)節(jié) 細(xì)節(jié) 細(xì)節(jié) 細(xì)節(jié) 。。。。

B Break Standard Weight

簽到題 直接暴力就好了

C Calculate Prime S

理解題意，首先x很明顯要求個(gè)逆元,因?yàn)閙不是素?cái)?shù),所以只好用擴(kuò)展歐幾里德求了, 對于S[n] 是很明顯的fibonacci數(shù)列(S[n]=fib[n+2] ),枚舉兩個(gè)就出來了,別忘了還有空集..

然后就不會(huì)了, 最后才知道fibonacci的一個(gè)性質(zhì)

1.gcd(fib(n),fib(m))=fib(gcd(n,m))$gcd(fib(n),fib(m))=fib(gcd(n,m))$ 證明：可以通過反證法先證fibonacci數(shù)列的任意相鄰兩項(xiàng)一定互素，然后可證n>m$n>m$時(shí)gcd(fib(n),fib(m))=gcd(fib(n?m),fib(m))$gcd(fib(n),fib(m))=gcd(fib(n-m),fib(m))$，遞歸可求gcd(fib(n),fib(m))=gcd(fib(k),fib(l))$gcd(fib(n),fib(m))=gcd(fib(k),fib(l))$，最后k=l$k=l$，不然繼續(xù)遞歸。K$K$是通過展轉(zhuǎn)相減法求出，易證k=gcd(n,m)$k=gcd(n,m)$，所以gcd(fib(n),fib(m))=fib(gcd(n,m))$gcd(fib(n),fib(m))=fib(gcd(n,m))$。

所以只有當(dāng) gcd(n,m)=1或2時(shí)(fib[1]==fib[2]==1) fib[n]與fib[m]互質(zhì) 所以若S[n] 要是一個(gè) PrimeS 則n+2必須是一個(gè)質(zhì)數(shù)或者4 ，自己畫畫就知道為什么4是特殊的了 所以構(gòu)造一個(gè)特殊的素?cái)?shù)表 P[i] 3 4 5 7 11 13………………. 所以第K個(gè)PrimeS 就是fib[P[k]]

還有一個(gè)結(jié)論： 計(jì)算(a/b)%c$(a/b)/%c$ 其中b能整除a 如果b與c互素，則(a/b)%c=a?bphi(c)?1$(a/b)/%c=a*b^{phi(c)-1}%c$ 如果b與c不互素，則(a/b)%c=(a%bc)/b$(a/b)/%c=(a/%bc)/b$ 對于b與c互素和不互素都有(a/b)%c=(a%bc)/b$(a/b)/%c=(a/%bc)/b$成立

就是枚舉出能夠整除x的PrimeS 用快速冪求取PrimeS 最后計(jì)算 就好了 注意下可能會(huì)爆int就好了

D Density of Power Network

明白題意讓求的是去掉平行線后,線與節(jié)點(diǎn)數(shù)的比值就好了 簽到題 暴力做

E Egg Painting

不會(huì) 還找不到題解…

F Friends

這個(gè)題比較6 確定題意后,直接暴力加邊就好了,直到不能在加邊為止

G Give Me Your Hand

看題解是個(gè)dp 然而dp廢。。。。 來日在補(bǔ)

H Hard to Play

簽到題 明白題意直接做就好了,

I In 7-bit

閱讀題 明白題意 直接處理就好了

J java Beans

簽到題 找環(huán)上和最大的長度為k的連續(xù)區(qū)間, 前綴和處理然后枚舉即可.

K Kindergarten Election

題面比較有意思,一群幼兒園同學(xué)要投票選個(gè)老大，（不能選自己），每個(gè)人都有一個(gè)心儀的老大目標(biāo)，然后1號小朋友要當(dāng)老大，可以拿糖賄賂其他小朋友來確保自己當(dāng)老大。問1號小朋友最少需要多少個(gè)糖果能確保自己當(dāng)上老大。

枚舉加貪心,

枚舉1號小朋友當(dāng)上老大時(shí)的票數(shù)，然后貪心選擇賄賂誰，維護(hù)下結(jié)果的就行了。

題目不難，就是不好想到枚舉，想直接進(jìn)行貪心，然后就會(huì)各種GG

—————————————————————————————-

最后發(fā)現(xiàn)這套題是之前省選訓(xùn)練過的題..

總結(jié): 英語讀題水平太菜, 模擬水平太差, 代碼能力有待加強(qiáng)

思維不夠開闊,膽子不夠大,至少暴力的想法是有的 但是卻不敢寫. 寫代碼的速度可以放慢些,寫快了細(xì)節(jié)上出錯(cuò)率大.