[??记录]AT2703 [AGC019D] Shift and Flip
command_block
2021-01-12 20:36:46
**题意** ： 给出两个长度为 $n$ 的 $01$ 串 $A,B$。
可以进行下列两种操作 ：
- 将 $A$ 循环移位（左移或右移）一次。
- 对某个 $B_i=1$ 的 $i$ ，将 $A_i$ 取反。
问使 $A$ 与 $B$ 相等至少需要几次操作，或指出无解。
$n\leq 2000$ ，时限 $\texttt{2s}$。
------------
显然 $B$ 全 $0$ 是无解的充要条件。
首先枚举最终 $A$ 转过几轮，然后 $A$ 中需要使用操作二的位置就能够确定了。
不妨将需要修改的位置设为 $1$ ，不需要的设为 $0$。
先思考如何修改这些位置，相当于 ： 将 $B$ 适当地旋转，使得 $A$ 的每个 $1$ 都被某个 $B$ 的 $1$ “擦过”。
不难发现， $B$ 的旋转最多只会回一次头。
每个 $A$ 中的 $1$ 分别向左向右查看 $B$ 中最近的 $1$ ，假设距离分别为 $dr,dl$ ，则 $B$ 右移达到 $dr$ 或者左移达到 $dl$。（注意要反过来）
若最终左移 $tl$ 右移 $tr$ ，则移动步数为 $tl+tr+\min(tl,tr)$ ，因为需要回头。
接下来考虑移动到给定位移 $td$ 的消耗。
不妨先向左，再向右，然后移到 $td$（右起）。保证 $tr\geq td$。
代价为 $2*(tl+tr)-td$。
先向右再向左可以简单地将串反转再求一次。
考虑如何选定合适的 $tl,tr$。
首先把 $dr\leq td$ 的点都丢掉。
接下来，问题就变成了 ： 有 $n$ 个约束，形为 ： $tl\geq dl$ 或者 $tr\geq dr$。
要求找出一对 $tl,tr$ 满足所有约束，且和最小。
将所有约束按照 $dl$ 排序，枚举 $tl$ 就能满足一个前缀，剩下的后缀 $dr$ 最大值就是 $tr$。
使用桶排序即可做到 $O(n^2)$。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#define ll long long
#define MaxN 2050
using namespace std;
char s[MaxN],t[MaxN];
int n,pl[MaxN],pr[MaxN],o[MaxN];
int calc(int k)
{
int cnt=0;
for (int i=0;i<n;i++)o[i]=0;
for (int i=0;i<n;i++)
if (s[i]!=t[(i+k)%n]){
cnt++;
o[pr[i]]=max(o[pr[i]],pl[i]);
}
int ans=n<<9;
for (int i=n-1;i>=k;i--)
o[i]=max(o[i+1],o[i]);
for (int i=k;i<n;i++)
ans=min(ans,i+o[i+1]);
return 2*ans-k+cnt;
}
void Init()
{
for (int i=0;i<n;i++)pl[i]=pr[i]=0;
int tl=n,tr=0;
for (int i=0;i<n;i++)if (t[i]=='1'){tl=i;break;}
for (int i=n-1;i>=0;i--)if (t[i]=='1'){tr=i;break;}
pl[0]=(t[0]=='1') ? 0 : n-tr;
for (int i=1;i<n;i++)
if (t[i]=='0')pl[i]=pl[i-1]+1;
pr[n]=tl;
for (int i=n-1;i>=0;i--)
if (t[i]=='0')pr[i]=pr[i+1]+1;
}
int main()
{
scanf("%s%s",s,t);
n=strlen(s);
bool fls=0,flt=0;
for (int i=0;i<n;i++)fls|=(s[i]=='1');
for (int i=0;i<n;i++)flt|=(t[i]=='1');
if (flt==0){puts(fls==flt ? "0" : "-1");return 0;}
Init();
int ans=n<<9;
for (int k=0;k<n;k++)
ans=min(ans,calc(k));
reverse(s,s+n);
reverse(t,t+n);
Init();
for (int k=0;k<n;k++)
ans=min(ans,calc(k));
printf("%d",ans);
return 0;
}
```