//在我对着D题发呆的时候，柴神秒掉了D题并说：这个D感觉比C题简单呀！，，我：[哭.jpg]（逃
Codeforces Round #435 (Div. 2)
codeforces 862 A. Mahmoud and Ehab and the MEX【水】
题意：定义一个集合的MEX为其中的最小的不在集合里的非负整数，现在给一个大小为N的集合和X，每次操作可以向其中加入一个非负整数或删除一个数，问最小的操作次数，使得这个集合的MEX为X。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[];
int main() {
int n, x, i, j, ans = , cnt = ;
scanf("%d %d", &n, &x);
for(i = ; i <= n; ++i) {
scanf("%d", &a[i]);
if(a[i] < x) cnt++;
else if(a[i] == x) ans++;
}
ans += x - cnt;
printf("%d\n", ans);
return ;
}
15ms
codeforces 862 B. Mahmoud and Ehab and the bipartiteness【dfs】
题意：给一棵n个结点的树，问最多能加多少边使得其是二分图并且不能有重边和自环。
题解：dfs染色算出可匹配最多数，将其减去n-1即为答案。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>g[];
int a[];
void dfs(int x, int fa, int t) {
a[t]++;
int len = g[x].size();
for(int i = ; i < len; ++i)
if(g[x][i] != fa) dfs(g[x][i], x, t^);
}
int main() {
int n, u, v, i;
scanf("%d", &n);
for(i = ; i <= n; ++i) g[i].clear();
a[] = a[] = ;
for(i = ; i<n-; ++i) {
scanf("%d%d", &u, &v);
g[u].push_back(v); g[v].push_back(u);
}
dfs(, , );
long long ans = 1ll*a[]*a[] - (n-);
printf("%lld\n", ans);
return ;
}
78ms
codeforces 862 C. Mahmoud and Ehab and the xor【构造】
题意：要构造n（≤10^5）个不同的非负整数（每个数≤10^6），使得它们异或和为x（≤10^5）。
题解：考察异或的自反性。注意观察数据范围，用特殊数据完成构造。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std; int main() {
int n, x, i;
scanf("%d%d", &n, &x);
if(n==) printf("YES\n%d\n", x);
else if(n == ) {if(!x) puts("NO");else printf("YES\n0 %d\n", x);}
else {
printf("YES\n");
for(i = ; i < n-; ++i) {printf("%d ", i); x ^= i;}
printf("%d %d %d\n", (<<), (<<), (<<)^(<<)^x);
}
return ;
}
31ms
待补。。= _ =
codeforces 862 D. Mahmoud and Ehab and the binary string【二分】
题意：已知一个01字符串的长度n (2 ≤ n ≤ 1000)（保证字符串至少包含一个0和一个1），现在你可以进行若干次询问（不超过15次），每次询问输出一个字符串，对应的输入给出了原字符串和你询问字符串的汉明距离（汉明距离：两个字符串对应位置的不同字符的个数），最后再输出原字符串任意一个0和一个1的位置。
题解：二分区间判断。利用两组询问的差值，看一个区间里有没有0或1。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = ;
char s[N], t[N];
int main() {
int n, i, d1, d2, l, r;
scanf("%d", &n);
for (i = ; i < n; i++) s[i] = '';
printf("? %s\n", s); fflush(stdout);
int p0 = , p1 = ;
l = , r = n - ;
scanf("%d", &d1);
while (l <= r) {
int m = (l + r) >> ;
strcpy(t, s);
for(i = l; i <= m; i++) t[i] = '';
printf("? %s\n", t); fflush(stdout);
scanf("%d", &d2);
if ((d2-d1) == (m-l+)) {
p0 = m; l = m + ; //printf("p0=%d\n",p0);
continue;
}
if ((d1-d2) == (m-l+)) {
p1 = m; l = m + ; //printf("p1=%d\n",p1);
continue;
}
r = m;
}
printf("! %d %d\n", p0+, p1+); fflush(stdout);
return ;
}
15ms