AtCoder Beginner Contest 126

https://atcoder.jp/contests/abc126

A - Changing a Character

#include <bits/stdc++.h>

using namespace std;

int main () {
    int n, k;
    string s;
    cin >> n >> k >> s;
    s[k-1] = (char)(s[k-1] - 'A' + 'a');
    cout << s;
}

B - YYMM or MMYY

#include <bits/stdc++.h>

using namespace std;
set<string> month = {"01", "02", "03", "04", "05", "06", "07", "08", "09", "10", "11", "12"};

int main () {
    string s;
    cin >> s;
    bool ok1 = false, ok2 = false;
    string s1 = s.substr (0, 2), s2 = s.substr (2, 2);
    if (month.count (s1))   ok1 = true;
    if (month.count (s2))   ok2 = true;
    if (ok1 && ok2)     cout << "AMBIGUOUS";
    else if (ok1)       cout << "MMYY";
    else if (ok2)       cout << "YYMM";
    else                cout << "NA";
}

C - Dice and Coin

#include <bits/stdc++.h>

using namespace std;

int main () {
    int n, k;
    cin >> n >> k;
    double ans = max (0.0, 1.0 * (n - k + 1) / n);
    //cout << ans << endl;
    for (int i = 1; i < min (k, n + 1); i++) {
        double dx = 1.0 / n;
        for (int j = i; j < k; j *= 2)  dx *= 0.5;
        //cout << dx << ' ';
        ans += dx;
    }
    cout << fixed << setprecision (10) << ans;
}

D - Even Relation

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5, M = N * 2;
int h[N], e[M], ne[M], w[M], idx, n, ans[N];

void add (int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void dfs (int u, int fa) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa)    continue;
        if (w[i] & 1)   ans[j] = !ans[u];
        else    ans[j] = ans[u];
        dfs (j, u);
    }
}

int main () {
    memset (h, -1, sizeof h);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add (a, b, c), add (b, a, c);
    }
    dfs (1, -1);
    for (int i = 1; i <= n; i++)    cout << ans[i] << endl;
}
//嗯搜, 暴力改

E - 1 or 2

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
int fa[N], n, m, ans;

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

int main () {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)    fa[i] = i;
    while (m --) {
        int a, b, c;
        cin >> a >> b >> c;
        a = find (a), b = find (b);
        if (a != b)     fa[a] = b;
    }
    for (int i = 1; i <= n; i++) {
        if (fa[i] == i) ans ++;
    }
    cout << ans;
}

F - XOR Matching

#include <bits/stdc++.h>

using namespace std;

signed main () {
    int m, k;
    cin >> m >> k;

    if (k >= (1ll << m))    cout << -1; //凑不成两个
    else if (m == 1) {
        if (k)  cout << -1;
        else    cout << "0 0 1 1";
    }
    else {
        for (int i = 0; i < (1ll << m); i++) {
            if (i != k)     cout << i << ' ';
        }
        cout << k << ' ';
        for (int i = (1ll << m) - 1; i >= 0; i--) {
            if (i != k)     cout << i << ' ';
        }
        cout << k << endl;
    }
}

//小结论: 0到2^m-1的异或和为0 (证: 相邻四个一组)