ICPC Thailand National competition 2024
===
比賽鏈結
---
https://codeforces.com/gym/105335/

比賽影片
---
{%youtube nioZbhBBZ-U %}

記分板
---
賽中成績 6/14 (如果大哥不黑至少 7/14)

題解
---
### A. Auntie's Magical Cake
---
#### 題目摘要

你有$N$個蛋糕，初始的美味度為0。你能吃一個蛋糕的條件為，它不在邊緣且它左右的蛋糕還未被吃。當蛋糕被吃時，你會獲得那塊蛋糕的美味度，你會向左右的蛋糕增加美味度直到碰到被吃過的蛋糕，並且增加的美味度為與目前被吃掉的蛋糕的距離，在最後你可以獲得剩下蛋糕的美味度，求你能獲得的最大美味度
#### 想法
感性證明不會有被吃掉的蛋糕中間有3個蛋糕，所以就設$dp_i$為做到第$i$個且第$i$個蛋糕有被吃的最大美味度為何就好
:::spoiler 實作

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int N=1e6+10;
ll dp[N];
 
ll calc(ll x){
    return x*(x+1)>>1;
}
 
int main(){
    int n;
    cin >> n;
    if (n==1||n==2){
        cout << 0 << '\n';
        return 0;
    }
    dp[0]=dp[1]=0;
    for(int i=2;i<n;i++){
        if (i>=2) dp[i]=max(dp[i], dp[i-2]+1+calc(n-i));
        if (i>=3) dp[i]=max(dp[i], dp[i-3]+3+calc(n-i));
    }
    cout << max(dp[n-1], dp[n-2]) << '\n';
}

:::

### B. Back in the Day
----
#### 題目摘要

給你一串數字代表按電話的次數，求最短字典序最小的字串

#### 想法

水題，greedy用最小長度構字串

:::spoiler 實作

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

#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define pb push_back

string mp[8] = {{"abc"}, {"def"}, {"ghi"}, {"jkl"}, {"mno"}, {"pqrs"}, {"tuv"}, {"wxyz"}};

int main() {
    string s; cin >> s;
    int n = s.size();
    int cnt = 1;
    vector<pair<int, int>> ans;
    rep (i, 1, n) {
        if (s[i] == s[i - 1]) cnt++;
        else {
            ans.pb({s[i - 1] - '2', cnt});
            cnt = 1;
        }
    }
    ans.pb({s[n - 1] - '2', cnt});
    for (auto [a, b] : ans) {
        int res = b % mp[a].size();
        if (res) cout << mp[a][res - 1];
        int hehe = 0;
        b -= res;
        rep (i, 0, b / mp[a].size()) {
            cout << mp[a].back();
        }
    }
}

:::

### C. Cattering
---
#### 題目摘要

$N$隻貓對$M$個貓糧做匹配，最大化每隻貓能匹配到貓糧的最小滿足度並構造解

#### 想法

對答案二分搜，check跑maxflow找最大匹配，最後隨便輸出解

:::spoiler 實作

#pragma GCC optimize("Ofast, no-stack-protector")
// #pragma GCC target("popcnt, abm, mmx, avx, arch=skylake")
#include<bits/stdc++.h>
using namespace std;

#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define pb push_back
#define all(x) (x).begin(), (x).end()

const int IINF = 1e9 + 7;

struct Dinic {
    struct edge {
        int v, r; ll rc;
    };
    vector<vector<edge>> adj;
    vector<int> dis, it;
    Dinic(int n) : adj(n), dis(n), it(n) {}

    void add_edge(int u, int v, ll c) {
        adj[u].pb({v, adj[v].size(), c});
        adj[v].pb({u, adj[u].size() - 1, 0});
    }

    bool bfs(int s, int t) {
        fill(all(dis), IINF);
        queue<int> q;
        q.push(s);
        dis[s] = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto [v, r, rc] : adj[u]) {
                if (dis[v] < IINF || rc == 0) continue;
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
        return dis[t] < IINF;
    }

