$A.$小苯的转盘游戏

  • 通过$x + 3 - 2$可实现$+1$操作
  • 通过$x - 2 - 2 + 3$可实现$-1$操作

所以可以实现任何数的转变

神奇的代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
const int mod = 998244353;


void solve()
{
    int x, y; std::cin >> x >> y;
    std::cout << "YES" << endl;
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
    int _t = 1;
    std::cin >> _t;
    while (_t--) solve();
    return 0;
}

$B.$小苯的最大异或

  • 这里的操作实际上相当于右移一位
  • 将$x$和$y$都右移结果一定不会更优。因为位数更少了
  • 最好的结果一定是下面的这种情况之一
    • $x$固定不动，将$y$右移若干位
    • $y$固定不动，将$x$右移若干位
  • 位数不多，直接暴力循环枚举
神奇的代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
const int mod = 998244353;


void solve()
{
    int x, y;
    std::cin >> x >> y;
    int tmpx = x, tmpy = y;
    int ans = 0;
    while(tmpx)
    {
        ans = std::max(ans, (tmpx ^ y));
        tmpx >>= 1;
    }
    while(tmpy)
    {
        ans = std::max(ans, (tmpy ^ x));
        tmpy >>= 1;
    }
    std::cout << std::max({ans, x, y}) << endl;
}


signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
    int _t = 1;
    std::cin >> _t;
    while (_t--) solve();
    return 0;
}

$C.$小苯的数位排序

  • 一个数通过这样的操作一定会变得更小
  • 一个数一直这样操作会变成个位数，然后就无法操作了
  • 最后一个数尽量不操作
  • 我们倒序遍历，只要比后面的数大就进行一次操作，直到比后面的数小或者不能操作为止，如果此时还是比后面的数大，返回$-1$
神奇的代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
const int mod = 998244353;

int calc(int x)
{
    int ret = 0;
    while(x)
    {
        ret += (x % 10);
        x /= 10;
    }
    return ret;
}

void solve()
{
    int n = 0; std::cin >> n;
    std::vector<int> a(n + 1, 0);
    int res = 0;
    for (int i = n; i >=1; i--) std::cin >> a[i];
    for (int i = 2; i <= n; i++)
    {
        int tmp = a[i];
        while(tmp > a[i - 1] && tmp >= 10) {tmp = calc(tmp); res++;}
        if (tmp > a[i - 1]) {std::cout << -1 << endl; return;}
        a[i] = tmp;
    }
    std::cout << res << endl;
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
    int _t = 1;
    std::cin >> _t;
    while (_t--) solve();
    return 0;
}

$D.$小苯的路径计数

题目说的是：

路径上所有点颜色都相同。

这句话可以等价理解成：

从祖先走到后代时，路径上的每一条父子边两端颜色都相同。

也就是说，一条路径 $u \to v$ 是合法的，当且仅当从 $u$ 到 $v$ 的过程中，经过的所有边都满足：

$$
c_{\text{father}} = c_{\text{son}}
$$

于是问题就转化为了：

对于每个点 $u$，有多少个后代节点可以通过“连续同色边”从 $u$ 走到？

状态定义

设 $dp_u$ 表示：从节点 $u$ 出发，只沿着“颜色相同”的父子边向下走，最多能够到达的节点数（包含 $u$ 自己）。

那么对于每个点 $u$：

  • $dp_u$ 包含了自己
  • 因此以 $u$ 为起点的合法路径条数就是

$$
dp_u - 1
$$

最终答案为：

$$
\sum_{u=1}^n (dp_u - 1)
$$

状态转移

假设 $v$ 是 $u$ 的一个儿子。

  • 如果 $c_v \ne c_u$，那么从 $u$ 出发不能通过这条边继续向下延伸
  • 如果 $c_v = c_u$，那么从 $v$ 出发能够到达的所有同色节点，从 $u$ 出发同样都可以到达

因此有转移方程：

