abc改版后的第一场。貌似人很多啊...

最后10min交上了F。就是到结束他还没测完...

改完后质量明显提高了。相当于abc和arc的合场？（不过EF题没有之前的arc题那么难）

比赛地址

A

按题意模拟即可。

#include <bits/stdc++.h>
using namespace std;

int n, k;
char s[1000];

int main() {
    cin >> n >> k;
    scanf("%s", s + 1);
    s[k] = s[k] - 'A' + 'a';
    puts(s + 1);
}

B

按题意模拟即可。

然而有点奇奇怪怪的坑点（我也不知道为什么我写挂了2发）

#include <bits/stdc++.h>
using namespace std;
char s[10];
int main() {
    cin >> s;
    for (int i = 0; i < 4; ++i) s[i] -= '0';
    int a = s[0] * 10 + s[1];
    int b = s[2] * 10 + s[3];
    if (1 <= a && a <= 12) {
        if(1 <= b && b <= 12) puts("AMBIGUOUS");
        else puts("MMYY");
    } else {
        if(1 <= b && b <= 12) puts("YYMM");
        else puts("NA");
    }
    return 0;
}

C

一开始一直没看懂题意...写完E再来写的C。而且精度好像有点卡...

发现\(n\)不大，可以枚举初始的数字。分析一下（并仔细研究题意）每个数的概率其实就是\(\frac{1}{n}\times (\frac{1}{2})^{\log_2 (\frac{k}{i})}\)

累加即可。

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, m;
double ans = 0, power[N];

int main() {
    cin >> n >> m;
    double tmp = 0.5;
    for(int i = 1; i <= 100000; ++i) {
        power[i] = tmp;
        tmp /= 2.0;
    }
    for(int i = 1; i <= n; ++i) {
        int cnt = 0, now = i;
        while(now < m) now *= 2, ++cnt;
        if(!cnt) ans += 1.0 / n;
        else ans += 1.0 / n * power[cnt];
    }
    printf("%.12lf\n", ans);
}

D

答案显然一定存在。那么我们只需要挨个涂色就好了...

只要连接的边是奇数就是异色，是偶数就是同色。

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
#define ll long long

struct edge {
    int to, nxt;
    ll v;
}e[N<<1];
int head[N], cnt, n;

void ins(int u, int v, ll w) {
    e[++cnt] = (edge) {v, head[u], w};
    head[u] = cnt;
}

int ans[N];

void dfs(int u, int fa) {
    for(int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if(v == fa) continue;
        if(e[i].v % 2) ans[v] = ans[u] ^ 1;
        else ans[v] = ans[u];
        dfs(v, u);
    }
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i < n; ++i) {
        int u, v; ll w;
        scanf("%d%d%lld", &u, &v, &w);
        ins(u, v, w); ins(v, u, w);
    }
    dfs(1, 0);
    for(int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
}

E

因为\(a_i\)只有\(0\)和\(1\)，所以题目给的关系相当于只要你知道一个就可以知道另外一个。

所以给题目中的\(u\)和\(v\)连一条边权为\(0\)的边，然后建个虚点，向每个点连\(1\)的边，跑最小生成树就能得到答案了。

赛后发现别人写的并查集贼短...

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;

int n, m, f[N];

struct edge {
    int u, v, w;
}e[N << 1];

int find(int x) {
    if(f[x] == x) return x;
    return f[x] = find(f[x]);
}

bool cmp(edge a, edge b) {
    return a.w < b.w;
}

int main() {
    scanf("%d%d", &n, &m);
    int cnt = 0;
    for(int i = 1; i <= m; ++i) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        e[++cnt] = (edge) {a, b, 0};
    }
    for(int i = 1; i <= n; ++i) {
        e[++cnt] = (edge) {n + 1, i, 1};
    }
    ++n;
    for(int i = 1; i <= n; ++i) f[i] = i;
    int ans = 0;
    sort(e + 1, e + cnt + 1, cmp);
    for(int i = 1; i <= cnt; ++i) {
        int x = find(e[i].u), y = find(e[i].v);
        if(x != y) {
            ans += e[i].w;
            f[y] = x;
        }
    }
    printf("%d\n", ans);
}

F

挺好玩的构造题...

因为是两个相同的数之间的数的\(xor\)和，那么其实只要第一个放\(k\)，然后顺序放\(0\)到\(2^{m-1}\)，再放个\(k\)，倒序放\(2^{m-1}\)到\(0\)即可。（这样每一段都可以抵消掉就剩下一个\(k\)）

影响存在性的就是除了\(k\)以外的所有数\(xor\)和是否为\(0\).（因为第一个\(k\)和第二个之间是没有另外的\(k\)的）

#include <bits/stdc++.h>
using namespace std;

int m, k;

int main() {
    cin >> m >> k;
    int sum = 0;
    for(int i = 0; i < (1 << m); ++i) if(i != k) sum ^= i;
    if(!k) {
        for(int i = 0; i < (1 << m); ++i) printf("%d %d ", i, i);
        puts("");
        return 0;
    }
    if(m == 1) {
        if(k >= 1) puts("-1");
        else puts("0 0 1 1");
        return 0;
    }
    if((1 << m) <= k) return puts("-1"), 0;
    printf("%d ", k);
    for(int i = 0; i < (1 << m); ++i) if(i != k) printf("%d ", i);
    printf("%d ", k);
    for(int i = (1 << m) - 1; i >= 0; --i) if(i != k) printf("%d ", i);
}