## 建中資訊校內賽題解
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;
}
```
---