首页 > 其他分享 >Codeforces Round 911 (Div. 2)

Codeforces Round 911 (Div. 2)

时间:2023-12-03 18:55:43浏览次数:35  
标签:tmp int tr Codeforces cin low fi Div 911

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;
}

标签:tmp,int,tr,Codeforces,cin,low,fi,Div,911
From: https://www.cnblogs.com/2aptx4869/p/17873546.html

相关文章

  • Codeforces Round 904 (Div. 2) C. Medium Design
    jly:开始的想法:首先枚举max的位置。包含它的一定是全加,剩下的一定都不加。然后求所有位置的最小值。初始全0,枚举max之后,因为是加区间,min一定在两端(最左或最右)。所以不需要枚举max,我们枚举min就好(因为加区间和初始全0,这个题的特殊性)。写法注意的点:下标从0开始,区间的左端点都-1,右端......
  • [Codeforces] CF1733C Parity Shuffle Sorting
    题面翻译给定一个长度为\(n\)的数组,你可以对它进行不超过\(n\)次操作。对于每次操作:选择两个下标\(l,r\),满足\(1\leql<r\leqn\);若\(a_l+a_r\)为奇数,将\(a_r\)赋值为\(a_l\),否则将\(a_l\)赋值为\(a_r\)。求一种方案,使得操作后的数组单调不减(即\(a_1\leq......
  • Codeforces Round 912 (Div. 2)
    A.HalloumiBoxes题意:长度为n的数组,你可以逆转最多k长度,问你能不能是数组递增思路:如果k>=2那么每个数都可以两两交换,如果下表1的地方是1就一定可以,k=1的话单独讨论usingnamespacestd;voidsolve(){ intn,k; cin>>n>>k; vector<int>a(n+1); for(inti=1;i<=n;i++){ ......
  • Codeforces Round 908 (Div. 2)
    总结T1题目大意:A,B两人玩游戏,游戏规则如下:整场游戏有多轮,每轮游戏先胜\(X\)局的人获胜,每场游戏先胜\(Y\)局的人获胜。你在场边观看了比赛,但是你忘记了\(x\)和\(y\),只记得总共比了\(1\len\le20\)局,和每局获胜的人,请判断谁获胜了。如果A获胜,输出A,如果B获胜,输......
  • CodeForces 1526F Median Queries
    洛谷传送门CF传送门首先,如果我们确定了\(1,2\)或\(n-1,n\)的位置,我们就能求出原排列。因为题目给了\(p_1<p_2\),所以可以不考虑对称性。也就是说我们知道两个位置是\(1,2\)或\(n-1,n\)但不确定究竟是\(1,2\)还是\(n-1,n\)也可以。然后,如果我们确定......
  • Codeforces Round 878 (Div. 3)
    CodeforcesRound878(Div.3)A:ABCA.CipherShifer题意:在自身后面添加一个字母,但是不能添加自身思路:找到第二个与自身相符的就再找#include<bits/stdc++.h>usingnamespacestd;constintMAX=110;chara[MAX];voidsolve(){intn;cin>>n;for(......
  • [Codeforces] CF1627B Not Sitting
    题意Rahul和Tina在玩一个游戏。游戏在一个\(n\timesm\)的网格图上进行,记第\(r\)行第\(c\)列上的格子为\((r,c)\)。定义\((a,b)\)与\((c,d)\)之间的距离为\(\left|a-c\right|+\left|b-d\right|\)。游戏开始后,Tina会选择恰好\(k\)个格子,并将其涂成粉红色。涂......
  • [Codeforces] CF1659B Bit Flipping
    题面给定一个长为\(n\)的01串,你可以进行\(k\)次操作。每次操作中,你可以选择任意一位,并将除了这一位以外的其它位翻转(\(1\)变\(0\),\(0\)变\(1\)),输出\(k\)次操作后能获得的字典序最大的字符串,并输出每一位在操作中被选择的次数。若有多解输出任意一解。思路可以发现......
  • [Codeforces] CF1675D Vertical Paths
    题目描述给定一棵由\(n\)个顶点组成的有根树。顶点由\(1\)到\(n\)编号。任何顶点都可以是树的根。请在树上找出这样一组路径:每个顶点恰好属于一条路径,每条路径可以包含一个或多个顶点;在每条路径中,每个节点的下一个节点是当前节点的子节点(即路径总是向下——从父节点......
  • Codeforces Round 912 (Div. 2) E - Geo Game
    考虑什么时候会改变答案的奇偶,显然可以根据\(x\oplusy\)的奇偶性分组,在组内进行跳跃不会改变,只有当组间跳跃的时候才会改变。打表观察先手什么时候必胜,其中:\(u\)是当前获胜目标为奇/偶(1/0),\(v\)是位于哪一组,\(a,b\)代表两组还剩多少,\(st\)代表当前答案的奇偶性。intdfs(intu,......