CodeforcesRound#519

Posted on | In |
Words count in article: 2.7k | Reading time ≈ 13

Codeforces Round #519

A. Elections

题意：有 $n$ 个人，每个人都有 $k$ 票，已知第 $i$ 个人会投给对手 $a_i$ 票，问假若 $\text{Awruk}$ 想赢， $k$ 最小是多少。

思路：思博题目，很显然对手的总票数为

那么想要赢，$\text{Awruk}$ 的票数应该至少为

可以知道两个人的总票数应该是 $nk$ ，所以就可以得到

代码：

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
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int N = 1e6 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;

il int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch))
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}

int n, sum, maxx = -inf;
int a[N];

int main()
{
	n = read();
	for (ri i = 1; i <= n; i++)
		a[i] = read(), sum += a[i], maxx = max(a[i], maxx);
	sum = sum * 2 + 1;
	int k = ceil(sum * 1.0 / n);
	printf("%d", max(k, maxx));
	return 0;
}

B. Lost Array

题意：给出一个 $a$ 序列，已知

求 $x$ 序列所有可能的长度。

思路：一眼看上去表示不会，然而这个题的 $n$ 和 $k$ 都非常小，所以我们可以考虑 $O(n^2)$ 的暴力。具体做法就是枚举长度然后判断是否合法。判断合法的方法很简单：是否有一个位置被重复赋过值。

代码：

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
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int N = 1e6 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;

il int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch))
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}

int n;
int a[N], x[N];
int ans[N];
bool vis[N];

il bool Check(int k)
{
	memset(vis, 0, sizeof(vis));
	memset(x, 0, sizeof(x));
	for (ri i = 1; i <= n; i++)
	{
		if (vis[i % k] && x[i % k] == a[i] - a[i - 1])
			continue;
		else if (!vis[i % k])
		{
			vis[i % k] = 1;
			x[i % k] = a[i] - a[i - 1];
		}
		else
			return 0;
	}
	return 1;
}

int main()
{
	n = read();
	for (ri i = 1; i <= n; i++)
		a[i] = read();
	for (ri i = 1; i <= n; i++)
		if (Check(i))
			ans[++ans[0]] = i;
	printf("%d\n", ans[0]);
	for (ri i = 1; i <= ans[0]; i++)
		printf("%d ", ans[i]);
	return 0;
}

C. Smallest Word

题意：给出一个只由 $a$ 和 $b$ 组成的字符串 $s$ ，对于第 $i$ 个位置，我们把 $s_1$ 到 $s_i$ 称作一个前缀串，现在 $\text{IA}$ 从 $s_1$ 开始，到每一个位置时都可以选择是否翻转该位置的前缀串，现在她想使翻转后的串字典序最小，问她该如何操作。

思路：很显然这又是一道思博贪心题，稍作思考不难发现一定可以把所有的 $a$ 都拼在一起放在最前面，那么如何做到呢？

由于题目是从前向后择的，也就是说，如果按照最优的情况，当且仅当以下两种情况会需要翻转：

  1. 该位置为连续 $b$ 子串的最后一位且不位于字符串的末尾
  2. 该位置为连续 $a$ 子串的最后一位

第二种情况很好理解，显然翻转就会把连续 $a$ 子串置于字符串开头；第一种情况成立的理由其实也很简单，因为遇到连续 $b$ 子串的时候字符串最前面一定是连续的 $a$ ，当前位置后面也一定是连续的 $a$ ，翻转可以将两个 $a$ 子串拼在一起，并最终翻转到最前面。

代码：

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
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int N = 1e6 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;
const int maxn = 1010;

il int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch))
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}

char s[maxn];

int main()
{
	scanf("%s", s);
	int len = strlen(s);
	s[len] = 'b';
	for (ri i = 0; i < len; i++)
	{
		if (s[i] == 'a' && s[i + 1] == 'b' || s[i] == 'b' && s[i + 1] == 'a')
			printf("1 ");
		else
			printf("0 ");
	}
	return 0;
}

D. Mysterious Crime

题意：给出 $1$ 到 $n$ 的 $m$ 个排列，问这 $m$ 个排列的公共子序列有几个

思路：考虑到 $m$ 很小，所以也可以暴力（卡了我一个小时），我们可以枚举起点然后找出从这个点开始的最长公共子序列长度，然后很显然公共子序列的数量就等于长度，然后统计就行了。

代码：

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int maxn = 1e5 + 10;

il int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch))
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}

int n, m;

int a[10][maxn], b[10][maxn];

int c[maxn];

int main()
{
	n = read(), m = read();
	for (ri j = 0; j < m; j++) 
		for (ri i = 1; i <= n; i++)
			a[j][i] = read();
	for (ri j = 0; j < m; j++)
		for (ri i = 1; i <= n; i++)
			b[j][a[j][i]] = i;
	
	ll ans = 0;
	
	for (ri i = 1; i <= n; i++)
	{
		if (c[i - 1])
			c[i] = c[i - 1] - 1;
		while (1)
		{
			if (c[i] + i > n)
				break;
			bool fail = 0;
			for (ri j = 1; j < m; j++)
			{
				int p = b[j][a[0][i]] + c[i];
				if (p > n || a[0][i + c[i]] != a[j][p])
				{
					fail =1;
					break;
				}
			}
			if (fail)
				break;
			c[i]++;
		}
		ans += c[i];
	}
	printf("%lld", ans);
}

E. Train Hard, Win Easy

题意：给出 $n$ 个人，每两个人组成一队做两道题，已知第 $i$ 个人写 $\text{A}$ 题和 $\text{B}$ 题的得分分别为 $x_i$ 和 $y_i$ ，该队伍的得分为两个人做两道题的得分之和（分配题目时以使团队得分最小的方式分配）。同时有 $m$ 对人互相不想组队，问每个人能组的所有队的得分之和。

