2021 高階競技程式設計課前賽 - 題解

政大的女朋友

Task Provider: smallbird
Task Setter: leo

首殺 pmcat (00:03)

解法說明

解法
$1$

因為 + 加上 + 會變成 -，而 - 的絕對值很小，代表影響很小，
因此只要 + 的數量是奇數的話，算出來的答案就會是正數，反之亦然，
所以只要計算 + 的數量就可以知道答案了。

解法
$2$

我們無法從輸入得知 - 到底是

- 1

- 2

還是

- 3

，
+ 也是一樣情況，所以不管是哪一種，答案都應該相同，
因此我們可以把 + 當作

2^{31} - 1

，把 - 當作

- 1

，
直接做計算，不過在 C++ 中，有號數溢位是 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.
$^{[A r i t h m e t i c o p e r a t o r s]}$

而無號數加有號數，有號數會被隱性轉型為無號數。

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.
$^{[u s u a l a r i t h m e t i c c o n v e r s i o n s]}$

標準程式

解法
$1$

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

#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";
}

整理房間

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

參考程式

#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$ 開始。

標準程式

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

石頭

Task Provider: ys
Task Setter: ys

首殺 ouob (00:02)

解法說明

一開始不曉得偉杰有幾顆石頭，於是假設偉杰目前擁有

0

顆石頭

因為在還沒做任何操作前，偉杰最少可以有
$0$ 顆

而操作過程中若偉杰只有

0

顆石頭，但還是要拿走

1

顆石頭的話
則這個操作就是不符合規則的操作，需要假設偉杰一開始的石頭要再多一顆：

if(cnt < 0) cnt++;

舉例來說，若操作為 --+
設偉杰一開始有

x = 0

顆石頭，則目前有

y = 0

顆石頭
下列 1、2、3 分別表示 --+ 各個操作：

由於
$y = 0$ 所以要假設
$x = 1$ ，則
$y = 1$ 。在這一步減少
$1$ 顆石頭，
$y$ 變為
$0$
由於
$y = 0$ 所以要假設
$x = 2$ ，則
$y = 1$ 。在這一步減少
$1$ 顆石頭，
$y$ 變為
$0$
在這一步增加
$1$ 顆石頭，
$y$ 變為
$1$

標準程式

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

天啟

Task Provider: arasHi
Task Setter: arasHi

首殺 p76094795 (00:11)

解法說明

Subtask 1
$O (max (a, b))$

此子任務只要照著題目敘述實作即可得分。

參考程式

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

請注意：這個子任務的變數範圍會超出 int 範圍，
請使用 long long 儲存數值。

假設

a > b

觀察一下會發現，大的數字重複減去小的數，
一直重複這個動作的話會有以下兩種可能：

$a = 0$
$a \neq 0 ，$
$a$ 會被減到小於
$b$

若是 1. 的話則得到題目所需的答案
若是 2. 的話則將

a, b

對調並繼續執行相減的操作

若一開始

a < b

的話，則不會執行任何減法，
會直接導到 2. ，因此會對調

a, b

後繼續執行減法，
可以得知一開始

a, b

相對關係不影響此作法正確性。

你如果直接將此作法送上去會得到一個 TLE，
因為如果

a, b

分別為

1

與

10^{18}

，
則該作法會花費很長的時間執行，
因此有一個方法可以加速相減的過程。
當你要重複執行

a - b

直到

a < b

時，
則該操作會等價於

a

對

b

取模，
也就是

a \div b

的餘數，在 C++ 可以用 a % b 得到。
如此一來就可以在很短的時間內得到答案。

此做法即為輾轉相除法，
而輾轉相除法可以求出兩個數的最大公因數（GCD），
因此做出這題的各位其實已經會求兩數的最大公因數了喔。

標準程式

#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";
}

考試星球

Task Provider: XDEv11
Task Setter: leo

首殺 felixchao (00:47)

解法說明

Subtask 1
$O (n^{2})$

對於每個人，檢查是否表現得比其他人都好，複雜度為

O (n^{2})

。

參考程式

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

。

標準程式

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

簡單的小遊戲

Task Provider: XDEv11
Task Setter: leo

首殺 dennis23314063 (01:05)

解法說明

Subtask 1
$O (t (5^{n m} \cdot n m))$

一個格子最多只會跟

4

個格子相鄰，因此數字最多為

4

，
只要枚舉每個格子的數字（

0 \sim 4

），
並檢驗相鄰的非

0

數量以及是否大於原本的數字即可，
如果枚舉所有可能都沒找到，則輸出 NO。

枚舉複雜度

O (5^{n m})

，檢驗

O (n m)

，總複雜度

O (5^{n m} \cdot n m)

參考程式

#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 (n m)$

根據上面所述，每個格子可分為下列三種情況：

