## 建中資訊校內賽題解 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)$ 懶人倍增法。  ---- ### $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--; } ```  有人寫遞迴的也是少 $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'; } } ```  好好看題目啊大哥 ---- 大家要記得好好看題目 --- ## 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]; } } } ``` ----  --- ## 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')$。 ---- 譴責（要記得開區域的陣列不會幫你清乾淨喔）  ---- ```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; } ``` 令人心痛之二（同一個人） ----  --- ## 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; } ``` ---