Codeforces Round #723 (Div. 2)

A. Mean Inequality

将 \(2n\) 个不同的数字排成一个循环，使得任意位置的数不是相邻两个数的平均值。

从小到大排序之后，前 \(n\) 个和后 \(n\) 个交替放。

因为数字两两不同，大的数字不可能是两个小的数字的平均数，小的同理。

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
#include <bits/stdc++.h>
using namespace std;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
} 

int a[51];

inline void work() {
	int n = rd();
	int m = 2 * n;
	for (int i = 1; i <= m; ++i) a[i] = rd();
	sort(a + 1, a + 1 + m);
	for (int i = 1; i <= n; ++i) printf("%d %d ", a[i], a[i + n]);
	puts("");
}

int main() {
	for (int t = rd(); t; --t) work();
	return 0;
}

B. I Hate 1111

询问一个正整数 \(x\) 是否可以拆分成若干个 \(11,111,1111,\dots\) 的和

根据 麦乐鸡定理 ，\(11\) 和 \(111\) 可以组成大于 \(11*111-111-11=1099\) 的任何数。

所以后面的数字都没用了， \(x\le 1099\) 的部分做一下 \(11\) 和 \(111\) 的完全背包，其他情况都是 YES 。

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
#include <bits/stdc++.h>
using namespace std;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
} 

#define N 1100

bool f[N];

inline void work() {
	int x = rd(); 
	puts(x >= N ? "YES" : (f[x] ? "YES" : "NO"));
}

int main() {
	f[0] = 1;
	for (int i = 11; i < N; ++i) f[i] |= f[i - 11];
	for (int i = 111; i < N; ++i) f[i] |= f[i - 111];
	for (int t = rd(); t; --t) work();
	return 0;
}

C. Potions

给一个数列，求一个最长的子序列，使得子序列任意前缀和都 \(\ge 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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
} 

priority_queue<int> q;

int main() {
	int n = rd();
	int ans = 0;
	ll nw = 0;
	for (int i = 1, a; i <= n; ++i) {
		a = rd(); 
		++ans; nw += a; q.push(-a);
		while (nw < 0) {
			nw += q.top(); q.pop(); --ans;
		}
	}
	printf("%d\n", ans);
	return 0;
}

D. Kill Anton

给定一个字符集只有 'A','D','O','T' 的串，将其重排使得恢复成原来的所需操作次数最大。

操作一次可以交换两个字符的位置。

猜一下操作次数只和逆序数相关（我一直不太会这种的证明），所以一定可以把同一类字符放到一起。

记 inv[i][j] 表示字符 i 前字符j 的顺序对数，即如果结果串中字符 i 在字符 j 前，增加的逆序数。

因此枚举 \(4!\) 种排列，计算一下哪一种逆序数最大即可。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const char tc[4] = {'A', 'N', 'O', 'T'};

ll cnt[4], inv[4][4];

inline int tr(char c) {
	if (c == 'A') return 0;
	if (c == 'N') return 1;
	return (c == 'O' ? 2 : 3);
}

string s;

inline void work() {
	cin >> s;
	for (int i = 0; i < 4; ++i) {
		cnt[i] = 0;
		for (int j = 0; j < 4; ++j) inv[i][j] = 0;
	}
	for (auto c : s) {
		int i = tr(c);
		for (int j = 0; j < 4; ++j)
			if (j != i) inv[i][j] += cnt[j];
		++cnt[i];
	}
	ll ans = -1;
	int p[4] = {0, 1, 2, 3}, res[4];
	do {
		ll tmpans = 0;
		for (int i = 0; i < 4; ++i)
			for (int j = i + 1; j < 4; ++j) tmpans += inv[p[i]][p[j]];
		if (tmpans > ans) {
			ans = tmpans;
			for (int i = 0; i < 4; ++i) res[i] = p[i];
		}
	} while(next_permutation(p, p + 4));
	for (int i = 0; i < 4; ++i)
		for (int j = 1; j <= cnt[res[i]]; ++j) putchar(tc[res[i]]);
	puts("");
}

int main() {
	int t;
	for (cin >> t; t; --t) work();
	return 0;
}

E. Oolimry and Suffix Array

给定后缀数组，求有多少个串长为 \(n\) ，字符集大小为 \(k\) 的字符串 \(S\) 符合这个后缀数组

后缀数组 \(sa_i\) 记录的是排名第 \(i\) 位的后缀的开始下标。

根据字典序要求，\(S_{sa_i}\) 和 \(S_{sa_{i+1}}\) 只有两种关系：\(S_{sa_i}<S_{sa_{i+1}}\) 或 \(S_{sa_i}=S_{sa_{i+1}}\)

小于一定是可以的，等于的充要条件是 \(rank_{sa_i+1}<rank_{sa_{i+1}+1}\) ，即去掉第一个字符字典序不变。

因此我们得到了含有 \(n-1\) 个不等号的不等式链，假设其中有 \(a\) 个是 \(\le\) 。

我们枚举有 \(i\) 个 \(\le\) 实际上是 \(<\) ，那么实际字符集大小是 \(n-i\) ，方案数就是

\[ \sum_{i=0}^a{a\choose i}{k\choose n-i}={a+k\choose n} \]

等式从组合含义理解，从 \(a+k\) 个里选 \(n\) 个，定价于枚举从前 \(a\) 个里选 \(i\) 个，剩余的从后 \(k\) 个里选。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define N 200007
#define mod 998244353

inline int fpow(int x, int t = mod - 2) {
	int res = 1;
	for (; t; t >>= 1, x = 1ll * x * x % mod)
		if (t & 1) res = 1ll * res * x % mod;
	return res;
}

int rk[N], pos[N], fac[N << 1] = {1};

int main() {
	int n = rd(), k = rd();
	for (int i = 1; i <= n; ++i) rk[pos[i] = rd()] = i;
	for (int i = 1; i < n; ++i) 
		k += (rk[pos[i] + 1] < rk[pos[i + 1] + 1]);
	if (k < n) {puts("0"); return 0;}
	for (int i = 1; i <= k; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
	printf("%lld\n", 1ll * fac[k] * fpow(fac[n]) % mod * fpow(fac[k - n]) % mod);
	return 0;
}