VP 2023 ICPC 沈阳

The 2023 ICPC Asia Shenyang Regional Contest
The 2nd Universal Cup. Stage 13: Shenyang

Date 2025.08.24
Solved 6 / 13

A	B	C	D	E	F	G	H	I	J	K	L	M
	Ø	O	待补	O					O	O		O

B. Turning Permutation

字典序问题的一个经典 trick 是按位确定一串前缀，然后算出后面随便放的方案数，和 k 做比较。这样的话就是外面 $O(n ^ 2)$，里面套个计数

考虑怎么计数，一个经典套路是 对值 $1…n$ 依次确定位置

设

$$
dp[i][j][t]
$$

• 已处理完 $1…i$
• $j$：$i$ 在当前 未确定后缀 的相对位置（$j=0$ 表示已固定到前缀）
• $t=0/1$：$i-1$ 在 $i$ 左 / 右

维护一个 len 表示后缀长度，按 $i$ 递增转移到 $i+1$：

• 若 $i+1$ 已在前缀：直接根据相对位置继承/过滤状态；
• 否则：
  • 若 $t=0$（$i-1$ 在 $i$ 左）：$i+1$ 也必须在右 ⇒ $nj \in [1,j]$
  • 若 $t=1$（$i-1$ 在 $i$ 右）：$i+1$ 必在左 ⇒ $nj \in [j+1,len+1]$
    对区间内位置累加，方向翻转 t^1。

细节比较多，看代码

#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
#define int i64
#define pb push_back
#define ep emplace
#define eb emplace_back
using namespace std;
int read(int x = 0, int f = 0, char ch = getchar()) {
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while (48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for (auto x : a) cout << x << " "; cout << "\n";
template <class T1, class T2> ostream &operator<<(ostream &os, const std::pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; i++) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; i++) cerr << *i << " "; cerr << '\n'; }
using pii = pair<int, int>;
const int inf = 1e18;

const int N = 50 + 5;

int n, k;
int a[N], vis[N], pos[N];
int dp[N][N][2];
// dp[i][j][t]:
//   已经处理完 1..i 这些数
//   j 表示数字 i 在「后缀」部分的相对位置（第 j 个，j = 0 表示已固定到前缀）
//   t = 0 表示 i - 1 在 i 的左侧, t = 1 表示 i - 1 在 i 的右侧

int calc(int lim) {
    memset(dp, 0, sizeof dp);
    int len = 0;

    bool in1 = vis[1], in2 = vis[2];
    if (in1 and in2) {
        dp[2][0][ pos[1] < pos[2] ? 0 : 1 ] = 1;
    } else if (in1 and !in2) {
        len = 1;
        dp[2][1][0] = 1;
    } else if (!in1 and in2) {
        len = 1;
        dp[2][0][1] = 1;
    } else {
        len = 2;
        dp[2][1][1] = 1;
        dp[2][2][0] = 1;
    }

    auto add = [&](int &x, int v) {
        x += v;
        if (x > lim) x = lim;
    };

    for (int i = 2; i < n; i++) {
        if (vis[i + 1]) {
            if (vis[i]) {
                int t = (pos[i] < pos[i + 1] ? 0 : 1);
                dp[i + 1][0][t] = dp[i][0][t ^ 1];
            } else {
                for (int j = 1; j <= len; j++) {
                    add(dp[i + 1][0][1], dp[i][j][0]);
                }
            }
            continue;
        }

        for (int j = 0; j <= len; j++) {
            for (int t = 0; t < 2; t++) {
                if (!dp[i][j][t]) continue;

                int st, ed;
                if (t == 0) {
                    st = 1;
                    ed = j;
                } else {
                    st = j + 1;
                    ed = len + 1;
                }
                for (int nj = st; nj <= ed; nj++) {
                    add(dp[i + 1][nj][t ^ 1], dp[i][j][t]);
                }
            }
        }
        len++;
    }

    int res = 0;
    if (vis[n]) {
        add(res, dp[n][0][0] + dp[n][0][1]);
    } else {
        for (int i = 1; i <= len; i++) {
            add(res, dp[n][i][0] + dp[n][i][1]);
        }
    }
    return res;
}


