C++ 交互题

2022.02.06 cf

Codeforces Round

Posted by zhangmh on 2022-02-08
Estimated Reading Time 9 Minutes
Words 1.9k In Total
Viewed Times

这一场挺离谱的，，C题过题比B要多

A. Reverse and Concatenate

img

给出字符串s，rev(s)是s翻转所得，用s+rev(s)或者rev(s)+s替换s，求经过k次操作后可以得到几个不同的字符串。

思路：我们可以发现，若s为回文串，那怎样变化得到的都是一个回文串，不会因为rev(s)所放置的位置而改变字符串，所以s为回文串时，无论k是几，输出1；若s不是回文串，经过一次操作后得到的两个字符串必都是回文串，再操作同第一种情况，分类讨论即可。

tip：判断回文串可以判断s是否等于string(s.rbegin(),s.rend())

AC代码：

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
int t,n,k;
string s;

bool pan(string s)
{
	string c=s;
	reverse(s.begin(),s.end());
	if(c==s) return true;
	else return false;
}

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>n>>k;
    	cin>>s;
    	if(pan(s)) cout<<"1"<<'\n';
		else 
		{
			if(k==0) cout<<"1"<<'\n';
			else cout<<"2"<<'\n';
		}
	}
	return 0;
}

os：Div2的A题出题速度显然比Div3慢很多，，，要继续加油哇

B. Fortune Telling

img

有一个长度为n的数列a，初始Alice和Bob分别有一个数d和d+3，他们可以通过两种操作改变手中的数字，现给出最后的结果y，问这个y是由谁得到的。

思路： 首先发现Alice和Bob两人的数奇偶性不同，加法和异或两种运算对二进制最低位的影响是一样的，所以把所有数异或或者加起来，判断其奇偶性与y是否一致。

AC代码：

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
int t;
ll n,x,y; 

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>n>>x>>y;
    	ll a;
    	for(int i=1;i<=n;i++)
    	{
    		cin>>a;
    	    x^=a;
		}
    	if(x%2==y%2) cout<<"Alice"<<'\n';
    	else cout<<"Bob"<<'\n';
	}
	return 0;
}

C. OKEA

img

给出nk的矩阵，矩阵中是1~nk，问是否存在一种填数的方式，使得每一横行任意连续长度的平均数都是整数，存在输出"YES"并输出一种情况，不存在输出"NO"。

思路： 分情况讨论‘。首先当k=1时，即每一橫行都是一个数时，平均数必为整数；当n为偶数时，无论k是多少也是可以的，因为此时nk为偶数，1~nk奇数偶数数量相同，我们可以把奇偶数分开，按照从小到大填入n行中，奇数填在一行，偶数填在一行，这样每一行都是公差为2的等差数列，满足任意长度的平均数都是整数；而其他情况则无法凑出满足条件的情况。

AC代码：

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=505;
int t,a[N*N],b[N*N];
ll n,k;

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>n>>k;
    	if(n%2==0)
    	{
    		memset(a,0,sizeof(a));
    	    memset(b,0,sizeof(b));
    		cout<<"YES"<<'\n';
    		int cnt=0,tot=0;
    		for(int i=1;i<=n*k;i++)
    		{
    			if(i%2) a[++cnt]=i;
    			else b[++tot]=i;
			}
			for(int i=1;i<=cnt;i++)
			{
				if(i%k) cout<<a[i]<<' ';
				else cout<<a[i]<<'\n';
			}
			for(int i=1;i<=tot;i++)
			{
				if(i%k) cout<<b[i]<<' ';
				else cout<<b[i]<<'\n';
			}
		}
		else if(k==1)
		{
			cout<<"YES"<<'\n';
    		for(int i=1;i<=n;i++) 
			cout<<i<<'\n';
		}
		else cout<<"NO"<<'\n';
	}
	return 0;
}

D. Finding Zero

img

img

n个数中有1个是0， 可以询问a[i]，a[j]，a[k]三个数，可以得到三个数最大值减去最小值结果，问在最多n*2-2次询问中怎样得到0的位置。

思路：要求是可以询问三个数，那么我们以n为4举例说明：a，b，c，d四个数，假设a=0，且b<=c<=d,若询问a，b，c，得到的结果是c；若询问b，c，d，得到结果为d-b；若询问a，c，d，得到结果为d；若询问a，b，d，得到结果为d。可以看出四个数四次询问中最大值d出现了不止一次，那么可以确定四个数中最大值d和b，c，将b，c排除，0一定在a和d中。若是6个数，先对前四个数进行四次询问，排除两个，再对后四个进行四次询问，排除两个，输出0可能位于剩余两个数中，那么n为偶数的情况都是类似这样的，这样需要进行n2-4次询问，满足条件；再看n为奇数时，开始时按照偶数来做，到最后剩余一个数，我们可以从前面随便加一个数，使最后四次询问凑够四个数，这样需要2n-2次询问，满足题意。

tip：交互题，注意细节处理。

AC代码：

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
int t,n,ans[6];

int get(int x,int y,int z)
{
	printf("? %d %d %d\n",x,y,z);
	fflush(stdout);//交互题可以写一个get函数使代码美观
	int res;
	cin>>res;
	return res;
}

struct node
{
	int pos;//记录位置
    int v;//记录返回值
} e[6];

bool cmp(node a,node b)
{
	return a.v<b.v;
}

void cal()
{
	for(int i=1;i<=4;i++) e[i].pos=ans[i];
	e[4].v=get(ans[1],ans[2],ans[3]);//四种询问的返回值
	e[3].v=get(ans[1],ans[2],ans[4]);
	e[2].v=get(ans[1],ans[3],ans[4]);
	e[1].v=get(ans[2],ans[3],ans[4]);
	sort(e+1,e+5,cmp);//排序后最大的到后面，前两个就是剩余的数
	ans[1]=e[1].pos,ans[2]=e[2].pos;
}

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>n;
    	int it=2;//记录最后访问的位置
    	ans[1]=1,ans[2]=2;//ans[i]和ans[2]存的是最后剩余的两个数
    	while(it<n)
    	{
    		if(it+2<=n)//判断n为偶数的情况
    		{
    			ans[3]=it+1,ans[4]=it+2;
    			cal();
    			it+=2;
			}
			else if(it+1<=n)//判断n为奇数的情况
			{
				ans[3]=it+1;
				for(int i=1;i<=n;i++)//从前面找一个不等于现有三个数的值加进去凑成四个数
				{
					if(i!=ans[1]&&i!=ans[2]&&i!=ans[3])
					{
						ans[4]=i;
						break;
					}
				}
				cal();
				break;
			}
		}
		printf("! %d %d\n",ans[1],ans[2]);
	}
	return 0;
}

os：交互题耶，没见过的题型

听说这次比赛AlphaCode鸽了？出题组好可爱：P

img

If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !

FEATURED TAGS
C++ 交互题
FRIENDS
ESC