$$
dp_u = 1 + \sum_{v \in son(u),\ c_v = c_u} dp_v
$$

其中：

  • $1$ 表示节点 $u$ 自己
  • 只有颜色相同的儿子才会对父亲产生贡献

为什么这样做是对的？

1. 为什么转移正确？

如果某个儿子 $v$ 与当前点 $u$ 颜色相同，那么：

  • 从 $v$ 出发能走到的所有同色后代
  • 在前面再接上一个 $u$
  • 依然构成一条全同色路径

因此可以直接把 $dp_v$ 累加到 $dp_u$ 中。

2. 为什么答案是 $\sum (dp_u - 1)$？

因为 $dp_u$ 统计的是：

从 $u$ 出发可达的所有同色节点个数，其中包含 $u$ 自己。

而题目要求路径满足 $u \ne v$，所以不能把“自己到自己”算进去。

故每个点贡献：

$$
dp_u - 1
$$

把所有点的贡献求和即可。

3. 为什么不会重复统计？

因为每一条合法路径都唯一对应一个起点 $u$。

而 $dp_u - 1$ 统计的，正是：

所有以 $u$ 为起点的同色路径数量。

所以每条路径只会在其起点处被统计一次，不会重复。

计算 $dp$

从下往上看：

  • $dp_4 = 1$
  • $dp_5 = 1$
  • $dp_3 = 1$

对于节点 $2$：

  • 儿子 $4$ 与 $2$ 同色，可以贡献
  • 儿子 $5$ 与 $2$ 不同色，不能贡献

所以：

$$
dp_2 = 1 + dp_4 = 2
$$

对于节点 $1$：

  • 儿子 $2$ 与 $1$ 同色，可以贡献
  • 儿子 $3$ 与 $1$ 不同色，不能贡献

所以：

$$
dp_1 = 1 + dp_2 = 3
$$

最终：

$$
dp_1 = 3,\quad dp_2 = 2,\quad dp_3 = 1,\quad dp_4 = 1,\quad dp_5 = 1
$$

答案为：

$$
(dp_1 - 1) + (dp_2 - 1) + (dp_3 - 1) + (dp_4 - 1) + (dp_5 - 1)
$$

即：

$$
2 + 1 + 0 + 0 + 0 = 3
$$

与实际结果一致。

复杂度分析

每条边只会在 DFS 中被遍历常数次，因此：

  • 时间复杂度：$O(n)$

  • 空间复杂度：$O(n)$

神奇的代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
const int mod = 998244353;

void solve()
{
    int n = 0; std::cin >> n;
    std::vector<std::vector<int>> g(n + 1);
    std::vector<int> col(n + 1, 0);

    for (int i = 1; i <= n; i++) std::cin >> col[i];

    for (int i = 1; i < n; i++)
    {
        int u, v; 
        std::cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    std::vector<int> dp(n + 1, 1);

    auto dfs = [&](auto&& dfs, int s, int fa) -> void
    {
        for (int v : g[s])
        {
            if (v == fa) continue;
            dfs(dfs, v, s);
            if (col[v] == col[s]) dp[s] += dp[v];
        }
    };

    dfs(dfs, 1, 0);

    int ans = 0;
    for (int i = 1; i <= n; i++) ans += (dp[i] - 1);

    std::cout << ans << endl;
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int _t = 1;
    std::cin >> _t;
    while (_t--) solve();

    return 0;
}

$E.$小苯的数字染色

问题转化

由于每次选择的区间都必须全部是白色，所以一旦某个区间被染红，这一段位置以后就再也不能参与其他操作。

因此，若进行了若干次操作，那么本质上就是：

选择若干个 两两不相交 的区间，每个区间 $[l,r]$ 需要满足端点奇偶性相同，并贡献分数 $a_l+a_r$。

于是题目就转化为一个经典模型：

从左到右考虑前缀，维护前若干个位置的最优答案。

状态设计

设$dp_i$表示：只考虑前 $i$ 个位置时，能够获得的最大分数。

那么转移时，讨论位置 $i$ 是否作为某个区间的右端点。

情况一：不选任何以 $i$ 结尾的区间

那么直接继承前一个位置的最优值：

$$
dp_i = dp_{i-1}
$$

情况二：选择某个区间 $[j,i]$

要求：

  • $j < i$
  • $a_j$ 与 $a_i$ 奇偶性相同

此时这个新区间的贡献为：

$$
a_j + a_i
$$

而由于区间之间不能重叠，所以在它左边只能接上前 $j-1$ 个位置的最优解，即：

$$
dp_{j-1}
$$

因此若选择区间 $[j,i]$，总收益为：

$$
dp_{j-1} + a_j + a_i
$$

于是得到转移：

$$
dp_i = \max\left(dp_{i-1},\ \max_{\substack{j<i\a_j\equiv a_i\pmod 2}} \left(dp_{j-1}+a_j+a_i\right)\right)
$$

优化

直接枚举所有 $j$ 会导致复杂度为 $O(n^2)$)，显然不可行。

