[ICPC 2025 Shanghai R] Round screws 题解

· · 题解

下文中默认 \oplus 的运算优先级最高。

首先在序列左右侧插入一个 0，问题本质就是若干个相同段之间有贡献，每一段填平为代表元的值不劣。

定义 f_i 表示以 i 为其中一段代表元、1 \sim i 中已有的代价，立即列出三要素：

f_0 = 0\\ f_i = \min_{j} (( a_i \oplus a_j )+ f_j - jC) + (i-1)C \\ \textrm{answer} = f_{n+1}

由于 n 过大，朴素转移不成立。

这里使用根号分治。定义 a_i 的高 w 位为 h_i，低的 \log V - w 位为 l_i。

定义 g_{i,j}，其中 i \in [0,2^w) 而 j \in [0,2^{\log V - w})：

g_{i,j} = \min_{h_u=i} ((j \oplus l_u) + f_u - uC )

插入时，h_u 固定，由定义枚举 j 即可，时间复杂度 \mathcal{O}(2^{\log V - w})。

访问时，j 固定，需要枚举 i，时间复杂度 \mathcal{O}(2^w)。

均衡 \mathcal{O}(n (2^{\log V - w} + 2^w ) )，取阈值 w = 0.5 \log V，即得到 \mathcal{O}(n\sqrt{V}) 的算法。

#include<bits/stdc++.h>
using namespace std;
const long long inf=1e18;
int T,n,c,a,lo,hi;
long long g[513][513],f;
inline void solve(){
    for(int i=0; i<512; i++) for(int j=0; j<512; j++) g[i][j]=inf;
    cin>>n>>c;
    for(int i=0; i<=n+1; i++){
        if(i==0 or i==n+1) a=0;
        else cin>>a;
        lo=a&((1<<9)-1), hi=((a-lo)>>9), f=inf;
        if(i==0) f=0;
        else for(int j=0; j<512; j++) f=min(f,g[j][lo]+((j^hi)<<9)+1ll*(i-1)*c);
        if(i==n+1) cout<<f<<"\n";
        else for(int j=0; j<512; j++) g[hi][j]=min(g[hi][j],f+(j^lo)-1ll*i*c);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>T; while(T--) solve();
    return 0;
}