Codeforces Contest 1138 problem B Circus —— 死亡1700,暴力

2024-04-07 00:32

本文主要是介绍Codeforces Contest 1138 problem B Circus —— 死亡1700,暴力,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Polycarp is a head of a circus troupe. There are n — an even number — artists in the troupe. It is known whether the i-th artist can perform as a clown (if yes, then ci=1, otherwise ci=0), and whether they can perform as an acrobat (if yes, then ai=1, otherwise ai=0).

Split the artists into two performances in such a way that:

each artist plays in exactly one performance,
the number of artists in the two performances is equal (i.e. equal to n2),
the number of artists that can perform as clowns in the first performance is the same as the number of artists that can perform as acrobats in the second performance.
Input
The first line contains a single integer n (2≤n≤5000, n is even) — the number of artists in the troupe.

The second line contains n digits c1c2…cn, the i-th of which is equal to 1 if the i-th artist can perform as a clown, and 0 otherwise.

The third line contains n digits a1a2…an, the i-th of which is equal to 1, if the i-th artist can perform as an acrobat, and 0 otherwise.

Output
Print n2 distinct integers — the indices of the artists that should play in the first performance.

If there are multiple answers, print any.

If there is no solution, print a single integer −1.

Examples
inputCopy
4
0011
0101
outputCopy
1 4
inputCopy
6
000000
111111
outputCopy
-1
inputCopy
4
0011
1100
outputCopy
4 3
inputCopy
8
00100101
01111100
outputCopy
1 2 3 6
Note
In the first example, one of the possible divisions into two performances is as follows: in the first performance artists 1 and 4 should take part. Then the number of artists in the first performance who can perform as clowns is equal to 1. And the number of artists in the second performance who can perform as acrobats is 1 as well.

In the second example, the division is not possible.

In the third example, one of the possible divisions is as follows: in the first performance artists 3 and 4 should take part. Then in the first performance there are 2 artists who can perform as clowns. And the number of artists in the second performance who can perform as acrobats is 2 as well.

题意:

给你n个人的两种技能,1代表会,0代表不会。现在有两场演出,每场需要分配n/2个人,每个人只能去一场,让你输出第一场去的人使得在第一场会第一个技能的人的数量=第二场会第二个技能的人的数量。

题解:

我真的服了,这是B该有的难度吗?而且为什么每个1700难度对我都这么不友好?sun dog。
还是不要看我的代码了,去看别人的吧,我自己写留个纪念。
我设会第一个技能但不会第二个技能为oz:one zero 同理可得:zo,oo,zz
首先如果zo有0个且oz也是0个且oo有奇数个,那么不论怎么分配都不可能相等
然后如果zo的数量-zz的数量>oz的数量+oo的数量,或者相反。也就是说一边无论怎么拿,会这个的人数都比另一边大,那么也是不可能的。
之后要考虑oz.size()和zo.size()的大小,我是直接做小的。如果(int)zo.size()>(int)oz.size()

重点:size()的有关操作最好是强转之后做,否则会re

那么oz肯定全部要取,之后就是while一下,看看要取多少oo,然后这里还有一个判断,我举个栗子:

oo zo oz+oo(给oz的oo,一开始假设全都给zo)
3  4   4

如果oo让给oz一个
那么就变成

oo zo oz+oo
2  4  5

如果再给一个,那么oz+oo就比zo最终所拥有的1多了,但是这是不被允许的,因为我后面并没有把zo的1补回来的办法。那么就要numoo+(int)zo.size()>(int)oz.size()+res+1的时候才能给。
注意这时候oo和zo的1的数量比oz多,那么我们之后把一个zo给oz,这样的话zo+oo的1的数量就会-1,但是oz的1的数量并不会加!
最后只需要加上少掉的zz就可以了。

第二种情况oz>zo。这时候一开始都一样,只要翻转一下,但是注意最后输出不能输出刚才找的这些,因为它是第二场。如果输出了第二场的技能1的话,可能就不对了,因为我们最后还有消去oz的过程。那么我们要用一个vis记录一下那些是第二场的,最后输出的时候判一下即可。

