Codeforces Round 930 (Div. 2)

[题目链接](https://codeforces.com/contest/1937)

A. Shuffle Party

题意

给出一个数组 起初 ，之后定义 操作为 : 找到最大的，不等于的因子 ，交换和 。

下面令 ，依次进行 ，问最终数值会在哪个位置。

思路

数值1会随着不断运行swap来移动位置，我们可以观察1的移动轨迹。

于是我们模拟一下操作会发现， i = 2时， 此时1移动到了位置2 。接下来若想要让位置2发生交换，那么就必须找到一个最小的k，使得这个k所对应的d恰好是2 。 并且k尽可能地小。 于是我们想到了2的2倍4 。 下一步数值1便从位置2 移动到了位置4。接下来就是4的2倍即8， 数值1又从位置4移动到了位置8 。 这样循环往复，直到数值1移动到了 , 并且满足 。数值1便无法移动，此时就是他的最终位置。

代码

找到小于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
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
	int n;
	cin>>n;
	int ans = 1;
	for(int j = 1;j<=40;j++){ //枚举2的j次方
		if(ans*2>n){cout<<ans<<'\n';return ;}
		ans *= 2;
	}
}
signed main(){
	int T = 1;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

B. Binary Path

题意

有一个的 地图，一个蚂蚱从undefined1，1)(2,n)$ 。每次可以**向右或者向下走** ，蚂蚱走到终点后，会形成一个路径，问这个路径的字典序最小情况是什么， 以及有多少种走法可以出现这种最小字典序的路径。

思路

刚开始看错题了呜呜呜

为了使字典序最小，我们可以总结出如下几个策略：

  • 如果右边的数和下边的数 ， 一个是0，而另一个是1，那么走0那个方向一定字典序更小。

  • 如果右边的数和下边的数相等， 那么走右边方向，因为一旦向下走到第二行走便不能回第一行，而在第一行则可以随时转去第二行。

如果很难理解策略2，可以尝试理解一下这个例子：

000111
011111

当位于起点时，右边和下边都是0 ，但此时若向下走，则之后只能向右走而导致最终路径为0011111 ，若向右走则是0001111 。

于是我们便得出了最优解的路线，再考虑这种方案数：

我们可以发现只有当已经走到了第n列，或者下方为0并且右方为1时， 会选择向下走。那么我们假设在 时选择了向下走。

那么多种方案的出现仅有可能是由于可以提前选择向下走(在时选择了向下走)，并且路径完全相同。

于是每当 便可以选择提前一格向下走，从而增多一种方案。于是总的方案数变为了: 对于 , 都有，而尽可能小来使得的可取数量尽可能多 。即在p之前的一些连续格子中，有多少个格子满足 **右边和下边的数相等** 。

代码

在实现代码时，有一些可能会有帮助的小技巧。

  1. 我们使用作为当前所在的行，flag = 0表示当前位于第一行，flag = 1表示当前位于第二行。循环枚举从到表示列，于是求路径时便可以用 来得到。

  2. 我们可以通过比较 和 的大小关系来进行操作 。

    • 如果 则表示需要向下走，于是便可以设置flag = 1。 但我们发现当i = n时不论如何都要向下走，于是我们不妨提前将设置为2，表示无论 为何值，此时 都会成立，便选择了向下走。

      而向下走时，i并不会变化，但for循环会使得i每次都加1，于是我们可以使用 i-- 来抵消每次for循环产生的i++

    • 我们用表示已经出现几个右等于下 的格子了，如果 ，那么就让cnt++

    • 如果 ，那么我们就需要重置cnt为0 。

下面是完整核心代码（只有solve()部分，其他部分和A题相同 ，所以如果不知道rep是什么可以看A题中的define声明）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void solve(){
	int n;cin>>n;
	string a[2];
	cin>>a[0]>>a[1];
	a[0] = " " + a[0];a[0]+='2';
	a[1] = " " + a[1];
	string ans;
	int p = 1;
	int cnt;
	bool flag = 0;
	rep(i,1,n){
		ans+=a[flag][i];
		if(!flag){
			if(a[0][i+1]>a[1][i]){
				flag = 1;i--;
			}else if(a[0][i+1]<a[1][i]){
				cnt=0;
			}else cnt++;
		}
	}
	cout<<ans<<'\n';
	cout<<cnt+1<<'\n';
}

C. Bitwise Operation Wizard

题意

这是一个交互题，有一个长度为n的数组pundefinedp_1,p_2,…,p_n)(0,1,2,…,n-1)(a,b,c,d)p_a | p_bp_c | p_d<.=.>i,jp_i \oplus p_j\oplus$ 表示按位异或）

思路

我们考虑 最大为多少。 较容易得知 ，若n-1的二进制表示有k位。 那么最大值就是这k位全部为1。 即整个数组中的最大数**mx** ，与另一个数的异或。 接下来我们分别找这两个数。

为了找， 我们发现这个数就是在这位中，对的各位取反得到的数。 （如若 那么)

先找到最大值，我们发现可以令 这样裁判就会明确指出某两个数的大小关系。 于是我们可以这样子枚举整个数组，进行挨个儿比较。就可以用 次确定 **最大数** 所处的位置。

1
2
3
4
5
for(int i = 1;i<=n-1;i++){
    cout<<"? "<<mx<<' '<<mx<<' '<<i<<' '<<i<<endl;
    char ch;cin>>ch;
    if(ch == '<') mx = i;
}

之后我们找所有的满足 为最大（即k位全是1） 的数的集合。 他们一定满足了对于上数位为的位置，的那个位置一定为 。

我们使用vec来记录数据，每当遇到更大的 就清空vec并放入 ,如果遇到了相等的数，就继续向vec中装入。

这样就可以在n次询问下得到所有的满足对于mx上数位为0的位置，num的那个位置一定为1 的数，那么我们为了发现，在中数位为1的位置上，num必须是0才能保证二者异或得到1。 也就是说要在vec中找到0最多的那个数，也就是最小的那个数。

于是我们可以在次询问下，得到vec中最小的数mn。

于是num就是mn，我们的最终答案就是 mn和mx。

代码

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
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
	int n;
	cin>>n;
	int mx = 0;
	for(int i = 1;i<n;i++){
		cout<<"? "<<mx<<' '<<mx<<' '<<i<<' '<<i<<endl;
		char ch;
		cin>>ch;
		if(ch == '<') mx = i; 
	}
	int p = 0;
	vector<int> vec;
	for(int i = 0;i<n;i++){
		cout<<"? "<<mx<<' '<<p<<' '<<mx<<' '<<i<<endl;
		char ch;
		cin>>ch;
		if(ch == '<') {vec.clear();p = i;vec.push_back(i);}
		if(ch == '=') {vec.push_back(i);}
	}
	int mn = 0;
	mn = vec[0];
	for(auto t : vec){
		cout<<"? "<<mn<<' '<<mn<<' '<<t<<' '<<t<<endl;
		char ch;
		cin>>ch;
		if(ch == '>') {mn = t;}
	}
	cout<<"! "<<mn<<' '<<mx<<endl;
}
signed main(){
	int T = 1;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

D