2022 全國賽心得

12月 18, 2022

2022 全國賽心得

在打完了北市賽後，順利進入了全國賽，全國賽在 $12/16, 12/17$ 舉辦，離北市賽比完有大概一個月的時間。

在這一個月的時間我請了公假，然後跟同學到費曼教室練習程式，前幾週因為有 $\text{NPSC}$，所以練的是團體賽，我跟 $\text{NPSC}$ 的隊友找一些 $\text{ICPC}$ 制的比賽打。比完 $\text{NPSC}$ 之後，我寫了一些 $\text{codeforces}$ 的題目，從我打過 $\text{round}$ 前幾場的題目去選，主要是在把之前沒解的題目寫一遍，然後在前一兩週，我跟同學挑了幾場 $\text{ICPC}$ 去打，因為全國賽的性質就是時間長、題目多，只是 $\text{ICPC}$ 沒有部分分。在前一週有全國模擬賽，我拿了 $377.5$ 分，有點慘，不過很神奇的在第五名。

$12/16$ 我們從建中出發，搭火車到新竹，然後有接駁車載我們到清大，一開始是開幕典禮、測機，然後我們就去飯店吃晚餐了，晚餐好多海鮮，吃不了，所以我在晚餐後另外去便利商店買。

$12/17$ 早餐吃飯店的自助餐，吃完就到考場，這次考試有好多東西要設置，像是螢幕要調黑色風格、夜間光線，然後還要用 $\text{terminal}$ 把螢幕亮度調到 $0.8$ 倍，$\text{codeblocks}$ 要改字體、改編譯器的東西，還要打 $\text{default code}$。

接下來我一題一題講我的解法：

題本連結

$\text{pA. 基地駐守 (base)}$

$0/100$：我的想法是做完全點對最短路後去 $\text{random}$ 一些東西，但一直都拿不到分。

$\text{Code：}$

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout<<"["<<#HEHE<<"] : ",dout(HEHE)
void dout(){cout<<'\n';}
template<typename T,typename...U>
void dout(T t,U...u){cout<<t<<(sizeof...(u)?", ":""),dout(u...);}
#else
#define debug(...) 7122
#endif

//#define int long long
#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a,I=b;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

mt19937 seed (time (NULL));
#define rnd(l,r) uniform_int_distribution<int>(l,r)(seed)

const int INF = 1e9;
const int SIZE = 505;

int n, m, s, x;
int w[SIZE], dis[SIZE][SIZE];
vector<tuple<int, int, int>> ans;
double point = 0;

int nk, nx;
int nw[SIZE], is[SIZE], vs[SIZE];

double power (double d, int up) {
    double re = 1;
    if (up < 0) up = -up, d = 1 / d;
    while (up) {
        if (up & 1) re = re * d;
        d = d * d;
        up >>= 1;
    }
    return re;
}

void work() {
    FOR (i, 1, n) {
        is[i] = 0;
        nw[i] = w[i];
        vs[i] = 0;
    }
    int X = rnd (x - 50, x), mx = 0;

    vector<tuple<int, int, int>> re;
    set<pair<int, int>> id;
    FOR (i, 1, n) id.emplace (nw[i], i);

    auto upd = [&] (int f, int i, int x) {
        if (x > 0) re.pb (f, i, x);
        else re.pb (i, f, -x);
        if (!vs[i]) {
            auto it = id.lower_bound ({nw[i], i});
            id.erase (it);
        }
        nw[i] += x;
        if (!vs[i]) id.emplace (nw[i], i);
    };

    while (id.size()) {
        auto [num, i] = *id.rbegin();
        vs[i] = 1;
        id.erase ({num, i});
        if (num == s) {
            is[i] = 1;
            continue;
        }
        int &val = nw[i];
        for (int j = 1; j <= n && val != s; j++) if (i != j && !is[j] && dis[i][j] <= X) {
            if (clock() > 60 * CLOCKS_PER_SEC / 100) return;
            if (val > s) {
                upd (i, j, val - s);
                val = s;
                mx = max (mx, dis[i][j]);
            } else {
                int delta = min (s - val, nw[j]);
                if (delta) {
                    upd (i, j, -delta);
                    val += delta;
                    mx = max (mx, dis[i][j]);
                }
            }
        }
        if (val == s) {
            is[i] = 1;
        }
    }
    int cnt = 0;
    FOR (i, 1, n) cnt += is[i];
    double np = 1 / (power (1.50, cnt) * power (3.00, min (0, mx - x)));
    if (np > point) {
        nk = cnt;
        nx = mx;
        point = np;
        ans = re;
    }

    //debug (cnt, mx, np);
}

