# SCIST S4 演算法季中賽題解

> 可以到這裡練習：https://codeforces.com/contestInvitation/2cd7f743f35be8e017938aed34b75ed2dd7bc29f

## pA 狂噴香水 (Crazy Perfume)
簡單來講就是大減小而已，但是有下面的考點需要注意：
1. JQK 處理
2. 字串轉數字

對於 JQK 的處理應該要反過來想，在一開始輸入的時候就直接輸入字串，並且把 JQK 轉為 "11","12","13" 的字串。
字串轉數字可以自己實作，但我更推薦直接使用 「stol」（或是 stoi） 函式。

:::spoiler Code

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio; cin.tie(0); cout.tie(0)
#define debug_container(container) for (auto i : container) cerr << i << ' '; cerr << '\n';
#define debug(x) cerr << x << '\n';
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vp;
 
int n;
 
void solve()
{
    cin >> n;
    int ans_1 = 0, ans_2 = 0;
    for (int i = 0; i < n; i++) 
    {
        string a, b;
        cin >> a >> b;
        if (a == "J") a = "11";
        if (a == "Q") a = "12";
        if (a == "K") a = "13";
        if (b == "J") b = "11";
        if (b == "Q") b = "12";
        if (b == "K") b = "13";
        
        int num_a = stoi(a), num_b = stoi(b);
        if (num_a > num_b) ans_2 += num_a - num_b;
        if (num_a < num_b) ans_1 += num_b - num_a;
    }
    
    cout << ans_1 << ' ' << ans_2 << '\n';
}
 
int main()
{
    fastio;
 
    solve();
 
    return 0;
}

:::

## pB 俄羅斯方塊（Tetris）
幾個想讓大家學習的東西（？）。
1. 實作量大可以考慮用函式
2. 習慣陣列上的座標系統 $(y,\ x)$

解法也沒什麼，就是「**首先暸解題目的意思，然後直接實作即可**」

:::spoiler 官解（+註解 143 行）

#include <bits/stdc++.h>
using namespace std;

/*
實作細節：

1. 所有內容皆為 1-based（遊戲平台中，0 被定義成邊界的座標）
2. 複雜操作都定義成函式
*/

// problem variable
int n, m;
int q;
int a, b, x;

// game status
bool game_over=0; // 遊戲是否結束（0=沒有結束，1=結束）
int line_clear_count=0; // 消除的行數
bool table[200][200]; // 遊戲面板（0=沒有填充，1=有點填充），table[y軸][x軸]

// 確認大小為 axb 的方塊是否能夠擺在 (x, y)
bool drop_check(int a, int b, int x, int y){
    bool ret=true;
    for (int i=y ; i<y+a ; i++){
        for (int j=x ; j<x+b ; j++){
            if (table[i][j]==1){
                ret=false;
            }
        }
    }
    return ret;
}

// 讓參數 axb，在第 x 行的方塊依照題目方式掉落，並更新 table
void drop_block(int a, int b, int x){
    for (int y=n+10 ; y>=0 ; y--){
        if (drop_check(a, b, x, y)==0){
            y++; // 如果不能的話，就擺在上一個 y 座標
            for (int i=y ; i<y+a ; i++){
                for (int j=x ; j<x+b ; j++){
                    table[i][j]=1;
                }
            }
            break;
        }
    }
    return;
}

// 檢查第 y 列是否可以被消行
bool line_clear_check(int y){
    bool ret=true;
    for (int x=1 ; x<=m ; x++){
        if (table[y][x]==0){
            ret=false;
        }
    }
    return ret;
}

// 對第 y 列執行消行並移動 y 列以上的所有方塊
void line_clear(int y){
    for ( ; y<=n ; y++){
        for (int x=1 ; x<=m ; x++){
            table[y][x]=table[y+1][x];
            table[y+1][x]=0; // 記得將移出的空間清空
        }
    }
    return;
}

// 檢查是否有方塊超出遊戲版面
bool game_over_check(){
    bool ret=false;
    for (int x=1 ; x<=m ; x++){
        if (table[n+1][x]==1){
            ret=true;
        }
    }
    return ret;
}

// 印出遊戲平台
void print_table(){
    for (int y=n ; y>=1 ; y--){
        for (int x=1 ; x<=m ; x++){
            if (table[y][x]==1){
                cout << "#";
            }else{
                cout << ".";
            }
        }
        cout << "\n";
    }
    return;
}

int main(){
    // 初始化：讓平台底部都當作有方塊
    for (int i=0 ; i<200 ; i++){
        table[0][i]=1;
    }

    // 輸入
    cin >> n >> m;

    // 查詢
    cin >> q;
    for (int i=0 ; i<q ; i++){
        cin >> a >> b >> x;

        // 讓方塊墜落
        drop_block(a, b, x);

        // 刪除並移動方塊
        for (int i=1 ; i<=n ; i++){
            while (line_clear_check(i)==true){
                line_clear_count++;
                line_clear(i);
            }
        }

        // 確認遊戲是否結束
        if (game_over_check()==true){
            game_over=true;
            break;
        }

        // 除錯輸出
        // print_table();
        // cout << "\n";
    }

    // 輸出
    if (game_over==true){
        cout << "Game Over\n";
    }else{
        cout << line_clear_count << "\n";
        print_table();
    }

    return 0;
}