void solve() {
    n = read();
    k = read();

    for (int p = 1; p < n; p++) {
        for (int v = 1; v <= n; v++) {
            if (vis[v]) continue;

            vis[v] = 1, pos[v] = p;

            for (int i = 1; i <= n; i++) {
                if (vis[i]) continue;
                pos[i] = p + 1;
            }

            bool ok = 1;
            for (int i = 2; i < n; i++) {
                if ((pos[i] - pos[i - 1]) * (pos[i] - pos[i + 1]) < 0) {
                    ok = 0;
                    break;
                }
            }
            if (!ok) { vis[v] = 0; continue; }

            int cnt = calc(k);
            if (cnt >= k) { a[p] = v; break; } 

            k -= cnt;
            vis[v] = 0;
        }

        if (!a[p]) { cout << "-1\n"; return; }
    }

    for (int i = 1; i <= n; i++) if (!vis[i]) a[n] = i;
    for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n];
}

signed main() {
    // for (int T = read(); T--; solve());
    solve();
    return 0;
}

M. Outro: True Love Waits

s 走到 t 等价于 0 走到 s xor t

那么题目 相当于先从 0 走到 s xor t，然后重复 k - 1 遍 s xor t 到 s xor t (相当于 0 走到 0)

从 0 走到 0 就是经典的 0 ^ 1 ^ 2 ^ 3 = 0，由于每次走完那条边会被删除，相当于消耗两个低位的 0。

那么无解的情况就是 s xor t 低位的连续的 0 的数量不够。

第 k 次到达 0 的步数就是 $s_k = \sum_{i = 1}^{k - 1} 4 ^ i$。

然后按照上面的分步骤算一算就行了

const int N = 1e6 + 5;
Z pw[N];

Z calc(int n) {
    Z res = power(Z(4), n + 1);
    res -= 4;
    res /= 3;
    return res;
}

void solve() {
    string s, t; cin >> s >> t;
    int k = read();

    int n = s.size(), m = t.size();
    ranges::reverse(s);
    ranges::reverse(t);
    while (n < m) n++, s += "0";
    while (n > m) m++, t += "0";

    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        if (s[i] == t[i]) {
            p[i] = 0;
        } else {
            p[i] = 1;
        }
    }

    if (n & 1) n++, p.push_back(0);

    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (p[i] == 0) {
            cnt++;
        } else {
            break;
        }
    }
    if (cnt != n and cnt / 2 + 1 < k) {
        cout << "-1\n";
        return;
    }

    Z res = calc(k - 1);
    // debug(res);

    for (int i = 0; i < n; i += 2) {
        if (p[i] == 1 and p[i + 1] == 0) res += pw[i / 2];
        if (p[i] == 1 and p[i + 1] == 1) res += 2 * pw[i / 2];
        if (p[i] == 0 and p[i + 1] == 1) res += 3 * pw[i / 2];
    }
    // debug(p);
    cout << res << '\n';
}

K. Maximum Rating

关于最高 Rating 变化次数：

若要最小化，则前面一直掉分，后面一直上分。而且后面上分的值从小到大。相当于要在一个前缀上面二分

若要最大化，则前面一直上分，后面一直下分。且次数为正数数量。

很容易构造出方案使得 [min, max] 之间的次数都能被取到

用线段树维护一下带修的即可

const int N = 1e6 + 5;

int idx;
struct Node {
    int ls, rs, sum, cnt;
} t[N << 4];

