Description:
给你2个长度为n的01串
从中选出(n/2)个,使得选出的数中第一排1的个数等于未选出数中第二排1的个数
输出一种方案即可,没有输出-1
Hint:
(n le 5000)
Solution:
这题比赛的时候傻逼了
后面发现其实就是暴力枚举解方程
(AuBao)想出一个O(n)做法力碾标算,这里放出来%一%:
设(a_i)为所选第一排是1的数
(b_i)表示其对应第二排的数
设(sum)表示第二排1的个数
有:
[sum a_i = sum- sum b_i
]
移过去用d数组代替
[sum d_i = sum
]
现在考虑d的取值,显然有0,1,2三种
且
[cnt0*0+cnt1*1+cnt2*2=sum
]
[cnt0+cnt1+cnt2=n/2
]
即
[cnt1*1+cnt2*2=sum
]
[cnt0+cnt1+cnt2=n/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;
}