:::

> 順帶一提，這一題的測資非常難出，我寫了近 200 行。
> 但非常有趣，生成的測資可以做成小 ascii 動畫

## pC 鹼基配對 (nucleobase)

~~有沒有在驚人的 note 字數中學到新東西呢~~
枚舉的精神不只是把東西都找過一遍，因為這件事小學生都會。枚舉的另一個重點是**如何不浪費資源在沒用的東西上**，做好這件事可以讓計算速度變快，節能減碳愛地球。

:::spoiler 子任務 1
如題目所說，最簡單的方式就是全部排列都試過一次，而這麼做要花 $O(n!)$ 的時間。
好在 $n \leq 8$ 所以這樣不會超時。

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<int> a(n), b(m);
    for(int i=0; i<n; i++)
        cin >> a[i];
    for(int i=0; i<m; i++)
        cin >> b[i];        

    sort(b.begin(), b.end());// 為了枚舉所以要排序

    do{
        int k = a[0] + b[0];
        bool pass = 1;
        for(int i=1; i<n; i++)
            pass &= (a[i] + b[i]) == k;

        if(pass){
            cout << "YES" << endl;
            return 0;
        }
    }while(next_permutation(b.begin(), b.end())); // 全排列枚舉

    cout << "NO" << endl;

    return 0;
}

:::

:::spoiler 子任務 2
全排列枚舉在毫無線索可以找答案時確實是個好方法，但是這題真的毫無線索嗎？
$a + b = k$ 全排列枚舉是在找 $a$ 和 $b$的組合，那我們可不可以找到 $a$ 和 $k$ 後，再去檢查是否存在 $b = k - a$。
所有可能的 $k$ 少於 $10000$ 個，而 $a$ 有 $100$ 個，$10^6$ 可以在時間內做完。

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<int> a(n);
    set<int> K;
    map<int, int> b;// 為了應對重複的數字
    for(int i=0; i<n; i++)
        cin >> a[i];
    for(int i=0; i<m; i++){
        int x;
        cin >> x;
        b[x]++;
    }

    for(int i=1; i<=100; i++)
        for(int j=1; j<=100; j++)
            K.insert(i + j);
    // cout << K.size() << endl; // 實際只有199個

    for(auto k:K){
        bool pass = 1;
        map<int, int> tmp_b = b;
        for(int i=0; i<n; i++){
            if(tmp_b[k - a[i]] == 0){// 如果沒有對應的 b 就沒了
                pass = 0;
                break;
            }
            tmp_b[k - a[i]]--;// 不然就拿走一個
        }

        if(pass){
            cout << "YES" << endl;
            return 0;
        }
    }

    cout << "NO" << endl;

    return 0;
}

:::

:::spoiler 子任務 3
再抬頭看看，題目最大數字範圍是 $10^9$，這再怎麼說都不適合枚舉 $k$ 了，但是 $n, m$ 只有 $2000$ 個，那有可能出現的 $k$ 一定在這些數字組合中。
更準確地說， $k$ 一定是 $a_0$ 和所有 $b$ 的組合，這樣一來就只有 $2000$ 個 $k$ 了。

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<int> a(n), b(m);
    map<int, int> b_cnt;

    for(int i=0; i<n; i++)
        cin >> a[i];

    for(int i=0; i<m; i++){
        cin >> b[i];
        b_cnt[b[i]]++;
    }

    for(int i=0; i<m; i++){
        int k = a[0] + b[i];// k 改從這裡生成

        map<int, int> tmp = b_cnt;
        bool pass = 1;
        tmp[b[i]]--;
        for(int i=1; i<n; i++){// 同子任務 2
            if(tmp[k - a[i]] == 0){
                pass = 0;
                break;
            }
            tmp[k - a[i]]--;
        }
        if(pass){
            cout << "YES" << endl;
            return 0;
        }

    }
    cout << "NO" << endl;

    return 0;
}

:::

:::spoiler 另解
因為是加減運算，所以也可以利用單調性來做這題。
實際上因為是加減運算，為了去掉單調性 $O(n\log{n})$ 的解法所以將輸入改成了 $n, m$。
原本是用 XOR 運算所以只用 $n$ 就夠了

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    int a[N], b[N];

    for(int i=0; i<n; i++)
        cin >> a[i];
    for(int i=0; i<m; i++)
        cin >> b[i];

    sort(a, a+n, greater<int>());
    sort(b, b+m);

    int idx=0;
    while(idx + n <= m){
        int k = a[0] + b[idx], j = idx+1;
        int pass = 1;
        for(int i=1; i<n; i++){
            while(j < m && a[i] + b[j] < k) j++;
            if(j >= m && i != n-1){
                pass = 0;
                break;
            }

            if(a[i] + b[j] == k){
                j++;
                continue;
            }
            else{
                pass = 0;
                break;
            }
        }
        if(pass){
            cout << "yes" << endl;
            return 0;
        }
        idx++;
    }
    cout << "no" << endl;

    return 0;
}

