Codeforces Round #354 (Div. 2)

http://codeforces.com/contest/676

http://codeforces.com/contest/676/problem/A
http://codeforces.com/contest/676/problem/B
http://codeforces.com/contest/676/problem/C
http://codeforces.com/contest/676/problem/D
http://codeforces.com/contest/676/problem/E

上面是題目

我AC的code :
pA : http://codeforces.com/contest/676/submission/18103173
pB : http://codeforces.com/contest/676/submission/18119627
pC : http://codeforces.com/contest/676/submission/18081711
pD : http://codeforces.com/contest/676/submission/18120507
pE : http://codeforces.com/contest/676/submission/18119387

題解：

pA :
題目是說：要swap一次，讓1和n的距離最遠。

那可以想像的是說，就盡量把1和n移到最邊邊一定是最好，那如果他們本身就在最邊邊了，那就他們兩個交換就好。
實作的部分就看code吧。

pB :
題目：有n個杯子，第一層有1個......第n層有n個。我要倒水t次，每次都從第一個上倒剛好一個杯子的水量。如果溢出來，就分兩半到左右兩邊。請問到最後有多少個杯子是滿的。

那可以發現的是：n很小。於是，認真實作倒水的動作即可。可以看看code。

pC :
題目：給你一個字串，只包含a,b。請問，在換過最多k個字元後，連續字元最長是多少(可以是a或b，比如說：aaab就是3，aaabbbbba就是4)。

先有一個greedy的想法：如果某個區段是最佳解，那這個區段一定包含這k個被轉換的字元(因為越長越好嘛！)。所以說，你會發現，這k個字元最好要聚集在一起，於是乎，就可以想出一個爬行法(two pointers)的作法。
實作的部分就看看code吧！

pD :
題目：有一個n*m的房間，每個房間都有門，有各種字元代表有哪些門是開著的。當兩個房間可以彼此互通時，才可以走過去。你可以在任意時刻順時針轉90度，這個時候，所有房間的門都要轉90度。請問，sx,sy到ex,ey的最短時間(轉90度，走房間的時間都是1)。

那，我還真的不知道可以怎麼做，於是乎就跟學長、社員討論一番後。才知道可以這樣做，也算有長知識吧：就是，最多只會有四種狀態(轉四次)，所以，我就在每個狀態，可以建邊的就建邊。在不同狀態時，(x,y)一定可以到轉90度後的狀態的(x,y)。於是乎，就最多有6nm個邊，可以開心地做BFS。
實作就看看code吧。

pE :
題目：人跟AI的對決：現在有一個n次式，有些位置已知，有些位置未知。在初始狀態(全部都未知)，電腦先下，所以說，一開始的電腦和人，都只能下這些已知的位置。未知的位置可以放進任意的實數(正的、負的、0、小數)如果到最後，這個n次式可以被Q(x) = x-k整除，那就代表人類獲勝，否則電腦就贏了。

這題也是跟學長&社員討論出來的。先分兩種情況：n次式的x=0 or x!=0。
如果x!=0，那，如果有未知項，那誰先掌握最後一個數字，誰就贏了！(因為可以填任意數字)。如果沒有未知項，那你就取一個質數p，讓這條式子對p做模運算，如果=0，那代表最後的結果有可能=0，就是okay(可是經過我的測試，如果單用1e9+7 or 1e9+9 or 兩個都用，都會爛掉，於是，要多取一些)。
如果x==0，那就分常數項討論：如果常數項未知，那目前誰先下，誰就贏。如果常數項已知，判斷是不是0就好了！
實作看code吧！

第一次全部都會，好開心 ^_^