Educational Codeforces Round 161

发表于 更新于 分类于

A - Tricky Template

没啥好说的，就是判断有几个\(a_i=c_i或b_i=c_i\)，有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
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
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;

void work()
{
	cin >> n;
	string a, b, c;
	cin >> a >> b >> c;
	auto check = [&]()
	{
		int cnt = n;
		for (int i = 0; i < n; i++)
		{
			if (a[i] == c[i] || b[i] == c[i])
				cnt--;
		}
		return cnt > 0;
	};
	if (check())
	{
		cout << "YES\n";
	}
	else
	{
		cout << "NO\n";
	}

}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

B - Forming Triangles

可以发现，\(2^i+2^i = 2^{i+1}\)，可见可构成三角形的只有两种情况：

  1. 两个相等的和一个小的组合
  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
67
68
69
70
71
72
73
74
75
// Problem: B. Forming Triangles
// Contest: Codeforces - Educational Codeforces Round 161 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1922/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;

void work()
{
	cin >> n;
	vector<ll> a(n), but(n + 1);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < n; i++)
		but[a[i]]++;
	__int128 big_n = n;
	__int128 ans = 0;
	__int128 sum = 0;
	for (int i = 0; i <= n; i++)
	{
		if (but[i] > 1)
		{
			__int128 x = but[i];
			ans += sum * (x * (x - 1)) / 2ll + (x * (x - 1) * (x - 2)) / 6ll;
		}
		sum += but[i];
	}
	auto print = [&](__int128 x)
	{
		string s;
		while (x)
		{
			s.push_back(x % 10 + '0');
			x /= 10;
		}
		reverse(s.begin(), s.end());
		if (s.size())
			cout << s << endl;
		else
			cout << 0 << endl;
	};
	print(ans);
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

C - Closest Cities

