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：

注意事項

比賽帳密將於測機前寄到參賽者報名時所用的信箱
由於將大量發送郵件，通知信件有可能被視為垃圾郵件，請參賽者特別注意（將使用 nhdktpr@gmail.com 發送）
對於比賽登入有任何問題歡迎在 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 的前一位，取最大值即是答案
時間複雜度：
$O (Q \log Q \times | S |)$

參考程式 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 中的所有字串，求出最佳的答案
時間複雜度：
$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 的題目
設
$d p_{i, j}$ 在第
$i$ 天才做第
$j$ 件事的最大成就感值
可以求出轉移式：
$d p_{i, j} = max_{0 \leq k \leq j} (d p_{i - 1, k} + \sum_{l = k + 1}^{j} s_{i, l} - \sum_{l = j + 1}^{m} d_{i, l})$
時間複雜度
$O (n m^{2})$
可以利用前綴 DP 優化為
$O (n m)$

參考程式（部分分）：



















































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

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

競賽資訊

賽制

開放語言與系統環境

注意事項

主辦單位

協辦單位

題解

PA. 新北耶誕城

解法

參考程式

PB. 2048

解法

參考程式

PC. 聖誕卡片

解法 1（適用於 C++）

參考程式 1

解法 2（適用於所有語言）

參考程式 2

PD. 籌辦

解法

參考程式（部分分）：

參考程式（前綴 DP）

Read more

HW2 陳克盈 112062205

HW1 陳克盈 112062205

14449 - Big orange cat's puzzle II

14444 - Big orange cat's puzzle