Codeforces Round 930 (Div. 2)

题目链接

A. Shuffle Party

题意

给出一个数组$a_1,a_2,…,a_n$ 起初$a_i = i$ ，之后定义$swap(k)$ 操作为 : 找到最大的，不等于$k$的因子$d$ ，交换$a_d$和 $a_k$ 。

下面令$i = 2,3,…,n$ ，依次进行$swap(i)$ ，问最终数值$1$会在哪个位置。

思路

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

于是我们模拟一下操作会发现， i = 2时， $swap(2)=swap(a_1,a_2)$ 此时1移动到了位置2 。接下来若想要让位置2发生交换，那么就必须找到一个最小的k，使得这个k所对应的d恰好是2 。 并且k尽可能地小。 于是我们想到了2的2倍4 。 下一步数值1便从位置2 移动到了位置4。接下来就是4的2倍即8， 数值1又从位置4移动到了位置8 。 这样循环往复，直到数值1移动到了$2^j$ , 并且满足$2^j \le n < 2^{j+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

题意

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

思路

刚开始看错题了呜呜呜

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

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

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

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

000111
011111

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

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

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

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

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

代码

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

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

  2. 我们可以通过比较 $a[0][i+1]$和$a[1][i]$ 的大小关系来进行操作 。

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

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

    • 我们用$cnt$表示已经出现几个右等于下 的格子了，如果$a[0][i+1] = a[1][i]$ ，那么就让cnt++

    • 如果$a[0][i+1] < a[1][i] $ ，那么我们就需要重置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的数组p$(p_1,p_2,…,p_n)$，他的n个元素分别为$(0,1,2,…,n-1)$ 排列顺序未知。每次询问你可以提供四个下标$(a,b,c,d)$ 裁判会回应你$p_a | p_b$和 $p_c | p_d$ 之间的大小关系（即$<.=.>$ ) 现在需要你在询问至多3*n次后， 得到一对下标$i,j$ ，满足 $p_i \oplus p_j$ 最大化。 （$\oplus$ 表示按位异或）

思路

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

为了找$num$， 我们发现这个数就是在这$k$位中，对$mx$的各位取反得到的数。 （如若$mx = 10100{(2)}$ 那么$num = 01011{(2)}$)

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

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;
}

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

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

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

于是我们可以在$vec.size() - 1$次询问下，得到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