题解：P17129 [ICPC 2025 Shanghai R] Round screws

ssy666666 · 2026-11-10 15:37:12 · 题解

非常好的一道题。

设 b_i = a_i \oplus a_{i-1}，那么整个序列的权值相当于是 b 的和，单点修就相当于把相邻两个位置都异或上一个值。

经典结论 a \oplus b \le a + b，所以如果你要对于相邻两个位置操作，一定会让一个位置变成 0。

那你对一段操作其实也是同理的，会把前面所有的都变成 0，然后异或到最后一个位置上。

因此，我们可以设计 dp_i 表示前 i 个位置，花费的最小值，设 sum_i = \oplus_{j=1}^i b_j（其实等于 a_i），那么有转移：

考虑优化这个转移，首先这个可以放到值域上去做，时间复杂度 O(nV)，但是你发现修改 O(1)，查询 O(V) 显然不优，根据平衡复杂度的理念，我们考虑平衡这两个东西。

我们设 g_{i,j} 表示从二进制上高九位为 i 的位置，转移到二进制下低九位为 j 的位置，的最小贡献。这里用到了一个性质：异或可以拆位。这样的话可以简单转移，时间复杂度 O(n \sqrt{V})。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std ;
const int MAXN = 1e5 + 7 ;
const int INF = 1e18 + 7 ;

int a[MAXN] , b[MAXN] ;
int sum[MAXN] ;
int dp[MAXN] ;
int g[1 << 9][1 << 9] ; 

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

    int mx = 0 ;
    for (int i = 1 ; i <= n ; i ++) {
        cin >> a[i] ;
        b[i] = a[i] ^ a[i - 1] ;

        mx = max(mx , b[i]) ;
    }

    b[n + 1] = a[n] ;

    for (int i = 1 ; i <= n + 1 ; i ++) {
        sum[i] = sum[i - 1] ^ b[i] ;

        dp[i] = INF ;
    }

    memset(g , 0x3f , sizeof(g)) ;

    for (int i = 0 ; i < (1 << 9) ; i ++) {
        g[0][i] = i ;
    }

    for (int i = 1 ; i <= n + 1 ; i ++) {
        int t = (sum[i] & ((1 << 18) - (1 << 9))) ;
        int l = sum[i] & ((1 << 9) - 1) ;

        for (int j = 0 ; j < (1 << 9) ; j ++) {
            dp[i] = min(dp[i] , g[j][l] + ((j << 9) ^ t) + p * (i - 1)) ;
        }

        for (int j = 0 ; j < (1 << 9) ; j ++) {
            g[t >> 9][j] = min(g[t >> 9][j] , dp[i] + (l ^ j) - p * i) ;
        }
    }

//  for (int j = 1 ; j <= n + 1 ; j ++) {
//      for (int k = 0 ; k < j ; k ++) {
//          dp[j] = min(dp[j] , dp[k] + p * (j - k - 1) + (sum[j] ^ sum[k])) ;
//      }
//  }
//  
    cout << dp[n + 1] << "\n" ;
}

signed main() {
//  freopen("xor.in" , "r" , stdin) ;
//  freopen("xor.out" , "w" , stdout) ;

    ios::sync_with_stdio(0) ;
    cin.tie(0) ;
    cout.tie(0) ;

    int t ;
    cin >> t ;
    while (t--) {
        solve() ;
    }

    return 0 ;
}