The 2023 ICPC Asia Jinan Regional Contest

2024/10/25 ICPC

---

qoj補題鏈接

順序按個人難度

---

D. Largest Digit

D. 題意

給定$a$和$b$的上下界，求$a+b$的最大位數。
|a|, |b| ~ 1e9

算出$a+b$的上下界，如果有超過10個數那肯定包含個位數是9的數，否則可以直接暴搜這些數。

複雜度 $O(log|a|)$。

D. 代碼

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

#define ll long long
#define MOD 998244353
#define pii pair<int, int>

int cnt(int x) {
    return x ? max(x % 10, cnt(x / 10)) : 0;
}

int main() {
#ifdef TEST
    freopen("zz.in", "r+", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t; cin >> t;
    while (t --) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        a += c, b += d;
  
        if (b - a + 1 >= 10) {
            cout << 9 << '\n';
        } else {
            int res = 0;
            for (int i = a; i <= b; ++ i) res = max(res, cnt(i));
            cout << res << '\n';
        }
    }

    return 0;
}

---

I. Strange Sorting

I. 題意

給定$n$的排列，每次操作可以把任意逆序對的區間排序好，輸出在$\lfloor \frac{n}{2} \rfloor$次内把整個數組排序的操作序列。
n ~ 1e2

考慮從左到右排序。如果當前位置已經排好（$a_i =i$），可以直接處理下一個位置。否則，考慮坐標${\ j\ |\ j\ge i \ \land a_j \leq a_i }$，包含了這些坐標的最小區間顯然是一個可操作區間，這個區間大小至少為2（至少有$i$和$a_j=i$）。操作這個區間可以排好$[i, a_i]$，最多只需要$\lfloor \frac{n}{2} \rfloor$次。

複雜度是 $O(nlogn)$ 。

I. 代碼

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

#define ll long long
#define MOD 998244353
#define pii pair<int, int>

#define N 110

int a[N];