可以发现，最优路线一定是一直朝着终点走，直接正反递推一下距离即可。

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
// Problem: C. Closest Cities
// Contest: Codeforces - Educational Codeforces Round 161 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1922/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;
ll a[N];
ll dp1[N], dp2[N];
void work()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	a[0] = -llinf;
	a[n + 1] = llinf;
	dp1[1] = 0;
	for (int i = 2; i <= n; i++)
	{
		if (abs(a[i - 2] - a[i - 1]) < abs(a[i - 1] - a[i]))
			dp1[i] = dp1[i - 1] + abs(a[i] - a[i - 1]);
		else
			dp1[i] = dp1[i - 1] + 1;
	}
	dp2[n] = 0;
	for (int i = n - 1; i >= 1; i--)
	{
		if (abs(a[i + 2] - a[i + 1]) < abs(a[i + 1] - a[i]))
			dp2[i] = dp2[i + 1] + abs(a[i] - a[i + 1]);
		else
			dp2[i] = dp2[i + 1] + 1;
	}
	cin >> q;
	for (int i = 1; i <= q; i++)
	{
		int x, y;
		cin >> x >> y;
		if (x < y)
			cout << dp1[y] - dp1[x] << endl;
		else
			cout << dp2[y] - dp2[x] << endl;
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

D - Berserk Monsters

可以发现，除了第一次以外，每一回合中被干掉怪物，在上一回合中，他的左邻居或者右邻居一定被干掉了（不然上一回合就会被干掉）。

也就是说，本次可能被干掉的位置，可以由上一次被干掉的人的位置推算而来。

具体的，我们维护一个链表，每次先删除掉由上一回合标记出来的人的节点，然后查询这些节点的左右邻居是否能被干掉，将能被干掉的节点记录下来，留到下一个回合使用。

第一回合可以直接暴力获取被删掉的节点，直接处理即可。

可以发现，每个节点最多可以被删除一次，每个节点最多拓展出2个下一回合的节点，因此复杂度为\(\Theta(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
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
// Problem: D. Berserk Monsters
// Contest: Codeforces - Educational Codeforces Round 161 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1922/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Author: MaxDYF
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 4e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;
typedef pair<pii, int> piii;
int n, m, k, q;
int a[N], b[N];
int l[N], r[N];
bool vis[N];
void work()
{
	cin >> n;
	fill(vis, vis + n + 1, 0);
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++)
		cin >> b[i];
	auto relative = [&](int x)
	{
		int v = 0;
		if (l[x])
			v += a[l[x]];
		if (r[x] <= n)
			v += a[r[x]];
		return b[x] - v;
	};
	vector<int> q;
	for (int i = 1; i <= n; i++)
	{
		l[i] = i - 1;
		r[i] = i + 1;
		q.push_back(i);
	}
	#define __DEBUG__ false
	for (int i = 1; i <= n; i++)
	{
		vector<int> vec;
		vec.clear();
		if (__DEBUG__)
		{
			for (int i = 1; i <= n; i++)
				cout << l[i] << " \n"[i == n];
			for (int i = 1; i <= n; i++)
				cout << r[i] << " \n"[i == n];
			for (int i = 1; i <= n; i++)
				cout << vis[i] << " \n"[i == n];
		}
		//
		for (auto id : q)
		{
			if (l[id] >= 0 && !vis[l[id]] && relative(l[id]) < 0)
				vec.push_back(l[id]), vis[l[id]] = 1;
			if (r[id] <= n && !vis[r[id]] && relative(r[id]) < 0)
				vec.push_back(r[id]), vis[r[id]] = 1;
		}
		//sort(vec.begin(), vec.end());
		for (auto id : vec)
		{
			if (l[id])
				r[l[id]] = r[id];
			if (r[id] <= n)
				l[r[id]] = l[id];
		}
		cout << vec.size() << " \n"[__DEBUG__];
		swap(q, vec);
	}
	cout << endl;
	
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

E - Increasing Subsequences

很巧妙的一道构造题。首先，考虑一个严格单增的数列，它的递增子序列个数为： \[ C_n^0+C_n^1+ \dots +C_n^n \]

由小学组合数学知识可以知道： \[ C_n^0+C_n^1+ \dots +C_n^n=2^n \] 那么，如果\(X\)是2的n次幂，直接输出一个长度为n的单增序列即可。

如果不是的话，一个容易想到的思路是看能否通过在这个单增数列中插入某些数，使得我们能够凑出\(2^0,2^1,2^2\dots 2^{n-1}\)这些数，这样就可以通过二进制拆分凑出X了。

考虑一个单增数列： \[ 1,2,3,4,5,6 \] 这个数列有6个数，所以有\(2^6\)个单增子序列。

那么，如果我们在1和2之间插入一个小于1-6的数（比如说0）： \[ 1,\mathop{0}\limits_{\uparrow},2,3,4,5,6 \] 经过计算，可以发现，在这个位置插入，正好多出了\(2^{5}\)个。

如果在2和3之间呢？ \[ 1,2,\mathop{0}\limits_{\uparrow},3,4,5,6 \] 计算可得，多出了\(2^4\)个。

以此类推，可以发现，在从后往前数第\(\text{i}\)个位置插入0时，总的个数增多\(2^{i-1}\)。而且，因为插入的数相同，所以这些数之间并不会产生新的贡献。

通过这种方式，就能够构建出一个正好有X个单增子序列的数列了。

因为\(X \leq 10^{18} \simeq 2^{60}\)，可以证明，最多不会超过120个数。

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
// Problem: E. Increasing Subsequences
// Contest: Codeforces - Educational Codeforces Round 161 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1922/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;
void work()
{
	ll x;
	cin >> x;
	vector<int> vec;
	int bit = 60;
	for (; bit >= 0; bit--)
		if (x & (1ll << bit))
			break;
	int now = 0;
	vec.push_back(0);
	for (int i = bit - 1; i >= 0; i--)
	{
		if ((1ll << i) & x)
			vec.push_back(0);
		if (i != 0)
			vec.push_back(++now);
	}
	cout << vec.size() << endl;
	for (auto x : vec)
		cout << x << ' ';
	cout << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

F - Replace on Segment

这题没写出来，官方题解写得非常详细，这里贴一个\(\text{DeepL}\)翻译版的。

原文链接，侵删

首先，我们提出以下主张：如果对一个线段进行操作，可以将结果线段视为一个元素（也就是说，我们可以将受操作影响的元素 "合并 "为一个）。这很直观，但正式的证明有点长，所以如果你对它不感兴趣，请随意跳过接下来用斜体写的段落。

正式证明： 假设我们将几个相邻的相等元素合并为一个元素。让我们证明这不会改变数组的答案。假设合并相邻相等元素前的数组为 \(a\) ，合并后的数组为 \(a'\) 。我们将证明 \(f(a) = f(a')\) ，其中 \(f(x)\) 是在数组 \(x\) 上解决问题的最少操作数。

  • \(f(a) \ge f(a')\) ：假设我们建立了一个操作序列，使 \(a\) 中的所有元素都相等。考虑我们合并得到 \(a'\) 的相邻相等元素段。让我们舍弃序列中所有操作中该元素段的所有元素，除了第一个元素，并删除所有现在影响零元素的操作。我们将得到一个有效的操作序列，使 \(a'\) 的所有元素都相等。因此， \(a\) 的任何有效操作序列都可以转化为 \(a'\) 的有效操作序列（可能会舍弃某些操作），这就是 \(f(a) \ge f(a')\) 的原因；
  • \(f(a) \le f(a')\) ：假设我们建立了一个操作序列，使 \(a'\) 的所有元素都相等。如果我们在所有操作中 "扩展 "合并分段后得到的元素，那么它就可以转化为 \(a'\) 的有效操作序列。因此， \(f(a) \le f(a')\) ；
  • 既然 \(f(a) \ge f(a')\) 和 \(f(a) \le f(a')\) ，那么 \(f(a) = f(a')\) 。

这意味着，在对一个分割段进行操作后，接下来的操作要么会影响整个分割段，要么不会影响分割段中的任何元素。

因此我们可以使用下面的动态编程思想：假设 \(dp[l][r][k]\) 是将线段 \([l, r]\) 上的所有元素转化为 \(k\) 所需的最小操作次数。如果我们想将所有元素转化为 \(k\) ，那么有两种选择：

  • 要么最后一次运算会将整个线段转化为 \(k\) ，因此我们需要计算从线段中去除所有等于 \(k\) 的元素所需的运算次数；
  • 或者将线段 \([l, r]\) 分割成几个线段，分别转化为 \(k\) 。

第二种方案很容易建模：我们遍历两个部分 \(i\) 之间的分割点，并用 \(dp[l][i][k] + dp[i+1][r][k]\) 更新 \(dp[l][r][k]\) 。然而，第一种方案就比较复杂了。

让我们为解决方案引入第二种动态编程：假设 \(dp2[l][r][k]\) 是将 \(k\) 从线段 \([l, r]\) 中移除的最小操作次数。那么，计算 \(dp[l][r][k]\) 的第一种方案就可以通过简单地用 \(dp2[l][r][k] + 1\) 更新 \(dp[l][r][k]\) 来实现。

现在，我们来演示如何计算 \(dp2[l][r][k]\) 。这与第一个动态编程非常相似：

  • 要么对线段的最后一次操作会将整个线段转化为其他元素 \(m\) ，因此我们可以对其进行迭代，并用 \(dp[l][r][m]\) 更新 \(dp2[l][r][k]\) ；
  • 或者是将线段 \([l, r]\) 分割成两部分，然后分别删除这两部分中等于 \(k\) 的元素（因此我们用 \(dp2[l][i][k] + dp2[i+1][r][k]\) 更新 \(dp2[l][r][k]\) ）。

好了，看起来我们在 \(O(n^4)\) 中找到了解决方案。不过还有一个问题。我们的动态编程中存在循环依赖关系：

  • \(dp[l][r][k]\) 依赖于 \(dp2[l][r][k]\) ；
  • \(dp2[l][r][k]\) 依赖于 \(dp[l][r][m]\) ，其中 \(m \ne k\) ；
  • \(dp[l][r][m]\) 取决于 \(dp2[l][r][m]\) ；
  • \(dp2[l][r][m]\) 取决于 \(dp[l][r][k]\) 。

我们要么以某种方式处理它们，要么将它们删除。模型解决方法是这样消除这些循环依赖关系的：当我们需要计算 \(dp[l][r][k]\) 时，让我们舍弃线段两端所有等于 \(k\) 的元素（即把 \(l\) 移到 \(l'\) 和 \(r\) 移到 \(r'\) ，其中 \(l'\) 和 \(r'\) 是不等于 \(k\) 的元素的第一次和最后一次出现）。同样，当我们需要计算 \(dp2[l][r][k]\) 时，让我们舍弃线段两端所有不等于 \(k\) 的元素。很容易证明这些操作不会使答案变差（如果从数组中删除一个元素，"修复 "数组的最小操作次数不会增加）。要证明这种方法能消除所有循环依赖关系也不难：如果我们考虑前面描述的循环依赖关系，我们可以看到在计算 \(dp[l][r][k]\) 时（如果有 \(a_l = k\) ）或在计算 \(dp[l][r][k]\) 时，元素 \(a_l\) 将被从数段中丢弃。(如果 \(a_l = k\) ）或计算 \(dp2[l][r][k]\) （如果 \(a_l \ne k\) ）时， \(a_l\) 元素都会被舍弃。

这样，我们就得到了一个在 \(O(n^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
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
// Problem: F. Replace on Segment
// Contest: Codeforces - Educational Codeforces Round 161 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1922/problem/F
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// Author: MaxDYF
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q, x;
int dp[101][101][101];
int f[101][101][101];
int a[101];
void work()
{
	cin >> n >> x;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			for (int k = 1; k <= x; k++)
				f[i][j][k] = dp[i][j][k] = inf;
	// f[i][j][c] : 把i到j的c变成非c
	// dp[i][j][c] : 把i到j全变成c
	for (int i = 1; i <= n; i++)
		for (int c = 1; c <= x; c++)
		{
			f[i][i][c] = (a[i] == c);
			dp[i][i][c] = (a[i] != c);
		}
	for (int len = 2; len <= n; len++)
		for (int i = 1; i + len - 1 <= n; i++)
		{
			int j = i + len - 1;
			for (int c = 1; c <= x; c++)
			{
				if (a[i] == c)
					dp[i][j][c] = min(dp[i][j][c], dp[i + 1][j][c]);
				else
					f[i][j][c] = min(f[i][j][c], f[i + 1][j][c]);
				if (a[j] == c)
					dp[i][j][c] = min(dp[i][j][c], dp[i][j - 1][c]);
				else
					f[i][j][c] = min(f[i][j][c], f[i][j - 1][c]);
			}
			for (int c = 1; c <= x; c++)
				for (int k = i; k < j; k++)
					f[i][j][c] = min(f[i][j][c], f[i][k][c] + f[k + 1][j][c]);
			for (int c = 1; c <= x; c++)
				for (int k = i; k < j; k++)
					dp[i][j][c] = min(dp[i][j][c], dp[i][k][c] + dp[k + 1][j][c]);
			for (int c = 1; c <= x; c++)
				dp[i][j][c] = min(dp[i][j][c], f[i][j][c] + 1);
			for (int c1 = 1; c1 <= x; c1++)
				for (int c2 = 1; c2 <= x; c2++)
					if (c1 != c2)
						f[i][j][c1] = min(f[i][j][c1], dp[i][j][c2]);
		}
	int ans = inf;
	for (int i = 1; i <= x; i++)
		ans = min(ans, dp[1][n][i]);
	cout << ans << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}