题目分析
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;
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;
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;
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题的随机化暴力。
