连通块 66pts
老套路，删边改加边；
但改完以后不知道怎么求最长路径了，当时也想到了维护直径，但不知道咋干；
具体地，用并查集维护连通性，每次合并时需要维护新的直径，不难发现，新的直径的两个端点一定在原来的两个直径的四个端点中选；
于是只有六种情况，枚举一下即可；
我们要直径有啥用呢？当我们查询一个点在其连通块内的最长路径时，那个端点一定是直径的两个端点中的一个；
于是可以快速查询；
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m;
int s[200005], a[200005], ans[200005], dep[200005], x[200005], y[200005];
int fa[200005], f[200005][25];
bool vis[200005];
int find(int x) {
if (x != fa[x]) fa[x] = find(fa[x]);
return fa[x];
}
struct sss{
int t, ne;
}e[5000005];
int h[5000005], cnt;
inline void add(int u, int v) {
e[++cnt].t = v;
e[cnt].ne = h[u];
h[u] = cnt;
}
void dfs(int x, int fat) {
f[x][0] = fat;
dep[x] = dep[fat] + 1;
for (int i = h[x]; i; i = e[i].ne) {
int u = e[i].t;
if (u == fat) continue;
dfs(u, x);
}
}
int lca(int x, int y) {
if (x == y) return x;
if (dep[x] < dep[y]) swap(x, y);
for (int i = 19; i >= 0; i--) {
if (dep[f[x][i]] >= dep[y]) x = f[x][i];
}
if (x == y) return x;
for (int i = 19; i >= 0; i--) {
if (f[x][i] != f[y][i]) {
x = f[x][i];
y = f[y][i];
}
}
return f[x][0];
}
int ask_dis(int x, int y) {
return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}
pair<int, int> ma[200005];
struct sas{
int x, y, dis;
bool operator <(const sas &A) const {
return dis > A.dis;
}
}c[15];
inline void unionn(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
c[1] = {ma[x].first, ma[x].second, ask_dis(ma[x].first, ma[x].second)};
c[2] = {ma[x].first, ma[y].first, ask_dis(ma[x].first, ma[y].first)};
c[3] = {ma[x].first, ma[y].second, ask_dis(ma[x].first, ma[y].second)};
c[4] = {ma[x].second, ma[y].first, ask_dis(ma[x].second, ma[y].first)};
c[5] = {ma[x].second, ma[y].second, ask_dis(ma[x].second, ma[y].second)};
c[6] = {ma[y].first, ma[y].second, ask_dis(ma[y].first, ma[y].second)};
sort(c + 1, c + 1 + 7);
ma[x] = {c[1].x, c[1].y};
fa[y] = x;
}
int main() {
freopen("block.in", "r", stdin);
freopen("block.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n - 1; i++) {
cin >> x[i] >> y[i];
add(x[i], y[i]);
add(y[i], x[i]);
}
dfs(1, 0);
for (int j = 1; j <= 19; j++) {
for (int i = 1; i <= n; i++) {
f[i][j] = f[f[i][j - 1]][j - 1];
}
}
for (int i = 1; i <= n; i++) {
fa[i] = i;
ma[i] = {i, i};
}
for (int i = 1; i <= m; i++) {
cin >> s[i] >> a[i];
if (s[i] == 1) vis[a[i]] = true;
}
for (int i = 1; i <= n - 1; i++) {
if (!vis[i]) unionn(x[i], y[i]);
}
for (int i = m; i >= 1; i--) {
if (s[i] == 1) {
unionn(x[a[i]], y[a[i]]);
} else if (s[i] == 2) {
int x = find(a[i]);
ans[i] = max(ask_dis(ma[x].first, a[i]), ask_dis(ma[x].second, a[i]));
}
}
for (int i = 1; i <= m; i++) {
if (s[i] == 2) cout << ans[i] << '\n';
}
return 0;
}
军队 0pts
赛时几乎没看；
也是复习了一下扫描线；
看到矩形覆盖，很容易想到扫描线（但我忘了咋打了）；
用扫描线处理出满足要求的数的个数，发现我们要求的乘积，两项和为定值，那么用一下基本不等式即可知道当这两项相等时（即都为 $ m $ 的一半）乘积最大；
那么我们用数组存一下满足条件的数，最后判断一下即可；
点击查看代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
long long n, m, c, k, q;
struct sss{
long long l, r, val;
};
vector<sss> line[500005];
long long b[500005];
long long sum[500005], sum1[500005];
namespace seg{
inline long long ls(long long x) {
return x << 1;
}
inline long long rs(long long x) {
return x << 1 | 1;
}
struct sas{
long long l, r, sum, ma;
}tr[5000005];
inline void push_up(long long id) {
long long t = min(tr[ls(id)].sum, tr[rs(id)].sum);
tr[ls(id)].sum -= t;
tr[rs(id)].sum -= t;
tr[ls(id)].ma -= t;
tr[rs(id)].ma -= t;
tr[id].sum += t;
tr[id].ma = max(tr[ls(id)].ma, tr[rs(id)].ma) + tr[id].sum;
}
void bt(long long id, long long l, long long r) {
tr[id].l = l;
tr[id].r = r;
if (l == r) {
return;
}
long long mid = (l + r) >> 1;
bt(ls(id), l, mid);
bt(rs(id), mid + 1, r);
}
void add(long long id, long long l, long long r, long long d) {
if (tr[id].l >= l && tr[id].r <= r) {
tr[id].sum += d;
tr[id].ma += d;
return;
}
long long mid = (tr[id].l + tr[id].r) >> 1;
if (l <= mid) add(ls(id), l, r, d);
if (r > mid) add(rs(id), l, r, d);
push_up(id);
}
long long ask(long long id, long long now) {
now += tr[id].sum;
if (now >= k) return (tr[id].r - tr[id].l + 1);
if (tr[id].l == tr[id].r) return 0;
long long ans = 0;
if (now + tr[ls(id)].ma >= k) ans += ask(ls(id), now);
if (now + tr[rs(id)].ma >= k) ans += ask(rs(id), now);
return ans;
}
}
using namespace seg;
int main() {
freopen("army.in", "r", stdin);
freopen("army.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> c >> k >> q;
long long x1, y1, x2, y2;
for (long long i = 1; i <= c; i++) {
cin >> x1 >> y1 >> x2 >> y2;
line[x1].push_back({y1, y2, 1});
line[x2 + 1].push_back({y1, y2, -1});
}
bt(1, 1, m);
for (long long i = 1; i <= n; i++) {
for (long long j = 0; j < line[i].size(); j++) {
sss x = line[i][j];
add(1, x.l, x.r, x.val);
}
long long t = ask(1, 0);
b[i] = min(t, m - t);
}
sort(b + 1, b + 1 + n);
for (long long i = 1; i <= n; i++) {
sum1[i] = sum1[i - 1] + b[i] * b[i];
sum[i] = sum[i - 1] + b[i];
}
long long x, y;
for (long long i = 1; i <= q; i++) {
cin >> x >> y;
long long yy = y / 2;
long long pos = upper_bound(b + 1, b + 1 + n, yy) - b;
if (pos == n + 1) {
cout << (long long)(sum[n] - sum[n - x]) * y - (sum1[n] - sum1[n - x]) << '\n';
} else if (pos <= n - x + 1) {
cout << (long long)x * (yy * y - yy * yy) << '\n';
} else {
cout << (long long)(sum[pos - 1] - sum[n - x]) * y - (sum1[pos - 1] - sum1[n - x]) + (yy * y - yy * yy) * (n - pos + 1) << '\n';
}
}
return 0;
}
进击的巨人 100pts
这题赛时10min打的 $ \Theta(n^2) $ 暴力然后过了，而且还是首A；
正解当然不是暴力，而是要推式子；
不难发现，每个 $ 0 $ 会原序列分割成两个互不相同的子序列，且两部分互不影响，于是我们可以分开考虑；
对于一个不包含 $ 0 $ 的一个极大子序列，设其最左区间左端点下标为 $ la $，最右区间右端点下标为 $ ra $（注意这里区间和下标的区别），同时设 $ cnt_i $ 表示从 $ la $ 到 $ i $ 的 $ ? $ 总个数（$ la \leq i \leq ra $），则这一个序列的答案（期望）为：
\[ \sum_{l = la}^{ra} \sum_{r = la}^{l - 1} (r - l)^k \times \frac{1}{2^{cnt_r - cnt_l}} \]对其使用二项式定理($ (x + y)^k = \sum^{k}_{i = 0} C^i_k \ x^i \ y^{k - i} $)，可得：
\[ \sum_{l = la}^{ra} \sum_{r = la}^{l - 1} \sum_{i = 0}^{k} C^i_k \ (-l)^i \ r^{k - i} \times 2^{cnt_l} \times \frac{1}{2^{cnt_r}} \]可以把 $ k $ 提出来，将包含 $ l $ 的项放一起，包含 $ r $ 的项放一起，则：
\[ \sum^{k}_{i = 0} C^i_k \sum^{l = la}_{ra} (-l)^i \ 2^{cnt_l} \times (\sum^{l - 1}_{r = la} r^{k - i} \ \frac{1}{2^{cnt_r}}) \]注意到后面括号那一堆是可以使用前缀和求的，所以枚举 $ i $ 和 $ l $ 即可，时间复杂度 $ \Theta(nk) $；
当然，也可以将 $ l $ 与 $ r $ 互换位置；
点击查看代码
#include <iostream>
#include <cstdio>
using namespace std;
const long long mod = 998244353;
long long n, k;
char c[200005];
long long cnt[200005];
long long sum[200005];
long long ans;
long long ksm(long long a, long long b) {
long long ans = 1;
while(b) {
if (b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
long long inv[200005];
long long p[200005];
long long fac[200005], fav[200005];
long long C(long long n, long long m) {
if (m == 0) return 1;
if (m == n) return 1;
if (n == 0) return 0;
if (m > n) return 0;
return fac[n] * fav[m] % mod * fav[n - m] % mod;
}
long long Lucas(long long n, long long m) {
if (m == 0) return 1;
return Lucas(n / mod, m / mod) * C(n % mod, m % mod) % mod;
}
int main() {
freopen("attack.in", "r", stdin);
freopen("attack.out", "w", stdout);
scanf("%lld %lld", &n, &k);
scanf("%s", c + 1);
n++;
c[n] = '0';
p[0] = 1;
fac[0] = 1;
inv[0] = 1;
fav[0] = 1;
for (long long i = 1; i <= n; i++) {
p[i] = p[i - 1] * 2 % mod;
inv[i] = ksm(p[i], mod - 2);
fac[i] = fac[i - 1] * i % mod;
fav[i] = ksm(fac[i], mod - 2);
}
long long ls = 1;
for (long long i = 1; i <= n; i++) {
cnt[i] = cnt[i - 1];
if (c[i] == '?') cnt[i]++;
if (c[i] == '0') {
cnt[i] = 0;
for (long long j = 0; j <= k; j++) {
if (ls > 1) sum[ls - 2] = 0;
for (long long l = ls - 1; l <= i - 1; l++) {
sum[l] = (sum[l - 1] + ksm(-l, j) * p[cnt[l]] % mod) % mod;
}
long long su = 0;
for (long long r = ls - 1; r <= i - 1; r++) {
su = (su + ksm(r, k - j) * inv[cnt[r]] % mod * sum[r - 1] % mod) % mod;
}
ans = (ans + su * Lucas(k, j) % mod + mod) % mod;
}
ls = i + 1;
}
}
printf("%lld", ans);
return 0;
}