在最角落只有
$2$ 個數字與其相鄰，因此最大為
$2$
在邊邊的只有
$3$ 個數字與其相鄰，因此最大為
$3$
其餘有
$4$ 個數字與其相鄰，因此最大為
$4$

只要一開始輸入的數字違反了上述的條件，則該筆輸入答案為 NO，
否則只要將數字填為可能的最大值，每個格子都是非

0

，
所以也剛好讓數字都可以達到最大值，範例如下：

標準程式

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

射箭比賽

Task Provider: leo
Task Setter: leo

首殺 p76094795 (01:00)

解法說明

這題主要是想藉著開學考讓大家知道有這種互動的題型，
希望寫完這題後可以大致上知道互動題的運作模式，
OJ 上面也還有其他互動題可以讓各位練習
只要有 Interactive 標籤的都是互動題。

另外，這題只要有認真讀完題敘就應該有

12

分可以拿，
鼓勵各位每一題都應該要仔細閱讀，
不要因為某一題過不了而一直卡在那邊。

Subtask 1
$O (1)$

直接把題目附的檔案上傳就可以了，因為

N \leq 2

，所以只有兩種情況：

$N = 1$ ，無法動作，只好投降
$N = 2$ ，射一顆，留下最後一顆

參考程式

#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 (N K)$

你只要不斷的射一顆，直到對方投降或是輪到自己的時候剩一顆而投降

參考程式

#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 (N K)$

最終輸的條件是輪到自己時只剩

1

顆，可以藉由這個推導，
如果雙方都採取最佳策略的話，那麼當氣球數量為

K + 2

顆時，你最多只能射

K

顆，
如此一來會剩下

2

顆，如果對方射掉一顆留下最後一顆，你就輸了；
若你只射

1

顆的話，對方可以選擇射

K

顆，
最後還是剩下最後一顆，一樣是你輸。

由於後手可以將每次雙方射掉的氣球數量控制在

n K + n

，
從上面這邊可以推論，當輪到某人時的氣球數量為

1, K + 2, 2 K + 3, \dots, n K + n + 1 (n \in {0, N})

時，
該玩家在這場遊戲的狀態必輸。
因此如果開場的氣球數量除以

K + 1

的餘數為

1

時則必輸，
否則只要每次射完後將氣球數量控制在

n K + n + 1

即可贏得比賽。

標準程式

需要注意不要射到負數個氣球，在此用 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;
    }
}

跳啊

Task Provider: ys
Task Setter: ys

首殺 visitorckw (00:35)

解法說明

Subtask 1~2

直接模擬題目敘述中的做法
當起點試到第

x

個格子時，作法如下：

當
$x \leq n$ ，可得到分數
$a_{x}$ ，並且將硬幣往右移動
$a_{x}$ 格 (就是移到位置
$x + a_{x}$ )
繼續第 1 步驟直到
$x > n$

該做法的複雜度為

O (n^{2})

參考程式

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

標準程式

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

消消樂

Task Provider: D4nnyLee
Task Setter: D4nnyLee

首殺 pmcat (01:09)

解法說明

在分成兩個子任務看之前，我們需要先分析題目要的東西。

每次操作都會得到

a x + b

分，也就是說做了

k

次之後會獲得的分數是

\sum_{i = 1}^{k} (a x_{i} + b)

。

$x_{i}$ 代表第
$i$ 次操作消去的石頭數量。

上面的公式可以化簡成

a \sum_{i = 1}^{k} x_{i} + k b

，如果石頭被消完的話，可以發現

\sum_{i = 1}^{k} x_{i}

會等於石頭總數，也就是

N

。
因此最後獲得的分數可以寫成

a N + k b

。

從公式中可以看出，會影響最後總分大小的只有

k

這個變數，也就是消完全部石頭的總操作數。

Subtask 1

在這個子任務中，

b

不會是負數，因此要得到最大分數的方法就是讓

k

愈大愈好。

讓

k

最大的方法就是每次操作都只消除一個石頭，所以這時

k

就會等於

N

。

答案為

(a + b) \cdot N

。

參考程式

#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

個。

消除全部的石頭就意味著要將所有的區段消除。

每次的操作都固定為從現有的區段中選出其中一個，並將這個區段中的所有石頭都消除。

只消除區段中的部分石頭只會多浪費一次操作，並不會讓結果更好。

假設現在有

c n t

個區段，要怎麼選才會得到最小的

k

？

可以觀察一下，如果

c n t \geq 3

，消除第

1

個或是第

c n t

個區段之後會讓區段的總數少

1

。
但是如果選擇其它的區段的話，在消除之後左右兩邊的區段會合併成一個區段，所以會讓區段的總數少

2

。
因此最好的取法就是每次都選頭尾以外的區段來消除。

