「Codeforces Round 435 div2」本人的第二次cf酱油记 | Bill Yang's Blog
0%

「Codeforces Round 435 div2」本人的第二次cf酱油记

题目分析

A. Mahmoud and Ehab and the MEX

题目大意: 用最少的操作数让集合的mex等于$x$,操作有删除元素、添加非负元素。
题目分析: 随便Hash乱搞一下。

B. Mahmoud and Ehab and the bipartiteness

题目大意: 给出一棵树,在树上加边要求仍然是一个二分图,不构成自环或重边,最多加多少边。
题目分析: 不同颜色的点间都可以加边,二分图染个色乘起来解决。

C. Mahmoud and Ehab and the xor

题目大意: 给定整数$n$,$x$,求一个含有$n$个元素的集合,使得他们的异或和为$x$。
题目分析: 此题做法略多。构造题,首先只有2 0是无解。可以发现性质,只要从$i\%4==0$的数开始全部异或起来每隔四个就可以得到0。这样我们就可以将$n$的范围降到4以内。为了防止初步了解,我们放开最后4个,将$n$的范围降到6以内。然后强行构造就可以了。当然$i$要取一个极大值。也可以用随机化做。

D. Mahmoud and Ehab and the binary string

题目大意: 交互题,现在有一个01字符串,串长不超过1000,你可以猜这个字符串是多少,系统将返回你猜的串和真实的串的汉明距离。你可以最多提15次问,最后输出串中任意一个0和1的位置。
题目分析: 15次提问是一个明显的提示,可以发现$\lceil\log_210^3\rceil=10$,因此我们可以二分区间,首先我们任意找一个位置通过两次询问验证他是0还是1,接着对0和1分类讨论。若该位置是0,那么我们在$[1,n]$区间范围内不断地寻找1所在位置,将$Left$~$mid$全部置为1,若比全是0的汉明距离多了$mid-Left+1$说明这段中不含有1(Left=mid+1),否则说明这段中含有1(Right=mid),不断二分就可以得到答案。若开始位置是1也类似。

E读不懂咯

F不会做略


比赛经历

拿到A题用了一分钟读题,然后用了3分钟写程序提交1A。

A题代码(已通过final test)

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
int n,x,Hash[105],ans=0;
int main() {
n=Get_Int();
x=Get_Int();
for(int i=1; i<=n; i++) {
int y=Get_Int();
if(y<x)Hash[y]++;
if(y==x)ans++;
}
for(int i=0; i<x; i++)
if(!Hash[i])ans++;
printf("%d\n",ans);
return 0;
}

成功get 492分。
接下来看B题,稍作思考后开始打代码。最终用了7分钟完成程序提交1A。

B题代码(已通过final test)

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005;
int n,Color[maxn];
long long Hash[maxn];
vector<int>edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
void Dfs(int Now,int color) {
Color[Now]=color;
Hash[color]++;
for(int i=0; i<edges[Now].size(); i++) {
int Next=edges[Now][i];
if(Color[Next])continue;
Dfs(Next,3-color);
}
}
int main() {
n=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
AddEdge(y,x);
}
Dfs(1,1);
printf("%I64d\n",Hash[1]*Hash[2]-(n-1));
return 0;
}

成功get 956分。
接下来思考第三题,读懂题后开始思考构造方法。
开始我想的是按位构造,但是贪心似乎有点小问题,而且很难实现。
hyc想了一种迷之直接构造法,他发现了我们在题解中写到的性质,然后告诉了我们,开始写代码。
然后陷入了死亡调试,因为我们这样的构造细节很多,稍不注意就死掉了。
我大概写了1个小时绝望了,然后开始看D题,achen和hyc还在继续调C题。

D题首先读题就懵逼了,这是啥,看不懂?
通过优秀的翻译软件baidu,我初步确认这是一道交互题。
什么是交互题,只听过以前神犇学长liuguangzhe提到过,但从没做过题,所以也不清楚交互流程。大概看了看题吐槽了一下就放弃了。
就这样平平淡淡地过了两个小时,在比赛结束前5分钟achen成功调出来过了pretest,然后将他的程序发了出来,hyc根据achen的程序成功调出了自己的程序,在比赛结束前1分钟通过了pretest。而我死了。
在等待final test的时候我们发现achen和hyc的代码有巨大的漏洞,果然,他们成功fst翻车。

比赛结束后,achen成功发现了自己的两处错误,提交终于A了,这是他的代码。

