# TPR #32 (Based on NHDK APCS 模擬賽 #1)

### 競賽資訊
- 比賽名稱：NHDK Ten Point Round #32 (Div. 2, based on NHDK APCS 模擬賽 #1)
- 比賽時間：12/18 13:40 ~ 16:10
- 使用平台：CMS（非 APCS 使用平台，當天早上 9:00 開放登入）
- 報名時間：即日起至 **12/17 18:00**
- 報名表單：https://forms.gle/NHSdUbhCHtCbzuBX9
- 競賽連結：將與帳號密碼一同寄至參賽者的信箱中
- 賽後 mirror 連結：https://codeforces.com/contestInvitation/64f22787871cc25f6aead746556959c5708480d3

### 賽制
- 共四題，每題滿分 100，共 400 分
- 有部分分（IOI 2012，以該題最後一筆上傳為準）
- 後測制（上傳後只驗證範例測資）
- 上傳完程式碼後需間隔 1 分鐘後才可進行下一次上傳（最後十分鐘不限）
- 單筆測資給分（每個測資 5 分，共 100 分）

### 開放語言與系統環境
- 系統使用 Ubuntu 22.04
- C++11 / g\++：
- Compiler：`g++ -DEVAL -std=gnu++11 -O2 -pipe -static -s -o <file> <file>.cpp`
- C11 / gcc：
- Compiler：`gcc -DEVAL -std=gnu11 -O2 -pipe -static -s -o <file> <file>.c -lm`
- Java / JDK：
- Compiler：`/usr/bin/javac spy.java`
- Runner：`/bin/sh -c jar cf spy.jar *.class`
- Python 2 / CPython：
- Python 3 / CPython：

### 注意事項
- 比賽帳密將於測機前寄到參賽者報名時所用的信箱
- 由於將大量發送郵件，通知信件有可能被視為垃圾郵件，請參賽者特別注意（將使用 [e-mail] 發送）
- 對於比賽登入有任何問題歡迎在 NHDK Discord Server 或是回信發問
- 比賽中有任何問題請使用系統內的提問系統提問
- Judge 上顯示之結果僅為範例測資之驗證結果，正式成績將於比賽後計算，並於賽後兩天內寄至參賽者報名時所用的信箱

### 主辦單位
NHDK 四校聯合初學者程式設計練習賽

### 協辦單位
SCIST 南臺灣學生資訊社群、AA 競程

# 題解

## PA. 新北耶誕城

### 解法
- 利用兩個變數，紀錄目前的連續遞增日數以及最長遞增日數
- 若連續遞增日數 > 最長遞增日數，則更新最長遞增日數
- 最後輸出最長遞增日數即可

### 參考程式

#include <bits/stdc++.h>

using namespace std;

int n;
int p[360];

