<style> .reveal .slides { text-align: left; font-size:35px } </style> ## 2023 Pretrain Final Contest ## 分析及簡易題解  ---- ## 題目 [contest link](https://codeforces.com/group/dnlUA4rsoS/contest/419656) - pA- An Easy Problem(易) - pB- Biconnected(中) - pC- Ciprime(中偏難) - pD- Daidaiso Lover(中偏易) - pE- Equip Itemark(中偏難) - pF- For Gym Badges(中偏難) - pG- Ground Truth(易) - pH- Heirloom(難) - pI- If You Are a Perfectionist(中偏易) ---- ### Scoreboard  --- 相信大家打完這場比賽也知道自己跟其他人實力的差距了 所有的實力都是靠平常不斷地刷題以及比賽經驗所累積的 如果想要變強 平常應該要好好刷題以及與隊友團練比賽 可以回想一下之前上課釋出的題單是否都已經刷完了 這次的內容都是上課學過的東西的變化，如果刷完了可以考慮去刷更多不同的變化，上課題單也只是基礎題而已 ---- 除此之外，如果你是卡在輸入輸出等等問題 甚至是語法不知道怎麼用 那也應該要去刷更多不同的題目以培養實作能力並熟記語法 如果不知道要刷什麼的話建議可以刷 UVa 的題目 很多題目都輸入長很奇怪能夠好好練你的輸入輸出的能力 ---- 而如果是題單都已經刷完了想寫更多題 這邊提供三份還不錯的題單 [刘汝佳紫書題單(算法竞赛入门经典 第二版 2014)](https://vjudge.net/article/45) [Competitive Programming 3 by Steven Halim](https://vjudge.net/article/768) [CSES Problem Set](https://cses.fi/problemset/) 建議好好照著題單刷，而不是去題庫隨機挑題目寫 如果覺得自己寫得不夠好可以去參考別人的程式碼可以學到很多東西 ---- 如果想增加實戰經驗，[atcoder](https://atcoder.jp) 每周六or日 會有一場 Atcoder Beginner Contest 可以定期參加 題目都是蠻經典的演算法 並且建議打完比賽可以參考題解的作法，並且往後面不會的題目多補1-2題 否則打完比賽沒補題原本不會的之後還是寫不出來，進步不大 --- ## 題解 題目的解釋順序將會按照難易度排序 --- ### pA- An Easy Problem 題意 : 給定n及再來n個數字，問是否為一個從1~n每個數字都有出現過的數組。 可以使用sort由小排到大後直接檢查value跟index是否相同 當然也有其他方式 像是記錄數字是否出現剛好一次 ---- example ```cpp= #include<iostream> #include<algorithm> const int N=1e5+5; int arr[N]={}; int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>arr[i]; sort(arr+1,arr+n+1); for(int i=1;i<=n;i++){ if(arr[i]!=i){ cout<<"NO\n"; return 0; } } cout<<"YES\n"; return 0; } ``` --- ### pG- Ground Truth 題意 : 給兩個四邊形的點，問一個點對一個點的距離，四個匹配加起來的最短距離會是多少。 可以直接枚舉排列組合4個點的順序再去進行計算 或是使用next_permutation去排列 時間複雜度上都沒問題 ---- example ```cpp= int ord[11]={0,1,2,3,4}; do{ double now=0; for(int i=1;i<=4;i++) now+=sqrt((v[ord[i]].x-ans[i].x)*(v[ord[i]].x-ans[i].x)+(v[ord[i]].y-ans[i].y)*(v[ord[i]].y-ans[i].y)); rans=min(rans,now); if(!flag){ rans=now; flag=1; } }while(next_permutation(ord+1,ord+4+1)); ``` 複雜度為 O($4 \cdot 4!$) --- ### pD- Daidaiso Lover 題意 : 動態加入或移除點座標，同時每次詢問離原點最近的點座標到原點之距離。 可以使用 mutiset 把每個座標存起來 或 map 紀錄每個座標的數量，以優化時間複雜度 使得每次新增刪除查詢都是 O($\log N$) ---- example ```cpp= struct cmp{ bool operator()(pair<int,int> lhs, pair<int,int> rhs){ return lhs.first*lhs.first+lhs.second*lhs.second < rhs.first*rhs.first+rhs.second*rhs.second; } }; multiset<pair<int,int>,cmp> st; while(k--){ int z,x,y; cin>>z>>x>>y; if(z==1) st.insert(make_pair(x,y)); else if(z==2) st.erase(st.find(make_pair(x,y))); int a=(*st.begin()).first,b=(*st.begin()).second; printf("%.10lf\n",sqrt((long long)a*(long long)a+(long long)b*(long long)b)); } ``` 總複雜度 O$(N\log N)$ --- ### pI- If You Are a Perfectionist 題意 : 給一個必定可以swap到合法的括號序列，問最少需要swap幾次 原本官解的做法是錯的，應該 rejudge 後有 3 隊變成 AC ---- 可以先用 stack 維護有幾個好的括號匹配 剩下來的括號會是 k 個右括號接 k 個左括號，像是以下 )))((( 而可以交換前兩個和最後兩個變成 (()()) 即可變成合法的匹配 也就是對於靠近中間的 k/2 個右括號，都匹配到左括號即可 因此要交換的數量為 (k+1)/2 ---- example ```cpp= void solve(){ int n; string str; cin >> n >> str; int ans = 0, cnt = 0; for(char c:str){ if(c == '(') ++cnt; else{ if(!cnt) ++ans; else --cnt; } } cout << (ans+1)/2 << endl; } ``` --- ### pB- Biconnected 題意 : 給一張無向圖，問他原本圖的最大邊減去最小生成樹裡面第n-k大的那條邊的權值。 因為cost的定義為，目前這張圖中最長那條線的消耗，所以其實就是最小瓶頸樹，那再結合題意就會是很簡單的最小生成樹閱讀理解題。 ---- example ```cpp= int32_t main(){ ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>m>>k; for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=m;i++) cin>>edge[i].x>>edge[i].y>>edge[i].w; sort(edge+1,edge+m+1,cmp); mx=edge[m].w; for(int i=1;i<=m;i++){ xx=Find(edge[i].x),yy=Find(edge[i].y); if(xx==yy) continue; used[++cnt]=edge[i].w,f[xx]=yy,now++; if(now==n) break; } cout<<mx-used[n-1-k]<<"\n"; } ``` --- ### pC- Ciprime 求出只有兩組因數且皆相異的數字。 可以得知是要使用篩法，其中的作法有 1 : 紀錄每個數字的倍數，被造訪四次的就會是答案，對於每一個v[i]一定會有4個因數都造訪過他。 2 : 數字一定可以分解成 a\* a \* b 或 a\* b\* b 或 $a^5$ ---- 第一種作法的官解，捨棄優化(時間複雜度可以)換取造訪次數以及正確性 ```cpp= const int N=1e7+5; int v[N], vis[N]; int main(){ ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); int flag=0; for(int i=2;i<=N-5;i++){ for(int j=i+i;j<=N-5;j+=i){ v[j]++; } } for(int i=2;i<=N-5;i++){ if(v[i]==4){ flag++; vis[++cnt]=i; } } int q; cin>>q; cout<<vis[q]<<"\n"; } ``` 總複雜度為調和級數 O($10^7\log 10^7$) --- ### pE- Equip Itemark F(N) = F(N-3) + 2*F(N-2) + F(N-1) 如果直接暴力算第 $O(N)$ 項肯定會 tle (N=$10^{18}$) 嘗試換到通靈矩陣快速冪式子 $\begin{bmatrix} 1&2&1\\1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{bmatrix} * \begin{bmatrix} f[n-1] \\ f[n-2] \\ f[n-3] \\ \end{bmatrix} = \begin{bmatrix} f[n] \\ f[n-1] \\ f[n-2] \\ \end{bmatrix}$ 複雜度 O($3^3\log N$) --- ### pF- For Gym Badges 可以觀察題目的限制 k 為奇數，題目是要將陣列切成 K 段，而這 K 段的 xor 值要相同，因此可以發現全部的 xor 值等於其中一段的 xor 值 例：切成 5 段，每段的 xor 值為 A， A xor A xor A xor A xor A = A， ---- 做法： 算出整個陣列的 xor 值，這個就是每一段的 xor 值 並且通過觀察發現，由於每一段的 xor 值會一樣，第一段跟第二段做 xor 會等於 0 因此前綴 xor 的陣列會長成這樣 ... A ... 0 ... A ... 0 ... A ，最後會是以 A 為結尾。 ---- ```cpp= void solve() { int n, k; cin >> n >> k; vector<int> a(n + 5); vector<int> xora(n + 5); for (int i = 0; i < n; i++) { cin >> a[i]; xora[i] = a[i] ^ (i > 0 ? xora[i - 1] : 0); } int allxor = xora[n - 1]; int flag = 0; vector<int> ans; for(int i = 0; i < n; i++) { if(flag == 0 && xora[i] == allxor) { flag = 1; ans.push_back(i); } else if(flag == 1 && xora[i] == 0) { flag = 0; ans.push_back(i); } } if(ans.size() >= k && ans.size() & 1 && flag == 1) { if(k == 1) { cout << n << '\n'; return; } for(int i = 0; i < k - 1; i++) { cout << ans[i] - (i > 0 ? ans[i - 1] : -1) << ' '; } long long sum = 0; cout << n - 1 - ans[k - 2] << '\n'; } else { cout << -1 << '\n'; } } ``` --- ### pH- Heirloom 拼拼圖 先特判 n=1，也就是只有一片拼圖的情況下是否四面都為 0 再來判是否為整個拼圖大小為 $1\times N$ ( 2 塊拼圖有三個 0）其他都是兩個0 其他就是求出四個角落（角落的兩個位置為 0）其中一個當左上 ---- ### 模擬 從左上開始每一列往右拼，拼完一列換下一列，拼不上的就是 -1 下一列的第一個會跟上一列的第一個同樣數字並且左邊是 0 找到就可以繼續拚下去 由於題目有說每個數字會出現兩次，所以可以開一個 pair<int,int> 陣列紀錄每個數字出現是在哪兩個拼圖上，當一個拚上之後就判斷他右邊的那個位置的拼圖能不能對上往上的那個，以及如果是最右邊要判斷是不是靠右的位置為 0 複雜度 $O(N)$