周赛 Round 138 题解

A 小苯的转盘游戏

知识点：线性不定方程，同余 / 模运算，构造性证明

设进行了 $a$ 次 $+3$ ， $b$ 次 $-2$ ，则最终有：

y=x+3a-2b

也就是：

y-x = 3a-2b

因为 $3$ 和 $2$ 互质，且我们可以让 $b$ 足够大来保证 $a$ 也非负。

更具体地说：

先选一个 $b$ ，满足
$y-x+2b\equiv 0\pmod 3$
再让 $b$ 足够大，使得
$a=\frac{y-x+2b}{3}\geq 0$

这样的 $a,b$ 总能找到，所以任意 $x,y$ 都可以互相到达。

时间复杂度 $O(1)$

void solve() {
    cout << "YES" << endl;
}

B 小苯的最大异或

知识点：位运算，枚举，优化暴力

对 $x$ 或 $y$ 做一次操作，相当于：

x \leftarrow \left\lfloor \frac{x}{2} \right\rfloor

也就是二进制右移一位：

x\leftarrow x>>1

所以，连续操作若干次后：

$x$ 可能变成 $x >> i$
$y$ 可能变成 $y >> j$

其中 $i, j$ 都是非负整数。

因为 $x$ 和 $y$ 的操作互不影响，最终只和“各自被操作了多少次”有关，和操作顺序无关。

所以最终所有可能状态一定是：

(x>>i,y>>j)

由于数据范围保证 $x, y \leq 10^9$ ，而 $10^9 < 2^{30}$ 。也就是说，最多右移 $30$ 次左右就会变成 $0$ ，再往后也还是 $0$ 。因此枚举 $0..30$ 已经完全覆盖所有情况。

我们只要把所有可能的 $i, j$ 都试一遍，取最大异或值即可。

时间复杂度 $O(1)$

void solve() {
    int x, y;
    cin >> x >> y;
 
    int ans = 0;
    for (int i = 0; i <= 31; ++i) {
        int a = x >> i;
        for (int j = 0; j <= 31; ++j) {
            int b = y >> j;
            ans = max(ans, a ^ b);
        }
    }
 
    cout << ans << endl;
}

C 小苯的数位排序

知识点：贪心，单调性，模拟，构造 / 可行性判断

每次操作把某个数变成它的各位数字和：

x \leftarrow digit\_sum(x)

这个操作有两个性质：

不会变大，只会变小或不变；
对于 $x \geq 10$ ，一定有 $digit\_sum(x) < x$ 。

所以一个数不断做下去，最终会变成一个一位数，并且之后再怎么做都不会变了。

我们要让整个数组非递减，也就是：

a_1 \le a_2 \le \cdots \le a_n

从右往左处理最合适，因为：

右边一旦确定，就不应该再动它；
左边怎么变，只会影响自己和更左边，不会影响已经处理好的右边。

所以我们从 $i = n-2$ 到 $0$ 依次处理：

如果 $a[i] \leq a[i+1]$ ，不用管；
如果 $a[i] > a[i+1]$ ，就只能不断对 $a[i]$ 做 $digit\_sum$ ，直到：
- 它变得 $\leq a[i+1]$ ，或者
- 它已经不再变化了，但还是大于 $a[i+1]$ ，这时无解。

时间复杂度 $O(n)$

void solve() {
    int n;
    cin >> n;
    auto calc = [&](ll x) {
        string s = to_string(x);
        ll sum = 0;
        for (auto v : s) sum += v - '0';
        return sum;
    };
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    int ans = 0;
    for (int i = n - 2; i >= 0; --i) {
        while (a[i] > a[i + 1]) {
            ll nxt = calc(a[i]);
            if (nxt == a[i]) {
                cout << -1 << endl;
                return;
            }
            a[i] = nxt;
            ans++;
        }
    }
    cout << ans << endl;
}

D 小苯的路径计数

知识点：树形 DP，DFS 遍历，祖先到后代路径计数，按路径终点统计贡献

对于每个节点 $v$ ，只需要知道，以 $v$ 为终点的、满足条件的同色路径有多少条。

设这个数量为 $dp[v]$ 。设 $v$ 的父亲是 $u$ ：

若 $c[v] \neq c[u]$ ，那么没有任何同色路径能从 $p$ 延伸到 $v$ ，所以
$dp[v] = 0$
若 $c[v] = c[u]$ ，则：
- $u -> v$ 本身是一条合法路径；
- 所有以 $u$ 为终点的同色路径，都可以再接上 $v$ 继续保持同色。

所以：

dp[v] = dp[u]+1

时间复杂度 $O(n)$

