Codeforces Round #737 (Div. 2) A~C题解

A. Ezzat and Two Subsequences

题意：
给一个由 $n$ 个实数组成的数组
将这 $n$ 个数分为两组，求这两组的平均值的和的最大值

思路：
我就直接说结论把，把除去最大值的其余 $n-1$ 的数的平均值与最大值相加即可
如何证明不用多说了，有了结论应该很好反证出来

时间复杂度：$O（n）$

#include <bits/stdc++.h>
using namespace std;
int n;
long double s[100010];

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		long double res = 0, ma;

		scanf("%Lf", &s[1]);
		res += s[1];
		ma = s[1];
		for (int i = 2; i <= n; i++) {
			scanf("%Lf", &s[i]);
			res += s[i];
			if (ma < s[i])
				ma = s[i];
		}
		//sort(s + 1, s + 1 + n);
		res = (res - ma) * 1.0 / (n - 1);

		res += ma;

		printf("%.08Lf\n", res);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

B. Moamen and k-subarrays

题意：
有一个由 $n$ 个不同整数组成的数组。需要按非递减顺序对数组进行排序，方法是将数组精确分割成 $k$ 个非空的子数组，然后对这 $k$ 个子数组任意重新排序，最后按新顺序合并子数组
问这种方法是否能成功

思路：
这 $n$ 个数是彼此不同但并不是连续的，因此只需要在读入的时候同时保存他们的相对位置，然后 $sort$ 排序之后判断新序列中有多少数是依旧相邻的，将新的非递减数组用题目所给的方法切割，判断这样精确切割出的子数组数量与 $k$ 的大小关系即可

因为新旧数组都是由这些精确切割出的子数组数量拼接而成的，因此从新旧数组入手都无所谓

时间复杂度：$O（n）$

#include <bits/stdc++.h>
using namespace std;
int n, m;
pair<int, int> s[100010];

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d %d", &n, &m);

		if (n == 1) {
			int a;
			scanf("%d", &a);
			printf("Yes\n");
			continue;
		}

		for (int i = 1; i <= n; i++) {
			scanf("%d", &s[i].first);
			s[i].second = i;
		}
		sort(s + 1, s + 1 + n);

		int res = 1;
		for (int i = 2; i <= n; i++) {
			if (s[i].second != s[i - 1].second + 1)
				res++;
		}

		if (res <= m)
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

C. Moamen and XOR

题意：
创建一个由 $n$ 个非负整数组成的数组，每个元素都小于 $2^k$
并且要满足 $a_1\&a_2\&a_3\&\dots \dots a_{n-1}\&a_n\ge a_1\oplus a_2\oplus a_3\oplus \dots \dots a_{n-1}\oplus a_n$
求符合条件的数组个数，答案对 $10^9+7$ 取余

思路：
$res=a_1\&a_2\&a_3\&\dots \dots a_{n-1}\&a_n$
$cnt=a_1\oplus a_2\oplus a_3\oplus \dots \dots a_{n-1}\oplus a_n$
首先看到$2^k$时，就将思考的方向放到位运算上，将 $res$ 和 $cnt$ 转换成二进制去想，然后再从最小位逐层向上去比较两者的大小

