Codeforces Round 915 Div 2

发表于 更新于 分类于

A. Constructive Problems

赛事通过观察法可得出答案就是\(\max(n, m)\)（bushi

可以发现，每一行每一列都至少得有一个，所以得证。

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
// Problem: A. Constructive Problems
// Contest: Codeforces - Codeforces Round 915 (Div. 2)
// URL: https://codeforces.com/contest/1905/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 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;

void work()
{
	cin >> n >> m;
	cout << max(n, m) << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

B. Begginer's Zelda

一开始想复杂了，总想着从直径考虑。其实没有这么复杂。

观察每次操作，可以发现，最优操作下，每次操作必定会少两个原图的叶子节点（最后一次可能只少1个）。所以只需判断叶子的数量\(cnt\),答案即为 \[ \lceil \frac {cnt}2 \rceil = \frac{cnt + 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
// Problem: B. Begginer's Zelda
// Contest: Codeforces - Codeforces Round 915 (Div. 2)
// URL: https://codeforces.com/contest/1905/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 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;
int x, y;
int in[N];
void work()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		in[i] = 0;
	for (int i = 1, x, y; i < n; i++)
	{
		cin >> x >> y;
		in[x]++;
		in[y]++;
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++)
		cnt += (in[i] == 1);
	cout << (cnt + 1) / 2 << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

C. Largest Subsequence

手玩几组样例可以发现，所有能进行的有效操作，等效于将一个字典序最大的不上升子序列给排序。

并且，这样操作完后，最大的那个字母一定在最后一个位置。也就是说，接下来的操作都是无效的。

所以能够发现，一个字符串能够用这种操作排序，当且仅当将串中这个字典序最大的不上升子序列取出排序、再插入回原序列中后，这个字符串有序。

模拟这个过程，\(O(n)\)即可完成。其步数为这个子序列的长度-1。

注意特判子序列中最大的那个字符有多个的情况，此时的答案为\(m-cnt\)，其中\(m\)为子序列长度，\(cnt\)为最大字符的个数。

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
// Problem: C. Largest Subsequence
// Contest: Codeforces - Codeforces Round 915 (Div. 2)
// URL: https://codeforces.com/contest/1905/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 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;
void work()
{
	string s;
	cin >> n;
	cin >> s;
	vector<int> vec;
	vec.reserve(n);
	for (int i = 0; i < n; i++)
	{
		while (!vec.empty() && s[i] > s[*(vec.rbegin())])
			vec.pop_back();
		if (vec.empty() || s[i] <= s[*(vec.rbegin())])
			vec.push_back(i);
	}
	int m = vec.size(), ans = m;
	for (int i = 1; i < m; i++)
		if (s[vec[i]] == s[vec[i - 1]])
			ans--;
		else
			break;
	for (int i = 0; i < m / 2; i++)
		swap(s[vec[i]], s[vec[m - i - 1]]);
	if (is_sorted(s.begin(), s.end()))
		cout << ans - 1 << endl;
	else
		cout << -1 << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

D. Cyclic MEX

让我们观察一下如何从原序列的答案推到循环左移一步的每一位的\(mex_i\)（\(mex_i\)定义为\(mex\{a_1,a_2,a_3,\dots a_i\}\)。

假设原序列的第一个数是\(x\)，左移一步，则对于之后\(mex_i\)来说：

  1. \(mex_i\leq x\)​，很明显不受影响。
  2. \(mex_i>x\)，可以发现由于前面缺少了\(x\)，\(mex_i\)就变成了\(x\)​。
  3. 对于最后一位，由于是排列，所以显然有\(mex_n=n\)。

显然，由于\(mex_i\)单调不降，我们可以用一个deque模拟这个过程。

每次将\(x\)​从队头取出，从队尾开始将\(mex_i>x\)的更新成\(x\)，然后再在队尾加入一个\(n\)即可。

很容易发现，每个元素都可能被更改多次，时间复杂度得不到保证。

但是，我们更改值的操作，只是把队尾\(mex_i\)的值给改成一个相同的数\(x\)，那么，我们可以让每个队列元素多记录一个值\(cnt\)，将这些\(x\)给压成一个元素。这样就能够大幅缩减复杂度。（应该是\(O(n)\)？但是不会证QAQ）

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
// Problem: D. Cyclic MEX
// Contest: Codeforces - Codeforces Round 915 (Div. 2)
// URL: https://codeforces.com/contest/1905/problem/D
// Memory Limit: 512 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 = 1e6 + 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;
pll q[N * 3];
int a[N];
int minn[N];
void work()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	minn[n + 1] = n;
	ll sum = 0, ans = 0;
	for (int i = n; i >= 1; i--)
		minn[i] = min(minn[i + 1], a[i]);
	int l = N, r = N;
	for (int i = 1; i <= n; i++)
	{
		sum += minn[i + 1];
		q[r++] = {minn[i + 1], 1};
	}
	ans = sum;
	for (int i = 1; i < n; i++)
	{
		int now = a[i], pos = r - 1;
		sum -= q[l].first;
		if (--q[l].second == 0)
			l++;
		ll cnt = 0;
		while (pos >= l && q[pos].first >= now)
		{
			sum -= q[pos].first * q[pos].second;
			sum += now * q[pos].second;
			cnt += q[pos].second;
			r--, pos--;
		}
		q[r++] = {now, cnt};
		q[r++] = {n, 1};
		sum += n;
		ans = max(ans, sum);
	}
	cout << ans << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}