int main() {
#ifdef TEST
    freopen("zz.in", "r+", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t; cin >> t;
    while (t --) {
        int n; cin >> n;
        for (int i = 1; i <= n; ++ i) cin >> a[i];

        vector<pii> res;

        for (int i = 1; i <= n; ++ i) {
            if (a[i] == i) continue;
            int c = a[i] - i;
            int j = i;
            while (c) c -= a[++ j] < a[i];
            assert(a[j] < a[i]);
            res.emplace_back(i, j);
            sort(a+i, a+j+1);
        }

        cout << res.size() << '\n';
        for (auto [l, r] : res) cout << l << ' ' << r << '\n';
    }

    return 0;
}

---

A. Many Many Heads

A. 題意

有一個平衡的方圓框序列，給定擾亂方圓框方向后的序列$S$，判斷這個擾亂后的序列是否只存在唯一的原序列。
|S| ~ 1e5

整體思路是先構造一個可行方案，然後在判斷是否存在另外一種方案。

注意到序列是平衡的，可以用類似於用堆判斷括號序列是否平衡的方法去構造一個可行序列，每次框的類型與堆頂匹配立即彈出，稱這個方案為一般解。

如果存在連續3個或以上類型相同的框，一般解中必然存在形如$..(A)(B)..$的匹配，其中A和B也是平衡的，顯然存在另一個解$..(A()B)..$。

如果存在2個以上的連續2個類型相同的框，一般解中必然存在形如$..()A()B()..$或$..(A()B)(C()D)..$或$..(A()B()C)(D)$或$..(A)(B()C)(D)..$或$..(A()B)(C)(D)..$或$..(A)(B)(C)(D)..$等等的匹配，每個都有對應的額外解。

判斷以上兩個條件即可。

複雜度是 $O(n)$。

A. 代碼

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

#define ll long long
#define MOD 998244353
#define pii pair<int, int>

#define N 100010

int id(char c) {
    return c == '(' || c == ')';
}

int main() {
#ifdef TEST
    freopen("zz.in", "r+", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t; cin >> t;
    while (t --) {
        string s; cin >> s;
        int cnt = 0;
        int res = 1;
        for (int i = 0; i < s.size();) {
            int j = i;
            while (j < s.size() && id(s[i]) == id(s[j])) ++ j;
            int sz = j - i;
            res &= sz <= 2;
            cnt += sz == 2;
            res &= cnt <= 2;
            i = j;
        }
        cout << (res ? "Yes\n" : "No\n");
    }

    return 0;
}

---

K. Rainbow Subarray

K. 題意

給定$a_n$，允許$k$次位置加減1的操作，求最大的公差為1的區間。
n ~ 5e5
k ~ 1e14

注意到下標的公差也是1，把兩個公差為1的區間相減會得到一個相等的區間。所以把$a_i$減去$i$，問題就轉化爲了求操作數内可行的最大相等區間。注意到區間的代價必然大於子區間的代價，而把一個區間變成相等的最優解是變成中位數。考慮用左右指針和滾動中位數來得出每個起始位置的最大可行終點位置，然後再取最大值。

複雜度是 $O(nlogn)$。

K. 代碼

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

#define ll long long
#define MOD ((int) (1e9) + 7)
#define pii pair<int, int>

#define N 500010

struct Median {
    multiset<int> l, r;
    ll lsum, rsum;

    void init() {
        l.clear(), r.clear();
        lsum = rsum = 0;
    }

    int size() {
        return l.size() + r.size();
    }
  
    ll cost() {
        if (size() == 0) return 0;
        return 1ll * l.size() * get() - lsum + rsum - 1ll * r.size() * get();
    }

    int get() {
        return *l.rbegin();
    }

    void balance() {
        while (l.size() > (size() + 1) / 2) {
            int el = *l.rbegin();
            l.erase(l.find(el)), lsum -= el;
            r.insert(el), rsum += el;
        }
        while (r.size() > size() / 2) {
            int el  = *r.begin();
            l.insert(el), lsum += el;
            r.erase(r.find(el)), rsum -= el;
        }
    }

    void add(int x) {
        if (size() == 0 || x <= get()) {
            l.insert(x), lsum += x;
        } else {
            r.insert(x), rsum += x;
        }
        balance();
    }

    void remove(int x) {
        if (x <= get()) {
            l.erase(l.find(x)), lsum -= x;
        } else {
            r.erase(r.find(x)), rsum -= x;
        }
        balance();
    }
  
} median;

int a[N];

int main() {
#ifdef TEST
    freopen("zz.in", "r+", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t; cin >> t;
    while (t --) {
        median.init();

        ll n, k; cin >> n >> k;
        for (int i = 1; i <= n; ++ i) cin >> a[i], a[i] -= i;

        int res = 0;
        median.add(a[1]);
        for (int i = 1, j = 1; i <= n; ++ i) {
            while (j <= n && median.cost() <= k) {
                if (++ j <= n) median.add(a[j]);
            }
            res = max(res, j - i);
            median.remove(a[i]);
        }  
        cout << res << '\n';
    }

    return 0;
}

---

G. Gifts from Knowledge

G. 題意

給定一個$r \times c$的網格，可以交換任意鏡像列，求滿足每個列最多只有一個1的可行方案數。
r * c ~ 1e6

首先每個列最多只能有1個1，列和鏡像列合計最多只能有2個1。考慮列和鏡像列上的1，如果他們在同一列上，則它們對應行的操作是相反的，反之則是相同的。

考慮對每行的操作狀態建圖，把需要同時發生的操作連通。顯然行的兩種操作（翻和不翻）不能同時發生，把它特判掉。這個圖必然存在2k個連通塊，因爲這些連通塊的取反（所有操作取反）形成雙射。

所以有k個操作關聯的行集合，每個可以選擇取反或不取反，方案數是$2^k$。

複雜度是 $O(rc)$。

G. 代碼

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

#define ll long long
#define MOD ((int) (1e9) + 7)
#define pii pair<int, int>

#define N 1000010

int f[N<<1];

void init(int n) {
    for (int i = 1; i <= n; ++ i) f[i] = i;
}

int find(int x) {
    return f[x] == x ? x : f[x] = find(f[x]);
}

void join(int x, int y) {
    f[find(x)] = find(y);
}

ll fp(ll b, ll p) {
    ll res = 1;
    for (; p; b=b*b%MOD, p>>=1) if (p&1) res=res*b%MOD;
    return res;
}


int main() {
#ifdef TEST
    freopen("zz.in", "r+", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t; cin >> t;
    while (t --) {
        int r, c; cin >> r >> c;
        vector<vector<bool>> g(r+10, vector<bool>(c+10, 0));
        for (int i = 1; i <= r; ++ i) {
            string s; cin >> s;
            for (int j = 1; j <= c; ++ j) {
                g[i][j] = s[j-1] - '0';
            }
        }
        init(2*r);

        ll res = 1;

        for (int i = 1; i <= (c+1)/2; ++ i) {
            int j = c + 1 - i;
    
            vector<pii> pts;
            for (int k = 1; k <= r; ++ k) {
                if (g[k][i]) pts.emplace_back(k, i);
                if (i != j && g[k][j]) pts.emplace_back(k, j);
            }

            if (pts.size() > 1 + (i != j)) {
                res = 0;
                break;
            }
    
            for (int i = 0; i < pts.size(); ++ i) {
                for (int j = i+1; j < pts.size(); ++ j) {
                    auto [x0, y0] = pts[i];
                    auto [x1, y1] = pts[j];
                    if (y0 == y1) {
                        join(x0, x1+r);
                        join(x0+r, x1);
                    } else {
                        join(x0, x1);
                        join(x0+r, x1+r);
                    }
                }
            }
        }

        for (int i = 1; i <= r; ++ i) res &= find(i) != find(i+r);
  
        int cnt = 0;
        for (int i = 1; i <= 2*r; ++ i) cnt += find(i) == i;

        cout << res * fp(2, cnt/2) << '\n';
    }

    return 0;
}

---

M. Almost Convex

M. 題意

給定平面上的$n$個點，記它的凸包和凸包點數為$S$和$|S|$，求由點集的$|S|$或$|S|+1$個點組成且包含所有點的多邊形的數量。
n ~ 2e3

大部分難度在於理解題目，題意已經把問題轉化成比較簡單的形式。

首先凸包本身算一個，然後我們考慮把凸包的一條邊$AB$通過凸包内部點$X$拆成兩條邊$AX$和$XB$。新多邊形包含所有點意味著$\triangle AXB $不包含其他凸包内部點，可以用$X$的極坐標下的極角排序中$A$和$B$是否相鄰來判斷。

複雜度是 $O(n^2logn)$。

M. 代碼

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

#define ll long long
#define MOD ((int) (1e9) + 7)
#define pii pair<int, int>

#define N 2010

typedef pair<pii, int> pt;

pii vectorize(pii A, pii B) {
    return pii(B.first - A.first, B.second - A.second);
}

ll cross(pii v0, pii v1) {
    return 1ll * v0.first * v1.second - 1ll * v0.second * v1.first;
}

double deg[N];

void polar_sort(vector<pt>& arr, pii center) {
    for (auto [p, id] : arr) {
        auto v = vectorize(center, p);
        deg[id] = atan2(v.second, v.first);
    }
    sort(arr.begin(), arr.end(), [&](pt a, pt b) {
        return deg[a.second] < deg[b.second];  
    });
}

pt stk[N];
int nxt[N], onhull[N];

int main() {
#ifdef TEST
    freopen("zz.in", "r+", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n; cin >> n;
    vector<pt> pts(n), ss;

    for (int i = 0; i < n; ++ i) {
        int x, y; cin >> x >> y;
        pts[i] = pt(pii(x, y), i);
    }
    sort(pts.begin(), pts.end());

    for (int i = 1; i < n; ++ i) ss.emplace_back(pts[i]);
    polar_sort(ss, pts[0].first);

    int sz = 0;
    stk[++ sz] = pts[0];
    stk[++ sz] = ss[0];
    for (int i = 1; i < ss.size(); ++ i) {
        while (sz >= 2) {
            auto p0 = stk[sz - 1].first;
            auto p1 = stk[sz].first;
            auto p2 = ss[i].first;
    
            if (cross(vectorize(p0, p1), vectorize(p1, p2)) < 0) {
                -- sz;
                continue;
            }
            break;
        }
        stk[++ sz] = ss[i];
    }

    for (int i = 1; i <= sz; ++ i) {
        onhull[stk[i].second] = 1;
        nxt[stk[i].second] = i == sz ? stk[1].second : stk[i+1].second;
    }

    int res = 1;
    for (int i = 0; i < n; ++ i) {
        auto [p, id] = pts[i];
        if (onhull[id]) continue;

        ss.clear();
        for (int j = 0; j < n; ++ j) if (pts[j].second != id) ss.emplace_back(pts[j]);
        polar_sort(ss, p);

        int cont = 0;
        for (int j = 0; j < ss.size(); ++ j) {
            int k = j == ss.size()-1 ? 0 : j+1;
            int cont = 1;
            cont &= onhull[ss[j].second];
            cont &= onhull[ss[k].second];
            cont &= nxt[ss[j].second] == ss[k].second || nxt[ss[k].second] == ss[j].second;
            res += cont;
        }
    }

    cout << res << '\n';

    return 0;
}

---

E. I Just Want… One More…

E. 題意

給定一個二分圖$U\rightarrow V$，其中$|U|=|V|$，求有多少條$U$到$V$且不在圖内的邊可以使最大匹配增加。
|U|, |V|, |E| ~ 1e5

考慮用最大流來解最大匹配。從最大匹配的殘量網絡中可知，連任意一條由源點$S$可達的點$P_S$到可達匯點$T$的點$P_T$的邊都能使最大匹配增加。

記最大匹配的殘量網絡中，$S$可達的屬於$U$的點的集合為$S_U$，可達$T$的屬於$V$的點的集合為$T_V$，答案為$|S_U|\times |T_V|$。

複雜度是 $O(|E|\sqrt{|U|})$。

E. 代碼

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

#define ll long long
#define MOD ((int) (1e9) + 7)
#define pii pair<int, int>

#define N 200010
#define inf 0x7fffffff

struct Edge {
    int u, v, c, nxt;
    Edge(): u(0), v(0), c(0), nxt(0) {};
    Edge(int u, int v, int c, int nxt): u(u), v(v), c(c), nxt(nxt) {};
};

struct MaxFlow {
    int n, m;

    Edge E[N<<2];
    int h[N], cur[N], dis[N], flow;
    int q[N], ql, qr;
    bool inS[N], inT[N];
  
    void init(int n) {
        this->n = n;
        this->m = 2;
        for (int i = 1; i <= n; ++ i) h[i] = 0;
    }

    void add_edge(int u, int v, int c) {
        E[m] = Edge(u, v, c, h[u]), h[u] = m ++; 
        E[m] = Edge(v, u, 0, h[v]), h[v] = m++;
    }

    bool bfs(int s, int t) {
        for (int i = 1; i <= n; ++ i) dis[i] = inf;

        ql = qr = 0;
        q[qr ++] = s;
        dis[s] = 0, cur[s] = h[s];

        while (ql < qr) {
            int u = q[ql ++];
            for (int i = h[u]; i; i = E[i].nxt) {
                auto& [_, v, c, __] = E[i];
                if (c && dis[v] == inf) {
                    dis[v] = dis[u] + 1;
                    cur[v] = h[v];
                    q[qr ++] = v;
                    if (v == t) return 1;
                }
            }
        }

        return 0;
    }

    int dfs(int u, int t, int in) {
        if (u == t) return in;
        if (dis[u] >= dis[t]) return 0;

        int out = 0;
        for (int i = cur[u]; i && in > out; i = E[i].nxt) {
            cur[u] = i;
            auto& [_, v, c, __] = E[i];
            if (dis[v] == dis[u] + 1 && c) {
                int vout = dfs(v, t, min(in - out, c));
                if (!vout) dis[v] = -1;
                E[i].c -= vout, E[i^1].c += vout, out += vout;
            }
        }
        return out;
    }

    void go(int s, int t) {
        flow = 0;
        while (bfs(s, t)) flow += dfs(s, t, inf);
    }

    void revisit(int s, int t) {
        for (int i = 1; i <= n; ++ i) inS[i] = inT[i] = 0;

        ql = qr = 0;
        q[qr ++] = s;
        inS[s] = 1;
        while (ql < qr) {
            int u = q[ql ++];
            for (int i = h[u]; i; i = E[i].nxt) {
                auto& [_, v, c, __] = E[i];
                if (c && !inS[v]) {
                    q[qr ++] = v;
                    inS[v] = 1;
                }
            }
        }

        ql = qr = 0;
        q[qr ++] = t;
        inT[t] = 1;
        while (ql < qr) {
            int u = q[ql ++];
            for (int i = h[u]; i; i = E[i].nxt) {
                auto& [v, _, c, __] = E[i^1];
                if (c && !inT[v]) {
                    q[qr ++] = v;
                    inT[v] = 1;
                }
            }
        }
    } 
} mf;

int main() {
#ifdef TEST
    freopen("zz.in", "r+", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t; cin >> t;
    while (t --) {
        int n, m; cin >> n >> m;
        int s = 2*n+1, t = s+1;

        mf.init(t);
        for (int i = 1; i <= n; ++ i) mf.add_edge(s, i, 1);
        for (int i = n+1; i <= 2*n; ++ i) mf.add_edge(i, t, 1);
        for (int i = 0; i < m; ++ i) {
            int u, v; cin >> u >> v; v += n;
            mf.add_edge(u, v, 1);
        }

        mf.go(s, t);
        mf.revisit(s, t);

        int Us = 0, Vs = 0;
        for (int i = 1; i <= n; ++ i) Us += mf.inS[i];
        for (int i = n+1; i <= 2*n; ++ i) Vs += mf.inT[i];

        cout << 1ll * Us * Vs << '\n';
    }


    return 0;
}

---

其他