    ll dfs(int u, int t, ll cap) {
        if (u == t || cap == 0) return cap;
        for (int &i = it[u]; i < adj[u].size(); ++i) {
            auto &[v, r, rc] = adj[u][i];
            if (dis[v] != dis[u] + 1) continue;
            ll tmp = dfs(v, t, min(cap, rc));
            if (tmp > 0) {
                rc -= tmp;
                adj[v][r].rc += tmp;
                return tmp;
            }
        }
        return 0;
    }

    ll flow(int s, int t) {
        ll ans = 0, tmp;
        while (bfs(s, t)) {
            fill(all(it), 0);
            while ((tmp = dfs(s, t, IINF)) > 0) {
                ans += tmp;
            }
        }
        return ans;
    }

};

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    int n, m; cin >> n >> m;
    vector a(n, vector<int>(m));
    int l = IINF, r = 0;
    rep (i, 0, n) rep (j, 0, m) {
        cin >> a[i][j];
        l = min(l, a[i][j]);
        r = max(r, a[i][j]);
    }
    r++;
    while (r - l > 1) {
        int mid = l + r >> 1;
        Dinic G(n + m + 2);
        int s = n + m, t = s + 1;
        rep (i, 0, n) G.add_edge(s, i, 1);
        rep (i, 0, m) G.add_edge(n + i, t, 1);
        rep (i, 0, n) rep (j, 0, m) if (a[i][j] >= mid) {
            G.add_edge(i, n + j, 1);
        }
        ll f = G.flow(s, t);
        if (f == n) l = mid;
        else r = mid;
    }
    cout << l << '\n';
    Dinic G(n + m + 2);
    int s = n + m, t = s + 1;
    rep (i, 0, n) G.add_edge(s, i, 1);
    rep (i, 0, m) G.add_edge(n + i, t, 1);
    rep (i, 0, n) rep (j, 0, m) if (a[i][j] >= l) {
        G.add_edge(i, n + j, 1);
    }
    ll f = G.flow(s, t);
    rep (i, 0, n) {
        for (auto [v, r, rc] : G.adj[i]) if (v != s && rc == 0) {
            cout << v - n + 1 << ' ';
            break;
        }
    }
}

:::

### D. Disinfection Patch
---
#### 題目摘要
給$N$個清潔劑以及$N$個細菌的座標，找到一組$(S, X, Y)$使得清潔劑$(x, y)$的座標變$(S \times x+X, S \times y+Y)$能夠一一對應到所有細菌點
#### 想法

對清潔劑和細菌座標sort後就能直接$O(N)$判對應點了，$N$不知道為啥給了$N^2$量級，怪題，但我們賽中被騙實作了$N^2 \log N$把清潔劑對每個細菌判斷一次

:::spoiler 實作

#pragma GCC optimize("Ofast, no-stack-protector")
// #pragma GCC target("popcnt, abm, mmx, avx, arch=skylake")
#include<bits/stdc++.h>
using namespace std;

#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define pll pair<ll, ll>
#define F first
#define S second

const int IINF = 1e9 + 7;

pll operator + (pll a, pll b) {
    return {a.first + b.first, a.second + b.second};
}