:::

:::spoiler 出爛了
理論上應該像上面說的這樣，但是，就是這個但是
因為地磁不穩導致的宇宙高能射線過量轟擊大腦，害我在使用測資腳本時少打了一個參數導致除了範測外所有答案都是 NO 這種事情.....
世界真的很神奇呢~
:::

## pD 找到蛇頭 (Find the Sneak Head)
這題有兩種解法，先講第一種，因為可以知道目前坐標儲存著連結到下一段的坐標，因此只要枚舉一次所有的格子，找到連結到尾巴最遠的那一格就是蛇頭。
另一種解法是可以發現不會有資料連結到蛇頭，這個在圖論上稱為入度為 $0$，那這樣就找到入度為 $0$ 者，即為蛇頭。

第二種解法可以自己試試看，非常簡單。
:::spoiler Code

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio; cin.tie(0); cout.tie(0);
// #define int long long
 
using namespace std;
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> v2i;
typedef vector<pii> vp;
typedef vector<vp> v2p;
typedef vector<v2p> v3p;
typedef vector<string> vs;
 
int n;
v2p graph;
 
void solve() {
    cin >> n;
    
    graph.resize(n, vp(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> graph[i][j].first >> graph[i][j].second;
            graph[i][j].first--, graph[i][j].second--;
        }
    }
    
    pii ans = {0,0};
    int maximum = -1e9;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int distance = 0;
            int x = i, y = j;
            while (graph[x][y].first != -1 && graph[x][y].second != -1) {
                distance++;
                int nx = graph[x][y].first;
                int ny = graph[x][y].second;
                x = nx, y = ny;
            }
            if (distance > maximum) {
                maximum = distance;
                ans = {i, j};
            }
        }
    }
    
    cout << ans.first + 1 << ' ' << ans.second + 1 << '\n';
} 
 
signed main() {
    fastio;
    solve();
    return 0;
}

:::

## pE 座位安排（Seats）
有些人可能是被 4 這個測資卡到，可以先自己思考一下 4 和其他的合數、其他的完全平方數有什麼不同。

**子任務 1**：直接按照題意實作，算出 $(n-1)!$ 再對 $n$ 取餘數。

**子任務 2**：在計算 $(n-1)!$ 的過程中，因為直接乘會溢位，所以每乘一次就要對 $n$ 取一次餘數。

**子任務 3**：範圍是 $2\leq n \leq 10^{14}$ ，直接算時間不夠而且可能會溢位所以要拿滿分必須用到數學性質。
首先是質數部分，note 給了威爾遜定理：$p$ 為質數時，$(p-1)! \equiv -1 \equiv p-1 \pmod p$，也就是當 $n$ 為質數時答案就是 $n-1$。
判斷質數的方法可以是測試 $2$ ~ $\left [ \sqrt{n} \right ]$ 中是否有 $n$ 的因數，因為當 $n$ 是合數時必定可以找到一個除了 1 以外 $\leq \sqrt{n}$ 的因數。
合數部分，非完全平方數的合數必定可以找到兩個相異因數相乘等於該合數，所以答案為 $0$。
完全平方數部分，$n\geq 3^{2}$ 時答案也必定是 $0$，因為假設此數為 $x^2$，則必定可以在 $<n$ 的正整數中找到 $x \times 1$ 及 $x \times 2$。$n=4$ 時找不到 $x \times 2$，所以是特例只能直接算。

:::spoiler 子任務 1 code

#include<iostream>
#include<cmath>
using namespace std;

int main(){
	long long n,x=1,i;
	cin>>n;
	for(i=1;i<n;i++){
		x*=i;
	}
	cout<<x%n<<'\n';
	return 0;
}

:::
::: spoiler 子任務 2 code

#include<iostream>
#include<cmath>
using namespace std;

int main(){
	long long n,x=1,i;
	cin>>n;
	for(i=1;i<n;i++){
		x*=i;
		x%=n;
	}
	cout<<x%n<<'\n';
	return 0;
}

:::
:::spoiler 子任務 3 code

#include<iostream>
#include<cmath>
using namespace std;

int main(){
	long long n,x,i;
	bool flag=0;
	cin>>n;
	x=sqrt(n);
	for(i=2;i<=x;i++){
		if(n%i==0){
			flag=1;
			break;
		}
	}
	if(flag){
		if(n==4){
			cout<<(2*3)%4<<'\n';
		}
		else{
			cout<<"0\n";
		}
	}
	else{
		cout<<n-1<<'\n';
	}
	return 0;
}

:::