void solve() {
    cin >> n >> m >> s >> x;
    FOR (i, 1, n) cin >> w[i], nk += w[i] == x;

    FOR (i, 1, n) {
        fill (dis[i], dis[i] + n + 1, INF);
        dis[i][i] = 0;
    }
    while (m--) {
        int a, b;
        cin >> a >> b;
        dis[a][b] = dis[b][a] = 1;
    }
    FOR (k, 1, n) FOR (i, 1, n) FOR (j, 1, n) dis[i][j] = min (dis[i][j], dis[i][k] + dis[k][j]);

    for (int t = 1; clock() <= 60 * CLOCKS_PER_SEC / 100; t++) {
        work();
    }
    //debug (point);
    cout << nk << ' ' << nx << ' ' << ans.size() << '\n';
    for (auto [a, b, c] : ans) cout << a << ' ' << b << ' ' << c << '\n';
}

int32_t main() {
    Waimai;
    solve();
}

$\text{pB. 自行車歸位 (bicycle)}$

$36/100$：我只有想到 $O(nm)$ 的 $\text{dp}$，可以先排序好後設 $\text{dp}_{i, j}$ 為把 $a_1\sim a_i$ 放到 $b_1\sim b_j$ 的最小值，$\text{dp}_{i, j} = \min (\text{dp}_{i, j - 1}, \text{dp}_{i - 1, j - 1} + \text{abs} (a_i - b_j))$。

$\text{Code：}$

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout<<"["<<#HEHE<<"] : ",dout(HEHE)
void dout(){cout<<'\n';}
template<typename T,typename...U>
void dout(T t,U...u){cout<<t<<(sizeof...(u)?", ":""),dout(u...);}
#else
#define debug(...) 7122
#endif

#define int long long
#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a,I=b;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int INF = 1e18;
const int SIZE = 2005;

int n, m;
int a[SIZE], b[SIZE];
int dp[SIZE][SIZE], to[SIZE][SIZE];

void solve() {
    cin >> n >> m;
    FOR (i, 1, n) cin >> a[i];
    FOR (i, 1, m) cin >> b[i];
    sort (a + 1, a + n + 1);
    sort (b + 1, b + m + 1);

    FOR (i, 1, n) fill (dp[i], dp[i] + m + 1, INF);
    FOR (i, 1, n) FOR (j, i, m) {
        dp[i][j] = dp[i][j - 1];
        to[i][j] = to[i][j - 1];
        int val = dp[i - 1][j - 1] + abs (a[i] - b[j]);
        if (val < dp[i][j]) {
            dp[i][j] = val;
            to[i][j] = j;
        }
    }
    cout << dp[n][m] << '\n';

    FOR (i, 1, n) FOR (j, 1, m) cout << dp[i][j] << " \n"[j == m];

    vector<pair<int, int>> ans;
    for (int i = n, j = m; i >= 1; i--) {
        int p = to[i][j];
        ans.pb (a[i], b[p]);
        j = p - 1;
    }
    for (auto [x, y] : ans) cout << x << ' ' << y << '\n';
}

int32_t main() {
    Waimai;
    solve();
}

$\text{pC. 卡牌 (card)}$

$100/100$：這題是區間 $\text{dp}$，令 $\text{dp}_{l, r}$ 為 $l\sim r$ 區間的最大值，可以由 $\text{dp}_{l, r - 1}, \text{dp}_{l + 1, r}$ 轉移，複雜度 $O(n^2)$。

$\text{Code：}$

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout<<"["<<#HEHE<<"] : ",dout(HEHE)
void dout(){cout<<'\n';}
template<typename T,typename...U>
void dout(T t,U...u){cout<<t<<(sizeof...(u)?", ":""),dout(u...);}
#else
#define debug(...) 7122
#endif

#define int long long
#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a,I=b;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1005;

int n;
int a[SIZE];
int dp[SIZE][SIZE];

void solve() {
    cin >> n;
    FOR (i, 1, n) cin >> a[i], a[i] /= 10;
    FOR (i, 1, n) dp[i][i] = (n + 9) * a[i];
    FOR (len, 2, n) for (int l = 1, r = len; r <= n; l++, r++) {
        dp[l][r] = max (dp[l][r], dp[l][r - 1] + (n - len + 10) * a[r]);
        dp[l][r] = max (dp[l][r], dp[l + 1][r] + (n - len + 10) * a[l]);
    }
    cout << dp[1][n] << '\n';
}

