## 建中資訊校內賽題解 by 8e7, FHVirus and Jass --- 大家覺得難嗎 www > 好難喔我都不會 ---- 預估的分數線: 實際的分數線: ---- 預估第一名破台時間: 1:30 實際破台時間: 2:29 --- ## A. 蛋餅愛函數 「蛋餅好軟><」—FHVirus ---- ### Subtask 1 給輸入太慢或是稍嫌累贅的實做 ~~或是你想拿 470 分嘲諷出題者~~ 實測過 C++ 不會有輸入輸出太慢的問題 > 其實是拿來給參賽者自信的啦哈哈 ---- ### Subtask 2 暴力對於每一筆詢問都乖乖跑,$O(QN)$。 有沒有更好的作法? ---- ### $O((N+Q) \log N)$ 懶人倍增法。 ![](https://i.imgur.com/Z43FjM7.png) ---- ### $O(N+Q)$ 對於每一個 $i$ ,不斷取其 $f(i)$, 最後一定會回到原本的 $i$。 對這些 $i$ 分群,處理每一群的大小及群內的順序。 然後查詢的時候直接取就好了。 ---- ### 聽說你的 submission 死不瞑目 有一些邊界的 case、實做小細節要注意 題目要好好看 ~~才不會跟某自然組出題者一樣 模考自然粗心錯到跟國文差不多分數~~ ---- ### Case 1 ```cpp= #include <iostream> using namespace std; int n, q, f[100000]={}; ``` 題目是 1-base 的,記得要多開 ---- #### Case 2 ```cpp= while(q!=0){ cin>>a>>b; m=c[a-1]; for(int i=0;i<b-1;i++){ m=c[m-1]; } cout<<m<<endl; q--; } ``` ![](https://i.imgur.com/s1awBH5.png) 有人寫遞迴的也是少 $b = 0$ ---- ### Case 3 ```cpp= while (q--) { int a, b; cin >> a >> b; if (!b) { cout << "0\n"; } else { while (b) { a = f[a]; b--; } cout << a << '\n'; } } ``` ![](https://i.imgur.com/io1bbav.png) 好好看題目啊大哥 ---- 大家要記得好好看題目 --- ## B. 與眾不同 「競程是一句謊言、一種假象。」—8e7 ---- ### Subtask 1: $n \leq 15$ ---- 枚舉所有可能的 01 字串。按照題目的定義檢查。 複雜度$O(n \cdot 2^n)$ ---- ### Subtask 2: $k \leq 2$ ---- 令$S_{i,j}$代表第$i$個字串的第$j$個字元,$a_i$代表目前與第$i$個字串的相異度。 $k = 1$的話,一定能得到相異度為$n$的答案, $S_{1,i}$是0的話就填1,是1的話就填0。 ---- $k = 2$ 維護目前的字串(前$i-1$個字元)與$S_1, S_2$的相異度。 假設$S_{1,i} = S_{2, i}$,那就填相反的字元。 否則填跟相異度較小者不同的字元,使$min(a_1, a_2)$增加一。 ---- ### Subtask 3: 無其他限制 $k = 3$怎麼做? ---- 如果$S_{1,i} = S_{2, i} = S_{3, i}$,那就填相反的字元。 否則一定有一個人的字元和另外兩個人的不同。以下用$x, y, z$代表第$1, 2, 3$個人與其他兩人不同的次數。 ---- 一開始先全部填與兩個人不同的字元,並把相異度算出來。 接著對相異度最小的那個人持續做「交換」操作。 假設$S_1$是相異度最小的人。那一次交換就是讓$a_1 += 1, a_2 -= 1, a_3 -= 1$。 注意到,如果$min(a_i)$的人不一樣了,那就代表持續做交換操作不能增加$min(a_i)$。 ---- 還原字串時,必須維護跟哪個字串交換以及交換的次數。 ---- 官解 ```cpp= //Challenge: Accepted #include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <utility> #include <assert.h> using namespace std; void debug() {cout << endl;} template <class T, class ...U> void debug(T a, U ... b) { cout << a << " "; debug(b...);} template <class T> void pary(T l, T r) { while (l != r) {cout << *l << " ";l++;} cout << endl; } #define ll long long #define ld long double #define pii pair<int, int> #define ff first #define ss second #define io ios_base::sync_with_stdio(0);cin.tie(0); string a[3]; int main(){ io int n, k; cin >> n >> k; for (int i = 0;i < k;i++) cin >> a[i]; if (k == 1) { for (int i = 0;i < n;i++) cout << (a[0][i] == '0' ? '1' : '0'); cout << "\n"; } else if (k == 2) { int cur = 0; for (int i = 0;i < n;i++) { if (a[0][i] == a[1][i]) cout << (a[0][i] == '0' ? '1' : '0'); else { cout << (cur ? a[0][i] : a[1][i]); cur ^= 1; } } } else { int x = 0, y = 0, z = 0, dif[3] = {0, 0, 0}; for (int i = 0;i < n;i++) { if (a[0][i] == a[1][i] && a[1][i] == a[2][i]) continue; if (a[0][i] == a[1][i]) x++, dif[0]++, dif[1]++; else if (a[0][i] == a[2][i]) y++, dif[0]++, dif[2]++; else z++, dif[1]++, dif[2]++; } int p = min_element(dif, dif + 3) - dif; while (true) { bool stop = 0; for (int i = 0;i < 3;i++) { if (i != p && dif[i] - 1 <= dif[p]) stop = 1; } if (stop) break; if (p == 0) z--, dif[1]--, dif[2]--; else if (p == 1) y--, dif[0]--, dif[2]--; else x--, dif[0]--, dif[1]--; dif[p]++; } for (int i = 0;i < n;i++) { if (a[0][i] == a[1][i] && a[1][i] == a[2][i]) { cout << (a[0][i] == '0' ? '1' : '0'); } else { if (a[0][i] == a[1][i]) cout << (x ? (x--, a[2][i]) : a[0][i]); else if (a[0][i] == a[2][i]) cout << (y ? (y--, a[1][i]) : a[0][i]); else cout << (z ? (z--, a[0][i]) : a[1][i]); } } } } ``` ---- 你真的覺得這會過嗎 ```cpp= int maxx=0; char maxxer[20]; int ttt=1e8; for(int i=0;i<ttt;i++){ for(int j=0;j<a;j++){ if(rand()%2==0){ w[j]='0'; }else{ w[j]='1'; } } int ans1=0,ans2=0,ans3=0; int ans=99999999; ... ans=min(ans,ans1); ans=min(ans,ans2); ans=min(ans,ans3); if(ans>maxx){ maxx=ans; for(int j=0;j<a;j++){ maxxer[j]=w[j]; } } } ``` ---- ![](https://i.imgur.com/IuTirDY.png) --- ## C. 走夜路小心遇到鬼,還有女高中生 「或許人世間的那些邂逅,都是建立在這種奇妙的平衡上的吧。」—醋青魚 ---- ### Subtask 1: $N, M, p, q, \leq 6$ 給人自信用的Subtask,預設沒有特別做法XD ---- ### Subtask 2: $c_{ij}=0$對於所有的$1\leq i\leq N,1\leq j\leq M$。 就是沒有鬼的意思啦。 可以想辦法枚舉其中一種步伐長度的次數,看另外一種步伐要走幾步才會剛好走到,再把所有可能取最小值。注意小心處理會踩出界的情況。 ---- ### Subtask 3: $p=q=1$ 需要用到BFS的技巧,作法如下: 維護一個queue紀錄走到的點,一開始將起點丟進queue裡,並開一個陣列紀錄起點到所有點的距離。 每次從queue的最前方拿出一個點,對於它的上下左右的點,如果沒有走到過,就將它的距離設為自己的距離加一,並且丟進queue的最後。 最後答案就是「從$(1,1)$到$(a,b)$的距離」+「從$(a,b)$到$(N,M)$的距離」。 ---- ### Subtask 4: 無特別限制 做法與上一個Subtask類似,但是「上下左右的點」要改成「上下左右各$p$格與各$q$格的點」,一樣做BFS就能得到答案。 ---- ### 實做方式 大部分的人應該都是暴力複製貼上吧? 這裡附上比較乾淨漂亮的方式 ---- ```cpp= const int dx[4] = {1, -1, 0, 0}; const int dy[4] = {0, 0, 1, -1}; inline bool ok(int x, int y){ return 0 <= x and x < N and 0 <= y and y < M and !a[x][y]; } int bfs( ... ){ // 中間省略 // 現在在 (x, y) for(int dir = 0; dir < 4; ++dir) for(int step: {P, Q}){ int nx = x + dx[dir] * step; int ny = y + dy[dir] * step; if(ok(nx, ny) and !vis[nx][ny]){ // ... } } } ``` 八方位也適用 --- ## D. DZ 的因數遊戲 「你會遭天譴。」—Zisk ---- ### Subtask 1: $x = 1$ 如果$y=1$,先手必敗,否則先手可以把$y$變成$1$,所以必勝。 ---- ### Subtask 2: $x | y$ 當$x=y$時,先手做任意操作,後手都可以做相對應操作使$x=y$成立。到$1$的時候先手就會輸,因此$x=y$時先手必敗。 反之,先手可以將$y$變成$x$,先手必勝。 ---- ### Subtask 3: $x$ 是質數 ---- 這裡要小心判所有的case。 1. $y = 1$時先手勝。 2. $y$是質數,先手敗。 3. $y$是合數且$x < y$,先手可以讓$y$變成質數,輪到後手時變成Case 2,因此先手必勝。 4. $y$是合數且$x > y$,先手敗。 另解: $x, y$中較大者,是合數的話先手勝,否則後手勝。 ---- ### Subtask 4: $x, y \leq 10^3$ ---- 首先我們發現,一個遊戲的結果完全由$x, y$決定。因此可能的遊戲數就是$xy$種。 令$dp[i][j]$代表數字是$i, j$時先手有沒有必勝策略(0是必敗,1是必勝)。 若$i \leq j$,轉移方式就是$dp[i][j] = max_{k | j}(1-dp[i][k])$。 $i > j$的轉移方式類似。 ---- 這邊可以預處理每個數字的因數(轉移來源),或是用$O(\sqrt n)$的時間判斷。如果預處理的話複雜度是$O(xy*log \ max(x, y))$。 ---- ### Subtask 5: $x, y \leq 10^6$ 沒優化的 Subtask 6 作法 ---- ### Subtask 6: $x, y \leq 10^8$ ---- 可以發現有很多狀態是不可能在遊戲中出現的。 更精確來說,狀態$dp[i][j]$須符合 $i | x, \ j | y$ 才能出現在遊戲中。 ---- 這樣的狀態有多少個呢? 一個數字$n$以下的最多因數個數可以用$n^{1/3}$估計。所以有用的狀態只有大約$x^{1/3}y^{1/3}$這麼多! 實際上,$10^8$以下最多因數的數字有$768$個因數,總狀態數不會超過$768^2 \approx 6*10^5$個。 ---- 我們可以分別對$x$和$y$做值域壓縮,一樣預處理因數做$DP$。 複雜度證明? ---- 令 $n = max(x, y)$,那總共有$n^{2/3}$個狀態,每個狀態最多$n^{1/3}$個轉移,所以總複雜度不會超過$O(n)$。 實際上,可以證明轉移數不會超過$k^3/4$,其中$k$是因數個數。 (這個上界還能更好) Hint: $(x, x')$ 的轉移可以映射到整數對$(x/x', x')$。 ---- 譴責(要記得開區域的陣列不會幫你清乾淨喔) ![](https://i.imgur.com/hLD85SJ.png) ---- ```cpp= #include <iostream> using namespace std; int N, a, b; int main() { cin >> N; while(N>0) { cout << 'Danb'; } return 0; } ``` ---- ```cpp= int main(){ int T; cin >> T; while(T--){ int x, y; cin >> x >> y; int cx = 0, cy = 0; for(int i = 2; (ll) i * i <= x; i++){ while(x % i == 0){ cx++; x /= i; } } if(x > 1) cx++; for(int i = 2; (ll) i * i <= y; i++){ while(x % i == 0){ cy++; y /= i; } } if(cx == cy) cout << "Zisk\n"; else cout << "Danb\n"; } return 0; } ``` ---- ```cpp= int main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t,x,y; string first = "Danb\n",second = "Zisk\n"; cin>>t; for(int i=0;i<t;++i){ cin>>x>>y; if(x==1){ if(y==1)cout<<second; else cout<<first; } else if(y%x==0){ if(x==y)cout<<second; else cout<<first; } // 這裡要 else 不然會多輸出 bool x_prime = is_prime(x),y_prime = is_prime(y); if(x_prime && y_prime)cout<<second; else cout<<first; } } ``` 令人心痛 記的最下面也要 else 喔 ---- ```cpp= bool is_prime(int a){ for(int i=1;i*i<=a;++i) if(a%i==0)return true; return false; } ``` 令人心痛之二(同一個人) ---- ![](https://i.imgur.com/0cYnIyA.png) --- ## E. 買分 「這世界一點也不平等。」—衣笠彰梧 ---- ### Subtask 1: $N,C\leq 100$ 首先觀察題目,我們可以發現要使所有人皆及格,可以做下列兩件事: 1. 將不及格的人分數提高到及格。 2. 將及格的人分數調低,使及格線下降到讓原本不及格的人及格。 總代價可以分為「花在加分上的代價」與「花在扣分上的代價」兩類。 但是可以改變的東西太多了,無法處理。 於是可以想辦法把某個東西固定,看會對答案造成什麼影響? ---- ### 想法:固定總分 當總分固定,及格線也就定了下來。 因此我們可以嘗試枚舉最終的總分,然後: * 將不及格的人分數提高到及格 * 依照$b_i$由小到大,將還能扣的人扣到剛好及格為止,直到總分$\leq$目標總分。 總分只有$O(NC)$種,每次枚舉需要$O(N)$,總複雜度$O(N^2C)$。 ---- ### Subtask 2: $N,C\leq 1000$ 總分太多種了,能否枚舉少一點東西? 更直觀的想法:枚舉及格線! * 將不及格的人分數提高到及格 * 依照$b_i$由小到大,將還能扣的人扣到剛好及格為止,直到總分$\leq$目標及格線$\times 2N$。 ---- 在做第二個步驟時,如果原本總分就達成目標,那就什麼也不用做。 反之,及格線是整數一定會比較好! 若及格線不是整數,考慮此及格線的上高斯: * 加分的部分,不會有任何減少。 * 扣分的部分,後者一定比前者少! 因為後者的目標總分比較高,可以扣比較少次。 及格線只有$O(C)$種,每次枚舉需要$O(N)$,總複雜度$O(NC)$。 ---- ### Subtask 3: $C\leq 5\times 10^5$ 枚舉一次及格線需要$O(N)$,太花費時間了。 有沒有辦法藉由及格線$=x$的答案,快速推算出及格線$=x+1$的答案? ---- 以下把需要加分的人和扣分的人分開討論。 當及格線由$x$變$x+1$時,所有原本$x$分的人都要多花$a_i$元,因此我們可以維護不及格的人以及他們的$\sum a_i$。 那扣分怎麼做? ---- 我們可以把全班及格的條件寫成 $min(s_i) \geq \frac{\sum si}{2n}$, 因此我們在加分之後還需要扣 $\sum s_i - 2n*min(s_i)$分。 ---- 預處理每個及格線所需要扣的分數。由大到小枚舉及格線。 可以把扣分的人分成已經扣到及格線 $A$ 跟還沒扣到及格線 $B$ 兩種。 ---- 當及格線下降一分,我們需要多扣$x$分的時候, 先把$A$的人各多扣一分,剩下的分數從$B$裡面$b_i$小的人開始拿,如果有人扣到及格線就把他變成$A$。 ---- ### Subtask 4: 無特別限制 連及格線都無法枚舉,怎麼辦? 藉由上一個子題,可以觀察出兩個非常有用的性質: * 及格線每上升一分,加分的代價的變化量會遞增。 * 及格線每上升一分,扣分的代價的變化量會遞減。 ---- ### 如何證明 加分的部分,因為不及格的人會越來越多,因此加分的代價的變化量遞增。 ---- 注意到,假設我在及格線$x$分時需要扣分的話,當及格線是$x-1$分時, $\sum ai - 2n*min(a_i)$ 會增加 $2n - k \geq n$,其中 $k$是加分的人數。 這個改變量是會遞增的,因此在$A$的人會一直留在$A$,在$B$的人會從$b_i$小的開始拿,代價變化量(斜率)會遞增。 $x$下降時斜率遞增,因此$x$上升時斜率遞減。 ---- ### 有了這個性質可以怎麼做 如果將及格線為$x$軸,總代價為$y$軸畫出的圖形,一定是先遞減後遞增的。 對斜率二分搜! 方法如下:若目前可能的範圍為$[l,r]$,令$mid=(l+r)/2$,比較及格線為$mid$的答案與$mid+1$的答案,若前者較小,則答案一定在$[l,mid]$;反之,則答案一定在$[mid+1,r]$。如此的複雜度為$O(NlogC)$。AC! 註: 三分搜也可以 ---- ```cpp= //Challenge: Accepted #include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <utility> #include <assert.h> using namespace std; void debug() {cout << endl;} template <class T, class ...U> void debug(T a, U ... b) { cout << a << " "; debug(b...);} template <class T> void pary(T l, T r) { while (l != r) {cout << *l << " ";l++;} cout << endl; } #define ll long long #define ld long double #define maxn 100005 #define mod 1000000007 #define pii pair<ll, ll> #define ff first #define ss second #define io ios_base::sync_with_stdio(0);cin.tie(0); struct obj{ ll s, a, b; obj() {s = 0, a = 0, b = 0;}; } v[maxn]; int n, c; ll tot = 0; ll solve(ll x) { ll ret = 0, sum = tot; for (int i = 0;i < n;i++) { if (v[i].s <= x) ret += (x - v[i].s) * v[i].a, sum += x - v[i].s; } ll goal = 2 * x * n; if (goal >= sum) return ret; for (int i = 0;i < n;i++) { if (v[i].s > x) { ret += min(sum - goal, v[i].s - x) * v[i].b; sum -= min(sum - goal, v[i].s - x); if (goal >= sum) return ret; } } return ret; } int main() { io cin >> n >> c; for (int i = 0;i < n;i++) cin >> v[i].s, tot += v[i].s; for (int i = 0;i < n;i++) cin >> v[i].a; for (int i = 0;i < n;i++) cin >> v[i].b; sort(v, v + n, [&] (obj x, obj y) {return x.b < y.b;}); ll low = 0, up = c; while (low < up) { ll mid = (low + up)/2; if (solve(mid) < solve(mid+1)) up = mid; else low = mid+1; } cout << solve((low + up) / 2) << endl; } ``` ---
{"title":"建中資訊校內賽題解","slideOptions":{"theme":"night","transition":"fade"}}
    1066 views