观察上式，对固定的 $i$ 来说，$a_i$ 是一个常数，因此真正需要维护的是：

$$
\max_{\substack{j<i\a_j\equiv a_i\pmod 2}} \left(dp_{j-1}+a_j\right)
$$

而一个数的奇偶性只有两种：

  • 偶数
  • 奇数

于是我们只需要维护两个值：

设

$$
best_0
$$

表示当前所有 偶数 左端点中，最大的

$$
dp_{j-1}+a_j
$$

设

$$
best_1
$$

表示当前所有 奇数 左端点中，最大的

$$
dp_{j-1}+a_j
$$

这样，当枚举到右端点 $i$ 时，只需要看 $a_i$ 的奇偶性，就能在 $O(1)$ 时间内得到最优转移。

转移过程

设当前处理到位置 $i$，记

$$
p = a_i \bmod 2
$$

为了兼容负数，代码中可以写成：

$$
p = ((a_i % 2)+2)%2
$$

那么：

1. 默认不选当前位置结尾的区间

$$
dp_i = dp_{i-1}
$$

2. 尝试选一个以 $i$ 为右端点的区间

若此前存在同奇偶性的左端点，则可以转移：

$$
dp_i = \max(dp_i,\ best_p + a_i)
$$

3. 将当前位置作为未来某个区间的左端点加入维护

因为以后如果要选择区间 $[i,k]$，那么它左边最多只能接前 $i-1$ 个位置的最优解，所以应更新：

$$
best_p = \max(best_p,\ dp_{i-1}+a_i)
$$

举个例子

考虑序列：

$$
[1,4,3,2]
$$

它们的奇偶性分别为：

  • $1$ 是奇数
  • $4$ 是偶数
  • $3$ 是奇数
  • $2$ 是偶数

可以形成的合法区间有：

  • $[1,3]$，贡献为 $1+3=4$
  • $[2,4]$，贡献为 $4+2=6$

由于这两个区间重叠，不能同时选择，因此答案应为：**$6$**

下面看 DP 过程。

  • $i=1$当前位置不能作为右端点，因为区间长度至少为 $2$。

    所以：$dp_1 = 0$

    然后把位置 $1$ 作为未来左端点加入维护：$best_{\text{odd}} = dp_0 + a_1 = 1$

$ $

  • $i=2$先继承前缀最优：$dp_2 = dp_1 = 0$

    位置 $2$ 是偶数，但当前没有可用的偶数左端点，所以无法形成新区间。

    更新左端点信息：

    $$
    best_{\text{even}} = dp_1 + a_2 = 4
    $$