pll operator - (pll a, pll b) {
    return {a.first - b.first, a.second - b.second};
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    int n; cin >> n;
    vector<pll> din(n), bac(n);
    for (auto &[x, y] : din) cin >> x >> y;
    for (auto &[x, y] : bac) cin >> x >> y;
    sort(all(din));
    sort(all(bac));
    if (bac[0] == bac.back()) {
        cout << 0 << ' ' << bac[0].F << ' ' << bac[0].S << '\n';
        exit(0);
    }
    vector<pll> vin;
    rep (i, 1, n) {
        vin.pb(din[i] - din[0]);
    }
    auto dis = [&](pll x) -> ll {
        return x.F * x.F + x.S * x.S;
    };
    sort(all(vin));
    rep (i, 0, n) {
        vector<pll> bin;
        rep (j, 0, n) if (i != j) bin.pb(bac[j] - bac[i]);
        sort(all(bin));
        pll z = {0, 0};
        int st = 0;
        while (st < n - 1 && bin[st] == z && vin[st] == z) {
            st++;
        }
        if (bin[st] == z || vin[st] == z) continue;
        if (vin[st].F == 0) {
            if (bin[st].S % vin[st].S != 0) continue;
            ll s = bin[st].S / vin[st].S;
            bool f = 1;
            rep (j, st, n - 1) {
                if (bin[j].F != vin[j].F * s || bin[j].S != vin[j].S * s) f = 0;
            }
            if (f && s >= 0) {
                cout << s << ' ';
                din[st].F *= s;
                din[st].S *= s;
                cout << bac[i].F - din[st].F << ' ' << bac[i].S - din[st].S << '\n';
                exit(0);
            }
            continue;
        }
        if (vin[st].S == 0) {
            if (bin[st].F % vin[st].F != 0) continue;
            ll s = bin[st].F / vin[st].F;
            bool f = 1;
            rep (j, st, n - 1) {
                if (bin[j].F != vin[j].F * s || bin[j].S != vin[j].S * s) f = 0;
            }
            if (f && s >= 0) {
                cout << s << ' ';
                din[st].F *= s;
                din[st].S *= s;
                cout << bac[i].F - din[st].F << ' ' << bac[i].S - din[st].S << '\n';
                exit(0);
            }
            continue;
        }
        if (bin[st].F % vin[st].F != 0 || bin[st].S % vin[st].S != 0) continue;
        ll s = bin[st].F / vin[st].F;
        if (bin[st].S / vin[st].S != s) continue; 
        bool f = 1;
        rep (j, st, n - 1) {
            if (bin[j].F != vin[j].F * s || bin[j].S != vin[j].S * s) f = 0;
        }
        if (f && s >= 0) {
            cout << s << ' ';
            din[0].F *= s;
            din[0].S *= s;
            cout << bac[i].F - din[0].F << ' ' << bac[i].S - din[0].S << '\n';
            exit(0);
        }
    }
    cout << -1 << '\n';
}

:::

### E. Executive's Holidays
---
#### 題目摘要

有$n$個人、$t$天，每一天規定要最少要$a_i$個人上班，求最大$\sum\limits_{i = 1}^n$(第$i$人最長連續休假時間)

#### 想法

將$a_i$限制反過來用n去扣掉，變成每天最多能有幾個人休息。

將天數當x軸每天最大休息人數當y軸畫長條圖，可以想到一個很好的greedy作法：
每次將最長的連續一條給一個人，刪掉那行後再做一樣的事。
更進一步的，可以直接想成切成一塊一塊目前最大長度可以到的最高矩形。
注意到每塊矩形的上界至少會對應到一個柱狀圖的頂端，因此矩形數量不會超過T個！

如此一來我們只需要知道每個舉行的長寬，對寬從大到小排序後取到剛好n個高就好，但要如何好好的算出矩形呢？

可以考慮從左往右掃用單調棧來維護，需要維護的是一個高度嚴格遞增的序列，對於同樣高度我們會想去維護最左端的那個。若出現下降的會需要去好好比對現在這個跟棧的前前一個的高度，總之就是把頂端取高的畫一條橫線切出矩形的感覺。

:::spoiler 實作

#pragma GCC optimize("Ofast, no-stack-protector")
// #pragma GCC target("popcnt, abm, mmx, avx, arch=skylake")
#include<bits/stdc++.h>
using namespace std;

#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define F first
#define S second

const int IINF = 1e9 + 7;