int32_t main() {
    Waimai;
    solve();
}

$\text{pD. 文字編輯器 (editor)}$

$100/100$：可以發現兩個 $x$ 間一定至少要有一個 $+$，所以可以找到中間沒有 $+$ 的兩個 $x$，然後可以計算括號數量用數學推出來 $+$ 要放哪裡。

$\text{Code：}$

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout<<"["<<#HEHE<<"] : ",dout(HEHE)
void dout(){cout<<'\n';}
template<typename T,typename...U>
void dout(T t,U...u){cout<<t<<(sizeof...(u)?", ":""),dout(u...);}
#else
#define debug(...) 7122
#endif

//#define int long long
#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a,I=b;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1e6 + 5;

int n;
string s;
int pre[SIZE];
vector<int> p;

void solve() {
    cin >> s;
    n = s.size();
    s = " " + s;
    p.clear();
    FOR (i, 1, n) {
        pre[i] = pre[i - 1];
        if (s[i] == 'x') p.pb (i);
        if (s[i] == '|') pre[i]++;
    }
    FOR (i, 1, p.size() - 1) {
        int l = p[i - 1] + 1, r = p[i] - 1;
        if (r - l + 1 == pre[r] - pre[l - 1]) {
            int num = 1, x = 0, y = 0;
            FOR (j, 1, p[i - 1]) {
                if (s[j] == 'x' || s[j] == '+') num = -num;
                else x += num;
            }
            num = 1;
            for (int j = n; j >= p[i]; j--) {
                if (s[j] == 'x' || s[j] == '+') num = -num;
                else y += num;
            }
            int len = r - l + 1;
            int xl = (x - y + len - 1) / 2;
            debug (x, y, xl);
            s[p[i - 1] + xl + 1] = '+';
            break;
        }
    }
    int num = 1;
    FOR (i, 1, n) {
        if (s[i] == '|') cout << (num == 1 ? '[' : ']');
        else {
            num = -num;
            cout << s[i];
        }
    }
    cout << '\n';
}

int32_t main() {
    Waimai;
    int tt;
    cin >> tt;
    while (tt--) solve();
}

$\text{pE. 齒輪組 (gears)}$

$100/100$：紀錄每個齒輪 $2,3$ 的次數再用連接方式去推下一個就好了。

$\text{Code：}$

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout<<"["<<#HEHE<<"] : ",dout(HEHE)
void dout(){cout<<'\n';}
template<typename T,typename...U>
void dout(T t,U...u){cout<<t<<(sizeof...(u)?", ":""),dout(u...);}
#else
#define debug(...) 7122
#endif

#define int long long
#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a,I=b;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 25;

int n;
int dir[SIZE], two[SIZE], three[SIZE];
int con[SIZE];
int s2[SIZE], s3[SIZE];

void solve() {
    cin >> n;
    FOR (i, 1, n) {
        int x, y;
        cin >> x >> y;
        if (x == 2) two[i] = y;
        else three[i] = y;
    }
    FOR (i, 2, n) cin >> con[i];
    FOR (i, 2, n) {
        dir[i] = dir[i - 1];
        if (con[i] == 1) dir[i] ^= 1;
    }

    FOR (i, 2, n) {
        if (con[i] == 2) s2[i] = s2[i - 1], s3[i] = s3[i - 1];
        else {
            int x = s2[i - 1] + two[i - 1] - two[i];
            int y = s3[i - 1] + three[i - 1] - three[i];
            s2[i] = x, s3[i] = y;
        }
    }
    cout << (dir[n] == 0 ? 1 : -1) << ' ' << s2[n] << ' ' << s3[n] << '\n';
}

int32_t main() {
    Waimai;
    solve();
}

$\text{pF. 百萬刮刮樂 (scratchcard)}$

$100/100$：把式子移一下可以發現 $(W_x-A_x,W_x-B_x,W_x-C_x)\leq (A_y-W_y,B_y-W_y,C_y-W_y)$，這就很像在問你三維偏序，可以用三個 $\text{vector}$ 存每種錢的 $a,b,c$，然後一組一組去做，要注意同一組時要扣掉自己跟自己的，複雜度 $O(n\times\log^2(n))$。

