Codeforces 1138B Circus (构造方程+暴力)
2024-10-08 05:26:06
题意:
给你两个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 ;
}
最新文章
- undefined method `environment&#39; for nil:NilClass when importing Bootstrap into rails
- 使用ruby搭建简易的http服务和sass环境
- Chrome浏览器二维码生成插件
- CF 628C --- Bear and String Distance --- 简单贪心
- 实例:图形绘制[OpenCV 笔记15]
- ASP.NET基础之HttpHandler学习
- 单例模式与静态变量在PHP中
- Django 2.0 官方文档翻译
- Luogu P3227 [HNOI2013]切糕 最小割
- springmvc接收数组方式总结
- Redis 常见配置
- vue2.0和better-scroll实现左右联动效果
- 用org.mybatis.generator 生成代码
- VSTS 更名为 Azure DevOps
- 和IDEA一样好用的go语言IDE:Goland
- [Jenkins] Manage Jenkins from Web Interface
- Mac安装并破解StarUML
- Office 2019 2016 安装破解教程
- #Pragma Pack与内存分配
- alibaba的JSON.toString会把值为null的字段去掉,谨记
热门文章
- 「newbee-mall新蜂商城开源啦」1000 Star Get !仓库Star数破千!记录一下
- 使用wireshark 对flutter 框架APP进行抓包
- 序言vue.js介绍
- Spring Boot 2.X(十九):集成 mybatis-plus 高效开发
- P1640 [SCOI2010]连续攻击游戏 二分图最大匹配 匈牙利算法
- Google搜索成最大入口,简单谈下个人博客的SEO
- python3三元运算
- Java入门 - 语言基础 - 15.StringBuffer
- Java入门 - 语言基础 - 19.方法
- Java入门 - 面向对象 - 06.接口