$ $

  • $i=3$先继承前缀最优：$dp_3 = dp_2 = 0$

    位置 $3$ 是奇数，可以和之前奇数左端点配对：

    $$
    dp_3 = \max(0,\ best_{\text{odd}}+a_3)=\max(0,1+3)=4
    $$

    然后更新：

    $$
    best_{\text{odd}} = \max(1,\ dp_2+a_3)=\max(1,3)=3
    $$

  • $i=4$先继承前缀最优：$dp_4 = dp_3 = 4$

    位置 $4$ 是偶数，可以和之前偶数左端点配对：

    $$
    dp_4 = \max(4,\ best_{\text{even}}+a_4)=\max(4,4+2)=6
    $$

最终答案为：

$$
dp_4 = 6
$$

复杂度分析

每个位置只会被扫描一次，并进行常数次更新，因此：

  • 时间复杂度: $O(n)$
  • 空间复杂度: $O(n)$
神奇的代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
#define endl '\n'
#define int long long

void solve()
{
    int n = 0;
    std::cin >> n;

    std::vector<int> a(n + 1, 0);
    for (int i = 1; i <= n; i++) std::cin >> a[i];

    const int INF = (int)4e18;
    std::vector<int> dp(n + 1, 0), best(2, -INF); // best[0] 偶, best[1] 奇

    for (int i = 1; i <= n; i++)
    {
        dp[i] = dp[i - 1];

        int flag = ((a[i] % 2) + 2) % 2;

        if (best[flag] != -INF)
        {
            dp[i] = std::max(dp[i], best[flag] + a[i]);
        }

        best[flag] = std::max(best[flag], dp[i - 1] + a[i]);
    }

    std::cout << dp[n] << endl;
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int _t = 1;
    std::cin >> _t;
    while (_t--) solve();
    return 0;
}

$F.$小苯的对称序列

注意到：

设某个对称子序列的公共和为 $S$，那么它一定满足：

$$
\text{第 }1\text{ 个} + \text{倒数第 }1\text{ 个} = S
$$

$$
\text{第 }2\text{ 个} + \text{倒数第 }2\text{ 个} = S
$$

$$
\dots
$$

于是，一个对称子序列一定是围绕着某个固定和 $S$ 构造出来的。

因此我们可以考虑：

**枚举这个公共和 $S$**，然后求在固定 $S$ 的条件下，最长能取多长。

为什么可以枚举 $S$？

题目给出：

$$
1 \le a_i \le 1000
$$

所以任意两个数之和一定满足：

$$
2 \le a_i + a_j \le 2000
$$

也就是说，公共和 $S$ 只可能在区间：

$$
[2,2000]
$$

一共只有 $1999$ 种可能，完全可以枚举。

状态设计

固定一个和 $S$ 之后，定义二维状态：

$$
dp[l][r]
$$

表示：

在区间 $[l,r]$ 中，能够选出的、满足“首尾配对和都等于 $S$”的最长对称子序列长度。

这个定义非常自然，因为一个对称子序列本质上就是“最外层一对 + 中间继续对称”。

这和最长回文子序列的区间 DP 十分相似。

状态转移

对于区间 $[l,r]$，有三种决策方式：

1. 不选左端点 $a_l$

那么答案就是：

$$
dp[l][r] = dp[l+1][r]
$$

2. 不选右端点 $a_r$

那么答案就是：

$$
dp[l][r] = dp[l][r-1]
$$

3. 选 $a_l$ 和 $a_r$ 作为最外层一对

这要求：

$$
a_l + a_r = S
$$

如果满足，那么它们可以作为当前子序列的最外层一对，中间继续在 $[l+1,r-1]$ 中寻找。

于是有：

$$
dp[l][r] = dp[l+1][r-1] + 2
$$

因此总转移为：

$$
dp[l][r]=
\begin{cases}
\max\bigl(dp[l+1][r],\ dp[l][r-1],\ dp[l+1][r-1]+2\bigr), & a_l+a_r=S,\[4pt]
\max\bigl(dp[l+1][r],\ dp[l][r-1]\bigr), & a_l+a_r\ne S.
\end{cases}
$$

边界条件