signed main() {
    cin >> n;
    int tmp = 0, ans = 0;
    for (int i = 0; i < n; i++)
        cin >> p[i];
    for (int i = 1; i < n; i++) {
        if (p[i] > p[i - 1])
            tmp++;
        else
            tmp = 0;
        ans = max(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}

## PB. 2048

### 解法
- 將移動、合併、生成各自寫成三種函式
- 移動：`move()`
- 合併：`merge()`
- 生成：`generate()`
- 制定好每種操作的起始位置以及掃描方向
- 上：起始位置為 $(1, 1), (1, 1), (1, 2), \dots , (1, m)$（最上那排），每次向下掃描 $(1, 0)$
- 下：起始位置為 $(n, 1), (n, 2), (n, 3), \dots, (n, m)$，每次向上掃描 $(-1, 0)$
- 左及右以此類推
- 根據每次操作方向依序呼叫以下函式
1. `move()`
2. `merge()`
3. `move()`
4. 若上述操作有成功，則呼叫 `generate()`

### 參考程式

#include <iostream>

using namespace std;

int n, m, q;
int num[10][10];

const int px[] = {-1, 1, 0, 0};
const int py[] = {0, 0, -1, 1};
int startx[] = {0, 0, 0, 0}; // startx[1] = n - 1
int starty[] = {0, 0, 0, 0}; // starty[3] = m - 1


int merge(int x, int y, int op) {
    int cnt = 0;
    for (int i = 0; ; i++) {
        int nowx = x - i * px[op];
        int nowy = y - i * py[op];
        int nxtx = x - (i + 1) * px[op];
        int nxty = y - (i + 1) * py[op];

        if (nxtx < 0 || nxtx >= n || nxty < 0 || nxty >= m)
            break;

        if (num[nowx][nowy] == num[nxtx][nxty] && num[nowx][nowy] > 0) {
            num[nowx][nowy] += num[nxtx][nxty];
            if (num[nowx][nowy] == 2048)
                num[nowx][nowy] = 2;
            num[nxtx][nxty] = 0;
            i++;
            cnt++;
        }
    }
    return cnt;
}

bool move(int x, int y, int op) {

    bool changed = false;
    for (int i = 0; i < max(n, m); i++) {
        for (int j = 0; ; j++) {
            int nowx = x - j * px[op];
            int nowy = y - j * py[op];
            int nxtx = x - (j + 1) * px[op];
            int nxty = y - (j + 1) * py[op];

            if (nxtx < 0 || nxtx >= n || nxty < 0 || nxty >= m)
                break;

            if (num[nowx][nowy] == 0 && num[nxtx][nxty] != 0) {
                swap(num[nowx][nowy], num[nxtx][nxty]);
                changed = true;
            }
        }
    }
    return changed;
}

int get_sum() {
    int res = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            res += num[i][j];

    return res;
}

bool generate() {
    bool success = false;
    int sum = get_sum();
    int newnum = (sum % 32 == 0 ? 4 : 2);
    int space = 0;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            space += (num[i][j] == 0);

    if (space == 0)
        return false;

    int pos = sum % space + 1;
    int cnt = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cnt += (num[i][j] == 0);
            if (cnt == pos) {
                num[i][j] = newnum;
                return true;
            }
        }
    }
    return false;
}

signed main() {
    cin >> n >> m >> q;
    startx[1] = n - 1;
    starty[3] = m - 1;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> num[i][j];
    
    int op;
    int ans = 0;
    while (q--) {
        cin >> op;
        op--;

        int x = startx[op];
        int y = starty[op];

        bool changed = false;

        for (int i = 0; x < n && y < m; i++) {
            changed |= move(x, y, op);
            int mge = merge(x, y, op);
            ans += mge;
            changed |= mge;
            changed |= move(x, y, op);

            x += (op >= 2);
            y += (op <= 1);
        }

        if (changed)
            generate();
    }
    cout << ans << endl;
    return 0;
}

## PC. 聖誕卡片

### 解法 1（適用於 C++）
- 首先將所有字串反轉（reverse），那麼題目所求就會變成最長共同前綴
- 利用 multiset 存字串
- 第 1、2 種操作對應到 multiset 的 `.insert(s)`、`.erase(.find(s))`
- 至於第三種操作，由於 multiset 是按照字典序排序，根據字典序的性質，字典序越接近的字串，其前綴越接近
- 因此只需要找到所求字串的 lower\_bound 以及 lower\_bound 的前一位，取最大值即是答案
- 時間複雜度：$\mathcal{O}(Q\log Q \times \lvert S \rvert)$

### 參考程式 1

#include <bits/stdc++.h>

using namespace std;

int q;
multiset<string> st;

signed main() {
    cin >> q;

    int opt;
    string s;

    while (q--) {
        cin >> opt;
        cin >> s;
        reverse(s.begin(), s.end());

        if (opt == 1)
            st.insert(s);
        else if (opt == 2)
            st.erase(st.find(s));
        else {
            string s1, s2;
            int ans = 0;
            int cnt = 0;

            if (st.lower_bound(s) != st.begin())
                s1 = *(--st.lower_bound(s));
            if (st.lower_bound(s) != st.end())
                s2 = *(st.lower_bound(s));
            for (int i = 0; i < min(s.size(), s1.size()); i++) {
                if (s[i] == s1[i])
                    cnt++;
                else
                    break;
            }
            ans = cnt;

            cnt = 0;
            for (int i = 0; i < min(s.size(), s2.size()); i++) {
                if (s[i] == s2[i])
                    cnt++;
                else
                    break;
            }
            ans = max(ans, cnt);
            cout << ans << endl;
        }
    }
}

