题意:

给你两个01串,要你选n/2个位置,使得选的位置在s1中"1"的数量等于未选的s2中"1"的数量

n<=5000,1s

思路:

设两个串中出现"00""01""10""11"的总数是A,B,C,D,我们选的个数分别是a,b,c,d

数据最多能承受n^2的暴力

根据题意,有a+b+c+d=n/2     ①

c+d=B-b+D-d    ②

联立得d=B+D+a-n/2

于是我们暴力a,可以得到d

然后将a,d带入①可得b+c=n/2-a-d

暴力b可得c

最后只要a,b,c,d是否全部合法,输出方案即可

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#include<map>
#include<functional>
#include<cmath> #define fst first
#define sc second
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lc root<<1
//#define rc root<<1|1
#define lowbit(x) ((x)&(-x)) using namespace std; typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PI;
typedef pair<ll,ll> PLL; const db eps = 1e-;
const int mod = 1e9+;
const int maxn = 2e6+;
const int maxm = 2e6+;
const int inf = 0x3f3f3f3f; int n;
char s1[maxn];
char s2[maxn];
int A,a,B,b,C,c,D,d;
int main(){
scanf("%d", &n);
scanf("%s", s1+);
scanf("%s", s2+);
for(int i = ; i <= n; i++){
if(s1[i]==''){
if((s2[i]==''))A++;
else B++;
}
else{
if(s2[i]=='')C++;
else D++;
}
}
int mm = min(A, n/);
a = b = c = d = -;
int ys = ;
for(a = ; a <= A && a <= n/; a++){
if(B+D-n/+a<=D&&B+D-n/+a>=){
d = B+D-n/+a;
//int m = min(min(n/2-a-d,B),n/2);
//printf("%d %d\n",a,d);
for(b = ; b <= B&&b<=n/-a-d; b++){
//printf(" %d\n",b);
if(n/-a-b-d<=C&&n/-a-b-d>=){
c = n/-a-b-d;
ys=;break;
}
}
if(ys)break;
}
}
//printf("%d %d %d %d\n", a,b,c,d);
if(!ys){
return printf("-1"),;
}
for(int i = ; i <= n; i++){
if(s1[i]==''){
if(s2[i]==''&&a){
a--;
printf("%d ",i);
}
else if(s2[i]==''&&b){
b--;
printf("%d ",i);
}
}
else if(s1[i]==''){
if(s2[i]==''&&c){
c--;
printf("%d ",i);
}
else if(s2[i]==''&&d){
d--;
printf("%d ",i);
}
}
}
return ;
}

最新文章

  1. undefined method `environment&#39; for nil:NilClass when importing Bootstrap into rails
  2. 使用ruby搭建简易的http服务和sass环境
  3. Chrome浏览器二维码生成插件
  4. CF 628C --- Bear and String Distance --- 简单贪心
  5. 实例:图形绘制[OpenCV 笔记15]
  6. ASP.NET基础之HttpHandler学习
  7. 单例模式与静态变量在PHP中
  8. Django 2.0 官方文档翻译
  9. Luogu P3227 [HNOI2013]切糕 最小割
  10. springmvc接收数组方式总结
  11. Redis 常见配置
  12. vue2.0和better-scroll实现左右联动效果
  13. 用org.mybatis.generator 生成代码
  14. VSTS 更名为 Azure DevOps
  15. 和IDEA一样好用的go语言IDE:Goland
  16. [Jenkins] Manage Jenkins from Web Interface
  17. Mac安装并破解StarUML
  18. Office 2019 2016 安装破解教程
  19. #Pragma Pack与内存分配
  20. alibaba的JSON.toString会把值为null的字段去掉,谨记

热门文章

  1. 「newbee-mall新蜂商城开源啦」1000 Star Get !仓库Star数破千!记录一下
  2. 使用wireshark 对flutter 框架APP进行抓包
  3. 序言vue.js介绍
  4. Spring Boot 2.X(十九):集成 mybatis-plus 高效开发
  5. P1640 [SCOI2010]连续攻击游戏 二分图最大匹配 匈牙利算法
  6. Google搜索成最大入口,简单谈下个人博客的SEO
  7. python3三元运算
  8. Java入门 - 语言基础 - 15.StringBuffer
  9. Java入门 - 语言基础 - 19.方法
  10. Java入门 - 面向对象 - 06.接口