Codeforces Round 930 Div 2

发表于 更新于 分类于

A. Shuffle Party

比赛想法：

观察样例，发现答案小于等于n，且是2的整数次幂，猜测答案为小于等于n的最大的2的整次幂。

赛后证明：

显然，对于一个整数\(d\)，它的最小倍数一定是\(2d\)。则对于1来说，每次都×2，最终答案就是最大的小于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
// Problem: A. Shuffle Party
// Contest: Codeforces - Codeforces Round 930 (Div. 2)
// URL: https://codeforces.com/contest/1937/problem/0
// 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()
{
	ll n;
	cin >> n;
	cout << (1LL << (int)log2(n)) << '\n';
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

B. Binary Path

显然，蚱蜢只会向右移动一次，总共有n种可能，所以我们可以枚举向右走的地方。

我们设两个变量maxid和s，分别表示在第maxid行向右行，以及有s个与其相等的序列。假设现在在第\(i\)行，显然有两种可能：向下走和向右走。有3种情况：

  1. 两个数相等：则这两种情况相等，s累加上1。
  2. 向下的是0，向右的是1：则只有向下走一种可能，更新maxid，s重置为1。
  3. 向下的是1，向右的是0：则显然只能向右走了，后面没有分支了，直接break。
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
// Problem: B. Binary Path
// Contest: Codeforces - Codeforces Round 930 (Div. 2)
// URL: https://codeforces.com/contest/1937/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;
int a[N][2], f[N][2];
void work()
{
	cin >> n;
	string s;
	cin >> s;
	for (int i = 1; i <= n; i++)
		a[i][0] = s[i - 1] - '0';
	cin >> s;
	for (int i = 1; i <= n; i++)
		a[i][1] = s[i - 1] - '0';
	int maxid = 1, s0 = 1;
	for (int i = 2; i <= n; i++)
	{
		if (a[i - 1][1] == a[i][0])
			s0++;
		else if (a[i - 1][1] > a[i][0])
		{
			s0 = 1;
			maxid = i;
		}
		else
			break;
	}
	for (int i = 1; i <= maxid; i++)
		cout << a[i][0];
	for (int i = maxid; i <= n; i++)
		cout << a[i][1];
	cout << '\n' << s0 << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

C. Bitwise Operation Wizard

非常有趣的一题。

我们设小于等于n-1的最大的2的整次幂数为\(2^p\)，容易发现，能得到最大的数对异或和为\(2^{p+1}-1\)。

每次可以询问(a | b)和(c | d)的大小关系。如果a=b, c=d，那么相当于询问a与b的大小。这样我们可以用n-1次询问得出最大的数maxn。

然后，令\(fix=(2^{p+1}-1) \oplus maxn\)，显然有\(fix|maxn=2^{p+1}-1\)。观察所有满足\(maxn|q=2^{p+1}-1\)的数，显然，\(fix\)是其中最小的。这样，我们只要先求出\(p\oplus q\)的最大值，每次更新最大值时再求出最小的\(q\)，这样这部分就能在\(2n\)次询问完成。总共小于\(3n\)。

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. Bitwise Operation Wizard
// Contest: Codeforces - Codeforces Round 930 (Div. 2)
// URL: https://codeforces.com/contest/1937/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;
	int maxid = 0;
	for (int i = 1; i < n; i++)
	{
		cout << "? " << maxid << ' ' << maxid << ' ' << i << ' ' << i << endl;
		char cmp;
		cin >> cmp;
		if (cmp == '<')
			maxid = i; 
	}
	int xorid = 0;
	if (maxid == 0)
		xorid = 1;
	for (int i = 0; i < n; i++)
	{
		if (i == maxid || i == xorid)
			continue;	
		cout << "? " << maxid << ' ' << xorid << ' ' << maxid << ' ' << i << endl;
		char cmp0;
		cin >> cmp0;
		if (cmp0 == '<')
			xorid = i;
		else if (cmp0 == '=')
		{
			cout << "? " << xorid << ' ' << xorid << ' ' << i << ' ' << i << endl;
			char cmp1;
			cin >> cmp1;
			if (cmp1 == '>')
				xorid = i;
		}
	}
	cout << "! " << maxid << ' ' << xorid << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

D. Pinball

对于第\(i\)位，发现左边每有一个>，就会有一次折返；右边每有一个<，也会有一个折返。

发现在坐标向右移动的过程中，左边的>递增，右边的<递减。我们用单调队列维护左边折返用时以及右边折返用时。

这题细节很多，需要注意写法。

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
// Problem: D. Pinball
// Contest: Codeforces - Codeforces Round 930 (Div. 2)
// URL: https://codeforces.com/contest/1937/problem/D
// 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 = 6e5 + 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 pre[N], nxt[N];
ll fwd[N];
ll ans[N];
void work()
{
	cin >> n;
	string s;
	cin >> s;
	s = ' ' + s;
	pre[0] = 0;
	for (int i = 1; i <= n; i++)
		ans[i] = 0;
	for (int i = 1; i <= n; i++)
	{
		pre[i] = pre[i - 1];
		if (s[i] == '>')
			pre[i]++;
	}
	nxt[n + 1] = 0;
	for (int i = n; i >= 1; i--)
	{
		nxt[i] = nxt[i + 1];
		if (s[i] == '<')
			nxt[i]++;
	}

	// fwd[i] = 0 left
    //            = 1 right
	for (int i = 1; i <= n; i++)
	{
		if (s[i] == '<')
			fwd[i] = pre[i - 1] > nxt[i + 1];
		else
			fwd[i] = pre[i - 1] >= nxt[i + 1];
		if (!fwd[i])
			ans[i] += i;
		else
			ans[i] += n - i + 1;
	}
	queue<ll> q1, q2;
	ll tag = 0, sum = 0;
	for (int i = 1; i <= n; i++)
	{
		tag += 2;
		if (s[i] == '>')
			q1.push(-tag);		
		if (s[i] == '>')
			sum += (q1.size() - 1) * 2LL;
		else
			sum += (q1.size()) * 2LL;
		while (q1.size() > nxt[i] + (int)(s[i] == '>'))
		{
			sum -= tag + q1.front();
			q1.pop();
		}

		ans[i] += sum;
	}
	tag = sum = 0;
	for (int i = n; i >= 1; i--)
	{
		tag += 2;
		if (s[i] == '<')
			q2.push(-tag);
		if (s[i] == '<')
			sum += (q2.size() - 1) * 2;
		else
			sum += q2.size() * 2;
		while (q2.size() > pre[i] + (int)(s[i] == '<'))
		{
			sum -= tag + q2.front();
			q2.pop();
		}

		ans[i] += sum;
	}
	for (int i = 1; i <= n; i++)
		cout << ans[i] << " \n"[i == n];
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}