SubaRyaのcode and 廢日常

題目來源: https://neoj.sprout.tw/problem/80/ 這題只是單純的RMQ問題，只要好好地維護遞迴的性質並且只要單點修改(不須推下去)，因此就變成了普通的模板題。 #pragma gcc optimize("o2") #include<bits/stdc++.h> #define int long long int #define IOS ios_base::sync_with_stdio(false) #define TO cin.tie(NULL) #define MAXN 1000000 using namespace std; struct Node{ int l,r; int lson,rson; int data; }; Node segtr[MAXN * 2 ]; int str[MAXN]; int ptr = 0 ; void build( int l, int r, int index) { segtr[index].l = l; segtr[index].r = r; int mid = (l + r) / 2 ; if (l == r - 1 ) segtr[index].data = str[l]; else { int lson = segtr[index].lson =++ ptr; int rson = segtr[index].rson =++ ptr; build(l,mid,lson); build(mid,r,rson); segtr[index].data = min(segtr[lson].data,segtr[rson].data); } } void modify( int x, int val, int index) { if (segtr[index].l == segtr[index].r - 1 ) segtr[index].data =

https://zerojudge.tw/ShowProblem?problemid=b229 發現了這個關係式 len[i]=2*len[i-1]+len[i-2] 就變水題 #pragma gcc optimize(o2) #include<bits/stdc++.h> #define int unsigned long long int #define IOS ios_base::sync_with_stdio(false) #define TO cin.tie(NULL) using namespace std; int len[ 55 ] = { 0 , 3 , 7 }; signed main() { for ( int i = 3 ;i <= 50 ;i ++ ) len[i] = 2 * len[i - 1 ] + len[i - 2 ]; int N; cin >> N; cout << len[N] << '\n' ; return 0 ; }

我的想法很直觀，就是用array儲存入和出的人(記得出的時間點也算，所以要加1)，然後掃過去紀錄時間軸的max值。 PS:我最後發現我這樣寫不管是時間上還是空間上都很爛，所以我去看了幾位大神的寫法才發現這題可以用離散化或是用map揍掉 m(_ _)m #pragma gcc optimize(o2) #include<bits/stdc++.h> #define int long long int #define IOS ios_base::sync_with_stdio(false) #define TO cin.tie(NULL) using namespace std; int str[ 100005 ]; signed main() { IOS;TO; int range = 0 ,a,b,n,maxu,ans; while (cin >> n) { ans = 0 ;maxu = 0 ; while (n -- ) { cin >> a >> b; str[a] ++ ; b += 1 ; str[b] -- ; range = max(range,b); } for ( int i = 0 ;i <= range;i ++ ) { maxu += str[i]; ans = max(maxu,ans); } cout << ans << endl; } return 0 ; }

雖然有一點煩(連續輸入我看漏了)，但只是裸裸的dsu題(模板+1/0) 據說我是題目連結(?  https://tioj.ck.tp.edu.tw/problems/1312 #pragma gcc optimize("o2") #include<bits/stdc++.h> #define int long long int #define IOS ios_base::sync_with_stdio(false) #define TO cin.tie(NULL) using namespace std; struct disjointset { int mem[ 10005 ],rank[ 10005 ]; void init( int num) { for ( int i = 0 ;i <= num;i ++ ) { mem[i] = i; rank[i] = 0 ; } } int find( int N) { if (mem[N] == N) return N; return mem[N] = find(mem[N]); } int same( int a, int b) { return find(a) == find(b); } void Union( int l, int r) { i f ( ! same(l,r)) { if (find(l) < find(r)) swap(l,r); mem[find(l)] = find(r); rank[find(l)] += find(r); } } }; signed main() { IOS;TO; int n,m,a,b,k; struct

 早上實作......嘛~  分四題:       PA:(100%) 單純的運算水題(分次利息-原本利息)       PB:(100%) 陣列轉個方向印出，空的印'*'即可       PC:(0%)  二維平面只有第0層安全，一個格子等價於一個房間，頂多容納1人。從第一層以上有倆倆之間的房間(不一定相鄰)可以互相穿梭，(以上佔分80%)，第0層也可以互相穿梭，佔分20%，請問最多有幾個人可以逃脫?嘛......圖論題，我想過爆搜(不大優)、DFS......之類的，but in vain. I have no idea!!!       PD:(40%) 將輸入sort後再從原字串的 '$'開始向sort的字串倒推源字串(這是一 個一個將最尾端的字元往排頭放，接著將全部的過程一字典續排序後再挑最後一欄的回朔結論)但我這個作法只拿了40%(?       Total:240/400  然後下午的筆試40題(20單選20填空)，除了考的資訊史之外，整體上沒什麼太大的問題。  接著，等成績打FGO、LoveLive。好開心又好興奮  拿了佳作......  嘛......明年再加油!!!(我還是好垃圾......) PC: https://drive.google.com/file/d/1SrgWh6eaDuxsv9b2KqNtjk0FgWqlA5kT/view PD:  https://drive.google.com/file/d/1u61Je3Ms25ZItPJlysk2uXNz4mLKPwsJ/view

  (300題45分鐘)   這次跟去年一樣在華僑高中，聽英選中100題，看英選中100題，看中選英100題，但是小抱怨一下，聽應選中時41~50、70~80、90~100有些題號沒唸，有些跳題，甚至不唸題......嘛......這樣就算了，但當我聽英選中回過神來時，我居然畫到看英選中的卡了!!!而且已經唸到第70多題了，算了，至少在唸到100題之前順利的copy到了正確的答案卡上，並且充分的利用25分鐘(實際上是18分鐘)寫完了另外200題，檢查了2次。Fortunately,最後還是有用光碟機重放沒播到的部分，感覺還算可以。   其實去年我也有比，但第一次沒跟上時間的腳步，因此到最後還有30多題沒寫完就交卷了，(實在不堪設想啊啊啊啊)

  人生一敗塗地，我直到考試前兩天才把所有課、作業、小考、線上期末考全部掃過(嘛......13周的課程濃縮成兩天還挺刺激的~XD)，但大部分時間都是花在看昕威電神介紹給我的新頁出版的微積分書。   這兩天學會了如何在分部積分下用表列法、三角反三角代換法、瑕積分、基礎的Shell & Disk method、重積分。   人生充實???   不，實際上在我人生第一次看完後在沒實戰過的情況下我垃圾到翻開了線上期末考出來寫，然後很華麗地拿了高中以來數學科第一個不及格---53.xx分   此時拿起手錶，星期六1:05am ，距離實考還有大約9個小時......算了，睡覺~   至考前有4小時，再次拿起書本開始狂複習、拿出錯過的題目訂正......總之，還算有精神讀得下去吧。   到了交大，考卷發下來了，共12題，2小時作答時間，大約掃個題......我鬆了一口氣，呼~認知範疇之內~爽!!!   考完試後身心果真舒暢~然後在教室外巧遇在校化學培根電神，他是來考化學筆試的，接著與電神聊了聊他的讀書方式與技巧......哈哈~他也跟我一樣是臨陣磨槍(吧?)~但聽說課程網上的所有考試他都滿分(?(我果然還是不能跟他混為一談 QAQ)   總之，這次的培訓計畫讓我深可體會時間的管理好重要(?

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 ; }