void solve() {
    int n;
    cin >> n;
    vector<int> c(n + 1);
    for (int i = 1; i <= n; i++) cin >> c[i];
    vector<vector<int>> g(n + 1);
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        g[u].pb(v), g[v].pb(u);
    }
    ll ans = 0;
    vector<ll> dp(n + 1);

    auto dfs = [&](auto &&self, int u, int fa) -> void {
        for (auto v : g[u]) {
            if (v == fa) continue;
            dp[v] = (c[v] == c[u] ? dp[u] + 1 : 0);
            ans += dp[v];
            self(self, v, u);
        }
    };

    dfs(dfs, 1, 0);
    cout << ans << endl;
}

E 小苯的数字染色

知识点：前缀 DP，状态压缩，按奇偶分类维护最优值

所以整个过程等价于：

按顺序选择若干个互不重叠的区间
每个区间只看两端点，且两端点数值奇偶性相同
目标最大化所有区间端点和

如果我们从左到右扫描数组：

当前点可以作为某个区间的左端点
也可以作为某个之前左端点的右端点
由于区间不能重叠，所以一旦某个区间被选中，它对后面的影响只体现在前缀最优值里

而且这里只和数值的奇偶性有关，所以只需要维护奇数端点和偶数端点两个状态即可。

设：

$dp$ ：扫描到当前位置之前，已经处理完的前缀能得到的最大分数
$m[0] / m[1]$ ：表示“当前有一个还没闭合的左端点”时，能得到的最大值，即：
$m[p] = \max(\text{前缀最优分数} + a_i)$

其中 $a_i$ 是某个奇偶性为 $p$ 的左端点。

扫描到 $a[i]$ ，设它的奇偶性为 $p$ 。

不把 $i$ 作为右端点： $ndp = dp$
把 $i$ 作为某个同奇偶左端点的右端点： $ndp = \max(ndp, m[p] + a[i])$

因为 $m[p]$ 里已经包含了“左端点 + 左边所有已经完成的区间”的最优值。
把 $i$ 作为新的左端点，以后可能和后面的同奇偶数配对： $m[p] = \max(m[p], dp + a[i])$

这里必须用当前的 $dp$ ，因为左端点前面的部分已经确定最优了。

时间复杂度 $O(n)$

constexpr ll INF = 2e18;

void solve() {
    int n;
    cin >> n;

    ll dp = 0;
    ll m[2] = {-INF, -INF};

    for (int i = 0; i < n; ++i) {
        ll a;
        cin >> a;
        int p = abs(a) % 2;

        ll ndp = dp;
        if (m[p] != -INF) ndp = max(ndp, a + m[p]);

        m[p] = max(m[p], dp + a);

        dp = ndp;
    }

    cout << dp << endl;
}

F 小苯的对称序列

知识点：区间嵌套 DP，按和分类，树状数组，前缀最值优化

对于一个对称子序列，设它首尾配对的和都等于 $S$ 。那么它的每一对端点都可以看成一个合法配对：

普通配对 $(l, r)$ ，要求 $a[l] + a[r] = S$ ，贡献长度 $2$
中心单点 $(i, i)$ ，要求 $2 * a[i] = S$ ，贡献长度 $1$

并且这些配对一定是嵌套的：

外层配对的左端点更小
外层配对的右端点更大

也就是说，合法答案本质上是：在所有满足 $a[l] + a[r] = S$ 的区间中，找一条左端点递增、右端点递减的最长链。

这就变成了一个经典的二维偏序最长链 / 加权 LIS 问题。

对每个可能的和 $S$ ，收集所有满足： $a[i] + a[j] = S, i \leq j$ 的配对 $(i, j)$ 。

对于某个固定的 $S$ ，我们处理这些配对：

如果 $i \neq j$ ， $wt := 2$
如果 $i = j$ ， $wt := 1$

设当前配对是 $(u, v)$ ，我们希望找到之前已经处理过的、能套在它里面的最好方案：

之前配对的左端点更小
右端点更大

也就是找满足： $u' < u$ 且 $v' > v$ 的最大 DP 值。

于是：

dp(u, v) = wt(u, v) + max{ dp(u', v') }

其中 $u' < u, v' > v$

把右端点 $v$ 反过来编号 $idx = n - v$

这样“右端点更大”就变成了 $idx$ 更小，可以用树状数组维护前缀最大值。处理顺序按左端点 $u$ 从小到大。每个配对 $(u, v)$ ：

查询 $BIT$ 中所有 $v' > v$ 的最大值
加上当前权值 $wt$
再把结果更新到 $v$ 对应的位置

时间复杂度 $O(n^2logn)$

template <class Int = ll>
struct BIT {
    vector<Int> a;
    int n;

    BIT() {}
    BIT(int n) { init(n); }

    void init(int n) {
        this->n = n;
        a.resize(n + 1);
    }