C题代码 by achen

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<ctime>
using namespace std;
const int MAXN=100005;
int Ans[MAXN],cnt;
int main()
{
int n,x;
cin>>n>>x;
if(x==0&&n==2){cout<<"NO";return 0;}
cout<<"YES\n";
if(x==0)
{
if(n%4==0)
{
for(int i=1; i<=n; i++)cout<<100004+i-1<<' ';
}
if(n%4==1)
{
for(int i=1; i<=n-1; i++)cout<<100004+i-1<<' ';
cout<<0;
}
if(n%4==2)
{
for(int i=1; i<=n-6; i++)cout<<i-1<<' ';
cout<<(1<<19)+(1<<18)<<' '<<(1<<19)+(1<<17)<<' '<<(1<<19)+(1<<16)<<' '<<(1<<18)+(1<<16)<<' '<<(1<<19)<<' '<<(1<<17);
}
if(n%4==3)
{
for(int i=1; i<=n-3; i++)cout<<100004+i-1<<' ';
cout<<((1<<19)^1)<<' '<<((1<<19)^2)<<' '<<3;
}
return 0;
}
if(n%4==0)
{
for(int i=1; i<=n-4; i++)cout<<100004+i-1<<' ';
cout<<(x^(1<<19))<<' '<<((1<<19)^(1<<18))<<' '<<(1<<18)<<' '<<0;
}
if(n%4==1)
{
for(int i=1; i<=n-1; i++)cout<<100004+i-1<<' ';
cout<<x;
}
if(n%4==2)
{
for(int i=1; i<=n-2; i++)cout<<100004+i-1<<' ';
cout<<(x^(1<<19))<<' '<<(1<<19);
}
if(n%4==3)
{
for(int i=1; i<=n-3; i++)cout<<100004+i-1<<' ';
cout<<(x^(1<<19)^1)<<' '<<((1<<19)^1)<<' '<<0;
}

return 0;
}

是不是无比丑陋的代码啊。
然而我并不擅长分类讨论,所以我看了一下其他人AC的方法,有一种随机化的方法非常厉害,于是我就采用了。

C题代码 by Bill_Yang

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<ctime>
#include<set>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
set<int>ans;
int n,x;
bool Check(int n,int x) {
ans.clear();
mt19937 g(rand());
while(ans.size()<n-1)ans.insert(g()%1000001);
for(auto it=ans.begin(); it!=ans.end(); it++)x^=*it;
ans.insert(x);
return x<=1000000&&ans.size()==n;
}
int main() {
srand(time(NULL));
n=Get_Int();
x=Get_Int();
int cnt=0;
while(!Check(n,x)&&++cnt<100);
if(cnt==100) {
puts("NO");
return 0;
}
puts("YES");
for(auto it=ans.begin(); it!=ans.end(); it++)printf("%d ",*it);
return 0;
}

多么简洁,多么机智,多么优美。
mt19937是一种优秀的随机数生成器,比rand不知道高到哪里去了。

然后我就去睡了。
今天早上起来发现D题没有想象的那么难,了解了一下交互方式后将D题A掉了。

D题代码 by Bill_Yang

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
string s;
int n,pos0=-1,pos1=-1,First;
int Ask(string s) {
printf("? %s\n",s.c_str());
fflush(stdout);
return Get_Int();
}
int main() {
n=Get_Int();
int mid=(0+n-1)>>1;
for(int i=0; i<n; i++)s.push_back('0');
First=Ask(s);
s[mid]='1';
if(First>Ask(s))pos1=mid; //原来的距离大 此处为1
else pos0=mid;
s[mid]='0';
if(pos1==-1) {
int Left=0,Right=n-1;
while(Left<Right) {
int mid=(Left+Right)>>1,tmp=Left;
for(int i=Left; i<=mid; i++)s[i]='1';
if(Ask(s)<First+mid-Left+1)Right=mid; //找到1
else Left=mid+1;
for(int i=tmp; i<=mid; i++)s[i]='0'; //清空
}
pos1=Left;
} else {
s.clear();
for(int i=0; i<n; i++)s.push_back('1');
First=Ask(s);
int Left=0,Right=n-1;
while(Left<Right) {
int mid=(Left+Right)>>1,tmp=Left;
for(int i=Left; i<=mid; i++)s[i]='0';
if(Ask(s)<First+mid-Left+1)Right=mid; //找到0
else Left=mid+1;
for(int i=tmp; i<=mid; i++)s[i]='1'; //清空
}
pos0=Left;
}
printf("! %d %d\n",pos0+1,pos1+1);
fflush(stdout);
return 0;
}

这是我们最后的成绩:

第一次计算rate的比赛成功青名:

这次考试就这样结束了,我发现构造题我还是比较弱,因为平时这种题接触的比较少,构造题的限制相当宽,因此放开思维随便乱搞说不定就能A掉,就像C题的随机化暴力。

姥爷们赏瓶冰阔落吧~