int fa[N]; intfindset(int x){ return fa[x] == -1? x : fa[x] = findset(fa[x]); }
intsolve(){ int n, m; cin >> n >> m; fill(fa, fa + n + 1, -1); int cnt = 0; FOR (_, 0, m) { int u, v; scanf("%d%d", &u, &v); int fu = findset(u), fv = findset(v); if (fu != fv) { ++cnt; fa[fu] = fv; } } return2 * (n - 1) - cnt; }
intmain(){ #ifdef zerol freopen("in", "r", stdin); #endif int T; cin >> T; FOR (Ca, 1, T + 1) { printf("Case #%d: %d\n", Ca, solve()); } }
Code-Eat Switcher
判断点是否在凸包内。先不考虑把一个 time slot 分割的情况,肯定是按照某一方(比如 coding)的性价比排序,然后一侧全是 coding,另一侧全是 eating。每一个分界线的位置对应一个点,考虑所有点,把相邻的连起来,就是所有最优解构成的凸包。剩下的问题就是如何判断一个点是否在凸包内了,找出这个点 x 轴上附近的两个点(二分搜索),看是否在那两个点构成的直线的下方(叉积判正负)。
const LL p_max = 1E6 + 100; LL pr[p_max], p_sz; voidget_prime(){ staticbool vis[p_max]; FOR (i, 2, p_max) { if (!vis[i]) pr[p_sz++] = i; FOR (j, 0, p_sz) { if (pr[j] * i >= p_max) break; vis[pr[j] * i] = 1; if (i % pr[j] == 0) break; } } }
constint N = 1E5 + 100; bool f[N]; set<LL> S;
voidcount(LL L, LL R, LL multiplier = 1){ if (L > R) return; fill(f, f + R - L + 1, true); FOR (i, 0, p_sz) { LL p = pr[i]; if (p * p > R) break; FOR (j, max((L + p - 1) / p, 2LL), R / p + 1) { f[j * p - L] = false; } } FOR (i, L, R + 1) if (f[i - L]) S.insert(i * multiplier); }
voidsolve(){ S.clear(); LL L, R; cin >> L >> R; count(L, R); FOR (i, L, R + 1) if ((i & 3) == 2) S.insert(i); count((L + 3) / 4, R / 4, 4); if (L <= 4 && 4 <= R) S.insert(4); if (L <= 8 && 8 <= R) S.insert(8); dbg(S); cout << S.size() << endl; }
intmain(){ #ifdef zerol freopen("in", "r", stdin); #endif get_prime(); int T; cin >> T; FOR (Ca, 1, T + 1) { printf("Case #%d: ", Ca); solve(); } }
int n, S; cin >> n >> S; FOR (i, 0, n) { x.clear(); int k; scanf("%d", &k); FOR (_, 0, k) { int t; scanf("%d", &t); x.push_back(t); } sort(x.begin(), x.end()); FOR (j, 1, 1 << x.size()) { LL v = 0; FOR (k, 0, x.size()) if ((j >> k) & 1) v = v * 1001 + x[k]; ++mp[v]; if (j == (1 << x.size()) - 1) a.push_back(v); } } LL ans = 0; for (LL& v: a) ans += n - mp[v]; cout << ans << endl; }
intmain(){ #ifdef zerol freopen("in", "r", stdin); #endif int T; cin >> T; FOR (Ca, 1, T + 1) { printf("Case #%d: ", Ca); solve(); } }
constint N = 1E5 + 100; vector<int> a[N]; int c[N], d[N];
intmain(){ FOR (i, 1, N) for (int j = i; j < N; j += i) a[j].push_back(i); int T; cin >> T; FOR (Ca, 1, T + 1) { printf("Case #%d: ", Ca); int n, m, Q; cin >> n >> m >> Q; FOR (i, 0, m) scanf("%d", d + i); FOR (i, 0, m) for (int t: a[d[i]]) ++c[t]; LL ans = 0; FOR (_, 0, Q) { int x; scanf("%d", &x); ans += n / x - c[x]; } printf("%lld\n", ans); FOR (i, 0, m) for (int t: a[d[i]]) --c[t]; } }
constint N = 20 + 10; using VLL = vector<pair<LL, LL>>; VLL L, R; pair<LL, LL> a[N];
voidgo(const VLL& a, pair<LL, LL> s, VLL& ret, int k){ if (k == a.size()) { ret.push_back(s); return; } go(a, {s.first + a[k].first, s.second + a[k].second}, ret, k + 1); go(a, {s.first, s.second + a[k].second}, ret, k + 1); go(a, {s.first + a[k].first, s.second}, ret, k + 1); }
#include<ext/pb_ds/assoc_container.hpp> usingnamespace __gnu_pbds; using Tree = tree<pair<LL, int>, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>; Tree t;
intmain(){ #ifdef zerol freopen("in", "r", stdin); #endif int T; cin >> T; FOR (Ca, 1, T + 1) { printf("Case #%d: ", Ca); L.clear(); R.clear(); t.clear(); int n; LL H; cin >> n >> H; FOR (i, 0, n) scanf("%lld", &a[i].first); FOR (i, 0, n) scanf("%lld", &a[i].second); go(VLL(a, a + n / 2), {0, 0}, L, 0); go(VLL(a + n / 2, a + n), {0, 0}, R, 0); sort(L.begin(), L.end()); sort(R.begin(), R.end(), greater<>()); LL k = 0, ans = 0; int clk = 0; for (auto& x: L) { while (k < R.size() && R[k].first + x.first >= H) t.insert({R[k++].second, clk++}); ans += k - t.order_of_key({H - x.second, -1}); } cout << ans << endl; } }
Round H
H-Index
方法1:无脑模拟,相比起方法2代码复杂度高了一些,但是思维复杂度很低。需要有一个支持边插入边查询求第 K 大,或者求小于某个数的数量的数据结构。代码中使用了树状数组。
constint M = 1e5 + 100; namespace bit { LL c[M]; inlineintlowbit(int x){ return x & -x; } voidadd(int x, LL v){ for (int i = x; i < M; i += lowbit(i)) c[i] += v; } LL sum(int x){ LL ret = 0; for (int i = x; i > 0; i -= lowbit(i)) ret += c[i]; return ret; } }
voidsolve(){ int n; cin >> n; int h = 0; vector<int> history; FOR (i, 0, n) { int v; scanf("%d", &v); history.push_back(v); bit::add(v, 1); while (i + 1 - bit::sum(h) >= h + 1) h += 1; printf("%d ", h); } for (int& v: history) bit::add(v, -1); puts(""); }
intmain(){ #ifdef zerol freopen("in", "r", stdin); #endif int T; cin >> T; FOR (Ca, 1, T + 1) { printf("Case #%d: ", Ca); solve(); } }
intfix(int n, int x, int y){ int cnt = 0, sum = 0; while (x < n && y < n) { cnt += 1; sum += G[x][y]; ++x; ++y; } if (cnt == sum) return0; if (sum == 0) return1; return INF; }
voidflip(bool& f){ f = !f; }
intcheck(int n, int op1, int op2){ memcpy(G, GG, sizeof G); int ans = op1 + op2; FOR (i, 0, n) { if (op1) flip(G[i][i]); if (!G[i][i]) { ++ans; FOR (j, 0, i + i + 1) { flip(G[j][i + i - j]); } } } FOR (i, 0, n - 1) { if (op2) flip(G[i][i + 1]); if (!G[i][i + 1]) { ++ans; FOR (j, 0, i + i + 2) { flip(G[j][i + i + 1 - j]); } } } FOR (i, 0, n) ans += fix(n, i, 0) + fix(n, 0, i); return ans; }
voidsolve(){ int n; cin >> n; FOR (i, 0, n) { scanf("%s", s); FOR (j, 0, n) GG[i][j] = s[j] == '#'; } int ans = INF; FOR (op1, 0, 2) FOR (op2, 0, 2) ans = min(ans, check(n, op1, op2)); cout << ans << endl; }
intmain(){ #ifdef zerol freopen("in", "r", stdin); #endif int T; cin >> T; FOR (Ca, 1, T + 1) { printf("Case #%d: ", Ca); solve(); } }
constint N = 100 * 2 * 2 * 2 + 10; vector<int> G[N], rG[N], vs; int used[N], cmp[N];
voidadd_edge(int from, int to){ G[from].push_back(to); rG[to].push_back(from); }
voiddfs(int v){ used[v] = true; for (int u: G[v]) { if (!used[u]) dfs(u); } vs.push_back(v); }
voidrdfs(int v, int k){ used[v] = true; cmp[v] = k; for (int u: rG[v]) if (!used[u]) rdfs(u, k); }
intscc(int n){ memset(used, 0, sizeof(used)); vs.clear(); for (int v = 0; v < n; ++v) if (!used[v]) dfs(v); memset(used, 0, sizeof(used)); int k = 0; for (int i = (int) vs.size() - 1; i >= 0; --i) if (!used[vs[i]]) rdfs(vs[i], k++); return k; }
char s[N]; int ans[N * 8], cnt[N * 8]; voidsolve(){ int n; cin >> n; FOR (i, 0, n * 8) { G[i].clear(); rG[i].clear(); } // i, j // /: (i + j) * 2 ^ ? // \: (i - j + 3 * n) * 2 ^ ? FOR (i, 0, n) { scanf("%s", s); FOR (j, 0, n) { int u = (i + j) * 2, v = (i - j + 3 * n) * 2; if (s[j] == '#') { add_edge(u, v); add_edge(u ^ 1, v ^ 1); add_edge(v, u); add_edge(v ^ 1, u ^ 1); } else { add_edge(u, v ^ 1); add_edge(u ^ 1, v); add_edge(v, u ^ 1); add_edge(v ^ 1, u); } } } int k = scc(n * 8); dbg(k); memset(ans, 0, sizeof ans); memset(cnt, 0, sizeof cnt); FOR (i, 0, n * 8) if (i % 2 == 0) { if (G[i].empty()) continue; assert(cmp[i] != cmp[i ^ 1]); int kk = min(cmp[i], cmp[i ^ 1]); dbg(i, cmp[i], cmp[i + 1]); cnt[kk] += 1; ans[kk] += cmp[i] > cmp[i ^ 1]; } int res = 0; FOR (i, 0, k) { res += min(ans[i], cnt[i] - ans[i]); } cout << res << endl; }
intmain(){ #ifdef zerol freopen("in", "r", stdin); #endif int T; cin >> T; FOR (Ca, 1, T + 1) { printf("Case #%d: ", Ca); solve(); } }