$\text{Code：}$

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout<<"["<<#HEHE<<"] : ",dout(HEHE)
void dout(){cout<<'\n';}
template<typename T,typename...U>
void dout(T t,U...u){cout<<t<<(sizeof...(u)?", ":""),dout(u...);}
#else
#define debug(...) 7122
#endif

//#define int long long
#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a,I=b;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int money[3] = {1000000, 2000000, 3000000};
const int INF = 1e9;
const int SIZE = 2e5 + 5;

int n;
ll ans;
vector<int> lis;
vector<tuple<int, int, int>> v[3];
int bit[SIZE];

void upd (int pos, int x) {
    for (; pos; pos -= pos & -pos) bit[pos] += x;
}

int que (int pos) {
    int re = 0;
    for (; pos <= n; pos += pos & -pos) re += bit[pos];
    return re;
}

void divide (vector<tuple<int, int, int, int>> &v, int l, int r) {
    if (l >= r) return;

    r -= l, l = 0;

    int mid = (l + r) / 2;
    vector<tuple<int, int, int, int>> vl, vr;
    FOR (i, 0, mid) vl.pb (v[i]);
    FOR (i, mid + 1, v.size() - 1) vr.pb (v[i]);
    v.clear();
    divide (vl, l, mid);
    divide (vr, mid + 1, r);

    int p1 = 0, p2 = 0;
    while (p1 < vl.size() || p2 < vr.size()) {
        int ty;
        if (p2 == vr.size()) ty = 0;
        else if (p1 == vl.size()) ty = 1;
        else if (get<0> (vl[p1]) >= get<0> (vr[p2])) ty = 0;
        else ty = 1;

        if (ty == 0) {
            auto [b, c, t, a] = vl[p1];
            v.pb (vl[p1]);
            p1++;
            if (t == 1) {
                int p = lower_bound (lis.begin(), lis.end(), c) - lis.begin() + 1;
                upd (p, 1);
            }
        } else {
            auto [b, c, t, a] = vr[p2];
            v.pb (vr[p2]);
            p2++;
            if (t == 0) {
                int p = lower_bound (lis.begin(), lis.end(), c) - lis.begin() + 1;
                ans += que (p);
            }
        }
    }
    FOR (i, 0, vl.size() - 1) {
        auto [b, c, t, a] = vl[i];
        if (t == 1) {
            int p = lower_bound (lis.begin(), lis.end(), c) - lis.begin() + 1;
            upd (p, -1);
        }
    }
}

bool ok (int g1, int g2) {
    ans = 0;
    if (g1 == g2) {
        for (auto [a, b, c] : v[g1]) {
            if (min ({a, b, c}) >= money[g1]) ans--;
        }
    }
    vector<tuple<int, int, int, int>> vv;
    int w = money[g1];
    for (auto [a, b, c] : v[g1]) {
        vv.pb (w - b, w - c, 0, w - a);
    }
    w = money[g2];
    lis.clear();
    for (auto [a, b, c] : v[g2]) {
        vv.pb (b - w, c - w, 1, a - w);
        lis.pb (c - w);
    }
    sort (vv.begin(), vv.end(), [] (auto A, auto B) {
        return get<3> (A) != get<3> (B) ? get<3> (A) > get<3> (B) : get<2> (A) > get<2> (B);
    });
    sort (lis.begin(), lis.end());
    lis.erase (unique (lis.begin(), lis.end()), lis.end());
    divide (vv, 0, (int) vv.size() - 1);
    return ans > 0;
}

const int MAX = 1e6;

void solve() {
    cin >> n;
    FOR (t, 1, n) {
        int w, a, b, c;
        int da, db, dc;
        cin >> w >> a >> b >> c;
        int p;
        FOR (i, 0, 2) if (w == money[i]) p = i;
        v[p].pb (a, b, c);
    }
    set<int> s;
    FOR (i, 0, 2) FOR (j, i, 2) {
        if (ok (i, j)) s.insert (money[i] + money[j]);
    }
    cout << s.size() << '\n';
    for (int x : s) cout << x << '\n';
}

int32_t main() {
    Waimai;
    solve();
}

$\text{pG. 算樹 (tree)}$

$27/100$：可以發現 $3\sim n$ 的排列一定可以做出來，所以直接計算階乘就好了。

$51/100$：暴力枚舉 $\text{Prufer code}$，我的做法是用一個 $\text{pq}$ 找目前最小葉節點，複雜度 $O(n^{n-1}\times\log(n))$。