思路：很显然就是求一个无向完全图删掉一些边后从每个点连出去的所有边的边权之和。但是 $n$ 相当的大，直接做很显然是不可能的，但是我们如果在草稿纸上写一下式子，就会发现这样一个结论：计算完全图的时候只要按照 $x_i - y_i$ 排序就可以快速计算了。证明很简单：

我们假设能够让排在 $i$ 前面的选手都写 $\text{A}$ 题，排在 $i$ 后面的选手都写 $\text{B}$ 题最优，那么对于 $\forall j < i$ ，一定有

移项，得

至此得证。

所以我们只要 $O(n)$ 的算出完全图时候的答案，删边的时候直接暴力减就可以了，复杂度 $O(nlogn)$ （快排的复杂度）。

代码：

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int N = 3e5 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;

il int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch))
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}

int n, m;
ll pre[N], succ[N];
struct node
{
	int x, y, id;
	ll ans;
	friend bool operator < (node a1, node a2)
	{
		return a1.x - a1.y < a2.x - a2.y;
	}
};
node a[N];

il bool cmp(node a1, node a2)
{
	return a1.id < a2.id;
}

int main()
{
	n = read(), m = read();
	for (ri i = 1; i <= n; i++)
		a[i].x = read(), a[i].y = read(), a[i].id = i;
	sort(a + 1, a + 1 + n);
	for (ri i = 1; i <= n; i++)
		pre[i] = pre[i - 1] + a[i].x;
	for (ri i = n; i; i--)
		succ[i] = succ[i + 1] + a[i].y;
	for (ri i = 1; i <= n; i++)
		a[i].ans += pre[i - 1] + 1ll * a[i].y * (i - 1) + succ[i + 1] + 1ll * a[i].x * (n - i);
	sort(a + 1, a + 1 + n, cmp);
	for (ri i = 1; i <= m; i++)
	{
		int x1 = read(), x2 = read();
		a[x1].ans -= min(a[x1].x + a[x2].y, a[x2].x + a[x1].y);
		a[x2].ans -= min(a[x1].x + a[x2].y, a[x2].x + a[x1].y);
	}
	for (ri i = 1; i <= n; i++)
		printf("%lld ", a[i].ans);
	return 0;
}
/*
3 2
1 2
2 3
1 3
1 2
2 3

*/

F. Make It One

题意：给出 $n$ 个数，问最少选出几个数，使得选出数的 $gcd$ 为 $1$ 。

思路：正解是神仙 $\text{DP}$ ，我当然不会了（

但是，我会莫比乌斯反演！想到在某谷上做过一道四元组统计，这不就是 $k$ 元组统计吗？然后掐指一算，我们发现：

也就是说，答案不可能超过 $7$ ！这样就使得暴力做 $k$ 元组统计成为可能。判断一个 $k$ 是否可行的时候只要看方案数是否为 $0$ 就行了。

Q&A：

Q： $C_{3 \times 10^5}^7$ 太大了爆 $\text{long long}$ 怎么办？

A：你不会取模吗？

Q：取模导致误判怎么办？

A：多模几个数啊！

代码：

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int N = 3e5 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;
const ll mod = 998244353;
const ll p = 19260817;

il int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch))
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}

int n, maxx = -inf;
ll times[N];

int prime[N], mu[N];
ll C[2][N][8];
ll f[2][N];

il ll pls(ll a, ll b, ll foo)
{
	if (a + b < 0)
	{
		a += b;
		while (a < 0)
			a += foo;
		return a;
	}
	else
		return a + b >= foo ? a + b - foo : a + b;
}

il void Get_C()
{
	C[0][0][0] = C[1][0][0] = 1;
	for (ri i = 1; i <= n; i++)
	{
		C[0][i][0] = C[1][i][0] = 1;
		for (ri j = 1; j <= 7; j++)
		{
			C[0][i][j] = pls(C[0][i - 1][j - 1], C[0][i - 1][j], mod);
			C[1][i][j] = pls(C[1][i - 1][j - 1], C[1][i - 1][j], p);
		}
	}
}

bool vis[N];

il void Get_mu()
{
	mu[1] = 1;
	for (ri i = 2; i <= maxx; i++)
	{
		if (!vis[i])
		{
			prime[++prime[0]] = i;
			mu[i] = -1;
		}
		for (ri j = 1, foo; j <= prime[0] && (foo = prime[j] * i) <= maxx; j++)
		{
			vis[foo] = 1;
			if (i % prime[j])
				mu[foo] = -mu[i];
			else
				break;
		}
	}
}

int main()
{
	n = read();
	for (ri i = 1; i <= n; i++)
	{
		int x = read();
		times[x]++;
		maxx = max(maxx, x);
	}
	Get_C();
	Get_mu();
	for (ri i = 1; i <= min(n, 7); i++)
	{
		memset(f, 0, sizeof(f));
		for (ri j = maxx; j; j--)
		{
			for (ri k = j; k <= maxx; k += j)
				f[0][j] += times[k], f[1][j] += times[k];
			f[0][j] = C[0][f[0][j]][i], f[1][j] = C[1][f[1][j]][i];
		}
		ll ans1 = 0, ans2 = 0;
		for (ri j = 1; j <= maxx; j++)
		{
			ans1 = pls(ans1, f[0][j] * mu[j], mod);
			ans2 = pls(ans2, f[1][j] * mu[j], p);
		}
		if (ans1 || ans2)
		{
			printf("%d", i);
			return 0;
		}
	}
	printf("%d", -1);
	return 0;
}

G. Speckled Band

留个坑以后再填 咕咕咕

0%