TOJ376

吶...
TOJ還是不給submit，
不過我感覺是沒問題了，就先放上來吧

這題主要算是math題吧
我到現在還是搞不太懂就是

這題基本上最直觀的解法就是直接加上去
結果還是TLE...
仔細看數字有到百億...

我看學長AC的時間是零
又想到費氏數列其實是有公式的
就開始往「是否能直接帶入公式」的方向思考
讓時間從O(n)變成O(1)

結果一直爬文阿
已知費氏數列的公式了，費氏數列合的公式怎麼求也不知道
浪費了兩三張計算紙感覺都在耍白癡，像是寫了好幾行得出了s(n-1)+f(n)=s(n)之類的廢話

後來觀察了一下，突然發現s(i)=f(i+2)-1，就莫名其妙發現的規律
用程式跑幾個大數字也正確就是了
像前5項的和(1+1+2+3+5)=第7項(13)-1=12

然後就想說很高興的帶公式直接O(1)得解
結果發現一個致命問題...
不知道怎麼取mod...
又試了一段時間，結果還是放棄了阿...公式解>口<


不知不覺打了一堆幹話:3
總之後來發現了，原來費氏數列還有一種求法是O(logn)
來源網站
參考了一下，就實作看看，原理甚麼的不懂
畢竟我根本沒學過矩陣

然後就做出來了...
時間的話跟直接加比起來,當n=100000000(億)，
相加耗費2秒多，矩陣只要不到0.001秒
看來是沒問題了...

搞了一個晚上終於解決，只是原理不知道心就是有點癢癢的

比較一下費氏數列我已知的三個解法
1.加法 : O(n) ,易實作,足以應付大部分狀況
2.公式解 O(1) ,應該不會用到,而且不夠彈性,像這題就想不到方法取mod(可能是我太笨QQ)
3.矩陣 O(logn) ,數字特別大會TLE才需要用到(約超過10^8)

