AtCoder Beginner Contest 199（Sponsored by Panasonic）

A - Square Inequality

int main() {
    IOS; cin >> n >> m >> k; n *= n, m *= m, k *= k;
    cout << (n + m < k ? "Yes\n" : "No\n");
    return 0;
}

B - Intersection

int main() {
    IOS; cin >> n; int mx = 0, mi = 1e9;
    rep (i, 1, n) cin >> m, umax(mx, m);
    rep (i, 1, n) cin >> m, umin(mi, m);
    cout << max(0, mi - mx + 1);
    return 0;
}

C - IPFL

string s, t;
 
int main() {
    IOS; cin >> n >> s;
    rep (i, 1, n) t += s.back(), s.pop_back(); reverse(all(t));
    for (cin >> m; m; --m) {
        int k, a, b; cin >> k >> a >> b;
        if (k == 2) swap(s, t);
        else {
             --a, --b;
            if (a < n && b < n) swap(s[a], s[b]);
            else if (a < n) swap(s[a], t[b - n]);
            else if (b < n) swap(t[a - n], s[b]);
            else swap(t[a - n], t[b - n]);
        }
    }
    cout << s << t;
    return 0;
}

D - RGB Coloring 2

暴力

int col[21], v[21][4];
VI h[21];
ll ans;

void dfs(int x) {
    if (x == n + 1) { ++ans; return; }
    if (h[x].empty()) { dfs(x + 1); return; }
    rep (i, 1, 3) if (!v[x][i]) {
        for (auto &y : h[x]) if (y > x && !v[y][i]) v[y][i] = x;
        dfs(x + 1);
        for (auto &y : h[x]) if (y > x && v[y][i] == x) v[y][i] = 0;
    }
}

int main() {
    IOS; cin >> n >> m;
    rep (i, 1, m) { int u, v; cin >> u >> v; h[u].pb(v); h[v].pb(u); }
    dfs(1); rep (i, 1, n) if (h[i].empty()) ans = ans * 3; cout << ans;
    return 0;
}

E - Permutation

状压dp

int a[19];
ll f[M];
vector<PII> q[19];

int main() {
    IOS; cin >> n >> m; f[0] = 1;
    rep (i, 1, m) cin >> k, q[k].pb(0, 0), cin >> q[k].back().se >> q[k].back().fi;
    rep (i, 1, n)  rep (j, 0, (1 << n) - 1) if (f[j]) {
        int c = 0;
        rep(k, 0, n - 1) if (j >> k & 1) ++c;
        if (c != i - 1) continue;
        rep (k, 0, n - 1) a[k + 1] = a[k] + (j >> k & 1);
        rep (k, 0, n - 1) if (!(j >> k & 1)) {
            bool flag = 1;
            for (auto& g : q[i]) if (a[g.se] + (k < g.se) > g.fi) flag = 0;
            if (flag) f[j ^ (1 << k)] += f[j];
        }
    }
    cout << f[(1 << n) - 1];
    return 0;
}