void solve() {
    int n, t; cin >> t >> n;
    vector<int> a(n + 1);
    rep (i, 0, n) {
        cin >> a[i];
        a[i] = t - a[i];
    }
    a[n] = 0;
    vector<pii> st;
    st.pb({-1, 0});
    vector<pii> rec;
    rep (i, 0, n + 1) {
        if (st.back().S < a[i]) {
            st.pb({i, a[i]});
            continue;
        }
        if (st.back().S == a[i]) continue;
        while (st.back().S > a[i]) {
            if (st.end()[-2].S < a[i]) {
                rec.pb({i - st.back().F, st.back().S - a[i]});
                st.back().S = a[i];
                break;
            } else {
                rec.pb({i - st.back().F, st.back().S - st.end()[-2].S});
            }
            st.pop_back();
        }
        if (st.back().S == a[i]) continue;
        st.pb({i, a[i]});
    }
    sort(all(rec), greater<pii>());
    int need = t;
    ll ans = 0;
    for (auto [w, h] : rec) {
        h = min(h, need);
        ans += 1LL * w * h;
        need -= h;
        if (need == 0) break;
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    solve();
}

:::

### F. Fill T
---
#### 題目摘要
給你$\,R \times C\,$的矩形，請你用T字形來構造填滿整個矩形
#### 想法
非常好構造實作題，先強制讓$\,R \leq C\,$，輸出時好好的x, y互換就好，中間多用函式避免搞重複咚咚
1. $R < 3$：一看就直接-1
2. $R = 3$：若C < 6就-1，否則如下圖，第二、五列那裡可以無限延長
3. $R = 4$：如下圖，右上左下固定後左右可以無限延長
4. $R = 5$：如下圖，第三列那裡可以無限延長

5. $R \geq 6$：如下圖，可以在左、右、下畫個T，使得R、C各少2，一直這樣做直到$R<6$套回之前的狀況

:::spoiler 實作

#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define ll long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define rep(X, a, b) for(int X = a; X < b; ++X)

void solve() {
    int r, c; cin >> r >> c;
    bool f = r > c;
    if (f) swap(r, c);
    if (r < 3) {
        cout << -1 << '\n';
        return;
    } 
    auto out = [&](vector<tuple<int, int, int, int, int, int>> &T) -> void {
        cout << T.size() << '\n';
        for (auto [x, y, u, l, d, r] : T) {
            if (f) {
                swap(x, y);
                swap(u, l);
                swap(d, r);
            }
            cout << x << ' ' << y << ' ' << u << ' ' << l << ' ' << d << ' ' << r << '\n';
        }
    };
    vector<tuple<int, int, int, int, int, int>> T;
    auto r3 = [&](int L, int R) -> void {
        T.pb({L, 2, 1, 0, 1, c - 5});
        T.pb({R - 2, 3, 1, c - 4, 0, 1});
        T.pb({R - 3, 1, 0, c - 5, 1, 2});
        T.pb({R, 2, 1, 1, 1, 0});
    };
    auto r4 = [&](int L, int R) -> void {
        T.pb({L, 2, 1, 0, 1, c - 3});
        T.pb({L + 1, 4, 1, 1, 0, c - 3});
        T.pb({R - 1, 1, 0, c - 3, 1, 1});
        T.pb({R, 3, 1, c - 3, 1, 0});
    };
    auto r5 = [&](int L, int R) -> void {
        T.pb({L + 1, 1, 0, 1, 1, c - 4});
        T.pb({L, 3, 1, 0, 1, c - 3});
        T.pb({L + 1, 5, 1, 1, 0, c - 3});
        T.pb({R - 1, 2, 1, c - 4, 1, 0});
        T.pb({R, 4, 3, c - 3, 1, 0});
    };
    if (r == 3) {
        if (c < 6) {
            cout << -1 << '\n';
            return;
        }
        r3(1, c);
        out(T);
        return;
    }
    if (r == 4) {
        r4(1, c);
        out(T);
        return;
    }
    if (r == 5) {
        r5(1, c);
        out(T);
        return;
    }
    if (r >= 6) {
        int L = 1, R = c, D = r;
        while (r >= 6) {
            T.pb({L, D - 1, D - 2, 0, 1, 1});
            T.pb({L + 2, D, 1, 1, 0, c - 4});
            T.pb({R, D - 1, D - 2, c - 4, 1, 0});
            L++, R--, D -= 2;
            r -= 2, c -= 2;
        }
        if (r == 4) r4(L, R);
        if (r == 5) r5(L, R);
        out(T);
        return;
    }
}
 
int main() {
    ZTMYACANESOCUTE;
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

:::

### G. Glory Road
---
#### 題目摘要
給三角形的3中點，求三頂點座標
#### 想法
列式看一下就好，注意一下輸出順序
:::spoiler 實作

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int N=1e6+10;
#define F first
#define S second
typedef pair<int,int> pii;
pii operator-(pii __, pii _){
    return {__.F-_.F,__.S-_.S};
}
pii operator+(pii __, pii _){
    return {__.F+_.F,__.S+_.S};
}
int main(){
    int n;
    pii A, B, C;
    cin >> A.F >> A.S >> B.F >> B.S >> C.F >> C.S;
    pii sum = A+B+C;
    B.F*=2;B.S*=2;
    A.F*=2;A.S*=2;
    C.F*=2;C.S*=2;
    pii a=sum-B;
    pii b=sum-C;
    pii c=sum-A;
    cout << a.F << ' ' << a.S << '\n' << b.F << ' ' << b.S << '\n' << c.F << ' ' << c.S;
}

:::

### H. Heavenly Sequence (待補)
---
#### 題目摘要

#### 想法

:::spoiler 實作

:::

### I. Ideal Permutation Pairing
---
#### 題目摘要
將長度為$N$的所有排列依字典序連成一個環，給其中一個排列，問它對面的排列是誰
#### 想法
不難發現題目就是要求我走$\frac{N}{2}\times (N-1)!$步後的排列為何，並且當走$(N-1)!$步時，只會將陣列中首項往下一個走，其餘位置的大小關係並不會變，因此只要找到首項在走$N!$後是誰，其餘再用剩餘的數字按照原本陣列的大小關係排就好，這樣能把$N$為偶數的狀況做完。而當$N$是奇數，可以拆成走$\lfloor\frac{N}{2}\rfloor\times(N-1)!+ \frac{N-1}{2}\times (N-2)!$，走$(N-2)!$時只要從找首項變成找頭兩項就好
:::spoiler 實作

#pragma GCC optimize("Ofast, no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define F first
#define S second

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i=0;i<n;i++) cin >> v[i];
    vector<int> rest;
    vector<pii> pos;
    int x=(v[0]+(n/2)-1+n)%n+1;
    for(int i=1;i<=n;i++) if (i!=x) rest.push_back(i);
    for(int i=1;i<n;i++) pos.push_back({v[i], i});
    sort(pos.begin(), pos.end());
    v[0]=x;
    for(int i=0;i<n-1;i++) v[pos[i].S]=rest[i];
    if (n&1){
        auto calc=[&](int x, int y)->pii {
            --x, --y;
            if (y>x) y--;
            y+=(n-1)/2;
            x+=(y/(n-1));
            y%=(n-1);
            if (x>(n-1)||((x==(n-1))&&(y==(n-1)))){
                x-=(n-1);
                y-=(n-1);
                if (y<0){
                    x--;
                    y+=(n-1);
                }
            }
            x++, y++;
            if (y>=x) y++;
            return {x, y};
        };
        auto [d1, d2]=calc(v[0], v[1]);
        rest.clear();
        for(int i=1;i<=n;i++) if (i!=d1&&i!=d2) rest.push_back(i);
        pos.clear();
        for(int i=2;i<n;i++) pos.push_back({v[i], i});
        sort(pos.begin(), pos.end());
        v[0]=d1, v[1]=d2;
        for(int i=0;i<n-2;i++) v[pos[i].S]=rest[i];
    }
    for(auto x:v) cout << x << ' ';
    cout << '\n';
}

