【枚举】AGC019D Shift and Flip

分析：

终于有道简单题了。。。

很显然，可以枚举A位置最终对应到哪个位置。方便起见，可以把B数组复制为三倍，然后就可以暴力枚举了。先检查每一位是否需要更改，如果需要，是否在其移动范围内就能遇到一个$b_i=1$的位置。如果不能，向左向右至少走多少步。

现在可以得到：每个无法满足的点需要向左/右移动的最小距离。

如果我们令向左最远的一个走左边，那么剩下的都可以走左边。如果向左最远的一个不走左边，其必须走右边，那么再来看次远的一个走左还是右。这样依次处理下去，就可以O(N)算出总的需要多走的左右步数。但需要排个序所以还是O(NlogN)的。

总的时间复杂度O(N^2logN)

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #define SF scanf #define PF printf #define MAXN 2010 #define INF 0x3FFFFFFF using namespace std; char s[MAXN*3],s1[MAXN]; int pre[MAXN*3],nl[MAXN*3],nr[MAXN*3],ans=INF,len; vector<pair<int,int> > add; void prepare(){
     nl[0]=-INF;for(int i=1;i<=len*3;i++){
     nl[i]=nl[i-1];if(s[i]=='1')nl[i]=i;}nr[len*3+1]=INF;for(int i=len*3;i>=1;i--){
     nr[i]=nr[i+1];if(s[i]=='1')nr[i]=i;}for(int i=1;i<=len*3;i++)pre[i]=pre[i-1]+s[i]-'0'; } int findl(int x){
     return min(INF,x-nl[x]); } int findr(int x){
     return min(INF,nr[x]-x); } int main(){
     SF("%s",s1+1);SF("%s",s+1);len=strlen(s+1);for(int i=len+1;i<=len*3;i++)s[i]=s[(i-1)%len+1];prepare();for(int i=1;i<=2*len+1;i++){
     add.clear();int sum=0;for(int j=1;j<=len;j++){
     if(s1[j]!=s[i+j-1]){
     sum++;int r=j+len;int l=j+i-1;if(l>r)swap(l,r);if(pre[r]-pre[l-1]==0)add.push_back(make_pair(findl(l),findr(r)));}}add.push_back(make_pair(0,0));sort(add.begin(),add.end());int adds=INF,maxv=0;for(int i=int(add.size()-1);i>=0;i--){
     if(add[i].first!=INF&&maxv!=INF)adds=min(adds,maxv*2+add[i].first*2);maxv=max(maxv,add[i].second);if(maxv==INF)break;}if(adds!=INF)ans=min(ans,adds+abs(len+1-i)+sum);}if(ans==INF)ans=-1;PF("%d",ans); }