题解 | #小苯的转盘游戏#

A 小苯的转盘游戏

观察得知,我们可以通过+3-2和+3-2-2实现+1 -1操作,输出YES即可

void solve(){
    int x,y;  cin >> x >> y;
    cout << "YES\n";
}	

B 小苯的最大异或

无论是对还是对执行操作都是非常有限的，我们可以暴力枚举操作次数，然后在枚举对 的操作次数，全程取即可.

void solve(){
    int x,y;  cin >> x >> y;
    int s1 = 0, s2 = 0;
    for (int i=0; (1<<i)<=x; i++){
        s1 = i;
    }
    s1++;
    for (int i=0; (1<<i)<=y; i++){
        s2 = i;
    }
    s2++;  s1 += s2;
    int ans = 0;
    for (int i=0; i<=s1; i++){
        for (int j=0; j<=i; j++){
            int v1 = x>>j, v2 = y>>(i-j);
            ans = max(ans,(v1^v2));
        }
    }
    cout << ans << '\n';
}	

C 小苯的数位排序

对于数,始终有，因此我们想要得到一个非递减数组需要保证右侧的元素尽可能大，从后往前开始模拟，求需要操作的次数。

i64 get(i64 x){
    i64 res = 0;
    while(x){
        res += x%10;
        x /= 10;
    }
    return res;
}
void solve(){
    int n;  cin >> n;
    vector<i64>a(n+1);
    for (int i=1; i<=n; i++) cin >> a[i];
    int ans = 0;
    for (int i=n-1; i>=1; i--){
        if (a[i+1] >= a[i]){
            continue;
        }
        else {
            while(a[i] >= 10 and a[i+1] < a[i]){
                a[i] = get(a[i]);
                ans++;
            }
            if (a[i] > a[i+1]){
                cout << "-1\n";
                return;
            }
        }
    }
    cout << ans << '\n';
}	

D 小苯的路径计数

定义表示从根结点出发到为止的合法路径方案数，考虑到达了节点，只有满足，才可继承父节点的路径方案数，且多出了一条的路径，即，遍历一遍树即可，最后统计答案。

void solve(){
    int n;  cin >> n;
    vector<vector<int>>g(n+1);
    vector<int>c(n+1);
    for (int i=1; i<=n; i++){
        cin >> c[i];
    }
    for (int i=1; i<n; i++){
        int u,v;  cin >> u >> v;
        g[u].pb(v);  g[v].pb(u);
    }
    vector<i64>dp(n+1);
    auto dfs = [&](auto &self, int u, int fa) -> void{
        for (int v:g[u]){
            if (v == fa)continue;
            if (c[v] == c[u]){
                dp[v] = dp[u] + 1;
            }
            self(self,v,u);
        }  
    };
    dfs(dfs,1,0);
    i64 ans = 0;
    for (int i=1; i<=n; i++) ans += dp[i];
    cout << ans << "\n";
}	

E 小苯的数字染色

定义状态表示到为止，经过一系列染色后得到的最大得分。考虑状态转移，首先很容易想到不进行染色，此时 考虑选择位置进行染色，此时我们需要考虑前个数中 其中 ，然后我们会发现暴力往前转移显然不行，这样复杂度达到. 考虑如何优化转移，我们发现每次转移使用，考虑用数组记录奇偶前缀的最大值,使得每次转移优化到.

void solve(){
    int n;  cin >> n;
    vector<i64>dp(n+1),a(n+1);
    for (int i=1; i<=n; i++){
        cin >> a[i];
    }
    int c = (a[1]%2+2)%2;
    i64 mx[2] = {-INF,-INF};
    mx[c] = dp[0] + a[1];
    for (int i=2; i<=n; i++){
        dp[i] = max(dp[i],dp[i-1]);
        int op = (a[i]%2+2)%2;
        dp[i] = max(dp[i],mx[op]+a[i]);
        mx[op] = max(mx[op],dp[i-1]+a[i]);
    }
    i64 ans = 0;
    for (int i=1; i<=n; i++) ans = max(ans,dp[i]);
    cout << ans << "\n";
}

F 小苯的对称序列

我们先考虑把对称的位置按照分组,区间表示与对称，对于和为的所有,相当于求出符合条件的最大整数,答案为，当然如果在区间内存在一个数满足此时答案为. 考虑如何求解，我们发现选定的个区间一定不存在或，我们可以先对所有整数对排序，按照升序排序，相等，按照降序排序。 对所有排序后，我们根据把进行分组 定义状态表示左右端点为时能得到的最大的值,联想到我们的排序策略,我们会发现所有满足的是我们已经处理过的，这样转移完全可行。又因为我们依照进行了分组处理，所以这样转移也不会出现的情况，我们只需要求出进行转移即可。用滚动数组记录状态，数组记录在前的状态,数组求解考虑时的新状态. 同时不要忘记的情况 注意要特判的情况

void solve(){
    int n;  cin >> n;
    vector<int>a(n+1);
    for (int i=1; i<=n; i++){
        cin >> a[i];
    }
    if (n == 1){
        cout << "1\n";
        return;
    }
    vector<vector<pii>>g(2005);
    for (int l=1; l<=n; l++){
        for (int r=l+1; r<=n; r++){
            g[a[l]+a[r]].pb({l,r});
        }
    }
    int ans = 0;
    vector<int>dp(n+1),f(n+1),tmp(n+1);
    for (int s=2; s<=2000; s++){
        auto &seg = g[s];
        if (seg.empty())continue;
        sort(all(seg),[&](auto x, auto y){if (x.fir != y.fir) return x.fir < y.fir;return x.sec > y.sec;});
        f = dp = tmp;
        for (int i=0; i<seg.size(); i++){
            int j = i, px = 0,mx = 0;
            int cl = seg[i].fir;
            while(j < seg.size() and seg[j].fir == cl){
                auto [l,r] = seg[j];
                int id = n-r+1;
                while(px<id){
                    mx = max(mx,f[px]);
                    dp[px] = max(dp[px],f[px]);
                    px++;
                }
                if (dp[id] <= mx + 1){
                    dp[id] = mx + 1;
                    if (s%2 == 0){
                        for (int k=l+1; k<r; k++){
                            if (a[k] == s/2){
                                ans = max(ans,dp[id]*2+1);
                            }
                        }
                    }
                }
                ans = max(ans,dp[id]*2);
                j++;
            }
            for (int j=1; j<=n; j++){
                dp[j] = max(dp[j],f[j]);
            }
            f.swap(dp);
            dp=tmp;
            i = j-1;
        }
    }
    cout << ans << '\n';
}