:::

### J. Jewel Collection
---
#### 題目摘要
有$N$種寶石$C$種顏色，每種寶石有價值$v_i$，並且可以顯現自己其中一種顏色，有個富豪想炫富，他不只要收集所有顏色，還要讓總價值越大越好，問如果能的話，輸出最大總價值並輸出每個顏色應該選哪種寶石，否則輸出-1
#### 想法
注意到每種寶石最多只有兩種顏色 ，~~一看，哇!這不就圖論嗎?~~
把顏色當作點，只有一個顏色的寶石當作自環，兩個顏色的當作一條邊。只要每個點能對應到一條邊，再讓邊權最大就能得到答案，換句話說，就是要求最大生成水母圖，實作時注意自環就好
:::spoiler 實作

#pragma GCC optimize("Ofast, no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=2e5+10;
vector<pair<int, int>> v[N];
int in[N], res[N];
bool vis[N], used[N];

ll ans=0;
int dsu[N];
bool cyc[N];
int root(int x){return (dsu[x]==x)?x:dsu[x]=root(dsu[x]);}
void merge(int a, int b, ll w, int idx){
    int ra=root(a), rb=root(b);
    if ((cyc[ra]==1&&cyc[rb]==1)) return;
    if (ra==rb){
        if (cyc[ra]) return;
        ans+=w;
        cyc[ra]=1;
        v[a].push_back({b, idx});
        if (a!=b) v[b].push_back({a, idx});
        in[a]++;
        if (a!=b) in[b]++;
    }else{
        ans+=w;
        if (cyc[ra]==0) swap(ra, rb);
        dsu[rb]=ra;
        v[a].push_back({b, idx});
        v[b].push_back({a, idx});
        in[a]++, in[b]++;
    }
}

