頹coding

題目連結： http://codeforces.com/problemset/problem/877/E 既然是對子樹做操作，那我們可以把樹壓平，並用線段樹區間改值、區間詢問。 # include < bits/stdc++.h > # define PB push_back # define N 200005 # define M (l+r)/2 # define jizz cin.tie(0);ios_base::sync_with_stdio(0); using namespace std; struct Node{ int w; bool tag; }seg[ 4 * N]; int n,t; int b[N],a[N]; vector< int > v[N]; int in[N],out[N]; void DFS (int now){ in[now] = ++t; a[t] = b[now]; for(int i : v[now]) DFS (i); out[now] = t; } void pull (int id){ seg[id] .w = seg[id << 1] .w + seg[id << 1 | 1] .w ; } void push (int id, int l ,int r){ if(seg[id] .tag == 0 || l == r)return; seg[id << 1] .w = M-l+1-seg[id << 1] .w ; seg[id <<1 | 1] .w = r-M-seg[id <<1 |1] .w ; seg[id << 1] .tag ^= 1; seg[id <<1 | 1] .tag ^= 1; seg[id] .tag = 0; } void build (int l,int r,int id){ if(l == r){ seg[id] .w = a[l]; retu...

題目連結： http://codeforces.com/problemset/problem/609/F 可以用青蛙的位置建一顆線段樹，存青哇所能吃到的位置的最大值。 對於這隻蚊子，先二分搜找到最後一隻位置小於蚊子的青蛙，接著區間搜尋哪一隻青蛙是可以吃到且是最左邊的。 開個multiset存哪幾隻蚊子先前沒被吃掉，如果有青蛙可以吃的距離有增加，就找multiset內有沒有蚊子可以被吃掉。 # include < iostream > # include < algorithm > # include < cmath > # include < bitset > # include < queue > # include < vector > # include < set > # define lld long long # define PB push_back # define F first # define S second # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' # define N 200005 # define M (l+r)/2 # define INF 2147483647 using namespace std; typedef pair< int , int > Pair; int n,m; Pair x[N]; int seg[ 4 *N],sol[N],ans[N]; multiset<Pair> s; void pull (int id){ seg[id] = max(seg[id<<1],seg[id<<1|1]); } void build (int l,int r, int id){ if(l == r){ seg[id] = x[sol[l]] .F +x[sol[l]] .S ; return; } build...

題目連結： http://codeforces.com/problemset/problem/600/E 題目為為子樹的眾數問題。 不難發現樹壓扁可以轉成序列區間眾數，因此再用莫隊去做。 # include < bits/stdc++.h > # define PB push_back # define F first # define S second # define lld long long # define N 100005 # define debug cout << "a" <<endl; using namespace std; typedef pair< int , int > Pair; struct Query{ int l,r,lid,id; bool operator < (const Query &x)const{ return lid == x .lid ? r < x .r : lid < x .lid ; } }q[N]; int n; int color[N]; vector< int > v[N],g; int in[N],out[N],sz[N],mx,t; lld h[N],ans[N],sum; void DFS (int now,int fa){ in[now] = t++; g. PB (color[now]); for(int i : v[now]){ if(i != fa) DFS (i,now); } out[now] = t-1; } void add (int x){ ++sz[x]; h[sz[x]] += x; mx = max(mx,sz[x]); } void sub (int x){ h[sz[x]] -= x; sz[x]--; if(!h[mx])mx--; } void MO (){ int L = 0,R = 0; add(g[L]); for(i...

題目連結： http://codeforces.com/contest/510/problem/C 先比較字串，對字元間的大小關係建一張圖，如果'a' < 'b'那'a'就連一條邊給'b'。 接著就找該圖的拓墣排序即可。 # include < iostream > # include < algorithm > # include < cmath > # include < bitset > # include < queue > # include < vector > # define lld long long # define PB push_back # define F first # define S second # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' using namespace std; typedef pair< int , int > Pair; string s[ 105 ],ans; bitset< 30 > g[ 30 ]; int in[ 30 ]; bool topu (){ queue<int> q; for(int i = 0 ; i < 26 ; i++)if(!in[i])q. push (i),ans+='a'+i; while(!q. empty ()){ int t = q. front ();q. pop (); for(int i = 0 ; i < 26 ; i++){ if(g[t][i] && (--in[i]) == 0){ q. push (i),ans += 'a'+i; } } } return an...

