[ARC219F] Range Division 题解

FFTotoro · 2026-05-11 21:49:18 · 题解

这个神秘的题意看上去就不太可做，因为很难决策每个数究竟要在什么时刻操作。从直觉上来讲，我们希望尽量让相邻的元素一起操作以减少次数。

不妨将 A_i 的二进制表示（不含前导 0）对应的 01 串记为 S_i，此时基础操作次数（即不进行任何区间长度 >1 的操作）即为 S_i 长度之和。两个元素只有在二进制最低位相同时才能进行共同操作，也就是说，对于两个元素 A_{i-1},A_i，最终减少的操作次数几乎就是 S_{i-1} 与 S_i 的最长公共子序列的长度（以下记为 \operatorname{lcs}(S_{i-1},S_i)）。

为什么说是“几乎”呢？操作过程中 A_i 变成 0 之后仍然能进行操作（如果能把左右两边的元素“连起来”一起操作，有机会减少次数），而此时 S_i 已经被删空了。解决办法就是在 S_i 前面加上若干个 0，但是无法直接确定要加多少个。

观察到数据范围很小（以下记 S_i 的长度上界为 V=\log_2\max A_i=60），尝试直接通过 DP 决策这个事情。令 S_i 前加入的 0 有 c_i 个，简单分析即可得出，一定存在一种最优策略，使得 c_i 不会超过 (N-1)V。

::::info[对于 c_i 上界的分析] 考虑 c_i 在最极端的情况下一定不会超过多少。

首先至少有一个 c_i=0，不然可以把所有字符串开头都一起删一个 0 并让答案变得更优。

不妨认为 c_1=0（仿照下面的思路分析，会发现其他情况的上界不会更大）。由于 c_2 的目的是让 S_1 和 S_3 能够共同操作，所以一定不会超过 S_1 中 0 的个数，即 c_2\le V；同理有 c_3\le c_2+V=2V……归纳可得 \max c_i\le(n-1)V。

其实这个上界很多情况下都取不到，不过已经足够了。 ::::

现在把答案写得更加形式化一点。规定 S_i(c_i) 为 S_i 前加入了 c_i 个 0 得到的字符串，操作次数即为：

计算 \operatorname{lcs}(S_i(c_i),S_{i-1}(c_{i-1})) 是简单的：令 m=\min\{c_{i-1},c_i\}，则该值等于 m+\operatorname{lcs}(S_i(c_i-m),S_{i-1}(c_{i-1}-m))，即两个字符串至少有一个就是原来的 S。这样大大简化了问题，只用对于 i\in[2,N] 预处理一下两种情况（可以通过简单 DP 实现）。另外观察到一个事实：若当前需要计算 \operatorname{lcs}(S_i(l),S_{i-1})（另一种情况同理），其实等价于计算 \operatorname{lcs}(S_i(\min\{l,V\}),S_{i-1})，对于每个 i，预处理的时间复杂度可以降为 O(V^2)。

令 f_{i,j} 为考虑了前 i 个位置且 c_i=j 的最小操作次数，转移直接暴力枚举 c_{i-1} 和 c_i，利用预处理出来的 \operatorname{lcs} 计算贡献。最终的时间复杂度为 O(N^3V^2)。如果枚举时额外保证 |c_i-c_{i-1}|\le V（正确性可以参考上文的 c_i 上界证明），可以做到 O(N^2V^2)。

具体实现中将 S_i 做了翻转，这样就可以转换为在末尾加入 0 而不是在开头，相对好写一点；并且注意代码中的下标从 0 开始。参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef basic_string<int> S;
const int V=60,I=1e9;
vector<int> lcs(S s,S t){
  t+=S(V,0); // 先在末尾加一些 0
  int n=s.length(),m=t.length();
  vector f(n+1,vector<int>(m+1));
  for(int i=0;i<=n;i++)
    for(int j=0;j<=m;j++){
      if(i<n&&j<m&&s[i]==t[j]){
        f[i+1][j+1]=max(f[i+1][j+1],f[i][j]+1);
      }
      else{
        if(i<n)f[i+1][j]=max(f[i+1][j],f[i][j]);
        if(j<m)f[i][j+1]=max(f[i][j+1],f[i][j]);
      }
    } // 经典的 LCS DP
  vector<int> r;
  for(int i=0;i<=V;i++)
    r.emplace_back(f[n][m-i]);
  reverse(r.begin(),r.end());
  // 对于每一种加 0 的个数都可以 O(1) 求出答案
  return r;
} // DP 预处理所有的 lcs
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int t; cin>>t;
  while(t--){
    int n; cin>>n;
    vector<S> s(n);
    for(int i=0;i<n;i++){
      long long x; cin>>x;
      while(x)s[i]+=x&1,x>>=1;
    } // 转换成 01 串
    int N=(n-1)*V;
    // 注意这里的 N 并非文中的 N，而是 c[i] 的上界
    vector<int> f(N+1);
    for(int i=0;i<=N;i++)
      f[i]=s[0].length()+i; // 基础贡献
    for(int i=1;i<n;i++){
      auto f1=lcs(s[i-1],s[i]),f2=lcs(s[i],s[i-1]);
      // 预处理两种情况：S[i-1] 加 0 或者 S[i] 加 0
      vector<int> g(N+1,I);
      for(int j=0;j<=N;j++)
        for(int k=max(j-V,0);k<=min(N,j+V);k++){
          if(j<=k)g[k]=min(g[k],f[j]-f1[min(k-j,V)]-j);
          else g[k]=min(g[k],f[j]-f2[min(j-k,V)]-k);
        } // 暴力枚举并转移
      for(int j=0;j<=N;j++)
        g[j]+=s[i].length()+j; // 加入基础贡献
      f=move(g); // 滚动数组
    }
    cout<<*min_element(f.begin(),f.end())<<'\n';
  }
  return 0;
}