int main(){
    int n, c;
    cin >> n >> c;
    vector<tuple<int, int, int, int>> edg(n);
    for(int i=1;i<=c;i++) dsu[i]=i, cyc[i]=0;
    for(int i=0;i<n;i++){
        int t;
        cin >> t;
        auto &[c, a, b, idx]=edg[i];
        if (t==1){
            cin >> a;
            b=a;
        }else cin >> a >> b;
        cin >> c;
        idx=i+1;
    }
    sort(edg.begin(), edg.end(), greater<tuple<int, int, int, int>>());   
    for(auto [c, a, b, idx]:edg){
        merge(a, b, c, idx);
    }
    bool phlag=1;
    for(int i=1;i<=c;i++) phlag&=cyc[root(i)];
    if (!phlag){
        cout << -1 << '\n';
        return 0;
    }
    queue<int> q;
    for(int i=1;i<=c;i++) if (in[i]==1) q.push(i), vis[i]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(auto [e, idx]:v[x]) if (e==x||!vis[e]){
            if (used[idx]) continue;
            used[idx]=1;
            in[e]--;
            res[x]=idx;
            if (in[e]==1){
                q.push(e);
                vis[e]=1;
            }
        }
    }
    cout << ans << '\n';
    for(int i=1;i<=c;i++) if (!vis[i]){
        int j=i;
        do{
            int nex=-1;
            for(auto [k, idx]:v[j]) if (!vis[k]){
                if (used[idx]) continue;
                used[idx]=1;
                res[j]=idx;
                nex=k;
                vis[k]=1;
                break;
            }
            if (nex==-1) break;
            j=nex;
        }while(j!=i);
    }
    for(int i=1;i<=c;i++) cout << res[i] << ' ';
    cout << '\n';
}

:::

### K. Kid Rally
---
#### 題目摘要
給你$N\times M$的座標，每個座標有$S_{i,j}$的值，有兩個人會分別成$(1, 1), (1, M)$開始，他們只能每次往下走一層，並且兩人的路徑不能香蕉，他們可以隨時結束，或是直到走到最底，最大化兩人分別走過的路徑上的和的乘積

#### 想法
~~一看就知道是裸dp，但我被隊友黑了~~。可以設$dp_{i, j}$為走到第$i$列且左邊的人的和為$j$，右邊的人最大和為多少，可以列出轉移式$dp_{i, j}=max(dp_{i-1, j+d}+e)$，$d$和$e$是$0$到$9$，並且$d$的位置在$e$的左邊。然而這題允許一個人停止後另一人繼續走，因此只要存每列最大值的後綴和，在每做完一列的dp後，讓較小和的那人加上後下一列的後綴和就好。複雜度為$O(100N^2)$，壓一下常以免被TLE
:::spoiler 實作