如果

1 \leq c n t \leq 2

，那就只能花

c n t

次操作把所有區段消除。

這邊很直覺的就可以寫出以下程式來算出

k

，

int k = 0;
while (cnt >= 3) {
    cnt -= 2;
    ++k;
}
k += cnt;

但其實

k

可以用一個公式就算出來，將

c n t

分成奇數和偶數兩種情況去分析：

奇數：
經過
$\frac{c n t - 1}{2}$ 次操作之後會剩下
$1$ ，因此
$k = \frac{c n t - 1}{2} + 1$
偶數：
經過
$\frac{c n t - 2}{2}$ 次操作之後會剩下
$2$ ，因此
$k = \frac{c n t - 2}{2} + 2 = \frac{c n t}{2} + 1$

上面兩個公式可以總結成

k = ⌊ \frac{c n t}{2} ⌋ + 1

。

有了

k

之後就可以直接算出最後的總分了。

標準程式

參考程式

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

通識選課

Task Provider: leo
Task Setter: leo

首殺 pmcat (00:37)

解法說明

Subtask 1
$O (N^{M} \cdot N M)$ by 剪枝

枚舉每個人最後所錄取的志願，並驗證是否符合抽籤規則，
如果枚舉過程中發現某堂課假設的錄取人數超過該堂課上限，
則不管後面的枚舉狀況如何，該枚舉必然不成立，
因此可以適當排除這些不可能的組合以加速枚舉過程，
這種技巧稱為「剪枝」

而驗證枚舉結果合法性的方式如下：

如果有一門還有餘額的課程在被錄取的課程前面，則不符合規則
如果有志願序較前面的錄取但是志願序較大的沒被錄取，則不符合規則

可以直接跑過所有人的第一志願，如果該志願是該學生錄取的志願，則將他錄取。
接著再跑一次第一志願看有沒有人有資格錄取卻沒被錄取。
如此一來志願較前面的人一定會優先被錄取到，
而且不會有明明前面的課程還有餘額卻沒有錄取到的狀況。
此驗證方法總複雜度為

O (\sum K) = O (N M)

，
而枚舉的複雜度為

O (\prod K) = O (N^{M})

，
因此算法總複雜度為

O (N^{M} \cdot N M)

。

要特別注意的是，有可能會有人沒有錄取任何志願，因此要記得枚舉這種狀況。

參考程式

#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 (N M)$

可以觀察 Subtask 1 驗證的過程，就可以發現以下做法：
從每個人的第一志願開始看，如果餘額還有剩就將該學生錄取進該課程，
接下來再看還沒有錄取任何課程那些人的第二志願，
接著重複以上動作，就可以完成抽籤了，總複雜度

O (\sum K) = O (N M)

標準程式

#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];
}

2021 高階競技程式設計課前賽 - 題解

首殺 pmcat (00:03)

解法說明

解法 1

解法 2

標準程式

解法 1

解法 2

首殺 anderson425 (00:04)

解法說明

Subtask 1

Subtask 2

標準程式

首殺 ouob (00:02)

解法說明

標準程式

首殺 p76094795 (00:11)

解法說明

Subtask 1 O(max(a,b))

Subtask 2 O(log⁡(max(a,b)))

標準程式

首殺 felixchao (00:47)

解法說明

Subtask 1 O(n2)

Subtask 2 O(n)

標準程式

首殺 dennis23314063 (01:05)

解法說明

Subtask 1 O(t(5nm⋅nm))

Subtask 2 O(nm)

標準程式

首殺 p76094795 (01:00)

解法說明

Subtask 1 O(1)

Subtask 2 O(NK)

Subtask 3 O(NK)

標準程式

首殺 visitorckw (00:35)

解法說明

Subtask 1~2

Subtask 3

標準程式

首殺 pmcat (01:09)

解法說明

Subtask 1

Subtask 2

標準程式

首殺 pmcat (00:37)

解法說明

Subtask 1 O(NM⋅NM) by 剪枝

Subtask 2 O(NM)

標準程式

Read more

2020 Week 7: Dynamic Programming

2020 Week 1: Introduction

2020 Week 4: Search

2020 Week 14: Number theory

解法
$1$

解法
$2$

解法
$1$

解法
$2$

Subtask 1
$O (max (a, b))$

Subtask 2
$O (\log (max (a, b)))$

Subtask 1
$O (n^{2})$

Subtask 2
$O (n)$

Subtask 1
$O (t (5^{n m} \cdot n m))$

Subtask 2
$O (n m)$

Subtask 1
$O (1)$

Subtask 2
$O (N K)$

Subtask 3
$O (N K)$

Subtask 1
$O (N^{M} \cdot N M)$ by 剪枝

Subtask 2
$O (N M)$