#define ls t[p].ls
#define rs t[p].rs
#define mid (l + r >> 1)
void pushup(int p) {
    t[p].sum = t[ls].sum + t[rs].sum;
    t[p].cnt = t[ls].cnt + t[rs].cnt;
}
void modify(int &p, int l, int r, int pos, int num) {
    if (!p) p = ++idx;
    if (l == r) { 
        t[p].sum += pos * num; 
        t[p].cnt += num; 
        return;
    }
    if (pos <= mid) modify(ls, l, mid, pos, num);
    else modify(rs, mid + 1, r, pos, num);
    pushup(p);
}
int query(int p, int l, int r, int sum) {
    if (l == r) {
        return sum <= 0 ? 0 : (sum + l - 1) / l;
    }
    if (t[rs].sum >= sum) {
        return query(rs, mid + 1, r, sum);
    } else {
        return query(ls, l, mid, sum - t[rs].sum) + t[rs].cnt;
    }
}

void solve() {
    int n = read(), q = read();

    int sum = 0, rt = 0;

    vector<int> a(n);
    for (auto &x : a) {
        x = read();
        if (x > 0) modify(rt, 1, inf, x, +1);
        sum += x;
    }
    while (q--) {
        int x = read() - 1, v = read();

        if (a[x] > 0) modify(rt, 1, inf, a[x], -1);
        if (v > 0) modify(rt, 1, inf, v, +1);

        sum += v - a[x];
        a[x] = v;

        int res = t[1].cnt - query(rt, 1, inf, sum) + 1;
        cout << res << '\n';
    }
}

E. Sheep Eat Wolves

(i, j, 0 / 1) 为状态，表示河对面有 i 只羊，j 只狼，农夫在 家 / 对面。

用 BFS DP 即可。

void solve() {
    int X = read();
    int Y = read();
    int P = read();
    int Q = read();

    vector dp(X + 1, vector(Y + 1, vector(2, -1)));
    dp[X][Y][0] = 0;

    queue<tuple<int, int, int>> q;
    q.emplace(X, Y, 0);

    while (!q.empty()) {
        auto [x, y, pos] = q.front();
        q.pop();

        if (x == 0) {
            cout << dp[x][y][pos] << '\n';
            return;
        }

        int npos = pos ^ 1;

        if (pos == 0) {
            for (int i = 0; i <= min(P, x); i++) {
                for (int j = 0; j <= min(P - i, y); j++) {
                    int nx = x - i;
                    int ny = y - j;
                    if (nx > 0 and ny > nx + Q) continue;
                    if (dp[nx][ny][npos] != -1) continue;

                    dp[nx][ny][npos] = dp[x][y][pos] + 1;
                    q.emplace(nx, ny, npos);
                }
            }
        } else {
            for (int i = 0; i <= min(P, X - x); i++) {
                for (int j = 0; j <= min(P - i, Y - y); j++) {
                    int nx = x + i;
                    int ny = y + j;
                    if (X - x - i > 0 and Y - y - j > X - x - i + Q) continue;
                    if (dp[nx][ny][npos] != -1) continue;

                    dp[nx][ny][npos] = dp[x][y][pos] + 1;
                    q.emplace(nx, ny, npos);
                }
            }
        }
    }
    
    cout << -1 << '\n';
}

J. Graft and Transplant

每一步操作会恰好让叶子数量增加 1，直到 n - 1。

n = 2 的情况需要特判。

void solve() {
    int n = read();

    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; i++) {
        int x = read();
        int y = read();
        g[x].push_back(y);
        g[y].push_back(x);
    }

    if (n == 2) {
        cout << "Bob\n";
        return;
    }

    int leaf = 0;
    for (int i = 1; i <= n; i++) {
        if (g[i].size() == 1) {
            leaf++;
        }
    }

    int d = n - 1 - leaf;
    if (d & 1) {
        cout << "Alice\n";
    } else {
        cout << "Bob\n";
    }
}

C. Swiss Stage

签到，模拟即可

void solve() {
    int x = read();
    int y = read();

    int ans = 0;
    for (; x < 3; x++) {
        if (x >= 2 or y >= 2) {
            ans += 2;
        } else {
            ans++;
        }
    }
    cout << ans << '\n';
}