# CF1684H Hard Cut 题解

何 $*3400$？

洛谷传送门

CF 传送门

题意

给定 $01$ 串 $s$，要求将 $s$ 划分为若干区间，使得每段区间视为二进制数的和为 $2$ 的幂次。

思路

设 $s$ 中 $1$ 的数量为 $cnt$，$cnt=0$ 显然无解。

设最后的和为 $2^d$，手玩可以发现 $d$ 若是 $O(n)$ 级别则很难有解，但 $2^d$ 是 $O(n)$ 级别则几乎有解，于是可以假定 $d$ 是 $O(\log n)$ 级别的。

一个直觉是 $2^d$ 与 $cnt$ 越接近越容易有解，因为这意味着每个区间的长度都不长，从而能划分出更多的区间，调整空间也更大。

考虑从小到大枚举 $d$ 并判断能否取到，首先能取到显然 $2^d\ge cnt$。

于是可以想到以下贪心：设当前已经划分的总和为 $sum$，每次选择最长的前缀（设其代表的二进制数为 $v$）满足 $sum+v+\text{去除该前缀后 1 的个数}\le 2^d$。取最长前缀的目的是使后面需要的总和与 $1$ 的个数差距最小。

发现没什么反例，交一发就过了。

事实上对于绝大多数 $s$，只需考虑最小的 $d$ 满足 $2^d\ge cnt$ 即能构造出方案，详见下面的证明。

代码

#include <bits/stdc++.h>
using namespace std;
int n,c;
string s;
bool check(int d){
  if(d<c) return 0;
  vector<pair<int,int> >res;
  int cnt=c;
  for(int i=1,j,v;i<=n;i=j+1){
    j=i-1,v=0;
    while(j<n&&v*2+cnt<=d) j++,v=v*2+s[j]-'0',cnt-=s[j]-'0';
    res.emplace_back(i,j),d-=v;
  }
  if(d) return 0;
  cout<<res.size()<<"\n";
  for(auto [l,r]:res) cout<<l<<" "<<r<<"\n";
  return 1;
}
void solve(){
  cin>>s,n=s.length(),s=" "+s,c=0;
  for(int i=1;i<=n;i++) c+=s[i]-'0';
  if(!c){cout<<"-1\n";return;}
  for(int d=1;!check(d);d<<=1);
}
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int Ca;cin>>Ca;while(Ca--)solve();
  return 0;
}

证明 by ChatGPT

设 $m=\operatorname{cnt}_1(s)$。若 $m=0$，所有段的值都为 $0$，显然无解。下设 $m>0$。

固定目标 $T=2^d\ge m$。贪心每次取最长前缀 $v$，满足

这里把剩余字符全部单独切开时，它们的和恰好是 $sufcnt1$，因此该条件表示：当前切法仍有可能不超过 $T$。

下面证明从最小的 $2^d\ge m$ 开始枚举一定能成功。

1. 贪心失败时的必要条件

假设目标 $T$ 时贪心最终切出了若干段。对第 $i$ 段记

并定义

$e_i$ 就是相比于把这一段全部拆成单字符后，多出来的贡献。

假设最后没有达到 $T$，而是还差

令

显然

考虑任意一个非最后段。由于贪心已经取了最长合法前缀，若再把下一位 $b$ 接进来，该段的值变为 $2v_i+b$，而后缀的 $1$ 数减少 $b$，所以必有

另一方面最终总和为 $T-\delta$，即

两式相减得到

这是核心不等式。

一个含 $c_i$ 个 $1$ 的二进制数至少为 $2^{c_i}-1$，故

于是

而 $c_i-e_i>0$ 时只能有两种情况：

或

由 (2)，$v_i=1$ 不可能出现在非最后段，所以至多出现一次。

同时 $v_i=3$ 至多出现两次：若出现三个，取最左边那个，则它右边至少还有两个 $e=1$，由 $\delta\ge1$，

矛盾。

因此

结合 (1) 得

即

所以，若目标 $T$ 贪心失败，则必有 $m\le T-m+2$。

2. 最小的二次幂几乎一定成功

令 $P$ 为最小的满足

的 $2$ 的幂。

若 $P=m$，把所有字符单独切开时总和已经是 $P$，贪心显然成功。

下面设 $P>m$，并令

由于 $P$ 是最小的二次幂，

因此

即

若贪心失败，由 (3) 又有

故只能全部取等：

因此必须恰好出现两个 $v_i=3$ 和一个最后的 $v_i=1$。

还需说明不存在额外的段。若某额外段满足 $c_i-e_i=0$，则 $e_i=c_i$，即 $v_i=2c_i$。由

可知 $c_i\le2$。$c_i=2$ 时要求 $v_i=4$，但 $4=(100)_2$ 只有一个 $1$，不可能；所以只有 $c_i=1,v_i=2$（或全零段）。

全零非最后段直接违反 (2)。而 $v_i=2$ 无论放在哪里也不可能：若它右边还有一个 $v=3$，则由 (2)

矛盾；若它在两个 $v=3$ 之后，则最左边的 $v=3$ 右侧已有 $e=1+1$，同样与 (2) 矛盾。

所以失败时切法只能是

因此

也就是说：

3. $m=5$ 时再试 $16$ 一定成功

若 $T=8$ 失败，上面已经证明贪心切出的值只能是

所以原串必形如

现在令目标为 $16$。

若 $b=0$，贪心得到

若 $b=1$，第一段取到 1101，值为 $13$，剩余部分恰好能贡献 $3$，故

若 $b\ge2$，第一段取到 1100，值为 $12$，剩余部分恰好能贡献

故

因此 $8$ 失败时，$16$ 必定成功。

综上，除全零串外一定有解；按从小到大的顺序枚举 $2^d\ge\operatorname{cnt}_1(s)$，上述贪心一定找到答案。事实上，除了 $m=5$ 这一种情况外，第一个二次幂就会成功；$m=5$ 时至多再尝试一次 $16$。