###### tags: `Made by FHVirus with Love and Constant Optimization`
# Infor 33rdx34th 期末演算法競賽 題解
:::success
恭喜各位比完了第一場正式的比賽！:tada:
不管是表現得超過預期、被卡 endl 、還是覺得被打爆也沒關係！
繼續努力吧！（反正這篇的作者也不會 C 的題目）
by `FHVirus`
:::
## A 題組
### A1 庭宇與軟軟的資訊社生活
用 `if` 好好判斷現在時間！
值得一提的是，思考一下會發現，分鐘根本不重要！
:::spoiler 點我看扣
```cpp=1
int main(){
int hour, min;
cin >> hour >> min;
// 沒錯，可以直接寫 and ！
if(7 <= hour and hour <= 11){
cout << "Good Morning" << endl;
} else if(12 <= hour and hour <= 17){
cout << "Good Afternoon" << endl;
} else {
cout << "Good Night" << endl;
}
return 0;
}
```
:::
---
### A2 置中不講五德
對於 $n$ 的每一個位數，只要不是五，就直接放在 $a$，並且把 $b$ 的那個位數設成 `'0'` ；否則，把 $a$ 的那個位數設成 `'4'`，並把 $b$ 的那個位數設成 `'1'` ，就不會出現五了！
解法並不為一（也可以設成 `'3'` 和 `'2'` 等），可以挑戰設計炫砲的演算法測試自己的極限喔！
:::spoiler 點我看扣
```cpp=1
// string 版本
int main(){
string n;
cin >> n;
for(int i = 0; i < n.size(); i++){
if(n[i] == '5'){
cout << '4';
}
else{
cout << n[i];
}
}
cout << endl;
for(int i = 0; i < n.size(); i++){
if(n[i] == '5'){
cout << '1';
}
else{
cout << '0';
}
}
// 還記得 '\n' 跟 endl 嗎？
// 兩個都可以使用喔！
cout << endl;
return 0;
}
// char[] 版本
int main(){
const int N = 334; // 多開一些保險！這是好習慣！
char n[N], a[N], b[N];
// 記得要清空雜物喔！
for(int i = 0; i < N; ++i){
n[i] = a[i] = b[i] = 0;
}
cin >> n;
for(int i = 0; i < N; ++i){
if(n[i] < '0' or n[i] > '9') break;
if(n[i] == '5'){
a[i] = '4';
b[i] = '1';
} else {
a[i] = n[i];
b[i] = '0';
}
}
cout << a << '\n' << b << endl;
return 0;
}
```
:::
---
### A3 品羲與祕聞
我們先把字母轉成數字，好好做維吉尼亞加密後再轉回字母就可以了！
這題的實作細節比較多，直接看扣吧！
:::spoiler 點我看扣
```cpp=1
string s, k, t;
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// 要輸入一整行，這時就要用 getline() ！
// 用 cin 的話，會讀到空白就結束了
getline(cin, s);
getline(cin, k);
// 把字母轉換成 0 ~ 25 的數字
// 記得判斷空白喔
for(int i = 0; i < s.size(); ++i){
if(s[i] != ' ') s[i] -= 'A';
}
for(int i = 0; i < k.size(); ++i){
if(k[i] != ' ') k[i] -= 'A';
}
// 多開一個 kptr 紀錄金鑰循環到哪個位置了
int kptr = 0;
for(int i = 0; i < s.size(); ++i){
if(s[i] == ' ') continue;
s[i] -= k[kptr];
if(s[i] < 0) s[i] += 26;
++kptr;
if(kptr == k.size()) kptr = 0;
}
// 再從 0 ~ 25 轉換回字母！
for(int i = 0; i < s.size(); ++i){
if(s[i] != ' ') s[i] += 'A';
}
cout << s << endl;
return 0;
}
```
:::
---
### A4 量子與他的一句話證明
這題就是閱讀素養＋暴力！
暴力測試每一個 $a$ ，在暴力算出 $p - a^2$ 是不是完全平方數就好了！
:::spoiler 點我看扣
```cpp=1
int main(){
int p;
cin >> p;
// 照著題目說的做！
if(p % 4 != 1){
cout << -1 << endl;
// 可以提前 return 0;
// 這樣就會提前結束，
// 不用把下面的程式包在 else{} 裡！
return 0;
}
for(int a = 1; a * a < p; a++){
// left 剩下的，抱歉我不會命名變數 QWQ
int left = p - a * a;
for(int b = 1; b * b <= left; b++){
if(b * b == left){
cout << a << ' ' << b << endl;
return 0;
}
}
}
// 因為被證明了所有除四餘一的質數都有解
// 所以不需要在最後處理沒有解的狀況！
// cout << -1 << endl;
return 0;
}
```
:::
或是有人希望可以用更有效率的方法判斷一個樹是不是完全平方數的話，請自行閱讀 [cmath 裡的 sqrt 函式](https://www.csie.ntu.edu.tw/~b98902112/cpp_and_algo/cpp02/built_in_function.html)！附上程式碼：
:::spoiler 點我看扣
```cpp=1
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int p;
cin >> p;
if(p % 4 != 1){
cout << -1 << endl;
return 0;
}
for(int a = 1; a * a < p; a++){
int left = p - a * a;
int root = sqrt(left); // 轉成 int 向下取整
if(root * root == left){
cout << a << ' ' << root << endl;
return 0;
}
}
// 因為被證明了所有除四餘一的質數都有解
// 所以不需要在最後處理沒有解的狀況！
// cout << -1 << endl;
return 0;
}
```
:::
---
---
## B 題組
### B1 至捷與他的結報惡夢
#### Subtask 1
我們先把 $a$ 排序好方便做事。
對於每個 $a_i$，都直接掃一遍看他最遠可以到哪個 $a_j (i \leq j)$，使得 $a_j - a_i \leq x$。
複雜度：$O(n^2)$
:::spoiler 點我看扣
```cpp=1
const int N = 2e5 + 225;
int n, x, a[N];
int main(){
cin >> n >> x;
// 只有一個敘述的 for 迴圈
// 可以不用大括號
for(int i = 0; i < n; ++i) cin >> a[i];
sort(a, a + n);
int ans = 0;
for(int i = 0; i < n; ++i){
for(int j = i; j < n; ++j){
// 這裡實際上的做法是看第ㄧ個超過的 j
// 這樣比較好算
if(a[j] - a[i] > x){
ans = max(ans, j - i);
break;
}
}
}
cout << ans << endl;
return 0;
}
```
:::
#### Subtask 2
觀察一下會發現，排序好之後選的數字會是一個區間 $[i, j]$，而且 $i$ 往右移動（變大）的時候， $j$ 一定不會往左（變小）！
如此這般，對於每一個 $i$ ，都把右界 $j$ 爬到最右邊的位置然後記錄答案就好了。
複雜度看起來沒變，但實際上左右界都只會爬過整個陣列一次，所以複雜度是 $O(n)$！
:::spoiler 點我看扣
```cpp=1
int main(){
// 加了下面這行輸入輸出會變快呦呦呦
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> x;
for(int i = 0; i < n; ++i) cin >> a[i];
sort(a, a + n);
int ans = 0, l = 0, r = 0;
for(; l < n; ++l){
while(r < n and a[r] - a[l] <= x) ++r;
ans = max(ans, r - l);
}
cout << ans << endl;
return 0;
}
```
:::
:::spoiler 奇恩電神奇怪解法
對每一個 $i$ 二分搜右界 $j$，這樣複雜度 $O(n \log n)$ 也不是不行啦⋯⋯
:::
---
### B2 嘉崴姐姐與他的數學作業
~~佳薇姐姐最高~~
異或（xor）有一個重要的性質是，對於任意整數 $x$， $x \oplus x = 0$ （那個怪符號是指異或）。
#### Subtask 1
$n$ 是奇數，可以讓所有數字都是 $x$，最後異或和就會兩兩抵銷剩下一個 $x$ ！既然所有數字都一樣，全距就是 `0` ！
:::spoiler 點我看扣
這是用 C 寫的，不是 C++，因為 C++ 沒辦法這麼短。
只要十八個字元就有十分，超賺的呢。
編譯記得選 C11 喔。
```c=1
main(){puts("0");}
```
:::
#### Subtask 2
$n = 1, 3$ 我們都知道怎麼做了對吧！
（筆者還想了一下 $n = 3$ 怎麼做，我弱><）
剩下 $n = 2$ 時，我們要找到兩個數$a, b$：
- $a \oplus b = 0$
- $|a - b|$ 最小
也就是說，我們要把 $x$ 中是 $1$ 的位元分成兩組，分別放在$a, b$ 裡。不難想到，把最大的那個放在其中一（WLOG 設為 $a$），剩下的全放在另一個（WLOG設為 $b$ ），這樣一定最好！（為什麽？想想看！）
至於剩下是 $0$ 的位元，在 $a, b$ 都要相同，不管是 $0$ 或是 $1$ 都不影響全距（小學數學！），所以不用考慮。
:::spoiler 點我看扣
```cpp=1
int n, x;
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> x;
// 記得判掉 x = 0 ！
if(n % 2 == 1 or x == 0){
cout << 0 << endl;
return 0;
}
// 一些些位元運算，讀者自己加油
int i;
for(i = 30; i >= 0; --i){
if(x & (1<<i)) break;
}
cout << ((1<<i) - (x - (1<<i))) << endl;
return 0;
}
```
:::
#### Subtask 3
其實只剩下一個狀況：用四個數字！
剩下多餘的數字一定可以兩兩抵銷，剩下的只要證明用四個數字一定可以達到最佳解。
首先，讓我們先考慮以下例子：
> $n = 4, x = 11001_2$
令四個數字為 $a, b, c, d$，我們可以知道，對於 $x$ 中為 $1$ 的位元， $a, b, c, d$ 一定要有奇數個是 $1$，反之亦然。WLOG 設在 $x$ 的最高位 $a, b, c$ 是一， $d$ 是零，則得到：
$$
\begin{align}
x &= 11001 \\
a &= 1\cdots \\
b &= 1\cdots \\
c &= 1\cdots \\
d &= 0\cdots \\
\end{align}
$$
我們已經知道誰可能是最大、最小了，WLOG 設 $a$ 為最大，接下來的策略就是讓 $a$ 接下來的位元盡量小、 $d$ 接下來的位元盡量大，而 $b, c$ 介在兩者間。
首先我們可以發現，若接下來的位元是 $1$，則只讓 $d$ 的那個位元是 $1$：
$$
\begin{align}
x &= 11001 \\
a &= 10\cdots \\
b &= 10\cdots \\
c &= 10\cdots \\
d &= 01\cdots \\
\end{align}
$$
但若接下來的位元是 $0$ ，則先一樣將 $d$ 設為一。
此時，$a, b, c$ 中一定要有一個人接收那一個 $1$，並且變成最大的數字，不妨假設是 $a$，則會得到：
$$
\begin{align}
x &= 11001 \\
a &= 101\cdots \\
b &= 100\cdots \\
c &= 100\cdots \\
d &= 011\cdots \\
\end{align}
$$
> 為何不乾脆不給任何人一個 $1$ 呢？
> 因為這樣在最後計算全距的時候相減會抵銷不變，
> 補起來方便最後的計算。
此時，最大值是誰已經確定了。接下來的位元只要都把 $d$ 設為$1$ ， $a$ 設為 $0$ ，並把要補成 $0$ 的位元補在 $b$ 裡即可（因為不會影響全距）。例如：
$$
\begin{align}
x &= 11001 \\
a &= 10100 \\
b &= 10010 \\
c &= 10000 \\
d &= 01111 \\
\end{align}
$$
讓我們拿出最大最小值獨立看：
$$
\begin{align}
x &= 11001 \\
a &= 10100 \\
d &= 01111 \\
\end{align}
$$
可以發現，最大值就是「 $x$ 的最高位 + $x$ 中最高位的 $0$ 那位取代為一」，最小值就是「 $x$ 的最高位以下全部補起來」。
我們將它們各加一方便計算，最小值就會變成「 $x$ 的最高位」，而相減的結果就會是「 $x$ 中最高位的 $0$ 那位取代為一 $+1$ 」！
:::spoiler 點我看扣
```cpp=1
int n, x;
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> x;
if(n % 2 == 1 or x == 0){
cout << 0 << endl;
return 0;
}
if(n == 2){
int i = 30;
for(; i >= 0; --i){
if((x>>i) & 1) break;
}
cout << (1<<i) - (x - (1<<i)) << endl;
return 0;
}
int i = 30;
bool has = false;
for(; i >= 0; --i){
if((x>>i) & 1) has = true;
else if(has) break;
}
cout << (1<<i) + 1 << endl;
return 0;
}
```
:::
---
### B3 杰楊和他的道路建設
#### Subtask 1
對於每一個點，都維護一個標籤，表示「這個點在哪一個連通塊裡面」。同一個連通塊的編號一樣就好了，不一定要排序好。
每次把兩個點連起來的時候：
* 如果兩個點在同一個連通塊中，答案不變，忽略。
* 如果兩個點不在同一個連通塊中，把其中一個所在的連通塊所有點都移到另一個連通塊中。
每次要計算答案的時候，分別計算每個連通塊中點對數即可！
複雜度：
* 合併兩個連通塊：$O(n)$
* 檢查答案：$O(n^2)$
* 總複雜度：$O(m)$ 次操作 $\times$ 每次操作 $O(n + n^2) = O(n^2m)$
:::spoiler 點我看扣
```cpp=1
const int N = 2e5 + 225;
int n, m;
int num[N];
bool vis[N];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++i) num[i] = i;
long long ans = 0;
for(int a, b; m; --m){
cin >> a >> b;
// 為什麼要把他們的編號（特別是 b）存起來？
// 想想看不存會有什麼 bug ！
int anum = num[a], bnum = num[b];
if(anum == bnum){
cout << ans << '\n';
continue;
}
// 合併兩塊
for(int i = 1; i <= n; ++i){
if(num[i] == bnum)
num[i] = anum;
}
// 對於每一塊計算答案
ans = 0;
fill(vis, vis + n, false);
for(int i = 1; i <= n; ++i){
if(!vis[i]){
long long siz = 0;
for(int j = i; j <= n; ++j){
if(num[j] == num[i]){
++siz;
vis[j] = true;
}
}
ans += siz * (siz - 1) / 2;
}
}
// 多筆輸出的時候， endl 會太慢
// 平常就習慣用 '\n' 也好
// 也可以 #define endl '\n' 喔
cout << ans << '\n';
}
return 0;
}
```
:::
#### Subtask 2
可以發現，每次操作只會動到頂多兩塊嘛！只算這兩塊的答案呢？
每次的答案變成對原本的答案加上「新連通塊的答案 - 原本兩塊連通塊的答案」，這樣就會更快了！
複雜度：修改 $O(n) \times O(m)$ 次操作 $= O(nm)$
:::spoiler 點我看扣
```cpp=1
const int N = 2e5 + 225;
int n, m;
int num[N];
bool vis[N];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++i) num[i] = i;
long long ans = 0;
for(int a, b; m; --m){
cin >> a >> b;
int anum = num[a], bnum = num[b];
if(anum == bnum){
cout << ans << '\n';
continue;
}
// 計算答案
long long asiz = 0, bsiz = 0;
for(int i = 1; i <= n; ++i){
if(num[i] == anum) ++asiz;
if(num[i] == bnum) ++bsiz;
}
ans += (asiz + bsiz) * (asiz + bsiz - 1) / 2 - asiz * (asiz - 1) / 2 - bsiz * (bsiz - 1) / 2;
// 合併
for(int i = 1; i <= n; ++i){
if(num[i] == bnum)
num[i] = anum;
}
cout << ans << '\n';
}
return 0;
}
```
:::
#### Subtask 3
「如果我們可以好好維護連通塊並且用 $O(\alpha (1))$ 合併」的想法，就用並查集解決！
不會的話可以去看 [這個](https://slides.com/jass921026/deck-824fe5#/5)！我懶了解釋了。
核心想法跟剛才一樣，只是用了一些技巧讓合併、查詢變成常數！
複雜度：修改 $O(\alpha(1)) \times O(m)$ 次操作，其中 $\alpha(1)$ 差不多就是常數，所以總複雜度 $\approx O(m)$！
:::spoiler 點我看扣
```cpp=1
const int N = 2e5 + 225;
int n, m;
long long ans;
int dsu[N], siz[N];
inline int Find(int a){ return a == dsu[a] ? a : dsu[a] = Find(dsu[a]);}
inline void Union(int a, int b){
if(Find(a) == Find(b)) return;
// 合併時順便紀錄答案
a = Find(a), b = Find(b);
long long asiz = siz[a], bsiz = siz[b];
ans -= asiz * (asiz - 1) / 2;
ans -= bsiz * (bsiz - 1) / 2;
ans += (asiz + bsiz) * (asiz + bsiz - 1) / 2;
siz[a] += siz[b];
siz[b] = 0;
dsu[b] = a;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++i) dsu[i] = i, siz[i] = 1;
for(int a, b; m; --m){
cin >> a >> b;
Union(a, b);
cout << ans << '\n';
}
return 0;
}
```
:::
---
### B4 社長的機器人遊戲
#### Subtask 1
我們先找到金幣所在的左右界，再看機器人在不在這個區間裡。
* 如果不在，就直接掃過去；
* 如果在，看看先往左還是先往右比較好。
複雜度：$O(n)$
:::spoiler 點我看扣
```cpp=1
const int N = 2e5 + 225;
int n;
char s[N];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> s;
int l, r;
for(int i = 0; i < n; ++i){
if(s[i] == '*'){
l = i;
break;
}
}
for(int i = n - 1; i >= 0; --i){
if(s[i] == '*'){
r = i;
break;
}
}
int robot;
for(int i = 0; i < n; ++i){
if(s[i] == 'R'){
robot = i;
break;
}
}
if(robot < l) cout << r - robot << endl;
else if(robot > r) cout << robot - l << endl;
else cout << min(robot - l + r - l, r - robot + r - l) << endl;
return 0;
}
```
:::
#### Subtask 2
出好玩的，跳過。
#### Subtask 3
想法要轉換一下：因為找答案很難，所以我們對答案二分搜！
那要怎麼檢驗一個時間 $t$ 可不可以達成呢？
觀察一下可以發現，一個金幣一定是被「左邊最靠近他的」或是「右邊最靠近他的」撿起來（因為兩個機器人錯身而過等價於碰到後反向而行），所以我們只要好好維護每一個機器人拿的左右界，並從左往右掃，在加入一個金幣時看看左邊的機器人有沒有辦法在時間 $t$ 內拿走，不行的話就看看右邊，好好做過去即可！
複雜度： $O(n \log n)$
:::spoiler 點我看扣
```cpp=1
const int N = 2e5 + 225;
int n;
char s[N];
// 對於金幣，左邊的機器人跟右邊的機器人
int lr[N], rr[N];
// 對於機器人，他要拿的金幣左界右界
int L[N], R[N];
bool check(int t){
// 記得好好初始化
for(int i = 1; i <= n; ++i){
if(s[i] == 'R') L[i] = R[i] = i;
}
for(int i = 1; i <= n; ++i){
if(s[i] != '*') continue;
// 如果這枚金幣已經會被順路拿走
if(rr[i] and L[rr[i]] <= i) continue;
// 左邊的機器人可以在合理時間內拿走它
if(lr[i] and min(
(lr[i] - L[lr[i]]) + (i - L[lr[i]]),
(i - lr[i]) + (i - L[lr[i]])
) <= t){
R[lr[i]] = i;
continue;
}
// 如果左邊不能拿右邊也不能拿
if(!rr[i] or rr[i] - i > t) return false;
// 給右邊的拿
L[rr[i]] = i;
}
return true;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> s + 1;
// 預處理
int cur = 0;
for(int i = 1; i <= n; ++i){
if(s[i] == 'R') cur = i;
if(s[i] == '*') lr[i] = cur;
}
cur = 0;
for(int i = n; i >= 1; --i){
if(s[i] == 'R') cur = i;
if(s[i] == '*') rr[i] = cur;
}
int l = 0, r = N * 2, m;
while(l < r){
m = (l + r) / 2;
if(check(m)) r = m;
else l = m + 1;
}
cout << l << endl;
return 0;
}
```
:::
---
---
## C 題組
### C1 8e7 和會讓他心痛的成發作品
#### Subtask 1
$O(n^2)$ DP！ $dp_i$ 代表最後接第 $i$ 個軟軟過程中能接到的軟軟數，好好轉移即可：
$$
dp_i = \max_{t_i - t_j \geq | x_i - x_j |}{dp_j + 1}
$$
實作時可以放入一個點 $(0, 0)$ 方便轉移，也記得要先把 $dp_i$ 設成 `INF` 喔。
:::spoiler 點我看扣
`FHVirus` 把這題寫的又短又噁，原因是因為上面三行怪東東都在模板裡了。 `STL` 真好用。
```cpp=1
#define FOR(i,n) for(int i = 0; i < n; ++i)
#define FOO(i,a,b) for(int i = a; i <= b; ++i)
void chmax(int &a, int b){ if(a < b) a = b;}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n; cin >> n;
vector<pii> a(n);
for_each(AI(a), [](pii &p){ cin >> p.ss >> p.ff;}); a.pb(0, 0); sort(AI(a));
vector<int> dp(n + 1, -2147483647); dp[0] = 0;
FOO(i,1,n) FOR(j,i) if(abs(a[i].ss - a[j].ss) <= a[i].ff - a[j].ff) chmax(dp[i], dp[j] + 1);
cout << *max_element(AI(dp)) << endl;
return 0;
}
```
:::
#### Subtask 2
讓我們來展開式子吧！
$$
t_i - t_j \geq |x_i - x_j| \\
\Rightarrow
\begin{cases}
t_i - t_j \geq x_i - x_j \\
t_i - t_j \geq x_j - x_i
\end{cases} \\
\Rightarrow
\begin{cases}
t_i - x_i \geq t_j - x_j \\
t_i + x_i \geq t_j + x_j
\end{cases} \\
$$
這時候我們把每一個點做座標的轉換，轉換到一個二維平面上，座標為 $a_i(t_i - x_i, t_i + x_i)$，可以發現問題就被轉換成：以 $(0, 0)$ 為開頭的不嚴格遞增 LIS 最長是多少？
做法也很簡單：把 $x < 0$ 的點拔掉好好做就好了！
:::spoiler 點我看扣
```cpp=1
const int N = 5e5 + 225;
int n;
int x[N], y[N], id[N];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n;
for(int i = 0; i < n; ++i){
int a, b; cin >> a >> b;
x[i] = b - a; y[i] = b + a;
id[i] = i;
}
// 丟入起始點方便轉移
x[n] = 0, y[n] = 0, id[n] = n; n++;
// 非嚴格遞增 LIS 的做法不太一樣喔
sort(id, id + n, [](int a, int b){
return x[a] != x[b] ? x[a] < x[b] : y[a] < y[b];
});
vector<int> lis;
for(int i = 0; i < n; ++i){
if(x[id[i]] < 0) continue;
if(lis.empty() or lis.back() <= y[id[i]]) lis.pb(y[id[i]]);
else *(upper_bound(AI(lis), y[id[i]])) = y[id[i]];
}
// 記得扣掉起始點！
cout << lis.size() - 1 << endl;
return 0;
}
```
:::
---
### C2 朝鴻與聖誕樹
待補。
---
### C3 思維與他的打怪人生
#### Subtask 1
直接枚舉從哪邊進去！
:::spoiler 點我看扣
```cpp=1
const int N = 1e5 + 225;
int n, x, a[N];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> x;
for(int i = 0; i < n; ++i) cin >> a[i];
for(int i = 0; i < n; ++i){
if(x <= a[i]){
cout << '0';
continue;
}
long long cur = x + a[i];
int l = i, r = i;
while((l > 0 and a[l-1] < cur) or (r < n-1 and a[r+1] < cur)){
if(l > 0 and a[l-1] < cur) cur += a[--l];
if(r < n-1 and a[r+1] < cur) cur += a[++r];
}
// 這語法快學！
cout << "01"[l == 0 and r == n-1];
}
return 0;
}
```
:::
#### Subtask 2 (Solution by `8e7`)
解一（by `8e7`）：好像叫二的冪次分層（？
- 觀察一：假設一開始的血量為 $x$ ，在位置 $i$ 開始，而他左邊的怪物全部血量都比 $x$ 小，也就是 $\forall left \leq j \leq i, \ a_j < x$ ，那麼我一定能打敗 $[left, i]$ 的所有怪物，對於右邊的怪物也是同樣的情況。
- 觀察二：假設有一個 $a_i = y \geq x$，則當我打敗 $a_i$ 時，新的血量會 $\geq 2x$ 。
結合這兩個做法，對於每一個起始位置 $i$ ，我用一個迴圈維護能打到的左右界 $[l, r]$ 使得 $\ l \leq i, r \geq i, \ \ a_{l - 1}, a_{r+1} \geq x, \forall l \leq j \leq r, a_j < x$ 。然後用前綴計算出打完這些怪物後的血量 $\ x + \sum a[l...r]$ 。接著判斷他能不能打敗左右界的怪物，能打敗左界就 `l--` ，打敗右界就把 `r++` ，這樣子一直做。當 $[l, r]$ 涵蓋整個區間時或左右界都無法打敗時，你就知道這個位置的答案了。
具體應該怎麼寫呢？對於每個 $a_i$ 我把他依照 $a_i / x$ 來分層。令 $v[p]$ 為第 $p$層不一定能打敗的怪物的序列。如果 $2^{p - 1} \leq a_i / x < 2^p$ 的話（ $p = 0, 0 \leq a_i /x < 1$），就把 $i$ 這個位置加到 $[0, p]$ 這些地方。查詢時維護目前打了幾次 $cnt$，當我把原本打不了的怪物打敗時 `cnt += 1`，以此類推。
因為這個迴圈只會跑 $O(logC)$ 次，而每次用lower_bound求出左右界，因此時間複雜度 $O(n\log n\log C)$ ，空間複雜度 $O(n \log C)$ 。
:::spoiler 點我看扣
```cpp=1
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#define maxn 100005
#define ll long long
using namespace std;
ll a[maxn], pref[maxn];
vector<int> layer[31];
bool poss[maxn];
inline int hbit(int a) {
int ret = 0;
while (a) {
a >>= 1;
//cout << 1 << endl;
ret++;
}
return ret;
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
ll n, x;
cin >> n >> x;
for (int i = 0;i < 31;i++) layer[i].push_back(-1);
for (int i = 0;i < n;i++) {
cin >> a[i];
pref[i] = a[i] + (i ? pref[i - 1] : 0);
int pos = hbit(a[i] / x);
for (int j = 1;j <= pos;j++)layer[j].push_back(i);
poss[i] = pos == 0;
}
for (int i = 0;i < 31;i++) layer[i].push_back(n);
for (int i = 0;i < n;i++) {
if (poss[i]) {
int lef = i, rig = i, cur = 1, ans = 0;
while (rig - lef + 1 < n) {
int ind = lower_bound(layer[cur].begin(), layer[cur].end(), i) - layer[cur].begin();
rig = layer[cur][ind] - 1, lef = layer[cur][ind - 1] + 1;
if (rig - lef + 1 == n) {
ans = 1;
break;
} else {
ll lw = (lef > 0 ? a[lef - 1] : 1LL<<60), rw = (rig < n - 1 ? a[rig + 1] : 1LL<<60);
ll val = x + pref[rig] - (lef ? pref[lef - 1] : 0);
//cout << i << " " << lef << " " << rig << " " << val << endl;
if (val > lw) {
lef--;
cur++;
} else if (val > rw) {
rig++;
cur++;
} else {
ans = 0;
break;
}
}
}
if (rig - lef + 1 == n) ans = 1;
cout << ans;
} else {
cout << 0;
}
}
cout << endl;
}
```
:::
註：本題靈感
---
### C4 均豪與他的燒雞之旅
待補。
---
### C5 FHVirus與他成為Top-Topcoder 的傳奇故事 (by `8e7`)
> 被出成題目了好害羞><
> 題序除了最後一題是 TIOJ 1080 之外都是真的><
#### Subtask 1
直接開一個$10^6$的背包紀錄哪些數字走得到，然後做前綴之後就可以回答了。
#### Subtask 2
其實我不知道這個$subtask$有沒有特定做法。原本想說開最小公因數那麼大的bitset硬做？但是感覺常數會炸。
#### Subtask 3
https://oi-wiki.org/graph/mod-shortest-path/
大致的想法是，對於任意一個 $a_i$，如果 $x$ 是可背包的，那麼 $x + na_i$一定可背包。
以下會將「所有時間的最小值」表示為 $x$。
因此，我可以對每一個 $k \ mod \ x$ ，找到最小的值 $d_i$ 使得 $d_i \equiv k (mod \ x)$ 且 $d_i$是可背包的。而每個 $d_i$ 可以透過最短路演算法找到，詳細請見網址。
把 $[l, r]$ 拆成 $[0, r] - [0, l-1]$ 。對於一個數字 $h$ ，在 $[0, h - 1]$ 中可背包的數字為 $\sum_{i = 0}^{x - 1} \lceil{\frac{x}{h - d_i}}\rceil$ 。因此把每個問題暴力回答就好，複雜度 $O(x^2\log x + qx)$ 。
#### Subtask 4
一樣的做法，再加上各種優化。
把 $Dijkstra$ 換成 $O(V^2)$ 的版本。
對於每個詢問，離線處理 $h\mod x$ 的結果，然後對每一個 $i\mod x$ 做前綴求解。複雜度 $O(x^2 + q \log x)$。
記得加上 `FHVirus` 輸入輸出喔！
:::spoiler 點我看扣
這題程式碼是由 `8e7` 提供， `FHVirus` 鴨腸。
```cpp=1
// Knapsack DP is harder than FFT.
#pragma GCC optimize("Ofast")
#include<unistd.h>
const int BUF_SIZE = 2e5 + 225;
char OB[BUF_SIZE]; int OP;
inline char RC(){static char buf[BUF_SIZE],*p=buf,*q=buf;return p==q&&(q=(p=buf)+read(0,buf,BUF_SIZE))==buf?-1:*p++;}
inline int R(){static char c;int a;while((c=RC())<'0');a=c^'0';while((c=RC())>='0')a*=10,a+=c^'0';return a;}
inline long long RL(){static char c;long long a;while((c=RC())<'0');a=c^'0';while((c=RC())>='0')a*=10,a+=c^'0';return a;}
inline void W(long long n){static char buf[20],p;if(n==0)OB[OP++]='0';p=0;while(n)buf[p++]='0'+(n%10),n/=10;for(--p;p>=0;--p)OB[OP++]=buf[p];OB[OP++]='\n';if(OP>BUF_SIZE-20)write(1,OB,OP),OP=0;}
#include <algorithm>
#include <vector>
#include <queue>
#define ll long long
#define pii pair<int, ll>
#define ff first
#define ss second
#define maxn 500005
#define jizz 7122 + 1
#define mod 1000000007
using namespace std;
const ll inf = 1LL<<60;
ll a[jizz];
bool done[jizz];
ll edge[jizz], mind[jizz], pref[jizz], ans[maxn];
vector<pii> que[jizz];
int x;
int main() {
int n, m;
n = R(), m = R();
for(int i = 0; i < n; ++i) a[i] = R();
sort(a, a + n);
x = a[0];
for(int i = 0; i < x; ++i) edge[i] = inf, mind[i] = inf;
for(int i = 0; i < n; ++i){
edge[a[i] % x] = min(edge[a[i] % x], a[i]);
}
ll b;
for(int i = 0; i < m; ++i){
b = R();
edge[b % x] = min(edge[b % x], b);
}
//for (int i = 0;i < x;i++) cout << edge[i] << endl;
mind[0] = 0;
for (int i = 0;i < x;i++) {
ll mi = inf, ind = 0;
for (int j = 0;j < x;j++) {
if (!done[j] && mind[j] < mi) {
mi = mind[j];
ind = j;
}
}
done[ind] = true;
for (int j = 0;j < x;j++){
mind[j] = min(
mind[j],
mind[ind] + edge[j - ind < 0 ? j - ind + x : j - ind]
);
}
}
sort(mind, mind + x);
//for (int i = 0;i < x;i++) cout << mind[i] << endl;
int q = R();
ll l, r;
for (int i = 1;i <= q;i++) {
l = RL(); r = RL() + 1;
que[r % x].emplace_back( i, r);
que[l % x].emplace_back(-i, l);
}
for (int i = 0;i < x;i++) {
for (int j = 0;j < x;j++) {
pref[j] = (j ? pref[j - 1] : 0) + (i - mind[j] < 0 ? (i - mind[j]) / x : (i - mind[j] + x - 1) / x);
//cout << pref[j] << " ";
}
//cout << endl;
for (pii j: que[i]) {
int ind = lower_bound(mind, mind + x, j.ss) - mind;
//cout << j.ff << " " << ind << endl;
if (j.ff > 0) {
ans[j.ff] += ind * (j.ss / x) + (ind ? pref[ind - 1] : 0);
//cout << j.ff << " " << ind << " " << ind * (j.ss / x) + (ind ? pref[ind - 1] : 0) << endl;
} else {
ans[-j.ff] -= ind * (j.ss / x) + (ind ? pref[ind - 1] : 0);
}
}
}
for (int i = 1;i <= q;i++) W(ans[i]);
write(1, OB, OP);
}
```
:::
Sign in with Wallet
Connect another wallet