A.小苯的转盘游戏

操作等价于 $+1$ 和 $-1$ ，因此无论如何答案为 $YES$ 。

时间复杂度 $O(1)$ 。

void solve(){
    puts("YES");
}

B.小苯的最大异或

共有 $30 * 30$ 种情况，全部遍历取最大即可。

时间复杂度 $O(logx*logy)$ 。

void solve(){
    ll x = read(), y = read(), ans = 0;
    for(ll i=0;i<30;i++){
        ll xx = x;
        for(ll j=0;j<30;j++){
            ans = max(ans, xx^y);
            xx>>=1;
        }
        y>>=1;
    }
    print(ans);
}

C.小苯的数位排序

对于 $x \in [1, 10^{18}]$ 最多操作 $3$ 轮后，会使得 $x = digit\_sum(x)$ 。

因此预处理每个数字操作三次后的数，总共四个。令 $b[i][j]$ 为 $a_i$ 操作 $j$ 次后的数字。

令 $dp[i][j]$ 为前 $i$ 个数字，且第 $i$ 个数字操作了 $j$ 次后的最小操作次数。

则有

dp[i][j] = \min_{\substack{k \in \{0,1,2,3\} \\ \text{b}[i-1][k] \le \text{b}[i][j]}} \left( dp[i-1][k] + j \right), \quad i \ge 1,\ j \in \{0,1,2,3\}

时间复杂度 $O(3*3*n)$ 。

void solve(){
    ll n = read();
    vector<ll> a(n+1);
    for(ll i=1;i<=n;i++) a[i] = read();
    vector<vector<ll>> b(n+1, vector<ll>(4)),dp(n+1, vector<ll>(4, INF));
    for(ll i=1;i<=n;i++){
        b[i][0] = a[i];
        for(ll j=1;j<=3;j++){
            ll pre = b[i][j-1];
            ll sum = 0;
            while(pre){
                sum += pre%10;
                pre/=10;
            }
            b[i][j] = sum;
        }
    }
    dp[0][0] = 0;
    for(ll i=1;i<=n;i++){
        for(ll pre=0;pre<=3;pre++){
            for(ll cur=0;cur<=3;cur++){
                if(b[i-1][pre]<=b[i][cur]){
                    dp[i][cur] = min(dp[i-1][pre]+cur, dp[i][cur]);
                }
            }
        }
    }
    ll ans = *min_element(all(dp[n]));
    print(ans==INF?-1:ans);
}

D.小苯的路径计数

令 $dp[u]$ 为以 $u$ 为父节点的路径的数量。

则可以有所有和其同颜色的子节点扩展而来，即：

dp[u] = \sum_{\substack{c_u = c_v}} dp[v] + 1, v\in g[u] , v\ne fa[u]

时间复杂度 $O(n)$ 。

void solve(){
    ll n = read();
    vector<ll> c(n+1);
    for(ll i=1;i<=n;i++) c[i] = read();
    vector<vector<ll>> g(n+1);
    for(ll i=1;i<=n-1;i++){
        ll u = read(), v = read();
        g[u].pb(v);
        g[v].pb(u);
    }
    ll ans = 0;
    vector<ll> cnt(n+1);
    function<void(ll, ll)> dfs = [&](ll u, ll p){
        ll pre = 0;
        cnt[u] = 0;
        for(auto v:g[u]){
            if(v == p) continue;
            dfs(v, u);
            if(c[u] == c[v]){
                cnt[u] += cnt[v] + 1;
            }
        }
        ans += cnt[u];
    };
    dfs(1, 0);
    print(ans);
}

E.小苯的数字染色

令 $dp[i]$ 为必选第 $i$ 个数字前 $i$ 个数字的最大得分。 $pre[i]$ 为前 $i$ 个数字的最大得分。

则

dp[i] = \max_{\substack{a[i] \equiv a[j] \pmod{2}}} a[i] + a[j] + pre[j-1],j \in [1, i-1]

考虑优化，把 $a[j] + pre[j-1]$ 变为一样，分 $a[j]$ 奇偶记录。转移 $a[i]$ 时找奇偶相同的即可。

时间复杂度 $O(n)$ 。

void solve(){
    ll n = read();
    vector<ll> a(n+1);
    for(ll i=1;i<=n;i++) a[i] = read();
    ll odd = -INF, even = -INF;
    vector<ll> dp(n+1),premx(n+1);
    for(ll i=1;i<=n;i++){
        if(a[i]&1) dp[i] = max(dp[i], odd+a[i]);
        else dp[i] = max(dp[i], even+a[i]);
        premx[i] = max(premx[i-1], dp[i]);
        if(a[i]&1) odd = max(odd, premx[i-1]+a[i]);
        else even = max(even, premx[i-1]+a[i]);
    }
    print(*max_element(all(dp)));
}

F.小苯的对称序列

不妨考虑枚举 $S = a_{i_1} + a_{i_m}$ ，即匹配对之和。其范围为 $[2, 2000]$ 。

令 $dp[l][r]$ 为区间 $[l, r]$ 内的最长长度。

对于长度为 $1$ 的区间，若 $a[i] * 2 = S$ ，则 $dp[i][i] = 1$ ，否则为 $0$ 。
若 $a[l]$ , $a[r]$ 均不选择，则 $dp[l][r] = max\{dp[l][r-1], dp[l+1][r],dp[l+1][r-1]\}$ 。
若 $a[l]+a[r]=S$ ，则额外一项 $dp[l][r] = max\{dp[l][r], dp[l+1][r-1] + 2\}$ 。

时间复杂度 $O(\max\{a_i\}*n^2)$ 。