#pragma GCC optimize("Ofast, no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> s(n, vector<int>(m));
    vector<vector<vector<bool>>> lr(n, vector<vector<bool>>(10, vector<bool>(10, 0)));
    vector<int> suf(n+1, 0);
    for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin >> s[i][j];
    int sum=0;
    for(int i=0;i<n;i++){
        vector<bool> pre(10, 0);
        int mx=0;
        for(int j=0;j<m;j++){
            for(int k=0;k<10;k++) if (pre[k]==1){
                lr[i][k][s[i][j]]=1;
            }
            pre[s[i][j]]=1;
            mx=max(mx, s[i][j]);
        }
        suf[i]=mx;
    }
    for(int i=n-1;~i;--i) suf[i]+=suf[i+1];
    ll ans=0;
    vector<int> dp(9001, -9001);
    dp[s[0][0]]=s[0][m-1];
    for(int j=0;j<=9;j++){
        ll a=j, b=dp[j];
        ans=max(ans, (a+suf[1])*b);
        ans=max(ans, a*(b+suf[1]));
    }
    for(int i=2;i<=n;i++) {
        vector<int> tmp(9001, -9001);
        for(int j=0;j<=i*9;j++) {
            for(int x=0;x<10;x++) for(int y=0;y<10;y++) if (lr[i-1][x][y]){
                if (j+x<=i*9) tmp[j+x]=max(tmp[j+x], dp[j]+y);
            }
        }
        dp.swap(tmp);
        for(int j=0;j<=i*9;j++){
            ll a=j, b=dp[j];
            ans=max(ans, (a+suf[i])*b);
            ans=max(ans, a*(b+suf[i]));
        }
    }
    cout << ans << '\n';
}

:::

### L. Lulu and Friends
---
#### 題目大綱
給你一個字串$T$，有$Q$筆詢問，每題詢問有一個字串$S$，問你最少需要刪減多少個$T$的字元使$S$成為$T$的子字串，不行輸出-1

#### 想法
注意到$\vert T\vert\le 20$，用位元枚舉就好
:::spoiler 實作

#include<bits/stdc++.h>
using namespace std;
 
map<string, int> mp;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    int n=s.size();
    for(int i=1;i<(1<<n);i++){
        string tmp;
        int l=-1, r=-1;
        for(int j=0;j<n;j++){
            if (i>>j&1){
                if (l==-1) l=j;
                r=j;
                tmp.push_back(s[j]);
            }
        }
        int res=0;
        for(int j=l;j<r;j++){
            if (~i>>j&1) res++;
        }
        if (mp.find(tmp)==mp.end()){
            mp[tmp]=res;
        }else{
            mp[tmp]=min(mp[tmp], res);
        }
    }
    int q;
    cin >> q;
    while(q--){
        string t;
        cin >> t;
        if (mp.find(t)==mp.end()) cout << -1 << '\n';
        else cout << mp[t] << '\n';
    }
}

:::

### M. Marriage Proposals (待補)
---
#### 題目大綱

#### 想法

:::spoiler 實作

:::

### N. [N]ew YoRHa Security
---
#### 題目大綱
給定一質數$P$，對於每個$1 \le k \le P-1$求有多少數對$1 \le x, y \le P-1$滿足
* $x ^ {y} \equiv k \mod P$
#### 想法
我不會數學QQ，打表通靈出對於一個數字的所有次方，有同樣循環節長度的循環節裡的元素都一樣，觀察到對一個數的次方模一個質數的循環節結尾會是1(再乘一次自己會變自己)，對P-1的所有因數長度看是不是循環節的結尾，直接對最短長度紀錄多少數字，再對每個可能長度對答案陣列加(數字 * ($P - 1$ / 循環節長度))，整體複雜度為$O(P \log P \times d )$，$d$是$P-1$的因數個數，數量最多差不多240
:::spoiler 實作

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define ll long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define rep(X, a, b) for(int X = a; X < b; ++X)

void solve() {
    int p; cin >> p;
    vector<int> d;
    for (int i = 1; i * i <= p - 1; ++i) if ((p - 1) % i == 0) {
        d.pb(i);
        if (i != (p - 1) / i) d.pb((p - 1) / i);
    }
    vector<vector<int>> len(p);
    sort(all(d));
    rep (i, 1, p) for (int x : d) {
        if (fpow(i, x, p) == 1) {
            len[x].pb(i);
            break;
        }
    }
    vector<ll> ans(p, 0);
    rep (i, 1, p) if (len[i].size()) {
        int sz = len[i].size(), l = (p - 1) / i;
        ll cur = len[i].back();
        rep (j, 0, i) {
            ans[cur] += 1LL * sz * l;
            cur = cur * len[i].back() % p;
        }
    }
    rep (i, 1, p) cout << ans[i] << ' ';
}
 
int main() {
    ZTMYACANESOCUTE;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

:::