当 $l=r$ 时，区间里只有一个元素。

单独一个元素本身也可以构成长度为 $1$ 的对称子序列，但它要想在当前固定的和 $S$ 下合法，必须满足：

$$
a_l + a_l = S
$$

即：

$$
2a_l = S
$$

所以边界为：

$$
dp[l][l] =
\begin{cases}
1, & 2a_l = S \
0, & \text{Otherwise}
\end{cases}
$$

为什么单点的边界这样设？

这是因为如果一个对称子序列长度为奇数，那么最中间那个数会和自己配对。

例如长度为 $5$ 时：$a_{i_1}+a_{i_5} = a_{i_2}+a_{i_4} = a_{i_3}+a_{i_3}$

也就是说中间那个数必须满足：

$$
2a_{i_3}=S
$$

因此当只剩一个数时，它只有在 $2a_l=S$ 时才能作为中心点贡献 $1$。

转移顺序

因为 $dp[l][r]$ 依赖于：

  • $dp[l+1][r]$
  • $dp[l][r-1]$
  • $dp[l+1][r-1]$

所以应按区间长度从小到大枚举。

具体来说：

  1. 先处理长度为 $1$ 的区间
  2. 再处理长度为 $2,3,\dots,n$ 的区间

这样在计算 $dp[l][r]$ 时，所有需要的更短区间状态都已经算好。

理解

这个区间 DP 的逻辑可以类比最长回文子序列：

  • 如果最优解不使用左端点，那么它一定包含在 $[l+1,r]$ 中
  • 如果最优解不使用右端点，那么它一定包含在 $[l,r-1]$ 中
  • 如果最优解同时使用了左右端点，那么必须满足 $a_l+a_r=S$，并且内部部分也必须继续构成同样公共和为 $S$ 的对称子序列

因此，这三种情况已经完整覆盖了所有可能性。

举个例子

考虑数组：

$$
[1,6,4,3,2,5]
$$

我们尝试固定：

$$
S=6
$$

此时满足两端和为 $6$ 的配对有：

  • $1+5=6$
  • $4+2=6$
  • $3+3=6$

于是可以选出子序列：

$$
[1,4,3,2,5]
$$

长度为 $5$，因为：

$$
1+5 = 4+2 = 3+3 = 6
$$

所以对于这个例子，答案至少为 $5$。

复杂度分析

公共和 $S$ 的范围是：$2 \sim 2000$

每枚举一个 $S$，都需要做一次区间 DP，复杂度为：$O(n^2)$

因此总复杂度为：$O(2000 \cdot n^2)$

由于本题中：$n \le 500$

因此这一复杂度可以接受。

空间复杂度为：$O(n^2)$

神奇的代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
const int mod = 998244353;

int dp[505][505];

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

    std::vector<int> vis(2001, 0), sum;
    for (int i = 1; i <= n; i++) vis[a[i] * 2] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            vis[a[i] + a[j]] = 1;
        }
    }
    for (int s = 2; s <= 2000; s++)
    {
        if (vis[s]) sum.push_back(s);
    }

    int ans = 1;

    for (int S : sum)
    {
        for (int i = 1; i <= n; i++)
        {
            dp[i][i] = (a[i] * 2 == S ? 1 : 0);
        }

        for (int len = 2; len <= n; len++)
        {
            for (int l = 1; l + len - 1 <= n; l++)
            {
                int r = l + len - 1;
                dp[l][r] = std::max(dp[l + 1][r], dp[l][r - 1]);

                if (a[l] + a[r] == S)
                {
                    if (len == 2) dp[l][r] = std::max(dp[l][r], 2LL);
                    else dp[l][r] = std::max(dp[l][r], dp[l + 1][r - 1] + 2);
                }
            }
        }

        ans = std::max(ans, dp[1][n]);
    }

    std::cout << ans << endl;
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);

    int _t = 1;
    std::cin >> _t;
    while (_t--) solve();

    return 0;
}