专栏文章

题解：P13687 【MX-X16-T5】「DLESS-3」XOR and Rockets

lluogu_gza我不曾忘记
P13687题解参与者 6已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@mioet1t2
此快照首次捕获于
2025/12/02 18:02
3 个月前
此快照最后确认于
2025/12/02 18:02
3 个月前
查看原文
记 xx 的从低到高的第 bb 位为 F(x,b)F(x,b)。
我们分两种情况讨论，最后一个数操作和不操作。

不操作

不操作的话整个序列的值域不超过 81928192，设 fi,jf_{i,j} 表示当前处理到了 ii 这个位置，aia_i 异或后的值是 jj，直接 dp 是 O(nV2)O(nV^2) 的，简单优化可以做到 O(nV)O(nV)。

操作

我们称区间 [l,r][l,r] 是好的当且仅当存在 xx 满足 al⊕x≤⋯≤ar⊕xa_l\oplus x\leq \cdots \leq a_r\oplus x，然后记最小的合法的 xx 为 f(l,r)f(l,r)。
我们用操作点将整个序列分为若干部分，显然这些部分都需要的好的，记他们分别是 [li,ri](1≤i≤m)[l_i,r_i](1 \leq i \leq m)。
我们记 gi=f(li,ri)⊕21000ig_i=f(l_i,r_i) \oplus 2^{1000i}。将第 ii 个部分异或上 gig_i，即可满足条件。这样我们就不必考虑相邻部分交界点是否递增，而只需要保证内部递增就行了。
也就是说，经过这样的转化后，每个部分都独立了。
于是问题就转移到了，如何在可接受的时间复杂度内求出每一个区间 [l,r][l,r] 是否是好的，将 al∼ara_l \sim a_r 提取出来变成一个序列 cc。
对于一个区间内的相邻点 i,i+1i,i+1，我们限制了 ci⊕x≤ci+1⊕xc_i\oplus x\leq c_{i+1}\oplus x。也就是说，假设 cic_i 和 ci+1c_{i+1} 在第 bb 位第一次出现了分歧（不同），那么这一位异或后的结果一定是 cic_i 是 00，ci+1c_{i+1} 是 11。
也就是说，如果 F(ci,b)=1F(c_i,b)=1，F(ci+1,b)=0F(c_{i+1},b)=0，那么 F(x,b)=1F(x,b)=1，如果 F(ci,b)=0F(c_i,b)=0，F(ci+1,b)=1F(c_{i+1},b)=1，那么 F(x,b)=0F(x,b)=0，显然这些限制不难记录在一个数组里面，只需要看所有的限制有没有冲突就行了。
核心代码：
CPP
const int N=5010,V=8192,inf=1e17;
int n;
int a[N],b[N];
int f[N];
bool can[N][N];
signed nd[N][N];
int dp[N][V],pre[V],suf[V];
void solve()
{
  n=R;
  fo(i,1,n) a[i]=R;
  fo(i,1,n) b[i]=R;
  fo(i,1,n) fo(j,1,n) can[i][j]=0,nd[i][j]=0;
  fo(i,1,n) f[i]=inf;
  f[0]=0;
  fo(i,1,n)
  {
    can[i][i]=1,nd[i][i]=0;
    int nd0[13]={0},nd1[13]={0};
    m1(nd0,0),m1(nd1,0);
    fo(j,i+1,n)
    {
      if(a[j]>a[j-1])
      {
        rep(k,12,0) if((a[j]>>k&1)!=(a[j-1]>>k&1)){nd0[k]=1;break;}
      }
      if(a[j]<a[j-1])
      {
        rep(k,12,0) if((a[j]>>k&1)!=(a[j-1]>>k&1)){nd1[k]=1;break;}
      }
      bool flag=1;
      fo(k,0,12) flag&=(nd0[k]==0||nd1[k]==0);
      if(!flag) break;
      can[i][j]=1;
      fo(k,0,12) if(nd1[k]) nd[i][j]+=(1<<k);
      // cout<<i<<' '<<j<<' '<<nd[i][j]<<endl;
    }
  }
  fo(i,1,n) fo(j,0,i-1) if(can[j+1][i])
  {
    f[i]=min(f[i],f[j]+b[i]);
  }
  int ans1=f[n];
  fo(i,1,n) fo(j,0,V-1) dp[i][j]=1e17;
  fo(j,0,V-1) dp[n][j^a[n]]=(j!=0)*b[n];
  // cout<<dp[n][0]<<endl;
  rep(i,n,1)
  {
    if(i!=n)
    {
      fo(j,0,V-1)
      {
        int val=(a[i]^j^a[i+1]);
        fo(k,val,val) if(j<=k) dp[i][j]=min(dp[i][j],dp[i+1][k]);
        dp[i][j]=min(dp[i][j],suf[j]+b[i]);
      }
    }
    pre[0]=dp[i][0];
    fo(j,1,V-1) pre[j]=min(pre[j-1],dp[i][j]);
    suf[V-1]=dp[i][V-1];
    rep(j,V-2,0) suf[j]=min(suf[j+1],dp[i][j]);
  }
  int ans=1e17;
  fo(i,0,V-1) ans=min(ans,dp[1][i]);
  write(min(ans1,ans)),puts("");
}
void main(){
  MT solve();
}

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...