    void update(int x, Int k) {
        for (; x <= n; x += x & -x) {
            a[x] = max(a[x], k);
        }
    }

    Int ask(int x) {
        Int ans = 0;
        for (; x; x -= x & -x) {
            ans = max(ans, a[x]);
        }
        return ans;
    }

    void clear() { fill(a.begin(), a.end(), 0); }
};

void solve() {
    int n, mx = 0;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i], mx = max(mx, a[i]);

    vector<vector<PII>> pairs(mx * 2 + 1);

    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int sum = a[i] + a[j];
            pairs[sum].pb({i, j});
        }
    }

    int ans = 0;
    BIT tr(n);

    for (int S = 2; S <= mx * 2; S++) {
        if (pairs[S].empty()) continue;

        tr.clear();
        int mxl = 0;

        for (auto [u, v] : pairs[S]) {
            int wt = (u == v) ? 1 : 2;

            int val = tr.ask(n - v - 1) + wt;

            mxl = max(mxl, val);

            tr.update(n - v, val);
        }
        ans = max(ans, mxl);
    }

    cout << ans << endl;
}

当然也可以不用树状数组，直接枚举区间内部状态，时间复杂度 $O(n^3)$

void solve() {
    int n, mx = 0;
    cin >> n;
    vector<int> a(n);
    vector<vector<int>> pos(1005);
    for (int i = 0; i < n; i++) cin >> a[i], mx = max(mx, a[i]), pos[a[i]].pb(i);
 
    vector<bool> flag(2 * mx + 1);
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            flag[a[i] + a[j]] = true;
        }
    }
 
    int ans = 0;
    vector<int> dp(n);
    vector<PII> upd;
 
    for (int S = 2; S <= mx * 2; S++) {
        if (!flag[S]) continue;
 
        fill(all(dp), 0);
        int cur = 0;
 
        for (int i = n - 1; i >= 0; i--) {
            int tar = S - a[i];
            if (tar < 0 || tar > 1000 || pos[tar].empty()) continue;
 
            upd.clear();
            for (auto j : pos[tar]) {
                if (j < i) continue;
 
                int in = 0;
                for (int k = i + 1; k < j; k++) {
                    if (dp[k] > in) {
                        in = dp[k];
                    }
                }
 
                int clen = (i == j) ? 1 : 2 + in;
                upd.pb({j, clen});
 
                if (clen > cur) {
                    cur = clen;
                }
            }
 
            for (auto [u, v] : upd) {
                if (v > dp[u]) {
                    dp[u] = v;
                }
            }
        }
 
        if (cur > ans) {
            ans = cur;
        }
    }
 
    cout << ans << endl;
}

乱搞 $1$ （疑似将要被击杀）：

知识点：枚举，区间 DP，滚动数组优化

设选出的对称子序列为

b_1,b_2,\dots,b_m

题目要求：

b_1+b_m=b_2+b_{m-1}=\cdots

也就是说，这个子序列一定存在一个固定的公共和 $S$ ，满足首尾配对都等于 $S$ 。

所以问题即为，枚举公共和 $S$ ，求在原数组中能选出的最长首尾配对和都等于 $S$ 的子序列长度。

因为 $a_i \le 1000$ ，所以 $S$ 的范围只需要枚举到 $2000$ 。

定义 $dp[l][r]$ 表示在区间 $[l,r]$ 中，能选出的、公共和为 $S$ 的最长对称子序列长度。

那么转移为：

不选左端点 $a_l$ ，答案是 $dp[l+1][r]$
不选右端点 $a_r$ ，答案是 $dp[l][r-1]$
如果 $a[l] + a[r] = S$ ，可以把它们作为一对首尾，再加上中间部分 $dp[l+1][r-1] + 2$

于是：

dp[l][r]=\max\Big(dp[l+1][r],\ dp[l][r-1],\ dp[l+1][r-1]+2\Big)

如果 $l=r$ ，单个数只能作为中心点：

dp[i][i]= \begin{cases} 1, & 2a_i=S\\ 0, & \text{otherwise} \end{cases}

但是 $5\times 2000\times 500^2 = 2.5\times 10^9$ ，最坏情况下肯定会 $\text{TLE}$ ，所以我们考虑剪枝，先算一个“理论上界” $tr$ 。对于固定的 $S$ ：

若 $x < S-x$ ，那么值为 $x$ 和 $S-x$ 的元素最多只能配成
$2 \cdot \min(freq[x], freq[S-x])$
若 $x = S-x$ （即 $S$ 为偶数且 $x=S/2$ ），这些元素可以全部用上，贡献 $freq[x]$

这就能计算出一个不考虑位置顺序的最大可能长度上界 $tr$ 。

