A
签到题
int main() {
IOS; int cas = 0;
for (cin >> _; _; --_) {
ll n, m; cin >> n >> m;
ll x = n * (n - 1), y = (m + n) * (m + n - 1), z = __gcd(x, y);
cout << "Case #" << ++cas << ": " << x / z << '/' << y / z << '
';
}
return 0;
}
E
铜牌题(大概?)
我个sb, 分数线离散化的时候没向下严格取整, wa的人没了
贪心, 首先先找到, 可以充当最高分的区间,
明显是 将 成绩按照 a 从高到低排序,
再用最高的 b 分即 (b_{max}), 去找到第一个 小于 (b_{max}) 的 (a_j)
则从 (a_1 ~ a_{j + 1}) 和 (b_{max}) 是可以当最高分的, 其他都不行
然后 最好想的就是 从 (a_1) 到 (a_{j+1}) 和 (b_{max}) O(n)的线性扫描, 统计最大值的答案
怎么统计呢有多少个人比当前分数线高呢? 还要保证统计个数的复杂度不超过 log (你线性扫描最高分 n)
(顺便说一句怎么扫, 扫 (a_i * p), 之后要记得把 i 的分从 (a_i) 改成 (b_i), 保证(a_{i+ 1}) 分数最高)
提供两种, 1是差分 2是树状数组
由于 a, b范围都是 1e9, 明显要离散化, 所以复杂度上限就是 nlogn
int c[N << 2], SIZ;
pair<PLL, PLL> a[N];
void add(int x, int k) {
for (; x <= SIZ; x += -x & x) c[x] += k;
}
int ask(int x) {
int ans = 0;
for (; x; x -= -x & x) ans += c[x];
return ans;
}
int main() {
IOS; int cas = 0;
for (cin >> _; _; --_) {
ll p; cin >> n >> p; vector<ll> s;
rep (i, 1, n) {
cin >> a[i].fi.fi >> a[i].fi.se;
a[i].se.fi = (a[i].fi.fi * p - 1) / 100;
a[i].se.se = (a[i].fi.se * p - 1) / 100;
s.pb(a[i].fi.fi); s.pb(a[i].fi.se);
s.pb(a[i].se.fi); s.pb(a[i].se.se);
}
sort(all(s)); s.erase(unique(all(s)), s.end());
SIZ = s.size();
rep (i, 1, SIZ) c[i] = 0;
rep (i, 1, n) {
a[i].fi.fi = lower_bound(all(s), a[i].fi.fi) - s.begin() + 1;
a[i].fi.se = lower_bound(all(s), a[i].fi.se) - s.begin() + 1;
a[i].se.fi = lower_bound(all(s), a[i].se.fi) - s.begin() + 1;
a[i].se.se = lower_bound(all(s), a[i].se.se) - s.begin() + 1;
add(a[i].fi.fi, 1);
}
sort(a + 1, a + 1 + n);
int ans = 0; ll mx = 0, w;
per (i, n, 1) {
umax(ans, n - ask(a[i].se.fi));
add(a[i].fi.fi, -1); add(a[i].fi.se, 1);
if (a[i].fi.se > mx) w = a[i].se.se, mx = a[i].fi.se;
if (mx >= a[i - 1].fi.fi) {
umax(ans, n - ask(w));
break;
}
}
cout << "Case #" << ++cas << ": " << ans << '
';
}
return 0;
}
F
铜牌题
明显是存在环才能有正贡献, 直接考虑每个连通图就完事, 并查集够了
int n, m, _, k;
int f[N], siz[N], h[N];
int find(int x) {
return x == f[x] ? x : f[x] = find(f[x]);
}
void unit(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
f[y] = x; siz[x] += siz[y]; h[x] += h[y];
}
int main() {
IOS; int cas = 0;
for (cin >> _; _; --_) {
cin >> n >> m;
rep (i, 1, n) f[i] = i, h[i] = 1, siz[i] = 0;
rep (i, 1, m) {
int u, v; cin >> u >> v;
++siz[find(v)]; unit(u, v);
}
ll ans = 0;
rep (i, 1, n) if (i == f[i]) ans += max(0, siz[i] - h[i]);
cout << "Case #" << ++cas << ": " << ans << '
';
}
return 0;
}
G
铜牌题
明显分块好吧,(这么大的数据, 就是开根号分块)
首先要知道一个数无限开根号就成1了, 所以 当 k == 1 或者 无限开根号时(即(n^{frac{1}{k}} == 1)) 直接答案 n
然后分块就行
ll qpow(ll a, ll b) {
ll ans = 1;
for (; b; b >>= 1, a = a * a)
if (b & 1) ans = ans * a;
return ans;
}
int main() {
IOS; int cas = 0;
for (cin >> _; _; --_) {
ll n, m, k; cin >> n >> m; k = pow(n, 1.0 / m);
cout << "Case #" << ++cas << ": ";
if (m == 1 || k == 1) { cout << n << '
'; continue; }
ll ans = 0;
per (i, k, 1) {
ll l = qpow(i, m) - 1, r = min(qpow(i + 1, m) - 1, n);
ans += r / i - l / i;
}
cout << ans << '
';
}
return 0;
}
K
铜++?
还是贪心, 这几题没啥数据结构, 就是思维
对于任何一个点, 其军队来源无非是 1 或者其他节点
什么情况下来源是其他节点呢?
当然是, 已经有军队的节点, 且其最大深度 dis[i] - dep[x] <= dep[x], x是父节点, dep 是深度
代表什么意思?
对于一个父节点, 其所有的子节点且 dis[i] - dep[x] <= dep[x] 都可以用一支从父节点来的军队遍历完,
这支军队要么最后停在 dis[i] - dep[x] > dep[x] 的节点(显然), 要么要听停在一个 dis[i] - dep[x] <= dep[x] 的节点
废话!!!
但是对于前者是肯定不会 在返回 x 的父节点去 x 的兄弟了, 当时后者可能会
然后 对于所有的 dis[i] - dep[x] <= dep[x] 节点, 节省的路费也是不同的, 显然是从 (dis[i] < dis[j]) x -> i -> x -> j 更划算
所以我们要对子节点排序, 从最浅到最深, 遇到dis[i] - dep[x] > dep[x] 节点, 直接在从 1 派一支军队
答案就有了
vector<VI> e;
int dep[N], dis[N];
ll ans;
bool cmp(int x, int y) {
return dis[x] < dis[y];
}
void dfs(int x, int fa) {
dis[x] = 0;
for (auto &y : e[x]) {
dep[y] = dep[x] + 1; dfs(y, x);
dis[x] = max(dis[x], dis[y] + 1);
}
sort(all(e[x]), cmp);
}
int dfs0(int x, int ls) {
if (e[x].empty()) { ans += ls; return 1; }
for (auto& y : e[x]) ls = min(dep[x], dfs0(y, ls + 1));
return ls + 1;
}
int main() {
IOS; int cas = 0;
for (cin >> _; _; --_) {
cin >> n; ans = 0; vector<VI>(n + 1, VI()).swap(e);
rep(i, 2, n) cin >> m, e[m].pb(i);
dfs(1, 0); dfs0(1, 0);
cout << "Case #" << ++cas << ": " << ans << '
';
}
return 0;
}