526互联

Codeforces Round 911 (Div. 2)

发布时间 2023-12-03 18:47:37作者: 洛绫璃

Codeforces Round 911 (Div. 2)

A - Cover in Water

int main() {
    IOS;
    for (cin >> _; _; --_) {
        cin >> n >> s + 1;
        int ans = 0;
        bool f = 0;
        for (int i = 1, j = 1; i <= n; i = ++j) if (s[i] == '.') {
            while (j + 1 <= n && s[j + 1] == '.') ++j;
            ans += j - i + 1;
            if (j - i + 1 >= 3) f = 1;
        }
        cout << (f ? 2 : ans) << '\n';
    }
    return 0;
}

B - Laura and Operations

int main() {
    IOS;
    for (cin >> _; _; --_) {
        int a, b, c; cin >> a >> b >> c;
        if (a == 0 && b == 0 && c != 0) cout << "0 ";
        else if (a == 0 && b != 0 && c == 0) cout << "0 ";
        else cout << (abs(b - c) & 1 ? "0 " : "1 ");
 
        if (a == 0 && b == 0 && c != 0) cout << "0 ";
        else if (a != 0 && b == 0 && c == 0) cout << "0 ";
        else cout << (abs(a - c) & 1 ? "0 " : "1 ");
 
        if (a != 0 && b == 0 && c == 0) cout << "0\n";
        else if (a == 0 && b != 0 && c == 0) cout << "0\n";
        else cout << (abs(b - a) & 1 ? "0\n" : "1\n");
    }
    return 0;
}

C - Anji's Binary Tree

const int N = 3e5 + 5;
 
int n, m, _, k, cas;
int tr[N][2], d[N];
char s[N];
 
void dfs(int x) {
    if (x == 0 || !d[x]) return;
    dfs(tr[x][0]);
    dfs(tr[x][1]);
    d[x] = min(d[tr[x][0]] + (s[x] != 'L'), d[tr[x][1]] + (s[x] != 'R'));
}
 
int main() {
    IOS; d[0] = 1e9;
    for (cin >> _; _; --_) {
        cin >> n >> s + 1;
        rep (i, 1, n) {
            cin >> tr[i][0] >> tr[i][1];
            d[i] = !tr[i][0] && !tr[i][1] ? 0 : 1e9;
        }
        dfs(1);
        cout << d[1] << '\n';
    }
    return 0;
}

D - Small GCD

容斥的时候，倒着来，先让更大的因子容斥完多余的计算，这样更容易处理

const int N = 1e5 + 5;

int n, m, _, k, cas;
int a[N], c[N];
ll b[N];
vector<int> fac[N];

int main() {
    IOS;
    for (int i = 1; i <= 1e5; ++i) for (int j = i; j <= 1e5; j += i) fac[j].pb(i);
    for (cin >> _; _; --_) {
        memset(c, 0, sizeof c); memset(b, 0, sizeof b);
        cin >> n;
        ll ans = 0;
        rep (i, 1, n) cin >> a[i];
        sort(a + 1, a + 1 + n);
        rep (i, 1, n - 1) for (int x : fac[a[i]]) b[x] += 1ll * (c[x]++) * (n - i);
        per (i, 5e4, 1) for (int j = i << 1; j <= 1e5; j += i) b[i] -= b[j];
        rep (i, 1, 1e5) ans += i * b[i];
        cout << ans << '\n';
    }
    return 0;
}

E - Transitive Graph

scc 缩点，dfs 算就好

const int N = 2e5 + 5, M = 2e5 + 5;
 
int n, m, _, k, cas;
int hc[N], toc[M], nec[M], totc;
int dfn[N], low[N], df, st[N], top;
int deg_in[N];
unordered_map<int, pair<int, ll>> used;
int c[N], scnt;
vector<pair<ll, VI>> scc;
bool inst[N];
int h[N], to[M], ne[M], tot;
int a[N];
 
void init(int n) {
    tot = 0;
    memset(h, 0, sizeof(int) * (n + 1));
}
 
void add(int u, int v) {
    ne[++tot] = h[u];
    to[h[u] = tot] = v;
}
 
void init_c(int n) {
    scnt = totc = top = df = 0;
    scc = vector<pair<ll, VI>>(1);
    used.clear();
    memset(dfn, 0, sizeof(int) * (n + 1));
    memset(low, 0, sizeof(int) * (n + 1));
    memset(hc, 0, sizeof(int) * (n + 1));
}
 
void add_c(int u, int v) {
    nec[++totc] = hc[u];
    toc[hc[u] = totc] = v;
}
 
void tarjan(int x) {
    dfn[x] = low[x] = ++df; inst[st[++top] = x] = 1;
    for (int i = h[x], y = to[i] ; i; y = to[i = ne[i]])
        if (!dfn[y]) tarjan(y), low[x] = min(low[x], low[y]);
        else if (inst[y]) low[x] = min(low[x], dfn[y]);
    if (low[x] == dfn[x]) {
        ++scnt; scc.pb(0ll, VI());
        for (int y = 0; y ^ x; y = st[top--])
            inst[st[top]] = 0, c[st[top]] = scnt,
            scc.back().se.pb(st[top]), scc.back().fi += a[st[top]];
    }
}
 
pair<int, ll> dfs(int x) {
    if (used.count(x)) return used[x];
    pair<int, ll> mx = {0, 0};
    for (int i = hc[x], y = toc[i]; i; y = toc[i = nec[i]]){
        pair<int, ll> tmp = dfs(y);
        if (tmp.fi > mx.fi) mx = tmp;
        else if (tmp.fi == mx.fi && tmp.se < mx.se) mx = tmp;
    }
    return used[x] = {scc[x].se.size() + mx.fi, scc[x].fi + mx.se};
}
 
int main() {
    IOS;
    for (cin >> _; _; --_) {
        cin >> n >> m; init(n); init_c(n);
        rep (i, 1, n) cin >> a[i];
        rep (i, 1, m) {
            int x, y; cin >> x >> y;
            add(x, y);
        }
        rep (i, 1, n) if (!dfn[i]) tarjan(i);
        memset(deg_in, 0, sizeof(int) * (scnt + 1));
        rep (i, 1, n) for (int k = h[i], y; k; k = ne[k]) {
            if (c[i] == c[y = to[k]]) continue;
            add_c(c[i], c[y]);
            ++deg_in[c[y]];
        }
        pair<int, ll> ans = {0, 0};
        rep (i, 1, scnt) if (!deg_in[i]) {
            pair<int, ll> tmp = dfs(i);
            if (tmp.fi > ans.fi) ans = tmp;
            else if (tmp.fi == ans.fi && tmp.se < ans.se) ans = tmp;
        }
        cout << ans.fi << ' ' << ans.se << '\n';
    }
    return 0;
}