376.cpp(不能完全AC，但可以參考

更新(7/4
TOJ修好後發現一堆問題
可惡...果然沒那麼順利...
結果又爬了一堆文
硬生生地把矩陣的算法之類的搞懂
...
真的有夠麻煩...
反正...終於AC了...
376-2.cpp(AC正解版

TOJ169

TOJ掛掉好幾天了...
都不能更新好困擾...
如果附檔有錯就算了吧...

DP問題...
受夠了阿...
我這題當初大概想了一整天吧

後來看看其實也就這樣...
只是真的很難去想到就是...
也不然啦...只是實作很多沒注意到的地方出現bug...

我當時的思想:
1.暴力解的話，要得知第i根的狀況，最多必須掃過i-1根的值，然而->嚴重TLE

2.
仔細觀察，其實不必
舉  1 3 4 5 2 為例
當我們判斷到第4根(假設前面都判斷完了，並得到正確答案)，
判斷和前面4的關係就好，
5大於前面的4，所以5的答案等於4的答案+1(多了4)，也就是2(4的答案)+1=3
若判斷到2，2小於等於前面的5，所以答案為0

這樣是不是比暴力解快呢?

然而--->WA!!

我想也是，沒那麼輕鬆嘛...

甚至連範例都會錯就是

3.

以1 10 2 4 3 5 7為例

正解是0 1 0 1 0 3 4，然而用第2種思想卻得到0 1 0 1 0 1 2 ??

恩...仔細觀察相信馬上就會發現原因，

當我們要得到第i根的答案時

我們必須還要判斷擋住i-1根的那個棒棒是否也會擋住第i根，

如果會，那才可以直接第i根的答案=第i-1根的答案+1

如果不會被擋住，我們還要把前面的再吃掉才行

至於擋到第i根的棒棒找法也很好找，答案為0代表前一個擋到，答案為1代表前兩個擋到

拆成步驟的話(直接跳到第4根

1 10 2 4 3 5 7

5>3，吃掉3的答案，並判斷擋住3的那根會不會擋住5

1 10 2 4 3 5 7

5>4，沒被擋住，所以也要吃掉4的答案，也要判斷擋住4的那根

1 10 2 4 3 5 7

5<=10，被擋住了，因此不吃掉10的答案，也不用繼續判斷了

最後5的答案就是3的答案(0)+4的答案(1)+吃掉3和4(2)

也就是0+1+2=3

基本上就這樣，而已，知道實作方法，程式碼寫起來也不長

只是DP真的有夠煩惱

169.cpp

TOJ168

嗯吶...

就跟紀錄最大值的程式一樣，只是多了記錄次數的需求

基本上也算DP問題啦

只是基礎到大家不把它當DP了...

輕鬆拿分的水題

後面的169才是真正麻煩的DP

168.cpp

TOJ162

不想多加解釋...

就是水題

if判斷複製貼上就好

162.cpp

TOJ16

一直考慮這要不要放在水題
我當初錯超多次的
不過後來看這不是超簡單...
我之前是沒想過放在陣列索引值儲存的方法
我是直接把每兩個數總和丟進去陣列...真慘...
基本上要注意的點
「這兩位手上一定要拿一部份的手提袋」
還有他輸出非常多(百萬，請不要用endl，會TLE
請改用\n，我也是第一次知道endl會導致TLE
從此之後要拚速度偶而就會用\n

嘛...我還是認為他是水題啦
只是那個陷阱真的有夠討厭>口<
另外還有加強版的我過不了就是QQ

16.cpp

TOJ13

這個就完全的經典
DP中的背包問題之中的無限背包問題
演算法筆記也有
當初我應該也是隨隨便便似懂非懂地就抓下來AC了

我個人認為他比一般背包問題好懂啦... 



我們開一個陣列，長度為體積+1(包含0)，分別記錄當時體積能取得的最大價值
一開始當然預設為0囉

假設題目要的體積為10，三個物品的體積價值分別為
2,3 / 3,7 / 4, 1 / 1,1

我們就來實作吧
一開始的陣列狀況
0 0 0 0 0 0 0 0 0 0 0
代表0~10的最大價值都是0

接著我們把2,3放進去
當體積為0~1的時候，放不了(因為體積是2)，所以最大價值維持原樣
體積為2~3的時候能放1個，最大價值為3
...4~5為6...10為15
最後變成
0 0 3 3 6 6 9 9 12 12 15
然而注意到了嗎，3,6,9,12,15怎麼來的?
是可以從少2個體積的值那個值+3得來

處理完了2,3的最大價值
接著我們把3,7丟進去

當體積為0~2的時候，是放不下的，維持原樣

當體積為3時，我們有兩種選擇

1.維持原本陣列的值

2.更新陣列的值

原本的值是3，更新的值是0+7(體積0的最大值加上該物品價值)

我們要取最大值，因此被更新了

這樣持續下去更新體積4,5,6....10

會被更新成

0 0 3 7 7 10 14 14 17 21 21

接著處理4,1

由於價值太小，會得到

0 0 3 7 7 10 14 14 17 21 21

處理1,1

在體積1的時候，更新的值(0+1)比原本的0大，更新

體積4的時候，也更新成5...

最後變成

0 1 3 7 8 10 14 15 17 21 22

該陣列每個位置的值就代表那個體積可以存放的最大價值

體積0最多為0，體積1最多為1，體積2最多為3...

而假設題目要的是體積為10，也就是22

希望我打的這篇有人看得懂QQ

13.cpp

TOJ126

經典的DP問題，跟跳樓梯很像
奇怪的是
當初跳樓梯問題我明明會，
怎麼換成這個我就不會了...
還好有好心學長給我提示，非常感謝...

總之
假設有有2,3,5
那麼滿分是10，最低分是-10，對吧
我們可以開一個陣列，代表-10到10，共21格(包含0

我說過這題跟跳樓梯很像吧
跳樓梯從哪裡跳? 0階!

沒錯
一樣的我們就從0分開始跳
一開始都沒有任何紀錄時，就只有0分一種可能
所以0代表不可能，1代表有可能，則一開始是
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0

再來呢，我們紀錄了第一筆資料 2分
我們答錯時，要扣2分，答對則要加2分
此時就是DP的關鍵，
拿出上一筆的資料 :
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0

其中1是代表上一筆為止可能的分數吧，

那麼，可能的分數±2不就是這筆資料可能的分數，變成

0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0

同樣處理下一筆資料3，

再上一筆得到所有可能發生的分數±3

0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0

再處理資料5

最後就得到所有可能發生的分數

1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1

也就是-10,-6,-4,0,4,6,10

恩，這樣描述不知道能不能理解呢?

如果不能理解的話也是可以詢問的啦

126.cpp

TOJ125

我是參考這裡的
裡面還提到這遊戲到本世紀初才有教授想到如何取勝...

基本上可以點進去看看，看懂後照做即可
125.cpp

TOJ315

這題看似基礎的快速冪
但他給的M實在太大了...
導致一點也不水阿...
個人目前想了一個晚上還是找不出正解
目前個人是覺得有三個以上的解
1.某個我想不出來的正解
2.把乘拆開用加的 ->太慢
3.用大數 ->太麻煩

大數直接複製14就好，
只是大數mod的部分要實作又要爬一堆資料了，實在不想浪費時間在這...

315-2.cpp(加法ver，時間很慢(370)

更新:
失敗想法:
f315.cpp(其實稍微調整一下c的取法，我認為有機會成功

更新:
315-3.cpp(大數ver，但時間還是很慢(360~400)
我想應該是mod方面的演算法需要改進

這方面我真的懶的研究...

更新:
315-2.1.cpp(加法ver，時間已經優化到極限了(60~80)，

排行榜上0聽說好像是用大數做的，結果這題還是要用大數阿...

那可能就沒什麼我想像中的正解了

更新:
315-3.1.cpp(大數ver，不用寫麻煩的函數，輕輕鬆鬆直接用(0)
索性去問了學長
好心的他馬上丟了關鍵字給我「__int128」
哇！竟然還有這麼好用的東西我不知道
除了cin跟cout不能直接用還要定義以外
其他的加減乘除模都可以用
超棒的!!!
最後丟上去果然就runtime0了，好爽

隨機img

F5會重置，然而不知有什麼用
可愛就夠了吧:3

網址是 : https://imgrandom.000webhostapp.com/imgrandom.gif

雖然是.gif檔，但是實際上是運作php的功能

TOJ180

嗯..
最近開始練習MST的kruskal
總算有點搞懂了基本的運作方法
這題基本上只要會MST就好
唯一的致命陷阱就在
「最低成本」
也就是就算你多蓋這條其實是浪費的(形成環
但只要你蓋了可以賺到錢(成本為負
你還是要蓋
我看了好幾遍題目才發現這陷阱=A=

其實也不能說陷阱啦，畢竟有負值的MST也是很重要的
提供測資:

1
3 4
1 3 200 500
2 3 100 1000
2 3 10 100
1 3 20 3

正解是-1290，如果你得到-1200，那就在Debug一下吧

180.cpp

TOJ190

這題看似又要用到什麼麻煩的演算法
其實他數字給很小
直接暴力不但不會TLE，runtime還都是0就是了...

190.cpp

TOJ238

簡單的BFS練習題...

明明是這樣的，可是不知道為甚麼我的runtime那麼久

好像BFS的題型我的Runtime都多別人幾倍...

又不知道怎麼開口要別人的code...

總之這題不難啦:3

應該也沒什麼陷阱

238.cpp

TOJ361

也是水題就是了
我也是寫完才發現標題有cannot judge，
不過還是過了...應該是沒有問題吧...
基本上就是數學加加減減
有夠麻煩...

361.cpp

TOJ41

MST其實有很多中方法
其中我用的是Kruskal演算法
這算我第一次實作MST，很害怕又興奮的感覺
至於原理其實我不太懂
總之我是看維基的例式才想到實作方法
為甚麼這樣會找到最小生成樹的原因我真的不清楚...
還好這題沒什麼陷阱，順利通關了

接著就是多練習MST的一些題型，熟悉MST的實作方法吧
41.cpp

SET練習 (TOJ165

在學MST，發現竟然好難搞懂set的部分QQ
於是就來複習這題了
set算是基礎的資料結構
很多演算法其實都會用到就是了
沒有學好必定會吃虧

基本上set就是記住幾個函式寫法
Init(),find(),union(),same()
基本上就沒什麼麻煩了，也都很短就是

165.cpp

BFS/DFS練習

主要讓自己更了解一下BFS/DFS的原理
基本上算蠻暴力的演算法...也蠻好用的啦
原理不難就是

BDFS.cpp

TOJ117,118,119,120,121,122,123,124

就這樣啊...
一堆水題...
基本上每題都能在幾分鐘內解完
除了有題需要前綴和的觀念才能解，
其他之前怎麼拿到WA的都不知...

117.cpp
118.cpp
119.cpp
120.cpp
121.cpp 
122.cpp
123.cpp
124.cpp

TOJ110,111,112,113,114,115

嗯吶...

就照題目需求的水題嘛...

好幸福的題目...

110.cpp

111.cpp
112.cpp
113.cpp
114.cpp
115.cpp

TOJ244,245,246,247,248

都是水題...
好像都照題目暴力解就好，有些地方int過不了開long long就好...

244.cpp
245.cpp
246.cpp
247.cpp
248.cpp

Sort練習

Sort是很好用的函數
雖然我不懂它的原理就是了
如果只會單純用他由小排到大實在太可惜了
Sort可以自訂排序的判斷，
像TOJ15就能運用Sort輕鬆解完

也可以用來直接倒轉整串數列的數值
嘛...是否比較快就不知道了啦

sort.cpp

TOJ133

題目敘述很複雜
總之是前綴和，搭拉拉

然後一個血恨提醒，
看到區間和,區間最大值,區間...，一定要記的加條判斷:
if(start>end)swap(start,end);
不知道有多少次忘記這個被陰到，氣死

133.cpp

TOJ69

題目就是要你N*K-1
甚至下面還好心的付給你程式碼了

其中題目附的code中
1.  cout<
2.  cout<
我想有筆測資是K和N=2^32
unsigned long long的範圍是2^64-1
因此2. K*N的時候會溢位，1. 就不會有此問題

不過我兩個都丟丟看還是都AC啦=A=

69.cpp

TOJ17

就輸出阿...
測資也只有1~26...
TOJ水題太多了點...


17.cpp

TOJ182

就...利用國中學過的畢氏定理判斷三角形類型而已...
這種題目TOJ有好幾題的樣子...

182.cpp

TOJ252

理解一下mod機制就好，
有空我寫一篇mod的筆記好了
感覺對mod的運算不太了解

252.cpp

TOJ47

練習lower_bound的小題目
不難就是了
lower_bound的用法(假設陣列為X[N]):

lower_bound(a,b,k):
a放入陣列要搜尋最前端的位置，可以用X，或是&X[0]
b放入陣列要搜尋最尾端的位置，X+N或，或是&X[N-1]
k則是放入要找的值
接著會傳回陣列第一個找到>=k的「位置」
如果需要把他轉換成值的話，在前面加*就可以了

lower_bound的用法牽扯到一些指標概念...

總之假設陣列為X[N](要排序過
*lower_bound(X,X+N,k) 會得到X陣列中>=k的值中最小的那個


47.cpp

TOJ224

剛剛想說可以利用前綴和的概念儲存每個階層，
結果溢位了:P
反正題目就很簡單，
乖乖地解就好
測資沒有那種40!之類的溢位答案，大可放心

224.cpp

TOJ296

我盡量優化了
可是Rank還是差了很多
嘛...老話一句能過就好...
我用的是埃式篩法，基本上還有線性篩法能用
基本上埃式應該是比較快，有興趣的話可以兩種都練習看看

至於判斷某質數是第幾個質數，可以用二分搜或lowerbound之類的

296.cpp
296-2.cpp(空間變大幾倍，理論上速度會變快，但不知道為甚麼反而變慢

TOJ23

我還是不了解互動題的機制
只能照著題目做了...
基本上這是很水的互動題就是了
CE比WA更容易拿到...

23.cpp

TOJ418

本來想說開始慢慢算這題
結果一看不是超簡單幹
1+N為平均每格的正值
1+M為平均每格的負值
(1+N)-(1-M)就是平均每格的值
平均值乘以總格數，最後會溢位的地方mod一下就好
靠杯超簡單
我考試時是在腦殘殺小，整段程式才寫三行我他馬拿不到AC
氣到中風

直接給關鍵:
cout<<(((N-M)%P*(N%P))%P*(M%P))%P<<endl;

我好像是那種考試時都會意外緊張的人:'<

418.cpp

TOJ62

這題真的靠杯麻煩的
還要用天降什麼的
當初我debug好像用了很久

此外好像一定要用到BFS之類的才行
否則你根本沒辦法正確判斷出有幾combo

總之有夠麻煩的
不過其實我國中一直其實一直夢想的寫程式大概就是這樣
寫一個想要做的遊戲，努力Debug，然後巴拉巴拉的體會社畜
可能是國小受到俺妹的影響吧...
俺妹真的影響我太多了...畢竟桐乃可愛

結果進了資訊社...
該怎麼說了，夢想破滅...?

好像只是一直在學演算法
而不是實作什麼東西...
不過我也很喜歡這樣啦:3
有種成長的感覺很實在

62.cpp

TOJ399

這題首先要了解xor的運算
簡單來說，xor不會影響到其他位數
也就是說，你個位數和個位數xor運算，
並不會十位數突然多了進位
這樣是不是簡單多了，少了進位的問題就讓大數麻煩少了一堆

這樣的話我們只要分別判斷每一位的運算結果再輸出即可

此外的問題就是當位數不同怎麼辦呢?
這也不難，其實就把低位數不夠的位數補上0就好
3跟0003，其實意思都一樣的
這樣是不是就沒有問題了?

所以就是從高位到低位，把每個位數xor的結果輸出，
就這樣，有沒有很水阿
當然還是要注意一下前導零就是

399.cpp

TOJ153

這題WA超多...

總之，完全按照題目就對了!!!
就算他說10 10 1是鈍角三角形，你也要這樣輸出!!!
除此題目有夠反直覺之外還真的就是水題...

153.cpp

TOJ55

嗯...基本上蠻簡單的一題
個人原本是用二分搜解...
不過後來發現用lowerbound和upperbound好像更快更easy...
或是你很閒，想要用線段樹...嗯...我覺得也是可以...
另外他記憶體不能開太大的樣子，
不然100萬陣列紀錄每個值應該是最快的方法

然後幹，我剛剛沒注意到是T20題單的題就丟了
離第一名越來越遠了

55.cpp(二分搜
55-2.cpp(upper,lower

TOJ281

Tag很好心的給你math的提示，
查一下就能找到

關鍵字「皮克定理」

老實說這種東西我根本不想知道
其還有一題完整的(多邊形格子點)，
但我懶得寫，感覺三角形就夠麻煩了
多邊形更麻煩的是你要判斷哪兩的點是相連的，
三角形則不用，每兩點必互相相連嘛~~

如果你有去查了，
你應該會得到一個公式 : i=A+1+b/2
i : 內部格子點含邊上的總數
A : 該多邊形面積
b : 該多邊形邊上的格子點數目

i當然就是我們要的，那A和b怎麼求呢...
恩...如果你聽過鞋帶公式，那可以直接將座標轉換成面積，
若沒有，也是可以用其他像海龍公式之類的，
反正都給你三個點的座標了，總有辦法的

接著就是比較麻煩的地方了...(其實也還好
計算邊上的格子點數
如果你寫過TOJ20了，那你可能會知道怎麼辦
如果沒有，那你則可以先寫TOJ20

另外依照我的AC程式結果
當三點連成一線的退化三角形，正解應該是線上格子點而非0


281.cpp(有點小疑惑但還是正解

TOJ170

就函數的練習而已
善用函數可以讓你的程式更易讀
像這題你不用函數可能就要兩三百行了
用了函數可以壓在幾十行解決
另外題目要看清楚，
我因為看錯題目在這題吃了好幾WA =A=

170.cpp

TOJ70

老實說...這題要說是水題嗎...
也不能完全算是吧...
畢竟虛數乘除的部分我還真的不知道
我也是上網才知道算法的
如果正式競賽考這題我還真的會爆(ノωヽ)

70.cpp

TOJ185

說實在我也不確定是不是這樣解
不過我看測資這樣，就猜是這樣了
也沒有試著證明過

總之
兩個序列乘積總和的最大值，
一定是最大*最大+第二*第二....
這個要證明的話可能要去問數學老師了

這題要實作不難，
果然最難的還是證明的部分，
或許哪天我有空去問數學老師後再更新這篇吧...

...
...
...
隔天更新
...
後來想了一下
假設只有各只有兩個數,a,b  x,y
a>b x>y 
可以變成a-b>0 ,x-y>0
則兩式相乘為(a-b)(x-y)>0  (兩個正整數相乘必>0)
變成ax-ay-bx+by>0
也就是ax+by>ay+bx
這就證明完了

至於多個數呢
其實也只是以上的延伸
我就懶得再更新了

185.cpp

TOJ44

我是用一般的BFS寫的，
不知道為什麼Rank差了兩三倍，
很想去問但怕打擾到他們，甚至被討厭...

總之基本上應該也算是正解
可以參考:3

44.cpp

TOJ171

這題也是水題
但其實也蠻容易粗心拿到WA的

主要就看你對C++的運算了解多少
N*80%
可能會有以下幾種寫法
N/10*8 ->會有錯誤，如N=25，(25/10)*8=2*8=16，實際上是20
N*8/10 ->會溢位，嘛...這部分其實開longlong就能解決了
N*0.8 ->會有小數點，可以用(int)(N*0.8)，把結果強制轉換成整數即可

基本上就這樣，算是水題，
這題WA有點多讓我有點意外...

171.cpp

TOJ140

一般的水題
在這裡提一個重要觀念
ax^3+bx^2+cx+d，這種一元多次方程式
可以寫成
((((0*x+a)*x+b)*x+c)*x+d)
這麼做比起寫a*x*x*x+b*x*x....這種寫法，
不但更方便也更有效率喔(相比後者,前者每高一次方只多2個運算，後者要多乘好幾次

140.cpp

TOJ355

基本上就是要你找第二大的值
基本上就是平常找最大值的延伸

後來我直接用sort取第二大發現也是能過

不知道為什麼這題還是有人TLE...(真的很神奇...
sort都能過的話,這題應該蠻水的吧...

355.cpp(正解版?
355-2.cpp(sort暴力解,時間約兩倍,空間好幾倍

TOJ50

依照題目需求照做...
注意不如以往，最後不需要換行
基本上是水題

50.cpp

TOJ291

嗯嘛...就水題...
會迴圈和判斷就好...
題目倒是感覺挺有趣的

291.cpp

TOJ237

嘛...簡簡單單的數學題
其中應該中間的X4最好找吧
全部-A1-B1-C3
(A2+B2+C2-全部)/2
...
嘛...
反正方法一堆自己想啦


237.cpp

TOJ142

很麻煩的水題
先判斷有沒有達成連線
再判斷是否都填滿了

程式碼搞到很長...

142.cpp

TOJ417

理解題意，稍微懂if就好
很水的送分題

417.cpp

TOJ421

前幾天的題目出來了
真感謝學長們的努力
這題基本上只要會寫線段樹就爽爽拿...?
靠北，那個機掰測資害我超煩躁
這題害我有些陰影QQ

嘛...以上題外話就是
這題是真的蠻簡單的...
就很基礎的線段樹...
只要會建樹+搜尋就好

421.cpp

TOJ56

又是嘟嚕嚕的最大公因數了
TOJ到底有多少題是最大公因數了
嗯嘛...不過這題的敘述到是講的很神奇就是了
反正看測資就看的出來了吧(看不出來怪我囉?

56.cpp

TOJ65

這題可能是TOJ最難的魔王題了
平均正解率竟然只有6,7%!!

讓我一一解析這難題的最佳解法
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
幹!直接用腳本大量傳啦!
垃圾題目


65.cpp

TOJ340

就眾多水題的其中一題
你說怎麼有人連13分的範測都拿不到...?
我怎麼知道

340.cpp

TOJ330

...


330.cpp

TOJ95,96,97,98,99

都水題就放在一起了...
基本上都是簡單的判斷啦計算啦

比較要注意的是99，
我到現在還是不知道反矩陣是什麼，

反正只要知道題目要判斷a*d-b*c的值就好

還要手動判斷一下小數位的小誤差

基本上就沒什麼了

95.cpp
96.cpp
97.cpp
98.cpp
99.cpp

TOJ20

就數學題

曾經聽學長說好像要學什麼向量之類的才能解

反正我是想一想就覺得應該是這樣就過了

剛剛查了一下好像是二上的數學

比較要注意的地方就兩點y軸和x軸相同的狀況，

我因為這樣吃了幾次RE，

基本上這題也是蠻水的

20.cpp

TOJ197

題目乍看之下很像背包問題
不過一個關鍵「物品可以以任意比例進行切割」，
也就是說其實只要優先拿性價比最高的武器就好

你就想像把每個東西全部切成一樣重量，但價值不一樣
那當然優先拿價值高的阿!!

這樣想其實這題蠻水的，也不是什麼複雜的背包問題
不過好像沒什麼人要做...

197.cpp

TOJ49

嗯嘛...
這題基本上是水題
但題目敘述有問題就是
a,b<2 font="" long="">
函式也要用long long
像我最大公因式的函式用int就吃了好幾個WA
反正有事沒事開long long省下一堆麻煩

49.cpp

TOJ134

嗯...
觀察題目好像也沒什麼用
我是實作後才發現那是費式數列的公式
既然知道是費式數列，那就簡單多了
結果還是WA啊!!!
畢竟當n=500時,結果大概是1.4e+104，105位數啊!!!
最後乖乖用大數加法就能輕鬆得到AC了~~

134.cpp

TOJ15

這題就只是要你喵喵喵的排序
排序這麼簡單的任務就交給sort啦~
另外題目的N,M大小關係注意一下，基本上這題就沒什麼問題了

15.cpp

TOJ58

很麻煩的水題
我看好像沒什麼人要寫的樣子...就我時間最多...
但真的水題阿
寫起來說實在也不到十幾分鐘...

58.cpp

TOJ45

嗯嘛...
題目看不太懂以外，其實這題很簡單
題目範圍甚至只有-65565~65565
方法有很多種，應該也有人直接丟進陣列用sort吧
反正只有65565*2+1個數字，也不會MLE也不會TLE
我就開一個陣列紀錄每個數字的出現次數
再同時記錄最大最小值就好

線段樹好像可以，但寫這題用線段樹www

45.cpp

TOJ100,101,102,103,104,105,106,107,108,109

嗯嘛...值得紀念的第100題也是水題
因為太多水題所以都放在一篇

看了之前寫的程式
用一堆if不知道在銃沙小...
這是成長的證明嗎...
我怎麼只覺得我以前像智障


100.cpp
101.cpp
102.cpp
103.cpp
104.cpp
105.cpp
106.cpp
107.cpp
108.cpp
109.cpp

TOJ132

就算看不懂題目(我還真的看不懂
看測資也能一眼看出是最大公因數就是了(不是嗎?

可參見TOJ3

基本上寫法一模一樣...
我就直接複製了...

132.cpp

TOJ293

嘛...沒什麼啊...?
你說怎麼拿到WA
這種題目想也知道有陷阱的嘛...提示都說很邪惡了

a,b≤10^18   x,y≤10^9
題目敘述沒錯的話
就來試著想想a,b,x,y之間的關係
嗯嗯?
沒有關係對吧...?
可是如果你WA的話，很有可能是做成a,b>x,y了

基本上陷阱就是這個了


293.cpp

TOJ19

就題目給你兩個圓的座標及半徑
判斷他有沒有交集
我想應該也沒人看不懂題目吧
畢竟大概算國中甚至國小就會的數學題目

19.cpp

TOJ127,128

水題，懶的解釋...

127.cpp

128.cpp

TOJ191

嘛...就DP中的Staircase Walk 問題，
多加了斜著走而已
SW問題基礎到數學課都教了...
但題目總不能講得太簡單...
像N,M大概就是混淆用的吧...

個人猜有人TLE是用BFS還是什麼寫的...

這題感覺也算水題...?

191.cpp

TOJ297

很基礎的線段樹題目(就連我之前暴力也有70就是了...
也只有用到線段樹的單點更新
連建樹都不用...

花了我兩小時Debug終於解決了，
我果然對線段樹還是很陌生阿，畢竟才接觸不到一星期...

主要就看清楚題目
1.20 20 15 -2 -2要輸出20 20 而非20 15
2.20 -1 -2 -1 要輸出20 就好，我則是把預設的最大最小值輸出了=A=
基本上應該沒有甚麼陷阱就是了

297.cpp

TOJ236

...

嗯...咖波很可愛...

236.cpp

TOJ36

本題重點 
將A*A*A*A*A*...11個 
=(A^11)=(A^5)^2*A=(((A*A)^2)*A)^2*A
這樣比起相乘10次，
大幅縮短了很多時間，可避免TLE
這就是快速冪

另外(A*A)%B跟(A%B)*(A%B)是一樣的，用後者避免溢位出現WA 

36.cpp

TOJ325

這個嘛...
有點類似126的DP問題
題目化簡就是找到可以組成<=總數一半的最大組合

實作的話 
假如題目是3,4,1,2，總和為10
開個大小為10+1的bool判斷(其實這題只要6就夠了)
一開始預設0為true;
1 0 0 0 0 0 0 0 0 0 0 
1 0 0 1 0 0 0 0 0 0 0，已知0可以，則0+3可以 
1 0 0 1 1 0 0 1 0 0 0，已知0,3可以，則0+4,3+4可以 
1 1 0 1 1 1 0 1 1 0 0，已知0,3,4,7可以，則0,1,3,4,5,7,8可以 
1 1 1 1 1 1 1 1 1 1 1，懶得打了...

總之就是這樣，
有不懂的話不如就研究程式碼吧
325.cpp

TOJ373

題目畫成圖大概長這樣，一個長方形+1或2個三角形的組合

簡簡單單加加減減
應該是沒什麼陷阱
就if判斷三角形的狀況就好


373.cpp

TOJ401

嘛...這題就是好像很麻煩的數學
其實也就是一般的多項式這樣,
題目換成簡單一點

f(x)=x^3-100x+b
當(2,400)在f(x)上方
b最大為多少
...
有沒有比較簡單
沒有的話或許這題真的很難

把題目搞懂後也就還好
基本上其他有需要講的都在附檔了...

401.cpp

TOJ8

第一次遇到的多測資題目...
我搞不懂直接用for(;true;)這樣
結果得到WA...

也算是水題就是了...

8.cpp

TOJ7

這題應該就稍微理解題意就能解了
也算是水題
話說這題重看，應該是DP問題...?

7.cpp

TOJ5

水題...
會用getline就好了...
我當時都還不會用string只會用char...

5.cpp

TOJ3

一切的開始...
當初自認會C++的我(嘛,其實也大概是會迴圈那樣有些基本知識吧
當初在這題吃了10個TLE,3個WA,1個CE
幹這到底沙小東西???

最後才知道了「輾轉相除法」這演算法
這也不過是9個月前的事而已了
哀...有夠菜的

嘛...反正這題算是水題啦

在此提供一個方便的gcd函式(學長教的
原理一樣是輾轉相除法就是了

int gcd(int a,int b)
{
    while((a%=b)&&(b%=a));
    return a+b;
}

3.cpp

TOJ332

嗯嘛...
首先簡化題目問題後
接著就不難了
就只是快速冪嘛~
只是要注意mod的定義就是了

332.cpp

TOJ14

其實就是基本的大數運算(實際上也只有相乘

我也是第一次碰大數...

一般的方法好像都是用int陣列，每個陣列儲存每個位數

像演算法筆記就是

結果TLE

接著就是找找看其他大數演算法

找到了Karatsuba大數乘法演算法

實作後也不知道為什麼更慢更慢更慢

後來我想想，更本沒必要只儲存一個位數啊幹，浪費位置

所以我就把每個陣列儲存的位數改成9位數(不能再多了)

結果就是一些亂七八糟的溢位問題

耗了我兩三天的假日:<

總算還是AC這題了

不過Rank還有更快的

據說是用快速傅立葉轉換做的

這個我就不清楚了，也不想了解，看到名子就豆頁疒甬

反正，能過就好了，對吧?

9.cpp

TOJ9

這題就是一般的BFS
不過好像很多人過不了，我也很難知道問題出在哪...

分兩個部分:走路,下坡車
走路部分當然就是用BFS寫了
下坡車的話，其實理論上要用BFS...
但我沒用還是過了，開心ヾ(*´∀`*)

9.cpp

TOJ249

很經典的DP問題:最大連續整數和
可以google就有一大堆人解
明明是這樣，為什麼還有WA(ꐦ°д°)
後來研究出是原來當測資全是負數，
答案至少要取一個最大的負數，而非通通不拿為0...
題目不講誰知道阿ヾ(≧皿≦ﾒ)ﾉ

知道後，有兩種更改方法，
一個是原本方法加上判別如果全部都是負數，輸出最大負數

一個則是將預設為0的連續和及最大連續和變數，改為預設為第一個變數就好
這樣說可能有點難懂
可以查看附檔內容...

249.cpp

TOJ240

我不知道這題算什麼演算法...

應該是greedy吧>A

確定演算法後要小心的地方就只有溢位的問題(因為數字很大

mod真的是能擺就擺阿...

240.cpp

TOJ239

我一開始也用線段樹吃了好幾次TLE，
最後問學長得到前綴和的提示...
才生出這個
這種方法理論上只能用在詢問次數不多的狀況吧
(像本題是1次
且應該區域更新只能加減(至少我認為乘除模同樣方法做不到QQ

239.cpp

TOJ198

能過就好了，是吧?
理論上應該有更快的方法(看Rank是這樣
只是懶得去理解

198.cpp

TOJ37,39,53,66,67,68

嗯嘛...
就幾題水題，蠻類似就放一起吧
只要肯花時間慢慢寫判斷就好的
基本上也不會TLE或MLE
...
就是水題嘛...
就是判斷而已嘛
打發時間很好用就是
其實全寫完也不會花多少時間...
像看起來最難的68我也才寫57行，一堆BFS什麼的馬的破百行
我之前寫得有些很亂都乾脆直接打掉重寫了(⁄ ⁄•⁄ω⁄•⁄ ⁄)

37.cpp
39.cpp
53.cpp
66.cpp
67.cpp
68.cpp