---
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

#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

#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 參考程式

#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

#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$ 顆石頭的話
則這個操作就是不符合規則的操作，需要假設偉杰一開始的石頭要**再多一顆**：

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

#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 參考程式

#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

#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 參考程式

#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

#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 參考程式

#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

#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 參考程式

#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 參考程式

#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` 取正的餘數

#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 參考程式

#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]]` 的值

s[i+a[i]] = max(s[i+a[i]], s[i] + a[i]);

> 這邊要注意到當選到 $i$ 格時，`s[i]` 早已得到答案

這樣在之後選到此 `i+a[i]` 格子時，就已經計算完到該格的最大分數了

以上該做法的複雜度為 $O(n)$

### 標準程式

:::spoiler

#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 參考程式

#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$，

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 參考程式

#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 參考程式

#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

#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>