$100/100$：我最後發現每個數字在 $\text{Prufer code}$ 裡出現的次數會是它的度數 $-1$，而且一定可以構造出一棵樹，所以可以用到排列組合和 $ \frac{(\sum a_i+\sum b_i)!}{\prod a_i!\prod b_i!}=\frac{(\sum a_i)!}{\prod a_i!}\times\frac{(\sum b_i)!}{\prod b_i!}\times C_{\sum a_i}^{\sum a_i+\sum b_i}$，先把前綴、後綴和積建好，之後枚舉數字，就可以知道現在該選哪個，複雜度 $O(n^2)$。

$\text{Code：}$

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout<<"["<<#HEHE<<"] : ",dout(HEHE)
void dout(){cout<<'\n';}
template<typename T,typename...U>
void dout(T t,U...u){cout<<t<<(sizeof...(u)?", ":""),dout(u...);}
#else
#define debug(...) 7122
#endif

#define int long long
#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a,I=b;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int INF = 2e9;
const int SIZE = 1005;

int n, k;
int d[SIZE];
int C[SIZE][SIZE];
int pre[SIZE], suf[SIZE];
int prep[SIZE], sufp[SIZE];

void solve() {
    cin >> n >> k;
    FOR (i, 1, n) cin >> d[i];
    FOR (i, 1, n) d[i]--;
    C[0][0] = 1;
    FOR (i, 1, n) {
        C[i][0] = 1;
        FOR (j, 1, i) C[i][j] = min (INF, C[i - 1][j - 1] + C[i - 1][j]);
    }

    k--;
    int pro = 1;
    for (int i = 1, m = 0; i <= n; i++) {
        m += d[i];
        pro = min (INF, pro * C[m][d[i]]);
    }
    debug (k, pro);
    if (k >= pro) {
        cout << "-1\n";
        return;
    }

    vector<int> ans;
    FOR (t, 1, n - 2) {
        prep[0] = sufp[n + 1] = 1;
        FOR (i, 1, n) {
            pre[i] = pre[i - 1] + d[i];
            prep[i] = min (INF, prep[i - 1] * C[pre[i]][d[i]]);
        }
        for (int i = n; i >= 1; i--) {
            suf[i] = suf[i + 1] + d[i];
            sufp[i] = min (INF, sufp[i + 1] * C[suf[i]][d[i]]);
        }
        bool f = 0;
        FOR (i, 1, n) if (d[i]) {
            int val = min (INF, prep[i - 1] * sufp[i + 1]);
            val = min (INF, val * C[pre[i - 1] + suf[i + 1]][pre[i - 1]]);
            val = min (INF, val * C[n - 2 - t][pre[i - 1] + suf[i + 1]]);
            debug (i, k, val);
            if (k >= val) k -= val;
            else {
                debug (t, i);
                d[i]--;
                ans.pb (i);
                f = 1;
                break;
            }
        }
        if (!f) {
            cout << "-1\n";
            return;
        }
    }
    for (int x : ans) cout << x << '\n';
}

int32_t main() {
    Waimai;
    solve();
}

$\text{pH. 城市規劃 (ussr)}$

$4/100$：可以直接把每個點排成一圈，然後連左右的就好了。

$35/100$：我這樣子構，挑出四個點放到外側，然後內側放兩行。

$\text{Code：}$

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout<<"["<<#HEHE<<"] : ",dout(HEHE)
void dout(){cout<<'\n';}
template<typename T,typename...U>
void dout(T t,U...u){cout<<t<<(sizeof...(u)?", ":""),dout(u...);}
#else
#define debug(...) 7122
#endif

#define int long long
#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a,I=b;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 105;

int n, k;

