Subscribed unsubscribe Subscribe Subscribe

0w1

Hi everyone, please feel free to have discussions with me!

TOJ 6 因數個數1 ( Math )

Test Online Judge 這題各種限制很緊,差點以為這個解法行不通 ( 或許我的解法也不是正解 )。 想著應該是要用篩法先預處理,利用質因數分解後的指數做組合算出答案。但如果傻傻地做,就會MLE,所以只能用 short存答案。這樣不會爆是很顯然的,因為最多只會有…

TOJ 101 哪裡有卦,哪裡就有源 ( 水題二分圖 )

http://sprout.tw/oj/pro/101/ 顯然就是二分圖。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXM = 2 * MAXN; int n; vector< int > G[ MAXN ]; void init(){ for(int i = 0; i < n; ++i) G[ i ].clear(); } int col[ MAXN ]; bo</bits/stdc++.h>…

TOJ 47 1d-kd-tree ( STL map )

TOJ

http://sprout.tw/oj/pro/47/ 題目的要點在於求離一個數距離最小的數,並且支持插入和修改。先考慮如果題目只求正方向距離最小,那其實只是求 lower_bound罷了。加了一個負方向其實也只是要找以該點在數線上對稱的lower_bound。因此我們只需要維護正數和負數…

TOJ 72 Happiness Function ( 三分搜 )

http://sprout.tw/oj/pro/72/ 一個三分搜模板。每次總是縮小至少三分之一的搜索範圍,慢慢走往凹點。 #include <cstdio> int n; double a[10], b[10], c[10]; double S(double t){ double mx = 0; for(int i = 0; i < n; ++i) if(a[i]*(t-b[i])*(t-b[i])+c[i] > mx) </cstdio>…

TOJ 275 同學會 ( Adhoc )

http://sprout.tw/oj/pro/275/ 這題雖然看起來很簡單,卻要想清楚很多細節才能寫好。最重要的關鍵是要發現如何做才能快速地發現那個團體中最後一個人。如果我們對每個團體紀錄 id的總和,剩下的人數,每次減少一個人就從 id總和減去它的 id,就能夠在刪除某…

TOJ 277 騎腳踏車 ( Greedy )

http://sprout.tw/oj/pro/277/ 很明顯如果希望疲累度最大,就不能讓休息站幫我們太多。讓休息站最沒有幫助的方法無疑是連續的,還有一個起點一個終點的情況。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e6 + 6; const int MAXA = 1e3 + 3; typedef </bits/stdc++.h>…

Monotonic optimal split point DP ( 凸性 2D / 1D 優化 )

http://sprout.tw/oj/pro/144/ Short summary for the problem: given an array of N ≤ 1000 numbers a[ 1 ], a[ 2 ] .., a[ N ], each pair of numbers a[ i ], a[ i + 1 ]adjacent to each other can merge into a new single number, producing a[ i ] + …