2012年2月29日 星期三

tioj 1416 Game Of Stone

快樂的遊戲題XD

好快樂好快樂好快樂~~~~~~

作法是這樣的
n=1( mod 4 ) 時才會贏
所以一開始先拿2之後一直跟他拿一樣的
直到小於3就break~~(一跟五當特殊情形)

原因勒...
首先得到資訊的順序是這樣的:
最早,你會知道 3 的時候若先手是偶數必輸,反則必贏
接著,你注意看題目了,注意到都是奇數
後來,你會發現當起始數字是4m+3時,後手只要一直學先手
到三的時候,一定是兩個人都是2m,故後手必贏。
最後!!!!!!!!!!!!!!!!!!
你馬上就知道若數字是4m+1時,先手只要先拿 2 ,情況就跟4m+3一樣,然後先手就贏了
 AC ~~~~~ XD


http://codepad.org/M9zfiQ37

2012年2月28日 星期二

tioj1385 芳佳的打工

這是個dp(大家好像都知道XD)

這題亂想其實還算可以想到的(就跟我一樣)

但還是有個規則可以去想:
想想操作,對任意一個字變成另一個字 1. 修改 2. 插入 3. 刪除 4. 不用作事
所以dp就可以做這四件事,然後邊邊(i=0 || j=0)要弄清楚
因為他沒有前一個可以看,要先自己建好。

然後我用滾動?! 搞不清楚專業名詞==
所以要%2

http://codepad.org/4zbZM218

Uva 11506 Angry Programmer

其實不難,只是第一次寫network flow變化圖題
寫了有點久...但一傳就AC了,還不錯XD
因為點也有流量限制而且又是無向圖
寫起來還真麻煩~用了奇怪的函數chg轉換入點跟出點
本來想亂寫,但好像還是乖乖的一個邊一個邊加比較好XDD

PS. int main()裡只有一行耶 > <

http://codepad.org/9MwpnmCm

USACO Sweet Butter

這提根本就是來亂的= =

用dijkstra作,居然TLE!!!!

亂用個SPFA就過了> <

後來發現......我忘記priority_queue回傳最大值+ +

真愚蠢............................................

http://codepad.org/ZoihqlZ0

2012年2月27日 星期一

USACO Magic Square

不需要用大腦,只要用手的題目

初始化 -> 佇列 -> 印出 -> AC

只是寫的好冗,有更短的code給我看!!!

感謝><

http://codepad.org/2QeHydOL

2011 TOI 初選 PROB4

想了半天想不出來,想超久(冏)
比賽時隨便寫了暴力,只對一筆
超廢的X{{{{{{{

後來被提示了一下,發現很簡單,真可惜沒想到~
code也小小隻的,很簡單co

想法如下:
sum of earn / sum of cost > P,移個項,-1*[ (sum of earn) - (sum of P*cost) ] < 0
用Bellman-Ford找個負圈(第一次寫XD),耶~完成!!!!
怎麼找ㄌ?如果第V次還有更新就是有負圈~

http://codepad.org/vn1rO8ZH

Codeforce 154B Colliders

1. 要把所以數字的質因數都預先存起來
2. 開一個一維的陣列存質數 i 的倍數是否開著

就醬~一個簡單的30分鐘codeXD

http://codepad.org/F12aO1tB

2012年2月26日 星期日

Minimum Cost Flow

這真是一個蠻麻煩的東西耶XP

-最小成本流量問題-

今天了解的大概是這樣:
演算法名稱::『最短成本路線流漸增式演算法』(亂取的XD)
演算法內容:: 用『某種可以求有負邊的最短路演算法』求最短路(cost)+盡量流過去~
演算法條件::
1. 要求由s到t流動f的最小花費(這就是演算法目的X))
2. 沒有負環(原因看證明)
演算法證明::
1. 證明『f=最小成本流量,若且為若剩餘圖沒有負環』
pf: 設 f ' 小於 f ( 在某圖以某相同流量流動的花費 )
(1) 流量相同 -> 差異為一個環(f ' - f 的流量圖,任一點入度=出度)
(2) f ' 小於 f & (1) -> 差異為一個負環(f ' + (-f){邊正負顛倒}小於零,那個差異是負的)
若剩餘圖有負環,因f ' - f = 負環,故f ' = f + 負環,得證。
2. 證明『每次都取s到t的最短路,就會是最小成本流量』
pf: 數學歸納法
(1) 因圖沒有負環,f0 = 最小成本流量 = 零
(2) 若fi 是最小成本流量,fi+1 是 fi + (s到t的最短路徑),故fi+1 也是最小成本流量。(反證法:若有另一路徑f 'i+1 fi+1 小,因fi+1 是 fi + (s到t的最短路徑),但卻存在一更小成本流量,由第一個證明得知這個圖有負環,而且是fi 的問題(因為s到t是最短路徑,無更短的),那麼fi 不是最小成本流量,故矛盾,假設不成立

2012年2月24日 星期五

USACO-Feed Ratios

這題智障智障的
題目裡說答案都小於100
直接枚舉O(n^3)就AC了XD
只是有零的時候麻煩死了
偷偷加了二分搜偷懶XP

ps. code裡的rb竟然讓html壞掉X{

http://codepad.org/6vN6S8h2

2012年2月23日 星期四

tioj1191 直到夢的盡頭

直到夢的盡頭

屌題~很好玩XDD
umm,其實很簡單
就...進位的轉換嘛~or. 寫個大數也行啦XP
(因為不會有6,就像是0,1,2,3,4,5,7,8,9的九進位)

http://codepad.org/6VvVzSFK