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