如果 $tr \leq ans$ ，说明这个 $S$ 再怎么做也不可能超过当前答案，直接跳过。

时间复杂度 $O(|a_i|n^2)$

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1), freq(1005);
    int mx = 0;
 
    for (int i = 1; i <= n; i++) cin >> a[i], freq[a[i]]++, mx = max(mx, a[i]);
 
    int ans = 0, mxs = mx * 2;
 
    for (int S = 2; S <= mxs; S++) {
        int tr = 0;
        for (int x = 1; x <= S / 2; x++) {
            if (S - x > 1000) continue;
            if (x * 2 == S) {
                tr += freq[x];
            } else {
                tr += 2 * min(freq[x], freq[S - x]);
            }
        }
        if (tr <= ans) continue;
 
        vector<int> dp(n + 1, 0);
        for (int i = n; i >= 1; i--) {
            int prev = 0;
            for (int j = i; j <= n; j++) {
                int temp = dp[j];
 
                if (i == j) {
                    dp[j] = (a[i] * 2 == S) ? 1 : 0;
                } else {
                    if (a[i] + a[j] == S) {
                        dp[j] = 2 + prev;
                    } else {
                        dp[j] = max(dp[j], dp[j - 1]);
                    }
                }
                prev = temp;
            }
        }
        ans = max(ans, dp[n]);
    }
 
    cout << ans << endl;
}

乱搞 $2$ ：

知识点： $\text{LCS}$ ， $\text{bitset}$ 优化，优化暴力

固定公共和 $S$ 以后，把原数组倒过来，记为 $rev$ ，然后把 $rev$ 里的每个数 $x$ 变成 $S-x$ ，得到数组 $b$ 。那么原数组中最长的、公共和为 $S$ 的对称子序列等价于 $a$ 和 $b$ 的最长公共子序列长度。

所以整题就是：

枚举 $S=2\sim 2000$
对每个 $S$ 求一次 $\text{LCS}$
取最大值。

时间复杂度 $O(|a_i|n^2/64)$

static constexpr int MAXB = 8;

struct Bits {
    ull b[MAXB]{};

    Bits operator|(const Bits& o) const {
        Bits r;
#pragma GCC unroll 8
        for (int i = 0; i < MAXB; ++i) r.b[i] = b[i] | o.b[i];
        return r;
    }

    Bits and_not(const Bits& o) const {
        Bits r;
#pragma GCC unroll 8
        for (int i = 0; i < MAXB; ++i) r.b[i] = b[i] & ~o.b[i];
        return r;
    }

    Bits operator-(const Bits& o) const {
        Bits r;
        unsigned long long borrow = 0;
#pragma GCC unroll 8
        for (int i = 0; i < MAXB; ++i) {
            borrow = _subborrow_u64(borrow, b[i], o.b[i], &r.b[i]);
        }
        return r;
    }

    Bits shl1_or1() const {
        Bits r;
        ull carry = 1;
#pragma GCC unroll 8
        for (int i = 0; i < MAXB; ++i) {
            r.b[i] = (b[i] << 1) | carry;
            carry = b[i] >> 63;
        }
        return r;
    }

    int count(int blocks) const {
        int res = 0;
        for (int i = 0; i < blocks; ++i) {
            res += __builtin_popcountll(b[i]);
        }
        return res;
    }
};

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    int blocks = (n + 63) / 64;
    ull last = (n % 64 == 0 ? ~0ull : ((1ull << (n % 64)) - 1));

    vector<Bits> occ(1001);
    for (int j = 0; j < n; ++j) {
        int v = a[n - 1 - j];
        occ[v].b[j >> 6] |= 1ull << (j & 63);
    }

    int ans = 1;
    for (int S = 2; S <= 2000; ++S) {
        Bits D;

        for (int x : a) {
            Bits M{};
            int y = S - x;
            if (1 <= y && y <= 1000) M = occ[y];

            Bits X = D | M;
            Bits Y = D.shl1_or1();
            Bits T = X - Y;
            D = X.and_not(T);

            for (int i = blocks; i < MAXB; ++i) D.b[i] = 0;
            D.b[blocks - 1] &= last;
        }

        ans = max(ans, D.count(blocks));
    }
    cout << ans << endl;
}

头文件

#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define eb emplace_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define endl "\n"
using namespace std;

using ll = long long;
using ld = long double;
using ui = unsigned;
using ull = unsigned long long;
using i128 = __int128;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;

void init() {
}

void solve() {
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    init();

    int t = 1;
    cin >> t;
    cout << fixed << setprecision(15);
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }

    return 0;
}

题解 | 周赛 Round 138

A 小苯的转盘游戏

B 小苯的最大异或

C 小苯的数位排序

D 小苯的路径计数

E 小苯的数字染色

F 小苯的对称序列

头文件