---
tags: 成大高階競技程式設計 2021
image: https://i.imgur.com/IIj9BcL.png
---
# 2021 高階競程 Contest #5 - 題解
## [forbid patrn](https://judge.csie.ncku.edu.tw/problems/109)
- Task Provider: GY
- Task Setter: ys
### 首殺 team21_32 (00:06)
### 解法說明
觀察到 $n = 3$ 的情況
- `100`
- `110`
- `111`
- `000`
這幾種字串不管向右 shift 幾次，都會是合法的字串
前 $2$ 種都能靠 shift 得到 $3$ 個不重複的字串，所以共有 $2 \times 3 + 2 = 8$ 個字串
> 其中向右 shift 一次表示最右邊的字元移到最左邊
再觀察到 $n = 4$ 的情況
- `1000`
- `1100`
- `1110`
- `1111`
- `0000`
這幾種字串不管向右 shift 幾次，都會是合法的字串
前 $3$ 種都能靠 shift 得到 $4$ 個不重複的字串，所以共有 $3 \times 4 + 2 = 14$ 個字串
依此類推不管 $n$ 為多少，總共會有 $(n-1)\cdot n +2$ 個字串
### 標準程式
:::spoiler
```cpp
#include<cstdio>
using namespace std;
long long n;
int main()
{
scanf("%lld", &n);
printf("%lld\n", n*(n-1)+2);
return 0;
}
```
:::
## [交友遊戲](https://judge.csie.ncku.edu.tw/problems/110)
- Task Provider: D4nnyLee
- Task Setter: D4nnyLee
### 首殺 team21_21 (00:41)
### 解法說明
因為每送一封信，寄件人跟收件人都會收到 $1$ 塊錢，因此每個人收到的錢的總數一定是偶數。
所以如果每個人的目標金額加起來是奇數的話就可以直接輸出 $-1$。
要注意到題目中沒有限制寄件人跟收件人一定要是不同人，
因此可以自己寄給自己，並且得到 $2$ 塊錢。
所以只要總和為偶數，我們就可以依序用以下的步驟達成目標：
1. 找出所有目標金額為奇數的人，將他們兩兩配成一對，並且讓其中一人寄信給另一人
2. 所有人都自己寄信給自己，直到達到目標金額
在步驟 $1$ 中，因為總和為偶數，所以目標金額為奇數的人一定有偶數個，也就代表奇數的人一定可以找到其他人跟他配。
### 標準程式
:::spoiler
```cpp
#include <iostream>
#include <vector>
#include <array>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> c(n);
for (auto &ci : c)
cin >> ci;
array<vector<int>, 2> arr{};
for (int i = 0; i < n; ++i)
arr[c[i] & 1].push_back(i);
if (arr[1].size() % 2) {
cout << "-1\n";
return 0;
}
vector<pair<int, int>> ans;
for (int i{1}, len = arr[1].size(); i < len; i += 2)
ans.emplace_back(arr[1][i - 1], arr[1][i]);
for (int i{0}; i < n; ++i) {
while (c[i] > 1) {
ans.emplace_back(i, i);
c[i] -= 2;
}
}
cout << ans.size() << '\n';
for (auto [u, v] : ans)
cout << u + 1 << ' ' << v + 1 << '\n';
return 0;
}
```
:::
## [超時空回歸](https://judge.csie.ncku.edu.tw/problems/111)
- Task Provider: arashi87
- Task Setter: arashi87
### 首殺 team21_12 (01:28)
### 解法說明
這題是很裸的拓墣排序，唯一變化的只有需要套上優先隊列來獲取最小的編號 (不過因為 $N$ 很小，也有人暴搜 AC)。每筆輸入都會給定 $D1$ 和 $D2$，所以可以知道 $D2$ 前面至少還有一個編號，因此 $D2$ 入度加一，接者把 $M$ 筆操作都這樣做一遍就可以得到一個所有點的入度陣列。
有了入度陣列後就可以很容易地知道入度為 $0$ 的點可以隨意排列，唯一需要遵循的只有按照大小排序而已，接著排序完所有入度為 $0$ 的點後需要將所有與之相連的點的入度也都減一 (相當於 $D1$ 已經確定位置了，所以 $D2$ 可以少顧慮一個點)，所以前面輸入時也需要維護一個陣列用來確認哪些點相連，接著只需要重複上述步驟直到所有點排序完畢。
需要注意的是有很多人想試著用權重加 sort 通過，不過這是行不通的，在兩個點入度相等的時候他們還是會有先後順序，一定會有其中一個點的入度先拔完，所以行不通。
### 標準程式
:::spoiler
```cpp
#include <queue>
#include <stdio.h>
#include <string.h>
#define maxN 507
using namespace std;
int n, m;
int mp[maxN][maxN], in[maxN];
priority_queue<int, vector<int>, greater<int>> pq;
int main()
{
while (~scanf("%d%d", &n, &m)) {
memset(mp, 0, sizeof mp);
memset(in, 0, sizeof in);
for (int i = 1, x, y; i <= m; i++)
scanf("%d%d", &x, &y), mp[x][y] = 1, in[y]++;
for (int i = 1; i <= n; i++)
if (!in[i])
pq.push(i);
while (!pq.empty()) {
int tp = pq.top();
pq.pop();
printf("%d ", tp);
for (int i = 1; i <= n; i++) {
if (mp[tp][i]) {
in[i]--;
if (!in[i])
pq.push(i);
}
}
}
puts("");
}
}
```
:::
## [眼神殺 - 羔羊](https://judge.csie.ncku.edu.tw/problems/112)
- Task Provider: HDU 5115
- Task Setter: raiso
### 首殺 -- (-:-)
### 解法說明
本題目的為尋找最佳決策，使用的策略為「枚舉最後一次決策」。
在區間 $[0, n-1]$ 的口試委員中，誰最後走傷害最小？在區間 的口試委員中，誰最後走傷害最小？
這就是一種 Top-Down 的思路，這樣我們需要做的就是「記憶化搜索」，避免重複計算。
在一個區間中，走的人可能有三種「最左、中間與最右」，轉移式：
將`dfs(L, R)` 定義成：當區間 $[L,R]$ 都離開後，受到的最小傷害值。
枚舉這個區間中最後一個走的人是誰就好了。
```
ans = min(ans, dfs(L+1, R)+A[L]);
ans = min(ans, dfs(L, R-1)+A[R]);
for(int i = L+1; i < R; i++) //"i" is the last one leaving.
ans = min(ans, dfs(L, i-1)+dfs(i+1, R)+A[i]);
```
### 標準程式
:::spoiler
```cpp
#include <bits/stdc++.h>
#define Int long long
using namespace std;
vector<Int> A, B;
int n;
vector< vector< Int > > his;
vector< vector< bool > > vis;
Int dfs(int L, int R) { //[L, R] leaving
if(vis[L][R] == 1) return his[L][R];
vis[L][R] = 1;
Int ans = LLONG_MAX;
//w=1
if(L == R) ans = A[L];
//w>1
if(L+1 <= R) ans = min(ans, dfs(L+1, R)+A[L]);
if(L <= R-1) ans = min(ans, dfs(L, R-1)+A[R]);
for(int i = L+1; i < R; i++) //"i" is the last one leaving.
ans = min(ans, dfs(L, i-1)+dfs(i+1, R)+A[i]);
//eye-damage
if(L-1 >= 0) ans += B[L-1];
if(R+1 < n) ans += B[R+1];
return his[L][R] = ans;
}
int main() {
cin >> n;
A.resize(n);
B.resize(n);
his.assign(n, vector<Int>(n));
vis.assign(n, vector<bool>(n, 0));
for(auto& it: A) cin >> it;
for(auto& it: B) cin >> it;
Int ans = dfs(0, n-1);
cout << ans << endl;
return 0;
}
```
:::
## [壞掉的電腦](https://judge.csie.ncku.edu.tw/problems/113)
- Task Provider: baluteshih
- Task Setter: leo
### 首殺 team21_34 (02:22)
### 解法說明
你可以透過對所有電腦查詢某台電腦是否為壞掉的，
例如標準程式中詢問所有人 $1$ 號是否為壞掉的，
如果是壞掉的話就可以直接輸出答案，
否則就可以對所有電腦二分搜，
並利用該電腦（即上面的 $1$ 號）來驗證區間是否存在壞掉的電腦，
因為題目保證會有壞掉的電腦，所以如果 $[l,m]$ 不存在壞掉的電腦，
則 $[m+1,r]$ 一定有壞掉的電腦，即可找出答案
### 標準程式
:::spoiler
```cpp
#include "lib0113.h"
int main() {
int n, l, r, m, cnt = 0;
n = Init();
for(int i = 1; i <= n; i++)
cnt += (Query(i, 1, 1) ? 1 : -1);
if(cnt > 0)
Fix(1);
for(l = 1, r = n; l < r;){
m = l + r >> 1;
if(Query(1, l, m))
r = m;
else
l = m + 1;
}
Fix(l);
}
```
:::
## [推甄季](https://judge.csie.ncku.edu.tw/problems/114)
- Task Provider: XDEv11
- Task Setter: ys
### 首殺 -- (-:-)
### 解法說明
我們可以把每個研究所的面試開始與結束時間當成二個事件，並用時間軸的方式儲存。
之後在每天的開始前，我們就將那天會開始開放面試的研究所加入；
在每天結束後，將那天結束開放面試的研究所移除；
並在每天的開放時段，去尋找可以面試並擁有前 $K$ 大炫耀資本的研究所。
而研究所若是以炫耀資本為觀點儲存，
在每次加入時，只要找到目前炫耀資本第 $K$ 大的研究所，並檢查是否需要替換；
而在每次移除時，則要找到目前炫耀資本第 $K+1$ 大的研究所，檢查是否補上；
這部分就是在 Range Query 時講過的 [K-th one](https://hackmd.io/@XDEv11/NCKU-AdvCP-2021-Range_Query#%E7%AC%AC-k-%E5%80%8B-1%EF%BC%88K-th-one%EF%BC%89)。
> 若移除的研究所炫耀資本為前 $K$ 大，它的炫耀資本應當比第 $K+1$ 大的研究所還大，
> 在移除後則由第 $K+1$ 大的研究所補上。
### 標準程式
:::spoiler
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class SGT {
int n;
vector<long long> t;
int left(int tv) { return tv + 1; }
int right(int tv, int tl, int tm) { return tv + 2 * (tm - tl); }
void modify(int p, long long x, int tv, int tl, int tr) {
if (tl == tr - 1) t[tv] += x;
else {
int tm{(tl + tr) / 2};
if (p < tm) modify(p, x, left(tv), tl, tm);
else modify(p, x, right(tv, tl, tm), tm, tr);
t[tv] = t[left(tv)] + t[right(tv, tl, tm)];
}
}
long long query(int l, int r, int tv, int tl, int tr) {
if (l == tl && r == tr) return t[tv];
int tm{(tl + tr) / 2};
if (r <= tm) return query(l, r, left(tv), tl, tm);
else if (l >= tm) return query(l, r, right(tv, tl, tm), tm, tr);
else return query(l, tm, left(tv), tl, tm) + query(tm, r, right(tv, tl, tm), tm, tr);
}
public:
explicit SGT(int _n) : n{_n}, t(2 * n - 1) {}
void modify(int p, long long x) { modify(p, x, 0, 0, n); };
long long query(int l, int r) { return query(l, r, 0, 0, n); }
int ps_lower_bound(long long ps) { /* binary search on tree */
if (ps > t[0]) return -1;
int tv{0}, tl{0}, tr{n};
while (tr - tl > 1) {
int tm{(tl + tr) / 2};
if (t[right(tv, tl, tm)] >= ps) tv = right(tv, tl, tm), tl = tm;
else ps -= t[right(tv, tl, tm)], tv = left(tv), tr = tm;
}
return tl;
}
};
void solve() {
int D, N, K;
cin >> D >> N >> K;
vector<vector<int>> vb(D), ve(D);
for (int i{0}; i < N; ++i) {
int c, b, e;
cin >> c >> b >> e, --b, --e;
vb[b].push_back(c);
ve[e].push_back(c);
}
SGT sgt{300001};
long long ans{0}, cnt{0};
for (int i{0}; i < D; ++i) {
for (auto& x : vb[i]) {
int kth{sgt.ps_lower_bound(K)};
if (x > kth) {
if (kth != -1) cnt -= kth;
cnt += x;
}
sgt.modify(x, 1);
}
ans = max(ans, cnt);
for (auto& x : ve[i]) {
int kth{sgt.ps_lower_bound(K + 1)};
if (x > kth) {
cnt -= x;
if (kth != -1) cnt += kth;
}
sgt.modify(x, -1);
}
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t{1};
//cin >> t;
while (t--) solve();
return 0;
}
```
:::
## 國軍弟兄們，上戰場囉！[Easy](https://judge.csie.ncku.edu.tw/problems/115), [Hard](https://judge.csie.ncku.edu.tw/problems/116)
- Task Provider: ICPC Taipei 2020 E
- Task Setter: raiso
### Easy 首殺 audit21_05 (02:55)
### Hard 首殺 -- (-:-)
### 解法說明
我們先從最後兩步驟看這個問題，如：`AAABBBA`，我們可以將這些弟兄看成三段$L(1,2,3),M(4,5,6),R(7)$，在這次的案例中，若要可以成功派出這些弟兄，$M$為可派出，$L$與$R$合併後可派出。
在一般化問題後，我們可以將問題換成，若區段$S$可派出，可能可以全派出，或是其中一段派出後，剩餘可派出，此段可能在$S$靠左、靠右或是都不靠。
`xxxxxxxxx`
`xxxx.....`
`...xxx...`
`.....xxxx`
:::spoiler
```cpp
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
string S;
int X;
bool sand(string S) {
for(auto it: S) if(it != S.back()) return 0;
if(S.size() < X) return 0;
return 1;
}
bool dfs(string S) {
//1 part
if(sand(S)) return 1;
bool isok = 0;
int n = S.size();
//2 part
for(int i = 1; !isok && i < n; i++) {
//LL->[0, i-1], RR->[i, n-1]
string LL = S.substr(0, i);
string RR = S.substr(i, n-i);
if(!isok && sand(LL) && dfs(RR)) isok = 1;
if(!isok && dfs(LL) && sand(RR)) isok = 1;
}
//3 part
for(int i = 1; !isok && i < n; i++) for(int j = i+1; !isok && j < n; j++) {
//LL->[0, i-1], MM->[i, j-1], RR->[j, n-1]
string LL = S.substr(0, i);
string MM = S.substr(i, j-i);
string RR = S.substr(j, n-j);
if(!isok && sand(MM) && dfs(string(LL+RR))) isok = 1;
}
return isok;
}
int main() {
cin >> S >> X;
bool isok = dfs(S);
cout << (isok? "Yes": "No") << endl;
}
```
:::
(未完待續，之後再詳細的解釋)
### 標準程式
:::spoiler
```cpp
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second
using namespace std;
string S;
int X, n;
int main() {
cin >> S >> X, n = S.size();
vector< pair<char, int> > A{mp(S[0], 0)};
for(auto it: S) {
if(it == A.back().x) A.back().y++;
else A.pb(mp(it, 1));
}
n = A.size();
vector< vector<int> > dp(n, vector<int>(n, INT_MIN));
//w=1
for(int i = 0; i < n; i++) dp[i][i] = A[i].y;
//w=2
for(int i = 0; i < n-1; i++) {
if(A[i].x == A[i+1].x) dp[i][i+1] = dp[i][i] + dp[i+1][i+1];
else if(dp[i+1][i+1] >= X) dp[i][i+1] = dp[i][i];
}
//w>2
for(int w = 3; w <= n; w++) for(int L = 0; L < n-w+1; L++) {
int R = L+w-1;
auto& now = dp[L][R];
//2 part
for(int i = L+1; i <= R; i++) if(dp[L][i-1] > 0 && dp[i][R] > 0){
//[L, i-1], [i, R]
if(A[L].x == A[i].x) now = max(now, dp[L][i-1] + dp[i][R]);
else if(dp[i][R] >= X) now = max(now, dp[L][i-1]);
}
//3 part
for(int i = L+2; i <= R; i++) if(A[L].x == A[i].x && dp[L+1][i-1] >= X && dp[i][R] > 0) {
//[L, L], [L+1, i-1], [i, R]
now = max(now, dp[L][L]+dp[i][R]);
}
}
cout << (dp[0][n-1] >= X? "Yes": "No") << endl;
return 0;
}
```
:::
Sign in with Wallet
Connect another wallet