### 解法 2（適用於所有語言）
- 第一步驟一樣，先將他反轉
- 建立兩個陣列 `v, del`
- `v`：目前集合中的字串
- `del`：等待刪除的字串
- 對於第一種操作，將字串加入 `v`
- 對於第二種操作，將字串加入 `del`
- 對於第三種操作，由於 `v` 中會存在一些應該被刪掉但還沒被刪掉的字串，因此需要先求出真正的 `v`
- 將 `v, del` 各自排序
- 建立新的陣列 `tmp`
- 利用雙指針或是二分搜，即可推出 `v` 中的每個字串是否有在 del 中，要是不存在，則加入 `tmp`
- 最後 tmp 即是真正的 `v`
- 枚舉 `v` 中的所有字串，求出最佳的答案
- 時間複雜度：$\mathcal{O}(100 \times Q \log Q)$

### 參考程式 2

#include <bits/stdc++.h>

using namespace std;

int q;

signed main() {
    cin >> q;

    int opt;
    string s;
    vector<string> v;
    vector<string> del;

    while (q--) {
        cin >> opt;
        cin >> s;
        reverse(s.begin(), s.end());

        if (opt == 1)
            v.push_back(s);
        else if (opt == 2)
            del.push_back(s);
        else {
            sort(v.begin(), v.end());
            sort(del.begin(), del.end());

            vector<string> tmp;
            int mx = 0;
            for (int i = 0, j = 0; i < v.size(); i++) {
                while (j < del.size() && del[j] < v[i]) 
                    j++;
                if (j < del.size() && del[j] == v[i]) {
                    j++;
                    continue;
                }
                tmp.push_back(v[i]);
                for (int k = 0; k < min(v[i].size(), s.size()); k++) {
                    if (v[i][k] == s[k])
                        mx = max(mx, k + 1);
                    else
                        break;
                }
            }
            v = tmp;
            del.clear();

            cout << mx << endl;
        }
    }
}

## PD. 籌辦

### 解法
- 不難看出這是一題 DP 的題目
- 設 $dp_{i, j}$ 在第 $i$ 天才做第 $j$ 件事的最大成就感值
- 可以求出轉移式：$dp_{i, j} = \displaystyle\max_{0 \le k \le j}(dp_{i - 1, k} + \sum_{l = k + 1}^{j}{s_{i, l}} - \sum_{l = j + 1}^{m}{d_{i, l}})$
- 時間複雜度 $\mathcal{O}(nm^2)$
- 可以利用前綴 DP 優化為 $\mathcal{O}(nm)$

### 參考程式（部分分）：

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define MAXN 1005

int n, m, k;
int s[MAXN][MAXN], d[MAXN][MAXN], dp[MAXN][MAXN];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> s[i][j];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            cin >> d[i][j];
    }

    memset(dp, -0x3f, sizeof(dp));
    dp[0][0] = 0;

    for (int i = 1; i <= n; i++) {
        dp[i][0] = dp[i - 1][0];
        for (int j = 1; j <= m; j++)
            dp[i][0] -= d[i][j];
        for (int j = 1; j <= m; j++) {
            for (int k = 0; k <= j; k++) {
                int tmp = 0;
                for (int l = k + 1; l <= j; l++)
                    tmp += s[i][l];
                for (int l = j + 1; l <= m; l++)
                    tmp -= d[i][l];
                dp[i][j] = max(dp[i][j], dp[i - 1][k] + tmp);
            }
        }
    }

    int ans = 0;

    for (int i = 1; i <= n; i++) {
        ans = max(ans, dp[i][m]);
    }
    cout << ans << endl;
    return 0;
}

### 參考程式（前綴 DP）

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define MAXN 3005

int n, m, k;
int s[MAXN][MAXN], d[MAXN][MAXN], dp[MAXN][MAXN];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;

    memset(dp, -0x3f, sizeof(dp));
    dp[0][0] = 0;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> s[i][j];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            cin >> d[i][j];
    }

    for (int j = 1; j <= m; j++) {
        int mx = 0;
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            mx = max(mx, dp[i][j - 1]);
            cnt += d[i - 1][j];
            dp[i][j] = max(dp[i][j], mx - cnt + s[i][j]);
        }
    }

    int ans = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
        }
        ans = max(ans, dp[i][m]);
    }
    cout << ans << endl;
}