題目連結： http://codeforces.com/contest/864/problem/E 類似背包的dp，dp[i][j] = max(dp[i][j-1],dp[i-1][j],dp[i-1][j-item[i].t]+item[i].p)。 最後再遞迴找是從哪裡轉移過來的。 # include < iostream > # include < algorithm > # include < cmath > # include < bitset > # include < queue > # include < vector > # define lld long long # define PB push_back # define F first # define S second # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' using namespace std; typedef pair< int , int > Pair; struct Ken{ int t,d,p,id; bool operator<(const Ken &x)const{ return d < x.d; } }item[ 105 ]; int dp[ 105 ][ 2005 ],ans; pair< int , Pair> f[ 105 ][ 2005 ]; vector< int > v; void solve (int x,int y){ if(f[x][y] .F == 0)return; ans++; v. PB (f[x][y] .F ); solve(f[x][y] .S .F ,f[x][y] .S .S ); } int main (){jizz int n;cin >> n; for(int i = 1 ; i <= n ;...

題目連結： http://codeforces.com/contest/862/problem/C 需要構造一個長度為n的序列，其全部xor起來等於k。 可以發現0^1^2^3為0 ，4^5^6^7為0，8^9^10^11為0........。 所以先構造出n%4個數字其xor總和為k，接著再如上所寫的規律一組一組丟進ans。 接著就特判一些東西，會無解的可能情況只有n = 2和k = 0的時候，同理當(n%4 = 2,k = 0)時因為無法構造出2個數字xor = 0，所以先隨便丟一些數字進去再構造即可。 # include < iostream > # include < algorithm > # include < cmath > # include < bitset > # include < queue > # include < vector > # define lld long long # define PB push_back # define F first # define S second # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' # define N 1000000 using namespace std; typedef pair< int , int > Pair; vector< int > ans; bitset< 1000006 > ok; int tmp = ( 1 << 18 )- 1 ,t = 0 ; int main (){jizz int n,k;cin >> n >> k; bool flag = 0; if(n == 2 && !k)return cout << "NO" << endl, 0; if(n%4 == 2 && !k){ fla...

題目連結： http://codeforces.com/contest/822 #A 啦啦啦 # include < iostream > using namespace std; int f (int a){return a == 1 ? 1 : a* f (a-1);} int main (){ int a,b;cin >> a >> b; cout << f( min (a,b)) << endl; } #B 窮舉 t 的子字串然後比較看哪一段的差異最小，並記錄是哪一段，最後再重新跑一次那一段，並輸出不一樣的位置。 # include < iostream > # include < string > using namespace std; int main (){ int n,m; cin >> n >> m; string s1,s2; cin >> s1 >> s2; int ans = 21474836,ans2; for(int i = 0 ; i < (m-n+1) ; i++){ int tmp = 0; for(int j = 0 ; j < n ; j++){ if(s1[j] != s2[j+i])tmp++; } if(ans > tmp)ans = tmp,ans2 = i; } cout << ans << endl; for(int j = 0 ; j < n ; j++){ if(s1[j] != s2[j+ans2]){ cout << j+1 << ' ';; } } return 0; } #C 可以按照 r-l+1 的數值分組。 窮舉所有旅途，要找x-(r-l)+1那組中不重複的區間的花費的最小，但因為你會窮舉所有旅...

題目連結： http://codeforces.com/contest/820 #A 就根據提意模擬就好 # include < iostream > using namespace std; int main (){ int c,v0,v1,a,l;cin >> c >> v0 >> v1 >> a >> l; int ans = 1,t = 0,s = v0; t += s; while(t < c){ t-=l; if(s+a > v1)s = v1; else s+=a; t += s; ans++; } cout << ans <<endl; return 0; } #B 題目有點難懂，我們只要固定1,2然後枚舉剩下的點即可。 # include < iostream > using namespace std; double abs (double x){return x < 0 ? -x : x;} int main (){ double n,a;cin >> n >> a; double h = (n-2)*180/n; double m = h/(n-2); double ans = 3; double k = abs(h - a); for(int i = 4; i <= n ; i++){ h -= m; if( abs (h - a) < k){ k = abs(h - a); ans = i; } } cout << "1 2 " << ans << endl; return 0; } #C 待編輯  #D 先預處理a[i]在 i 的左邊還是右邊，往右滑時總合會加在左邊的個數以及...

題目連結： http://codeforces.com/contest/821 #A 照著敘述做就好。 # include < iostream > using namespace std; int a[ 60 ][ 60 ]; int main (){ int n;cin >> n; for(int i = 0 ; i < n ; i++) for(int j = 0; j < n ; j++) cin >> a[i][j]; for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < n ; j++){ if(a[i][j] != 1){ bool flag = 0; for(int s = 0 ; s < n ; s++) for(int p = 0 ; p < n ; p++) if(a[i][s] + a[p][j] == a[i][j]) flag = 1; if(!flag){ puts("No"); return 0; } } } } puts("Yes"); return 0; } #B 枚舉所有Y點，然後O(1)判斷那個點可以拿幾根香蕉。 # include < iostream > # include < cmath > using namespace std; long long m,b; long long a (long long y){return (y-b)*-m;} long long check (...

題目連結： http://codeforces.com/contest/816 #A 就勇敢的給他暴力做下去～ '9' + 1 會變成 ':'。 # include < iostream > # include < string > using namespace std; int main (){ string s;cin >> s; int ans = 0; while(1){ if(s[0] == s[4] && s[1] == s[3])break; s[4]++; if(s[4] == ':')s[4] = '0',s[3]++; if(s[3] == '6')s[3] = '0',s[1]++; if(s[1] == '4' && s[0] == '2')s[1] = s[0] = '0'; if(s[1] == ':')s[1] = '0',s[0]++; ans++; } cout << ans << endl; return 0; } #B 感覺就有很多人會寫線段樹區間加值ＸＤ 但只要記每個區間的左界、右界，然後掃過去每個點被覆蓋的次數就是在這之前出現的左界數 - 右界數。詢問就用前綴和即可。 # include < iostream > # define N 200005 # define jizz cin.tie(0);ios_base::sync_with_stdio(0); using namespace std; int l[N],r[N],tmp,c[N],a,b; int main (){jizz int n,k,q;cin >> n >> k >> q; for(int i = 0 ; i ...

題目連結： http://codeforces.com/contest/814 #A k >= 2時一定是輸出Yes，至於k = 1時就只要比第 i 項有沒有小於 i-1 項。 # include < iostream > # include < algorithm > # define endl '\n' # define jizz cin.tie(0);ios_base::sync_with_stdio(0); using namespace std; int a[ 7122 ],b[ 7122 ]; int main (){ int n,k;cin >> n >> k; for(int i = 0 ; i < n ; i++)cin >> a[i]; for(int j = 0 ; j < k ; j++)cin >> b[j]; if(k >= 2){cout << "Yes" << endl;return 0;} for(int i = 0 ; i < n ; i++){ if(!a[i])a[i] = b[0]; if(a[i] < a[i-1] && i){ cout << "Yes" << endl; return 0; } } cout << "No" << endl; return 0; } #B 有些人會用很多條件去判斷哪一格該放哪一個數字，但其實因為 a 序列和 b 序列皆和 p 序列差一個數字，而a != b，因此可以直接嘗試看看把a序列數字重複的那兩格擇一替換成缺少的那個數字，並檢查是否與 b 序列差一，差一的即為p序列。 # include < iostream > # include < bitset > # define endl ...

題目連結： http://codeforces.com/contest/812 #A 一開始我題目有點看不太懂，就隨便寫一寫pretest過了，沒想到之後被hackＸＤ。 就是一題暴力題，code有點醜。 # include < iostream > # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' using namespace std; bool ok[ 5 ][ 5 ]; int main (){jizz for(int i = 1 ;i <= 4; i++ ) for(int j = 1; j <= 4 ; j++) cin >> ok[i][j]; bool flag = 0; for(int i = 1; i <= 4; i++){ if(ok[i][4]){ if(i == 1 && (ok[2][1] || ok[4][3] || ok[i][1] || ok[i][2] || ok[i][3] || ok[3][2])) flag = 1; else if(i == 2 && (ok[1][3] || ok[3][1]|| ok[i][1] || ok[i][2] || ok[i][3] || ok[4][2])) flag = 1; else if(i == 3 && (ok[2][3] || ok[4][1]|| ok[i][1] || ok[i][2] || ok[i][3] || ok[1][2])) flag = 1; else if(i == 4 && (ok[3][3] || ok[1][1]|| ok[i][1] || ok[i][2] || ok[i][3] || ok[2][2])) ...