---
tags: 成大高階競技程式設計 2021
image: https://i.imgur.com/IIj9BcL.png
---
# 2021 高階競技程式設計課前賽 - 題解
## [政大的女朋友](https://judge.csie.ncku.edu.tw/problems/79)
- Task Provider: smallbird
- Task Setter: leo
### 首殺 pmcat (00:03)
### 解法說明
#### 解法 $1$
因為 `+` 加上 `+` 會變成 `-`，而 `-` 的絕對值很小，代表影響很小，
因此只要 `+` 的數量是奇數的話，算出來的答案就會是正數，反之亦然，
所以只要計算 `+` 的數量就可以知道答案了。
#### 解法 $2$
我們無法從輸入得知 `-` 到底是 $-1$, $-2$ 還是 $-3$，
`+` 也是一樣情況，所以不管是哪一種，答案都應該相同，
因此我們可以把 `+` 當作 $2^{31}-1$，把 `-` 當作 $-1$，
直接做計算，不過在 C++ 中，有號數溢位是 [Undefined Behavior](https://en.wikipedia.org/wiki/Undefined_behavior)，
因此需先轉為無號數進行二進制加法，再將結果轉為有號數。
> Unsigned integer arithmetic is always performed modulo $2^n$ where $n$ is the number of bits in that particular integer.
> When signed integer arithmetic operation overflows (the result does not fit in the result type), the behavior is undefined.[$^{[Arithmetic\ operators]}$](https://en.cppreference.com/w/cpp/language/operator_arithmetic)
而無號數加有號數，有號數會被隱性轉型為無號數。
> If the unsigned operand's conversion rank is greater or equal to the conversion rank of the signed operand, the signed operand is converted to the unsigned operand's type.[$^{[usual\ arithmetic\ conversions]}$](https://en.cppreference.com/w/cpp/language/operator_arithmetic#Conversions)
### 標準程式
#### 解法 $1$
:::spoiler
```cpp!
#include <iostream>
using namespace std;
int main() {
int cnt = 0;
char a, b, c;
cin >> a >> b >> c;
if (a == '+') ++cnt;
if (b == '+') ++cnt;
if (c == '+') ++cnt;
if (cnt == 1 || cnt == 3) cout << "yes\n";
else cout << "no\n";
}
```
:::
#### 解法 $2$
:::spoiler
```cpp!
#include <iostream>
using namespace std;
int main() {
unsigned res = 0;
char a, b, c;
cin >> a >> b >> c;
if (a == '+') res += 2147483647;
else res += -1;
if (b == '+') res += 2147483647;
else res += -1;
if (c == '+') res += 2147483647;
else res += -1;
if (int(res) > 0) cout << "yes\n";
else cout << "no\n";
}
```
:::
## [整理房間](https://judge.csie.ncku.edu.tw/problems/80)
- Task Provider: D4nnyLee
- Task Setter: D4nnyLee
### 首殺 anderson425 (00:04)
### 解法說明
#### Subtask 1
從限制可以看到 $1 \leq x_i \leq 5$，代表可以分別定義 $5$ 個變數分別紀錄 $x_i = 1$ 有幾個、$x_i = 2$ 有幾個，以此類推。
輸出的時候只要先輸出這 $5$ 個變數的值，然後再輸出 $95$ 個 $0$ 就可以通過 Subtask 1 了。
> 因為 $x_i = 6$ 以後的都不可能出現，所以後面的必定都為 $0$。
:::spoiler 參考程式
```cpp
#include <iostream>
using namespace std;
int main(){
int n, a = 0, b = 0, c = 0, d = 0, e = 0, x;
cin >> n;
while(n--){
cin >> x;
if(x == 1)
a++;
else if(x == 2)
b++;
else if(x == 3)
c++;
else if(x == 4)
d++;
else if(x == 5)
e++;
}
cout << a << " " << b << " " << c << " " << d << " " << e;
for(int i = 5; i < 100; i++)
cout << " 0";
cout << "\n";
}
```
:::
#### Subtask 2
現在 $x_i$ 的最大值從 $5$ 增加到 $100$ 了，如果要延續 Subtask 1 的作法，
從 $5$ 個變數增加到 $100$ 個變數，且多增加許多 `if` 條件判斷，也是可以通過。
但是這個方法光是要一直複製貼上就很累人，因此可以用陣列來簡化那些繁瑣的程式碼。
宣告一個長度為 $100$ 的陣列 `arr`，而 `arr` 的每一個元素都代表其對應的箱子裡面有多少物品。
每次讀到一個 $x_i$ 的時候就將對應的元素加 $1$，最後再將陣列輸出就可以拿到滿分了。
> 我的實作方式是將 `arr[i]` 對應到第 $i + 1$ 個箱子，
> 因為題目的箱子編號是從 $1$ 開始，而陣列的索引值是從 $0$ 開始。
### 標準程式
:::spoiler
```cpp
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
int n;
cin >> n;
array<int, 100> arr{};
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
++arr[x - 1];
}
for (int i = 0; i < 100; ++i)
cout << arr[i] << ' ';
cout << endl;
return 0;
}
```
:::
## [石頭](https://judge.csie.ncku.edu.tw/problems/81)
- Task Provider: ys
- Task Setter: ys
### 首殺 ouob (00:02)
### 解法說明
一開始不曉得偉杰有幾顆石頭，於是假設偉杰目前擁有 $0$ 顆石頭
> 因為在還沒做任何操作前，偉杰**最少**可以有 $0$ 顆
而操作過程中若偉杰只有 $0$ 顆石頭，但還是要拿走 $1$ 顆石頭的話
則這個操作就是不符合規則的操作，需要假設偉杰一開始的石頭要**再多一顆**：
```cpp
if(cnt < 0) cnt++;
```
舉例來說，若操作為 `--+`
設偉杰一開始有 $x = 0$ 顆石頭，則目前有 $y = 0$ 顆石頭
下列 1、2、3 分別表示 `--+` 各個操作：
1. 由於 $y = 0$ 所以要假設 $x = 1$，則 $y = 1$。在這一步減少 $1$ 顆石頭，$y$ 變為 $0$
2. 由於 $y = 0$ 所以要假設 $x = 2$，則 $y = 1$。在這一步減少 $1$ 顆石頭，$y$ 變為 $0$
3. 在這一步增加 $1$ 顆石頭，$y$ 變為 $1$
### 標準程式
:::spoiler
```cpp
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int main()
{
cin >> n >> s;
int cnt = 0;
for(int i = 0; i < n; i++) {
if(s[i] == '+') cnt++;
if(s[i] == '-') cnt--;
if(cnt < 0) cnt++;
}
cout << cnt;
return 0;
}
```
:::
## [天啟](https://judge.csie.ncku.edu.tw/problems/82)
- Task Provider: arasHi
- Task Setter: arasHi
### 首殺 p76094795 (00:11)
### 解法說明
#### Subtask 1 $O(\max(a,b))$
此子任務只要照著題目敘述實作即可得分。
:::spoiler 參考程式
```cpp
#include <iostream>
using namespace std;
int main() {
int a, b;
cin >> a >> b;
while(a && b){
if(a < b)
swap(a, b);
a -= b;
}
cout << max(a, b) << "\n";
}
```
:::
#### Subtask 2 $O(\log(\max(a,b)))$
<font class="focus">請注意：這個子任務的變數範圍會超出 int 範圍，
請使用 long long 儲存數值。</font>
假設 $a>b$
觀察一下會發現，大的數字重複減去小的數，
一直重複這個動作的話會有以下兩種可能：
1. $a=0$
2. $a\neq0，$$a$ 會被減到小於 $b$
若是 1. 的話則得到題目所需的答案
若是 2. 的話則將 $a,b$ 對調並繼續執行相減的操作
若一開始 $a<b$ 的話，則不會執行任何減法，
會直接導到 2. ，因此會對調 $a,b$ 後繼續執行減法，
可以得知一開始 $a,b$ 相對關係不影響此作法正確性。
你如果直接將此作法送上去會得到一個 <font color="#3498db">TLE</font>，
因為如果 $a,b$ 分別為 $1$ 與 $10^{18}$ ，
則該作法會花費很長的時間執行，
因此有一個方法可以加速相減的過程。
當你要重複執行 $a-b$ 直到 $a<b$ 時，
則該操作會等價於 $a$ 對 $b$ 取模，
也就是 $a\div b$ 的餘數，在 C++ 可以用 `a % b` 得到。
如此一來就可以在很短的時間內得到答案。
此做法即為[輾轉相除法](https://zh.wikipedia.org/zh-tw/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95)，
而輾轉相除法可以求出兩個數的最大公因數（GCD），
因此做出這題的各位其實已經會求兩數的最大公因數了喔。
### 標準程式
:::spoiler
```cpp
#include <iostream>
using namespace std;
int main() {
long long a, b, t;
cin >> a >> b;
while(b){
t = a % b;
a = b;
b = t;
}
cout << a << "\n";
}
```
:::
## [考試星球](https://judge.csie.ncku.edu.tw/problems/83)
- Task Provider: XDEv11
- Task Setter: leo
### 首殺 felixchao (00:47)
### 解法說明
#### Subtask 1 $O(n^2)$
對於每個人，檢查是否表現得比其他人都好，複雜度為 $O(n^2)$。
:::spoiler 參考程式
```cpp!
#include <iostream>
#include <vector>
#include <array>
#include <string>
using namespace std;
void solve() {
int n;
cin >> n;
vector<array<int, 3>> v(n);
for (auto& [x1, x2, x3] : v) cin >> x1 >> x2 >> x3;
for (int i{0}; i < n; ++i) {
bool flag{true};
for (int j{0}; j < n; ++j) {
if (j == i) continue;
int w{0};
for (int k{0}; k < 3; ++k) if (v[i][k] > v[j][k]) ++w;
if (w < 2) {
flag = false;
break;
}
}
if (flag) {
cout << i + 1 << '\n';
return ;
}
}
cout << "-1\n"s;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t{1};
//cin >> t;
while (t--) solve();
return 0;
}
```
:::
#### Subtask 2 $O(n)$
因為最多只有一個人有機會表現得比其他人都好，
可以先兩兩進行比較，淘汰掉一個人，再找下一個比較，
$n$ 次後可淘汰掉 $n-1$ 個人，剩下的一個人只需要再與全部人比較一次即可，
複雜度為 $O(n)$。
### 標準程式
:::spoiler
```cpp!
#include <iostream>
#include <vector>
#include <array>
using namespace std;
void solve() {
int n;
cin >> n;
vector<array<int, 3>> v(n);
for (auto& x : v) cin >> x[0] >> x[1] >> x[2];
int cand{0}; // candidate
for (int i{0}; i < n; ++i) {
int w{0};
for (int k{0}; k < 3; ++k) if (v[cand][k] > v[i][k]) ++w;
if (w < 2) cand = i;
}
for (int i{0}; i < n; ++i) {
if (i == cand) continue;
int w{0};
for (int k{0}; k < 3; ++k) if (v[cand][k] > v[i][k]) ++w;
if (w < 2) {
cout << "-1\n"s;
return ;
}
}
cout << cand + 1 << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t{1};
//cin >> t;
while (t--) solve();
return 0;
}
```
:::
## [簡單的小遊戲](https://judge.csie.ncku.edu.tw/problems/84)
- Task Provider: XDEv11
- Task Setter: leo
### 首殺 dennis23314063 (01:05)
### 解法說明
#### Subtask 1 $O(t(5^{nm}\cdot nm))$
一個格子最多只會跟 $4$ 個格子相鄰，因此數字最多為 $4$，
只要枚舉每個格子的數字（$0\sim4$），
並檢驗相鄰的非 $0$ 數量以及是否大於原本的數字即可，
如果枚舉所有可能都沒找到，則輸出 `NO`。
枚舉複雜度 $O(5^{nm})$，檢驗 $O(nm)$，總複雜度 $O(5^{nm}\cdot nm)$
:::spoiler 參考程式
```cpp
#include <iostream>
using namespace std;
int n, m, a[3][3], tmp[3][3];
bool valid(int x, int y){
return x >= 0 && x < n && y >= 0 && y < m && tmp[x][y];
}
int calc(int x, int y){
static const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
int cnt = 0;
for(int i = 0; i < 4; i++)
if(valid(x + dx[i], y + dy[i]))
cnt++;
return cnt;
}
bool dfs(int x){
int r = x / m, c = x % m;
if(x >= n * m){
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(!((!tmp[i][j] || calc(i, j) == tmp[i][j]) && tmp[i][j] >= a[i][j]))
return 0;
return 1;
}
for(int i = 0; i <= 4; i++){
tmp[r][c] = i;
if(dfs(x + 1))
return 1;
}
return 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
cin >> n >> m;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cin >> a[i][j];
if(dfs(0)){
cout << "YES\n";
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cout << tmp[i][j] << " \n"[j == m - 1];
}
else{
cout << "NO\n";
}
}
}
```
:::
#### Subtask 2 $O(nm)$
根據上面所述，每個格子可分為下列三種情況：
1. 在最角落只有 $2$ 個數字與其相鄰，因此最大為 $2$
2. 在邊邊的只有 $3$ 個數字與其相鄰，因此最大為 $3$
3. 其餘有 $4$ 個數字與其相鄰，因此最大為 $4$
只要一開始輸入的數字違反了上述的條件，則該筆輸入答案為 `NO`，
否則只要將數字填為可能的最大值，每個格子都是非 $0$，
所以也剛好讓數字都可以達到最大值，範例如下：
```
2 3 3 3 2
3 4 4 4 3
3 4 4 4 3
2 3 3 3 2
```
### 標準程式
:::spoiler
```cpp
#include <iostream>
#include <vector>
#include <string>
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector<vector<int>> mtx(n, vector<int>(m));
for (auto& vt : mtx)
for (auto& x : vt) cin >> x;
for (int i{0}; i < n; ++i)
for (int j{0}; j < m; ++j) {
int neb{4};
if (i == 0 || i == n - 1) --neb;
if (j == 0 || j == m - 1) --neb;
if (mtx[i][j] > neb) {
cout << "NO\n"s;
return ;
} else mtx[i][j] = neb;
}
cout << "YES\n"s;
for (auto& vt : mtx) {
for (auto& x : vt) cout << x << ' ';
cout << '\n';
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t{1};
cin >> t;
while (t--) solve();
return 0;
}
```
:::
## [射箭比賽](https://judge.csie.ncku.edu.tw/problems/85)
- Task Provider: leo
- Task Setter: leo
### 首殺 p76094795 (01:00)
### 解法說明
<font class="focus">這題主要是想藉著開學考讓大家知道有這種互動的題型，
希望寫完這題後可以大致上知道互動題的運作模式，
OJ 上面也還有其他互動題可以讓各位練習
只要有 Interactive 標籤的都是互動題。</font>
<font class="focus">另外，這題只要有認真讀完題敘就應該有 $12$ 分可以拿，
鼓勵各位每一題都應該要仔細閱讀，
不要因為某一題過不了而一直卡在那邊。</font>
#### Subtask 1 $O(1)$
直接把題目附的檔案上傳就可以了，因為 $N\leq2$，所以只有兩種情況：
- $N=1$，無法動作，只好投降
- $N=2$，射一顆，留下最後一顆
:::spoiler 參考程式
```cpp
#include "lib0085.h"
int main(){
int t, n, k, shot;
t = Lets_shoot();
while(t--){
Game(&n, &k);
if(n == 2)
shot = Shooting(1);
else
Surrender();
}
}
```
:::
#### Subtask 2 $O(NK)$
你只要不斷的射一顆，直到對方投降或是輪到自己的時候剩一顆而投降
:::spoiler 參考程式
```cpp
#include "lib0085.h"
int main(){
int t, n, k, x;
t = Lets_shoot();
while(t--){
Game(&n, &k);
if(n == 1){
Surrender();
continue;
}
while(n != 1 && (x = Shooting(1))){
n -= 1 + x;
if(n == 1)
Surrender();
}
}
}
```
:::
#### Subtask 3 $O(NK)$
最終輸的條件是輪到自己時只剩 $1$ 顆，可以藉由這個推導，
如果雙方都採取最佳策略的話，那麼當氣球數量為 $K+2$ 顆時，你最多只能射 $K$ 顆，
如此一來會剩下 $2$ 顆，如果對方射掉一顆留下最後一顆，你就輸了；
若你只射 $1$ 顆的話，對方可以選擇射 $K$ 顆，
最後還是剩下最後一顆，一樣是你輸。
由於後手可以將每次雙方射掉的氣球數量控制在 $nK+n$，
從上面這邊可以推論，當輪到某人時的氣球數量為 $1,K+2,2K+3,\dots,nK+n+1(n\in\{0,\mathbb{N}\})$ 時，
該玩家在這場遊戲的狀態必輸。
因此如果開場的氣球數量除以 $K+1$ 的餘數為 $1$ 時則必輸，
否則只要每次射完後將氣球數量控制在 $nK+n+1$ 即可贏得比賽。
### 標準程式
:::spoiler
需要注意不要射到負數個氣球，在此用 `mod_abs` 取正的餘數
```cpp
#include "lib0085.h"
int mod_abs(int x, int mod){
return x < 0 ? x + mod : x;
}
int main(){
int t, n, k, x;
t = Lets_shoot();
while(t--){
Game(&n, &k);
if(n % (k + 1) == 1){
Surrender();
continue;
}
while(x = Shooting(mod_abs(n % (k + 1) - 1, k + 1)))
n -= mod_abs(n % (k + 1) - 1, k + 1) + x;
}
}
```
:::
## [跳啊](https://judge.csie.ncku.edu.tw/problems/86)
- Task Provider: ys
- Task Setter: ys
### 首殺 visitorckw (00:35)
### 解法說明
#### Subtask 1~2
直接模擬題目敘述中的做法
當起點試到第 $x$ 個格子時，作法如下：
1. 當 $x \le n$，可得到分數 $a_x$，並且將硬幣往右移動 $a_x$ 格 (就是移到位置 $x + a_x$)
2. 繼續第 1 步驟直到 $x > n$
該做法的複雜度為 $O(n^2)$
:::spoiler 參考程式
```cpp
#include<bits/stdc++.h>
using namespace std;
int constexpr maxn = 1e6 + 10;
int n, a[maxn];
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
int best = 0;
for(int i = 1; i <= n; i++) {
int x = i, sum = 0;
while(x <= n) sum += a[x], x += a[x];
best = max(best, sum);
}
cout << best << endl;
return 0;
}
```
:::
#### Subtask 3
假設 $s(i)$ 為硬幣移到 $i$ 格子時，目前可得到的最大分數
例如 $a = [2, 1, 3, 4]$，則 $s(3) = 2$
> 從起點 $i = 1$ 可跳到 $i = 3$ 共得到 $2$ 分
若從起點 $i = 2$ 跳至 $i = 3$ 只能得 $1$ 分
假設對於格子 $x$，已知比 $x$ 小的格子只有 $i$ 和 $j$ 格子能一步到達 $x$
> 也就是說 $x = i + a_i$ 及 $x = j + a_j$
若想知道 $s(x)$ 為多少，則只需看 $s(i) + a_i$ 和 $s(j) + a_j$ 何者較大
然而這裡的 $s(i)$ 及 $s(j)$ 也得靠比 $i$ 或 $j$ 小的格子求得
依此類推，若想算出 $s$，需要從第 $1$ 格至 $n$ 格依序計算
實作上，利用陣列 `s`
當起點選到第 $i$ 格時，就更新 `s[i+a[i]]` 的值
```cpp
s[i+a[i]] = max(s[i+a[i]], s[i] + a[i]);
```
> 這邊要注意到當選到 $i$ 格時，`s[i]` 早已得到答案
這樣在之後選到此 `i+a[i]` 格子時，就已經計算完到該格的最大分數了
以上該做法的複雜度為 $O(n)$
### 標準程式
:::spoiler
```cpp
#include<bits/stdc++.h>
using namespace std;
int constexpr maxn = 1e6 + 10;
int s[maxn], n, a;
int main()
{
cin >> n;
int best = 0;
for(int i = 1; i <= n; i++) {
cin >> a;
if(i+a > n) best = max(best, s[i] + a);
else s[i+a] = max(s[i+a], s[i] + a);
}
cout << best << endl;
return 0;
}
```
:::
## [消消樂](https://judge.csie.ncku.edu.tw/problems/87)
- Task Provider: D4nnyLee
- Task Setter: D4nnyLee
### 首殺 pmcat (01:09)
### 解法說明
在分成兩個子任務看之前，我們需要先分析題目要的東西。
每次操作都會得到 $ax + b$ 分，也就是說做了 $k$ 次之後會獲得的分數是 $\sum^{k}_{i = 1}(ax_i + b)$。
> $x_i$ 代表第 $i$ 次操作消去的石頭數量。
上面的公式可以化簡成 $a \sum^{k}_{i = 1}{x_i} + kb$，如果石頭被消完的話，可以發現 $\sum^{k}_{i = 1}{x_i}$ 會等於石頭總數，也就是 $N$。
因此最後獲得的分數可以寫成 $aN + kb$。
從公式中可以看出，會影響最後總分大小的只有 $k$ 這個變數，也就是消完全部石頭的總操作數。
#### Subtask 1
在這個子任務中，$b$ 不會是負數，因此要得到最大分數的方法就是讓 $k$ 愈大愈好。
讓 $k$ 最大的方法就是每次操作都只消除一個石頭，所以這時 $k$ 就會等於 $N$。
答案為 $(a + b) \cdot N$。
:::spoiler 參考程式
```cpp
#include <iostream>
using namespace std;
int main() {
int t, n, a, b;
string s;
cin >> t;
while(t--){
cin >> n >> a >> b >> s;
cout << n * (a + b) << "\n";
}
}
```
:::
#### Subtask 2
現在多了 $b$ 是負數的情況，因此當 $b$ 是負數時必須要讓 $k$ 愈小愈好。
這邊將連續的一段石頭視為一個「區段」，舉例來說，
`WWW` 就只有一個區段，而 `WWWBBW` 有 $3$ 個，`WBWBW` 有 $5$ 個。
消除全部的石頭就意味著要將所有的區段消除。
每次的操作都固定為從現有的區段中選出其中一個，並將這個區段中的所有石頭都消除。
> 只消除區段中的部分石頭只會多浪費一次操作，並不會讓結果更好。
假設現在有 $cnt$ 個區段，要怎麼選才會得到最小的 $k$？
可以觀察一下，如果 $cnt \geq 3$，消除第 $1$ 個或是第 $cnt$ 個區段之後會讓區段的總數少 $1$。
但是如果選擇其它的區段的話，在消除之後左右兩邊的區段會合併成一個區段，所以會讓區段的總數少 $2$。
因此最好的取法就是每次都選頭尾以外的區段來消除。
如果 $1 \leq cnt \leq 2$，那就只能花 $cnt$ 次操作把所有區段消除。
這邊很直覺的就可以寫出以下程式來算出 $k$，
```cpp
int k = 0;
while (cnt >= 3) {
cnt -= 2;
++k;
}
k += cnt;
```
但其實 $k$ 可以用一個公式就算出來，將 $cnt$ 分成奇數和偶數兩種情況去分析：
* 奇數：
經過 $\frac{cnt - 1}{2}$ 次操作之後會剩下 $1$，因此 $k = \frac{cnt - 1}{2} + 1$
* 偶數：
經過 $\frac{cnt - 2}{2}$ 次操作之後會剩下 $2$，因此 $k = \frac{cnt - 2}{2} + 2 = \frac{cnt}{2} + 1$
上面兩個公式可以總結成 $k = \lfloor \frac{cnt}{2} \rfloor + 1$。
有了 $k$ 之後就可以直接算出最後的總分了。
### 標準程式
:::spoiler 參考程式
```cpp
#include <iostream>
using namespace std;
void test_case()
{
int n, a, b;
string s;
cin >> n >> a >> b >> s;
if (b >= 0)
cout << n * (a + b) << '\n';
else {
int cnt = 1;
for (int i = 1; i < n; ++i)
if (s[i] != s[i - 1])
++cnt;
cout << a * n + (cnt / 2 + 1) * b << '\n';
}
}
int main(void)
{
int t = 1;
cin >> t;
while (t--)
test_case();
return 0;
}
```
:::
## [通識選課](https://judge.csie.ncku.edu.tw/problems/88)
- Task Provider: leo
- Task Setter: leo
### 首殺 pmcat (00:37)
### 解法說明
#### Subtask 1 <font class="focus">$O(N^M\cdot NM)$ by 剪枝</font>
枚舉每個人最後所錄取的志願，並驗證是否符合抽籤規則，
如果枚舉過程中發現某堂課假設的錄取人數超過該堂課上限，
則不管後面的枚舉狀況如何，該枚舉必然不成立，
因此可以適當排除這些不可能的組合以加速枚舉過程，
這種技巧稱為「剪枝」
而驗證枚舉結果合法性的方式如下：
1. 如果有一門還有餘額的課程在被錄取的課程前面，則不符合規則
2. 如果有志願序較前面的錄取但是志願序較大的沒被錄取，則不符合規則
可以直接跑過所有人的第一志願，如果該志願是該學生錄取的志願，則將他錄取。
接著再跑一次第一志願看有沒有人有資格錄取卻沒被錄取。
如此一來志願較前面的人一定會優先被錄取到，
而且不會有明明前面的課程還有餘額卻沒有錄取到的狀況。
此驗證方法總複雜度為 $O(\sum K)=O(NM)$，
而枚舉的複雜度為 $O(\prod K)=O(N^M)$，
因此算法總複雜度為 $O(N^M\cdot NM)$。
要特別注意的是，有可能會有人沒有錄取任何志願，因此要記得枚舉這種狀況。
:::spoiler 參考程式
```cpp
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 8, MAXM = 8;
vector<int> vul[MAXN + 1];
int n, m, stu[MAXN + 1], res[MAXM + 1], cnt[MAXN + 1];
bool dfs(int now){
if(now > m){
int admit[MAXN + 1] = {};
bool used[MAXM + 1] = {};
for(int j = 0; j < n; j++){
for(int i = 1; i <= m; i++){
if(used[i] || j >= vul[i].size())
continue;
if(vul[i][j] == res[i])
used[i] = 1, admit[res[i]]++;
}
for(int i = 1; i <= m; i++){
if(used[i] || j >= vul[i].size())
continue;
if(admit[vul[i][j]] < stu[vul[i][j]])
return 0;
}
}
return 1;
}
for(int i : vul[now]){
res[now] = i;
cnt[i]++;
if(cnt[i] <= stu[i] && dfs(now + 1))
return 1;
cnt[i]--;
}
res[now] = -1;
return dfs(now + 1);
}
int main() {
int x, k;
cin >> n >> m;
memset(res, -1, sizeof(res));
memset(cnt, 0, sizeof(cnt));
for(int i = 1; i <= n; i++)
cin >> stu[i];
for(int i = 1; i <= m; i++){
cin >> k;
for(int j = 1; j <= k; j++){
cin >> x;
vul[i].push_back(x);
}
}
dfs(1);
for(int i = 1; i <= m; i++)
cout << res[i] << " \n"[i == m];
}
```
:::
#### Subtask 2 $O(NM)$
可以觀察 Subtask 1 驗證的過程，就可以發現以下做法：
從每個人的第一志願開始看，如果餘額還有剩就將該學生錄取進該課程，
接下來再看還沒有錄取任何課程那些人的第二志願，
接著重複以上動作，就可以完成抽籤了，總複雜度 $O(\sum{K})=O(NM)$
### 標準程式
:::spoiler
```cpp
#include <iostream>
#include <queue>
using namespace std;
const int MAXN = 1000, MAXM = 1000;
queue<int> vol[MAXM];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, stu[MAXN + 1], res[MAXM] = {}, tmp, k;
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> stu[i];
for(int i = 0; i < m; i++){
cin >> k;
while(k--){
cin >> tmp;
vol[i].push(tmp);
}
}
for(int rem = m; rem;){
for(int i = 0; i < m && rem; i++){
if(res[i])
continue;
if(vol[i].empty()){
rem--;
res[i] = -1;
continue;
}
if(stu[vol[i].front()])
res[i] = vol[i].front(), stu[vol[i].front()]--, rem--;
vol[i].pop();
}
}
for(int i = 0; i < m; i++)
cout << res[i] << " \n"[i == m - 1];
}
```
:::
<style>
.focus {
color: red;
font-weight: bold;
}
</style>
Sign in with Wallet
Connect another wallet