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

· · 题解

模拟赛暴砍 0 分。

因为 (x\oplus z)+(y\oplus z)\ge x\oplus y，所以将中间那个数改成它两边的数是肯定不劣的，这相当于是将他删除。我们在开头和结尾加入一个不可修改的 0，这样可以将加一个数变为加上它与前一个或后一个的异或，总答案为 \sum\limits_{i=0}^{n}a_i\oplus a_{i+1}。我们将 f_0 赋值为 (n+1)*C，在后面每保留一个数减去 C，得到 dp 方程：f_i=\min\limits_{j=0}^{i-1}(f_j+(a_i\oplus a_j)-C)。

但这个是 O(n^2) 的，考虑优化。首先，将枚举下标改为枚举值域。然后想到二进制平衡规划，定义 g_{h,l} 为从高 9 位为 h 的数转移到低 9 位为 l 的数的最小值。设 a_i 的高 9 位为 H_i，低 9 位为 L_i，转移为：f_i+(l\oplus L_i)\rightarrow g_{H_i,l}，f_i=\min\limits_{h} (g_{h,L_i}+2^9\times(h\oplus H_i))-C。答案为 f_{n+1}。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+7,M=520;
int t,n,C,a[N];
ll g[520][520],f[N];
inline void add(int x,ll val){
    int h=x>>9,l=x&((1<<9)-1);
    for(int i=0;i<(1<<9);i++)g[h][i]=min(g[h][i],val+(l^i));
}
inline ll ask(int x){
    int h=x>>9,l=x&((1<<9)-1);
    ll ans=4e18;
    for(int i=0;i<(1<<9);i++)ans=min(ans,g[i][l]+((i^h)<<9)-C);
    return ans;
}
inline void work(){
    cin>>n>>C,a[0]=a[n+1]=0;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=0;i<=n+1;++i)f[i]=4e18;
    memset(g,0x3f,sizeof(g));
    f[0]=1ll*(n+1)*C;add(0,f[0]);
    for(int i=1;i<=n+1;++i)f[i]=ask(a[i]),add(a[i],f[i]);
    cout<<f[n+1]<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)work();
    return 0;
}