#include<bits/stdc++.h>
using namespace std;
#define pa pair<int,int>
const int N=5e3+5;
int a[N],b[N];
vector<int>ans,zz,zo,oz,oo;
int vis[N];
int main()
{int n,sec=0;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%1d",&a[i]);for(int i=1;i<=n;i++){scanf("%1d",&b[i]);if(a[i]==0&&b[i]==0)zz.push_back(i);else if(a[i]==0&&b[i]==1)zo.push_back(i);else if(a[i]==1&&b[i]==0)oz.push_back(i);else if(a[i]==1&&b[i]==1)oo.push_back(i);}if((int)zo.size()==0&&(int)oz.size()==0&&((int)oo.size())%2==1)return 0*printf("-1\n");if((int)zo.size()-(int)zz.size()>(int)oz.size()+(int)oo.size()||(int)oz.size()-(int)zz.size()>(int)zo.size()+(int)oo.size())return 0*printf("-1\n");//if(n==4990)//printf("%d %d %d %d\n",zo.size(),oz.size(),zz.size(),oo.size());if((int)zo.size()>(int)oz.size()){int i=0;for(int i=0;i<(int)oz.size();i++)printf("%d ",oz[i]);int numoo=(int)oo.size(),res=0;while(numoo+(int)zo.size()>(int)oz.size()+res+1&&numoo){numoo--;printf("%d ",oo[res++]);}while(numoo+(int)zo.size()>(int)oz.size()+res)printf("%d ",zo[i++]),res++;while(i<zo.size()&&oz.size()+res<n/2)printf("%d ",zz[i++]),res++;}else{int azo=0,aoz=0,aoo=0,azz=0;for(int i=0;i<(int)zo.size();i++)vis[zo[i]]=1,azo+=(a[zo[i]]==0&&b[zo[i]]==1);int numoo=oo.size(),res=0;while(numoo+(int)oz.size()>(int)zo.size()+res+1&&numoo){numoo--;vis[oo[res++]]=1,aoo+=(a[oo[res-1]]==1&&b[oo[res-1]]==1);}int i=0;while(i<(int)oz.size()&&numoo+(int)oz.size()>(int)zo.size()+res)vis[oz[i++]]=1,res++,aoz+=(a[oz[0]]==1&&b[oz[0]]==1);//if(n==5000)//printf("%d\n",res);while((int)zo.size()+res<n/2)vis[zz[i]]=1,i++,res++,azz+=(a[zz[i-1]]==0&&b[zz[i-1]]==0);//if(n==4990)//printf("%d %d %d\n",azo+aoo+azz+aoz,azo+aoo,oz.size()-aoz+oo.size()-aoo);for(int i=1;i<=n;i++)if(!vis[i])printf("%d ",i);}printf("\n");return 0;
}

这篇关于Codeforces Contest 1138 problem B Circus —— 死亡1700,暴力的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/881235

相关文章

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

uva 10025 The ? 1 ? 2 ? ... ? n = k problem(数学)

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k,? 处可以填 + 也可以填 - ,问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明,令 S(n) = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n,搜出当 S(n) >=

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

2014 Multi-University Training Contest 8小记

1002 计算几何 最大的速度才可能拥有无限的面积。 最大的速度的点 求凸包, 凸包上的点( 注意不是端点 ) 才拥有无限的面积 注意 :  凸包上如果有重点则不满足。 另外最大的速度为0也不行的。 int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;}struct poin

2014 Multi-University Training Contest 7小记

1003   数学 , 先暴力再解方程。 在b进制下是个2 , 3 位数的 大概是10000进制以上 。这部分解方程 2-10000 直接暴力 typedef long long LL ;LL n ;int ok(int b){LL m = n ;int c ;while(m){c = m % b ;if(c == 3 || c == 4 || c == 5 ||

2014 Multi-University Training Contest 6小记

1003  贪心 对于111...10....000 这样的序列,  a 为1的个数,b为0的个数,易得当 x= a / (a + b) 时 f最小。 讲串分成若干段  1..10..0   ,  1..10..0 ,  要满足x非递减 。  对于 xi > xi+1  这样的合并 即可。 const int maxn = 100008 ;struct Node{int

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja