Codeforces Round 934 Div 2

发表于 更新于 分类于

A.Destroying Bridges

显然，如果k大于等于了n-1，那么可以将与1相连的所有边给去掉，最小值就是1。

如果不够，显然不存在任何一种方法将某一个点孤立出来。

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
// Problem: A. Destroying Bridges
// Contest: Codeforces - Codeforces Round 934 (Div. 2)
// URL: https://codeforces.com/contest/1944/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 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 >> k;
	int ans = n;
	if (k >= n - 1)
		cout << 1 << endl;
	else
		cout << n << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

B. Equal XOR

我们将左半边称作\(A\)，右半边称作\(B\)，发现有以下性质：

  1. 倘若\(A\)里某数只有一个，那\(B\)一定存在且仅存在一个这个数；
  2. 倘若\(A\)里有p对相同的数，那么另一边也一定有且仅有p对相同的数。

知道这两个性质，我们很容易想到构造合法方案的方法。详情见代码。

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
// Problem: B. Equal XOR
// Contest: Codeforces - Codeforces Round 934 (Div. 2)
// URL: https://codeforces.com/contest/1944/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 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 >> k;
	vector<int> a(2 * n), but1(n + 1), but2(n + 1);
	for (int i = 0; i < 2 * n; i++)
		cin >> a[i];
	vector<int> q1, q2;
	for (int i = 0; i < 2 * n; i++)
	{
		if (i < n)
			but1[a[i]]++;
		else
			but2[a[i]]++;
	}
	for (int i = 1; i <= n; i++)
		if (but2[i] == 1 && but1[i] == 1 && (int)(q1.size()) < 2 * k)
		{
			q1.push_back(i);
			q2.push_back(i);
		}
	if (q1.size() % 2 == 1)
	{
		q1.pop_back();
		q2.pop_back();
	}
	for (int i = 1; i <= n; i++)
		if ((int)q1.size() < 2 * k && but1[i] == 2)
		{
			q1.push_back(i);
			q1.push_back(i);
		}
	for (int i = 1; i <= n; i++)
		if ((int)q2.size() < 2 * k && but2[i] == 2)
		{
			q2.push_back(i);
			q2.push_back(i);
		}
	for (auto x : q1)
		cout << x << ' ';
	cout << endl;
	for (auto x : q2)
		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();
	}
}

C. MEX Game 1

我们假设数字p只有一个，\(\{0,1,2,\ldots p-1\}\)都有两个以上，显然，Alice必须将\(p\)取掉，否则\(p\)就会被Bob取掉，答案就被固定在\(p\)了。

而对于Bob来说，由于他是后手，所以取任何一个次数大于1的数都是没有意义的（在取到0之前就会被Alice取掉）。所以，和Alice一样，他的最优选择就是取掉当前数字最小的、出现次数为1的数。

由于前面Alice取掉了最小的那个\(p\)，所以Bob只能取第二大的\(q\)。所以最大的mex就是\(q\)。

注意，如果只有一个次数为1的数，或者一个都没有，就不存在第二大的数了。此时我们应该选择出现的最大数字+1，即mex = maxnum + 1。

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
// Problem: C. MEX Game 1
// Contest: Codeforces - Codeforces Round 934 (Div. 2)
// URL: https://codeforces.com/contest/1944/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;

void work()
{
	cin >> n;
	vector<int> a(n), but(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		but[a[i]]++;
	}
	vector<int> ans;
	bool bj = 0;
	for (int i = 0; i < n; i++)
	{
		if (but[i] == 1)
			ans.push_back(i);
		else if (but[i] == 0)
		{
			ans.push_back(i);
			bj = 1;
			break;
		}
	}
	if (bj == 0)
		ans.push_back(n);
	if (ans.size() == 1)
	{
		cout << ans[0] << endl;
	}
	else
	{
		cout << ans[1] << endl;
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

E. Tree Compass

很有意思的结论图论题。

考虑分类讨论。

\(N\)是奇数

令这棵树的直径节点个数为\(N\)。显然，这条直径是原树的一个子图，而这条链答案显然为\(\lfloor\frac{N}{2}\rfloor+1\)，所以答案的下界一定是\(\lfloor\frac{N}{2}\rfloor+1\)。

这条直径就只有一个中心点。我们直接对这个点操作，对\(d=\{0,1,2\ldots[\frac{N}{2}]\}\)染色，显然染完了所有节点，答案为\(\lfloor\frac{N}{2}\rfloor+1\)，达到了答案下界，所以是最优解。

\[N\]​是偶数

在这种情况下，N显然存在两个中心点pos1,pos2。我们发现，如果对pos1进行\(d=d_0\)的操作，相当于对pos2进行了一次\(d=d_0-1\)的操作。继续分类讨论。

我们令半径\(R=\frac N 2\)，我们对pos1进行\(d=1\)的操作，相当于对pos2进行了\(d=0\)的操作；对pos2进行\(d=1\)的操作，相当于对pos1进行了\(d=0\)​的操作。在这一轮操作里，我们用2次完成了对\(pos1,pos2\)的\(d=0,1\)的操作。此时再对\(R\)分类讨论。

\(R\)是偶数

我们进行\(\frac R 2\)轮上述操作，就完成了整张图的覆盖。共用\(cnt=2 \times \frac R 2=\frac N 2\)。这种情况显然达到了答案下界。

R是奇数

这种情况下，我们先做\(\lfloor\frac R2\rfloor\)轮上述操作，此时，我们还剩下离\(pos1\)距离为\(d=R-1,R\)的节点没有覆盖。因此需要再覆盖两次。最终答案为\(cnt=2 \times \frac{R-1} 2+2=2R+1=\frac N 2+1\)次，也达到了下界。

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
124
125
// Problem: E. Tree Compass
// Contest: Codeforces - Codeforces Round 934 (Div. 2)
// URL: https://codeforces.com/contest/1944/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;

int d1[N], d2[N];
vector<int> E[N];
int maxpos = -1;
int to1[N], to2[N];
// find tree radium module from oi-wiki
void dfs(int u, int fa) {
  d1[u] = d2[u] = 0;
  to1[u] = to2[u] = -1;
  for (int v : E[u]) {
    if (v == fa) continue;
    dfs(v, u);
    int t = d1[v] + 1;
    if (t > d1[u])
    {
      to2[u] = to1[u];
      to1[u] = v;
      d2[u] = d1[u];
      d1[u] = t;
    }
    else if (t > d2[u])
    {
      d2[u] = t;
      to2[u] = v;
    }
  }
  if (maxpos == -1 || d1[u] + d2[u] > d1[maxpos] + d2[maxpos])
  	maxpos = u;
}
void work()
{
	cin >> n;
	maxpos = -1;
	if (n == 1)
	{
		cout << "1\n1 0" << endl;
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		E[i].clear();
	}
	for (int i = 1; i < n; i++)
	{
		int x, y;
		cin >> x >> y;
		E[x].push_back(y);
		E[y].push_back(x);
	}
	dfs(1, 0);
	vector<int> ans;
	ans.push_back(maxpos);
	int l = to1[maxpos], r = to2[maxpos];
	//cout << "maxpos = " << maxpos << endl;
	while (l != -1)
	{
		ans.push_back(l);
		//cout << "now l = " << l << endl;
		l = to1[l];
	}
	reverse(ans.begin(), ans.end());
	while (r != -1)
	{
		ans.push_back(r);
		//cout << "now r = " << r << endl;
		r = to1[r];
	}
	if (ans.size() % 4 != 0)
	{
		int pos = ans[ans.size() / 2], len = (ans.size()) / 2;
		cout << len + 1 << endl;
		for (int i = 0; i <= len; i++)
			cout << pos << ' ' << i << '\n';
		cout << flush;
	}
	else
	{
		int pos1 = ans[ans.size() / 2], pos2 = ans[ans.size() / 2 - 1];
		int len = ans.size() / 2 - 1;
		cout << len + 1 << endl;
		for (int i = 1; i <= len; i += 2)
		{
			cout << pos1 << ' ' << i << endl;
			cout << pos2 << ' ' << i << endl;
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}