Description:

给你2个长度为n的01串

从中选出\(n/2\)个,使得选出的数中第一排1的个数等于未选出数中第二排1的个数

输出一种方案即可,没有输出-1

Hint:

\(n \le 5000\)

Solution:

这题比赛的时候傻逼了

后面发现其实就是暴力枚举解方程

\(AuBao\)想出一个O(n)做法力碾标算,这里放出来%一%:

设\(a_i\)为所选第一排是1的数

\(b_i\)表示其对应第二排的数

设\(sum\)表示第二排1的个数

有:

移过去用d数组代替

现在考虑d的取值,显然有0,1,2三种

且

即

O(n)枚举即可

另附被爆踩的官方\(n^2\)的做法:

#include <map>

#include <set>

#include <stack>

#include <cmath>

#include <queue>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define ls p<<1

#define rs p<<1|1

using namespace std;

typedef long long ll;

const int mxn=1e5+5;

int n,m,cnt,hd[mxn];

inline int read() {

    char c=getchar(); int x=0,f=1;

    while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}

    while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}

    return x*f;

}

inline void chkmax(int &x,int y) {if(x<y) x=y;}

inline void chkmin(int &x,int y) {if(x>y) x=y;}

struct ed {

    int to,nxt;

}t[mxn<<1];

inline void add(int u,int v) {

    t[++cnt]=(ed) {v,hd[u]}; hd[u]=cnt;

}

char p[5005],q[5005];

int sum,cnt0,cnt1,cnt2;

vector<int > g0,g1,g2;

int main()

{

    n=read(); scanf("%s %s",p+1,q+1);

    for(int i=1;i<=n;++i) {

        if(p[i]=='0'&&q[i]=='0') ++cnt0,g0.push_back(i);

        if(p[i]=='0'&&q[i]=='1') ++cnt1,g1.push_back(i),++sum;

        if(p[i]=='1'&&q[i]=='0') ++cnt1,g1.push_back(i);

        if(p[i]=='1'&&q[i]=='1') ++cnt2,g2.push_back(i),++sum;

    }

    int c1,c0;

    for(int i=0;i<=cnt2;++i) {

        c1=sum-i*2; c0=n/2-i-c1;

        if(c1<0||c0<0) continue ;

        if(c1<=cnt1&&c0<=cnt0) {

            for(int j=0;j<c0;++j)

                printf("%d ",g0[j]);

            for(int j=0;j<c1;++j)

                printf("%d ",g1[j]);

            for(int j=0;j<i;++j)

                printf("%d ",g2[j]);

            exit(0);

        }

    }

    puts("-1");

    return 0;

}