先假设 $k==1$ 的情况：
一共有 $2^n$ 种方案，可以注意到，只有当左边 $n$ 个数全都为 $1$ 时，$res==1$ ，其余情况 $res==0$；而右边就不一样了，一个长度为 $n$ 的$01$数组，一共有 $2^n$ 种组合方式，其中 $2^{n-1}$ 种方式中 $1$ 的个数为奇数，$cnt==1$，剩余 $2^{n-1}$ 种方式中 $1$ 的个数为偶数 ，$cnt==0$
分析到这里，就会意识到需要讨论 $n$ 的奇偶了：
当 $n$ 为奇数时，右边 $2^{n-1}$ 种方式中 $1$ 的个数为偶数，$cnt==0$ 的情况下，左边由于 $\&$ 的性质，是必然 $res==0$ 的；而右边 $2^{n-1}$ 种方式中 $1$ 的个数为奇数，$cnt==1$ 的情况下，有且仅有一种情况，即 $n$ 个 $1$ 时才有 $res==cnt==1$ ，其余均为 $0==res<cnt==1$。所以 $n$ 为奇数时，有且只有 $res==cnt$ 的情况是合法的，且方案数为 $2^{n-1}+1$
当 $n$ 为偶数时，右边 $2^{n-1}$ 种方式中 $1$ 的个数为奇数，$cnt==1$ 的情况下，只有 $0==res<cnt==1$ 一种情况；右边 $2^{n-1}$ 种方式中 $1$ 的个数为偶数，$cnt==0$ 的情况下，有且仅有一种情况，即 $n$ 个 $1$ 时才有 $1==res>cnt==0$ ，剩余 $2^{n-1}-1$ 种方案均为 $res==cnt==0$ 。所以 $n$ 为偶数时，合法的方案数为 $2^{n-1}$，一种是 $res>cnt$，其余为 $res==cnt$

分析完 $k==1$ 的特殊情况之后，就需要继续拓展，即将 $res$ 和 $cnt$ 的二进制状态由一位数向 $k$ 位数延伸
先看当 $n$ 为奇数时，因为它只有等于这一种合法方案，所以想要求合法的方案，就需要让 $res$ 和 $cnt$ 的二进制状态的每一位都是相等的，所以最终的方案数为 $k\ast (2^{n-1}+1)$

而 $n$ 为偶数时就比较麻烦了，因为它的每一位都有败（$re{s}^{\prime }<cn{t}^{\prime }$，单层方案数为 $aa==2^{n-1}$）、胜（$re{s}^{\prime }>cn{t}^{\prime }$，单层方案数为 $bb==1$）、平（$re{s}^{\prime }==cn{t}^{\prime }$，单层方案数为 $cc==2^{n-1}-1$）三种状态（ ${}^{\prime }$ 表示二进制的一位），所以要用前 $i-1$ 层的方案数（设成a、b、c吧）去推导前 $i$层的方案数（设成A、B、C吧）：
A = a * (aa + cc) + b * aa + c * aa ;
B = a * bb + b * (cc + bb) + c * bb ;
C = c * cc ;
最终的方案数为 $B+C$

然后在计算过程中记得取余

时间复杂度：$O（k）$

#include <bits/stdc++.h>
using namespace std;
long long n, k;
const long long mod = 1e9 + 7;

long long qmi(long long a, long long b) {
	long long res = 1 % mod;
	while (b) {
		if (b & 1)
			res = (long long)res * a % mod;
		a = (long long)a * a % mod;
		b >>= 1;
	}
	return res % mod;
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%lld %lld", &n, &k);

		if (k == 0) {
			printf("1\n");
			continue;
		}

		if (n & 1) {
			long long a = qmi((long long)2, n - 1) % mod;
			a = (a + 1) % mod;
			long long  r = a;
			for (int i = 1; i < k; i++) {
				r = (r * a) % mod;
			}
			printf("%lld\n", r);
		} else {

			long long a = qmi((long long)2, n - 1) % mod; //败
			long long b = 1; //胜
			long long c = (a - 1 + mod) % mod; //平
			long long aa = a, bb = b, cc = c;
			long long aaa, bbb, ccc;
			for (int i = 1; i < k; i++) {
				aaa = (a * (aa + cc) % mod + b * aa % mod + c * aa % mod) % mod;
				bbb = (a * bb % mod + b * (cc + bb) % mod + c * bb % mod) % mod;
				ccc = (c * cc) % mod;
				a = aaa;
				b = bbb;
				c = ccc;
			}
			printf("%lld\n", (b + c) % mod);
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55