Codeforces Round #586 (Div. 1 + Div. 2) 题解

codeforces 1120 A - Cards

题意： 给你若干个zero和若干个one的字母卡片的乱序，求组合后的0和1排列最大号码
思路： 判断z的个数就好了，就可以求出1的个数都放前面，然后在输入相应的0的个数

#include<bits/stdc++.h>
using namespace std;
char ss[100005];
int main() {
	int z = 0;
	int k;
	scanf("%d", &k);
	scanf("%s", ss);
	for(int i = 0; i < k; i++) {
		if(ss[i] == 'z') {
			z++;
		}
	}
	for(int i = 0; i < (k-4*z)/3; i++) {
		printf("1 ");
	}
	for(int i = 0; i < z; i++) {
		printf("0 ");
	}

	return 0;
}

codeforces 1120 B - Multiplication Table

题意： 输入一个n*n的二维数组 $M$ ， $M_{i j} = M_{j i} = a_{i} * a_{j}$ , 不输入 $M_{i i}$ ,求 $a_{i i}$
思路： 一开始以为gcd，后来被fst了…原来可以 $O (n)$ 求
$M_{i (i - 1)}$ * $M_{(i + 1) i}$ / $M_{(i + 1) (i - 1)}$ = $M_{i i}$
根据上面的公式可以直接得出答案
所以其实很简单…

#include<bits/stdc++.h> 
using namespace std;
#define maxn 1005 
#define ll long long
ll a[maxn][maxn];
int main() {
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			scanf("%lld", &a[i][j]);
		}
	}
	for(int i = 0; i < n; i++){
		a[i][i] = sqrt(a[i][(i-1+n)%n] * a[i][(i+1)%n] / a[(i+1)%n][(i-1+n)%n]);
		printf("%lld ", a[i][i]);
	}
	return 0;
}

codeforces 1120 C - Substring Game in the Lesson

题意： 输入一个字符串, 字串[l,r]一开始有l和r都在k位置上，Ann和Mike在最聪明且Ann先手的情况下，可以移动l到小于等于l的位置和移动r到大于等于r的位置,得到的子串必须比原来字典序小，不能移动的人输
思路： 博弈，只要k前面有字符比他小那么Ann一定可以赢，直接把l移到前面最小的字符就胜利了

#include<bits/stdc++.h>
using namespace std;
char ss[1000005];
int ans[1000005];
int main() {
	scanf("%s", ss);
	int minn = ss[0];
	ans[0] = 0;
	int len = strlen(ss); 
	puts("Mike");
	for(int i = 1; i < len; i++){
		if(ss[i] > minn){
			puts("Ann");
		}else {
			puts("Mike");
		}
		minn = min(minn, (int)ss[i]);
	}
	return 0;
}

codeforces 1120 D - Alex and Julian

题意： 当a和b和abs(a-b)三个数属于一个集合的时候，a和b之间有一条边，把集合B里面的数删除掉最少数量的子集使得剩下的数字在 集合为所有整数 可以构成一个二分图
思路：
判定二分图的基本方法：不存在奇环
起点为 0，如果 B 中存在整数 a，那么 0 与 a 之间有一条边，a 与 2 * a 之间也有一条边，如果这时 B 中还存在着整数 2 * a，那么这时 0，a，2 * a 这三个点就形成了奇环。
考虑到这里，我们发现，如果我们已经选中了一个数 a，那么要不存在奇环，只有将 a / 2（a % 2 == 0）， a / 4（a % 4 == 0）…… ，a * 2 ，a * 4，…… 全部删去。
转换一下就是判断每个数字转为2进制，根据后导零的个数来分类，可以分出最多63个集合，每个集合内的数字都可以符合条件，取个数最多的集合

#include<bits/stdc++.h>
using namespace std;
#define maxn 300005
#define ll long long
ll a[maxn];
int b[100], n;

int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		scanf("%lld",a+i);
		++b[__builtin_ctzll(a[i])];
	}
	int z = max_element(b, b+62) - b;
	printf("%d\n", n-b[z]);
	for(int i = 0; i < n; i++) {
		if(__builtin_ctzll(a[i])!=z)printf("%lld ",a[i]);
	}
	return 0;
}