SubaRyaのcode and 廢日常

8/13~8/17我在清大程式解題營的基礎班裡進修，收益不少，也挫折不少。   首先今年是ION CAMP第二屆，除了營長&副營長之外其他講師貌似都跟第一屆不一樣，然後今年的我覺得講得讓我比較懂(?   我基礎班的課都是跟 李昕威 電神與 王均倍 大神坐在教室最後面耍費(因為有插座)，但在邊刻CF的同時我也順便學會了懶惰標記、BIT、離散化、SPFA、MST(Kruskal&Prim)、KMP,複習了dsu的union by rank，也同時被王均倍指點了可以改成union by size(開心)   這次進階班是在晚上基礎班打模擬賽同時開班，因此我第一天時猶豫要聽課還是練習早上&下午所學，但聽說比賽後的題目會放到SOJ上當Problem題，我便毫不猶豫地踏向進階班......   在進ION CAMP前才被一階電神醍醐灌頂過學會&精熟的差別，因此第一天的目標即是 學會 進階班的課程即可   我在進階班裡學會了Treap、SCC、2-SAT、LCA、持久化線段樹，持久化隨機二叉樹，然後完全聽不懂莫隊、樹練剖分(QAQ)   大約晚上10點半回到宿舍，不是打CF就是學刻模板，還記得第三天晚上卦長來我們宿舍看到我在打CF，他問說我是甚麼顏色，我回說可愛綠人，他回我他也是淺綠，雖然我只打兩次，哈哈，(嗚......我聽了快崩淚了，感到莫名帶刺的安慰TAT)   最後一天有基礎&進階班混和上機考，我莫名的發現編譯器無法執行我的程式，de了一小時的bug才發現我用的那台電腦的編譯器不支援C++11 QQ，這時我才拿出我的筆電(我學乖了)   結業後一階電神告訴了我我這次來學經驗，而他是環境適合專心打code，但我怎麼貌似在進階班時瞄到他在看天才麻將少女(?   然後早上上課時我也瞄到了鄰座的王均倍在打賽爾號，頓時也讓我重新回想起了童年的那份回憶，感動感動~~   還有吃飯時營長放Fate Zero給我們看，可惜我前面沒看到，要記得補~

題目URL:  https://pc2.tfcis.org/dev/index.php/problem/view/15/ 下圖是一份WA的code，不管是賽中or賽後我都de不到bug，但是剛剛發現了一件事，我要算距離的點相減沒有加abs(我是垃圾)，所以附上了AC code做比較。(提醒，賽中我忘了lower_bound的寫法，然後我也是垃圾不知道有開放網路，所以當場手刻了二分搜結果吃了TLE，好孩子千萬別學我這個垃圾) #pragma GCC optimizer("O2") #include<bits/stdc++.h> #define int long long int #define IOS ios_base::sync_with_stdio(false) #define TI cin.tie(NULL) using namespace std; signed main() { int a,b,c,d,e; vector < int > v; cin >> a >> b >> c; for ( int i = 0 ;i < a;i ++ ) { cin >> d; v.emplace_back(d); } sort(v.begin(),v.end()); while (b -- ) { cin >> e; int low = (lower_bound(v.begin(),v.end(),e) - v.begin()); if (low == 0 ) { if (abs(v[low] - e) <= c) cout << "Yes" << endl; else cout << "No"

題目URL: https://pc2.tfcis.org/dev/index.php/problem/view/43/ MST的裸題，簡單來說只要把operator的比較換一下，就變最大生成樹了，然後順便善用dsu並且小複習。(清大營隊進修ing) #pragma GCC osptimize("O2") #include<bits/stdc++.h> #define int long long int #define IOS ios_base::sync_with_stdio(false) #define TI cin.tie(NULL) using namespace std; const int MI = 100005 ; int num,a,b,w; struct edge{ int from,to,weight; }; bool operator < (edge & a,edge & b) { return a.weight > b.weight; } vector < edge > v; int vnum,vedge; struct disjointset{ int f[MI],rank[MI]; void init( int N) { for ( int i = 0 ;i <= N;i ++ ) { f[i] = i; rank[i] = 0 ; } } int find( int val) { if (f[val] == val) return val; return f[val] = find(f[val]); } bool same( int a, int b) { return find(a) == find(b); } void Union( int l, int r)

題目URL: https://pc2.tfcis.org/dev/index.php/problem/view/41/ 來到了清大的營隊，回顧一下最短路徑的裸題~ debug到死才發現我是垃圾~(因為我忘了把adj clear掉) #pragma GCC optimize("O2") #include<bits/stdc++.h> #define int long long int #define weight first #define index second #define IOS ios_base::sync_with_stdio(false) #define TI cin.tie(NULL) using namespace std; using edge = pair < int , int > ; const int INF = 2147483647 ; int vnum,dist[ 400005 ]; int num,M,st,t,a,b,w; vector < edge > adj[ 400005 ]; void dijkstra( int s) { vector < bool > vis(vnum, false ); fill(dist,dist + vnum + 5 ,INF); dist[s] = 0 ; priority_queue < edge,vector < edge > ,greater < edge >> pq; pq.emplace( 0 ,s); while ( ! pq.empty()) { int u = pq.top().index; pq.pop(); if (vis[u]) continue ; vis[u] = true ; for ( auto v : adj[u]) { if (dist[v.index] > dist[u] + v.

題目URL:  http://codeforces.com/contest/999/problem/A 這題主要是判斷ai小就break，兩頭掃過去判斷一下順便記數，但記得特判全部都可以的時候 #include<bits/stdc++.h> using namespace std; int str[ 1005 ]; signed main() { int a,num,total = 0 ,key = 0 ; cin >> num >> a; for ( int i = 1 ;i <= num;i ++ ) { cin >> str[i]; if (str[i] <= a && key == 0 ) { total ++ ; } if (str[i] > a) key = 1 ; } if (total == num) return cout << num , 0 ; total = 0 ; for ( int i = 1 ;i <= num;i ++ ) { if (str[i] <= a) total ++ ; else break ; } for ( int i = num;i >= 1 ;i -- ) { if (str[i] <= a) total ++ ; else break ; } cout << total << endl; return 0 ; }

題目URL: http://codeforces.com/contest/1017/problem/C 稍微想了一下，原來不是要我們去算真正的LIS&LDS(鬆了一口氣)，其實這題有一個小技巧，就是自己sqrt(n)為一組為遞減順序，依此類推，至於如果sqrt後有小數，那就是剩下的自己一組，每一組的頭即是最小遞增數量(LIS)，每一組的數量(剩下的除外)即是最小遞減的數量(LDS) #include<bits/stdc++.h> using namespace std; main() { priority_queue < int ,vector < int >> pq; int num,isq,flag = 1 ; double sq; cin >> num; isq = sqrt(num); sq = sqrt(num); if (sq == ( double )isq) { for ( int i = 1 ;i <= num;i ++ ) { pq.push(i); if (i % isq == 0 ) { while ( ! pq.empty()) { cout << pq.top() << " " ; pq.pop(); } } } } if (sq > ( double )isq) { isq ++ ; for ( int i = 1 ;i <= num;i ++ ) { pq.push(i); if (i % isq == 0 )

題目URL: http://codeforces.com/contest/1017/problem/B 如果稍為的想一下，是否有想出只有判斷到同一個index的情況下只有ai=0 bi=0 或ai=1 bi=0 才會有需要採取交換的動作呢?(可以停下來想一下) 接下來只要判斷到以上條件，就需要"分別"跟在a裡有1 、0的數字交換，因此在輸入時就可以先把a裡面有1、0的數字分開加總，最後在下面判斷時即可加總需要換的數量。 但是記得每判到了一個就得把自己數的總和減1，否則會在後面時重複記數。 #include<bits/stdc++.h> using namespace std; string a,b; signed main() { long long int len,totala = 0 ,totalb = 0 ,total = 0 ; cin >> len; cin >> a; cin >> b; for ( int i = 0 ;i < len;i ++ ) { if (a[i] == '0' ) totala ++ ; else totalb ++ ; } for ( int i = 0 ;i < len;i ++ ) { if (a[i] == b[i] && a[i] == '0' ) { total += totalb; totala -- ; } else if (a[i] != b[i] && a[i] == '1' ) { total += totala; totalb -- ; } } cout << total << endl;

題目URL:  http://codeforces.com/contest/1017/problem/A 由於第一個就是要比較的人，因此輸入時就將四個數相加，其餘的輸入相加與之比較，即可排名次 #include<bits/stdc++.h> using namespace std; int total[ 1005 ]; main() { int num,a,b,c,d,ans = 1 ; cin >> num; for ( int i = 0 ;i < num;i ++ ) { cin >> a >> b >> c >> d; total[i] = a + b + c + d; if (total[ 0 ] < total[i] && i >= 1 ) ans ++ ; } cout << ans << endl; return 0 ; }

題目URL: http://codeforces.com/contest/1016/problem/A 這題主要是分堆的技巧，嘛......每一筆的"和"跟每一筆的"除"去做然後記得將商數乘以原來的除數就可以維護這題的小性質。 #include<bits/stdc++.h> using namespace std; map < int , int > str; main() { ios_base :: sync_with_stdio( false ); cin.tie( NULL ); long long int a,b,total = 0 ,num; cin >> a >> b; for ( int i = 0 ;i < a;i ++ ) { cin >> num; total += num; str[i] = total / b; total -= (str[i] * b); } for ( int i = 0 ;i < a;i ++ ) cout << str[i] << " " ; cout << endl; return 0 ; }

題目URL:  http://codeforces.com/contest/1003/problem/A 水題~記數後挑最大的即可 #include<bits/stdc++.h> using namespace std; int str[ 1005 ]; main() { int a,num,maxu = 0 ; cin >> num; while (num -- ) { cin >> a; str[a] ++ ; } for ( int i = 0 ;i < 1005 ;i ++ ) maxu = max(maxu,str[i]); cout << maxu << endl; return 0 ; }

題目URL: http://codeforces.com/contest/1008/problem/B 第一組取最大，後面判斷是否有遞減，可以組成任一組遞減即為YES。 #include<bits/stdc++.h> using namespace std; map < int , int > a,b; int num,maxa,maxb,minu; main() { int deter = 0 ; cin >> num; for ( int i = 0 ;i < num;i ++ ) { cin >> a[i] >> b[i]; } maxa = max(a[ 0 ],b[ 0 ]); for ( int i = 1 ;i < num;i ++ ) { //cout << maxa << endl; maxb = max(a[i],b[i]); minu = min(a[i],b[i]); if (maxa < maxb) { if (maxa < minu) { deter = 1 ; break ; } else { maxa = minu; } } else if (maxa >= maxb) maxa = maxb; } if (deter) return cout << "NO" , 0 ; cout << "YES" << endl; return 0 ; }

題目URL: http://codeforces.com/contest/1004/problem/A 可以擴張就擴張，要判斷的是數若兩數之間一減一加(分別是右、左)加的那個數後比減的大，就不得擴張 #include<bits/stdc++.h> using namespace std; int str[ 1005 ],ans[ 1005 ]; main() { int a,b,flag = 0 ,total = 1 ; cin >> a >> b; for ( int i = 0 ;i < a;i ++ ) { cin >> str[i]; if (i >= 1 ) { if (str[i - 1 ] + b < str[i] - b) total += 2 ; else if (str[i - 1 ] + b == str[i] - b) total ++ ; } } cout << total + 1 << endl; return 0 ; }

題目URL: http://codeforces.com/contest/1006/problem/A 嘛......判斷偶數就減1，奇數不變，就可以輸出啦~ #include<bits/stdc++.h> using namespace std; int str[ 1005 ]; main() { int num; cin >> num; for ( int i = 0 ;i < num;i ++ ) cin >> str[i]; for ( int i = 0 ;i < num;i ++ ) { if (str[i] % 2 == 0 ) cout << str[i] - 1 << " " ; else cout << str[i] << " " ; } cout << endl; return 0 ; }

題目URL: http://codeforces.com/contest/1015/problem/E1 淹水淹水淹水法啦~~~~ 其實可以建四個方向前綴，取size的min，再O(n^2)比較，但O(n^3)可以過的話有何不可呢??(只可惜E2的hard edition就QQ了~) #include<bits/stdc++.h> using namespace std; char m[ 1005 ][ 1005 ]; int sor[ 4 ],a,b,total = 0 ,tot = 0 ,cou = 0 ,flag = 0 ,f = 0 ; int ans[ 10005 ],ansi[ 10005 ],ansj[ 10005 ],stri[ 10005 ],strj[ 10005 ]; signed main() { cin >> a >> b; for ( int i = 1 ;i <= a;i ++ ) for ( int j = 1 ;j <= b;j ++ ) { cin >> m[i][j]; if (m[i][j] == '*' ) { stri[flag] = i; strj[flag] = j; flag ++ ; } } int aa = 0 ,bb = 0 ,cc = 0 ,dd = 0 ; for ( int i = 0 ;i < flag;i ++ ) { aa = 0 ; tot = 1 ; while ((m[stri[i]][strj[i] - tot] == '*' || m[stri[i]][strj[i] - tot] == '#' ) && \ (m[stri[i]][strj[i] + tot] == '*' || m[

題目URL: http://codeforces.com/contest/6/problem/C 這題很單純的是用deque去頭尾比總和拔值，並且分別記數 #include<bits/stdc++.h> using namespace std; signed main() { deque < int > de; int num,a = 0 ,b = 0 ,t,totala = 0 ,totalb = 0 ; cin >> num; for ( int i = 0 ;i < num;i ++ ) { cin >> t; de.push_back(t); } a += de.front(); de.pop_front(); totala ++ ; while ( ! de.empty()) { //cout << a << " " << b << endl;; if (b >= a) { a += de.front(); de.pop_front(); totala ++ ; } else { b += de.back(); de.pop_back(); totalb ++ ; } } cout << totala << " " << totalb << endl; return 0 ; }