void solve() {
    cin >> n >> k;
    if (k == 0) {
        if (n == 1) {
            cout << "0 0\n\n";
        } else {
            cout << "-1\n";
        }
        return;
    }
    if (k >= n || n * k % 2 != 0) {
        cout << "-1\n";
        return;
    }
    if (n == 2 && k == 1) {
        cout << "0 0\n";
        cout << "1 0\n";
        cout << "2\n";
        cout << "1\n";
        return;
    }
    if (k == 1) {
        cout << "-1\n";
        return;
    }
    if (k == 2) {
        FOR (i, 1, n - 1) cout << "0 " << i << '\n';
        cout << "1 " << n << '\n';
        FOR (i, 1, n) {
            int l = i - 1, r = i + 1;
            if (l <= 0) l += n;
            if (r > n) r -= n;
            cout << l << ' ' << r << '\n';
        }
        return;
    }
    if (n == 4 && k == 3) {
        cout << "0 0\n1 1\n0 2\n10 2\n";
        FOR (i, 1, n) {
            FOR (j, 1, n) if (i != j) cout << j << ' ';
            cout << '\n';
        }
        return;
    }
    if (k == 3) {
        cout << "3 1\n";
        FOR (i, 2, n / 2 - 1) cout << "2 " << i << '\n';
        cout << "3 " << n / 2 << '\n';
        cout << "0 " << 1 << '\n';
        FOR (i, n / 2 + 2, n - 1) cout << "1 " << i - n / 2 << '\n';
        cout << "0 " << n / 2 << '\n';

        cout << "2 " << n / 2 << ' ' << n / 2 + 1 << '\n';
        FOR (i, 2, n / 2 - 1) cout << i - 1 << ' ' << i + 1 << ' ' << i + n / 2 << '\n';
        cout << n / 2 - 1 << ' ' << "1 " << n << '\n';
        cout << n / 2 + 2 << ' ' << "1 " << n << '\n';
        FOR (i, n / 2 + 2, n - 1) cout << i - 1 << ' ' << i + 1 << ' ' << i - n / 2 << '\n';
        cout << n - 1 << ' ' << n / 2 + 1 << ' ' << n / 2 << '\n';
        return;
    }
}

int32_t main() {
    Waimai;
    solve();
}

$\text{pI. 聖誕燈飾 (xmas)}$

$100/100$：直接做就好，複雜度 $O(n\times\log(n))$。

$\text{Code：}$

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout<<"["<<#HEHE<<"] : ",dout(HEHE)
void dout(){cout<<'\n';}
template<typename T,typename...U>
void dout(T t,U...u){cout<<t<<(sizeof...(u)?", ":""),dout(u...);}
#else
#define debug(...) 7122
#endif

//#define int long long
#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a,I=b;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1e6 + 5;

int n, m;
int a[SIZE], b[SIZE];

void solve() {
    cin >> n >> m;
    FOR (i, 1, n) cin >> a[i], a[i]--;
    FOR (i, 1, n) cin >> b[i], b[i]--;
    FOR (i, 1, n) {
        int add = (b[i] - a[i] + m) % m;
        cout << add << '\n';
        for (int j = i; j <= n; j += i) {
            a[j] += add;
            if (a[j] >= m) a[j] -= m;
        }
    }
}

int32_t main() {
    Waimai;
    solve();
}

心得：我前面好像很快就把簡單題寫好了，看到 $\text{pF}$，知道是三維偏序，但是 $\text{debug}$ 很久，那裡的程式執行視窗我不知道怎麼貼上東西，導致要一直自己手打輸入。再來我一開始以為 $\text{pD,pG}$ 會是很難的題，我到比賽後半段才去碰它們，$\text{pD}$ 觀察一下後發現超好寫，$\text{pG}$ 只有先寫出第二子題，然後 $\text{pA}$ 花了滿久時間去寫，但一分都沒拿到。最後我大概在 $622$ 分的時候就想說我拿不到分數了，所以我就出去吃一下東西，回來看到 $\text{pG}$，發現一個東西，想一想就突然知道題目要問什麼了，然後在前幾年的 $\text{TOI}$ 初選有考過類似的東西，我大概知道要怎麼寫，可是這時時間只剩下 $20$ 分鐘了，我要把一堆數學的東西刻好，過程中錯誤一堆，但很神奇的是一下就找到錯在哪裡了，更神奇的是竟然過範測了，這時加上比賽延長的 $2$ 分鐘，我剩的時間只剩下 $2$ 分多鐘了，很驚險的是上傳之後就過了，然後上傳的時間是 $4:59:11$。賽後聽別人說 $\text{pH}$ 是奇怪數學題，然後 $\text{pA}$ 沒有人會做，$\text{pB}$ 好像沒想像的那麼難。

最後我拿到 $671$ 分 (計分板)，並列三個第一，不過我是三個裡最晚拿到分數的，最終結果是一等獎，我有點不敢相信，因為我去年連北市賽三等獎都沒有。然後進了前十名代表不用考初選了，好開心。

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$ 歡迎追蹤！

搜尋此網誌

Caido Coding Blog

2022 全國賽心得

留言

張貼留言

熱門文章

110年建中科學班心得