奇观 55pts
赛时打的 $ \Theta(n^5) $ 和 $ m = 0 $ 的特殊性质拿了55pts；
考虑正解，首先，$ CCF $ 这三个字母是可以分开维护的；
对于 $ C $，其可以看作一个连了四个点的线段，对于 $ F $，其可以看作一个连了三个点的线段在再最后分别多连两个点；
设 $ f_{i, j} $ 表示维护一个连了 $ i $ 个点的线段，最后一个点为 $ j $ 时的方案数，有转移：
\[ f_{i, j} = \sum_{k \ is \ connected \ to \ i}^{k \leq n} f_{i - 1, k} \]这东西可以前缀和维护，然后我们只需维护到 $ i = 4 $ 即可；
最后 $ C $ 直接算，对于 $ F $ 枚举最后一位的数 $ j $，答案即为 $ \sum_{j = 1}^{n} f_{3, j} \times (d_j) ^ 2 $，其中 $ d_j $ 为能与 $ j $ 相连的点数；
点击查看代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long
const long long mod = 998244353;
int n, m;
long long f[5][100005], g[5][100005];
vector<int> v[100005];
main() {
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
int x, y;
for (int i = 1; i <= m; i++) {
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
v[i].push_back(0);
v[i].push_back(i);
v[i].push_back(n + 1);
sort(v[i].begin(), v[i].end());
v[i].erase(unique(v[i].begin(), v[i].end()), v[i].end());
}
for (int i = 1; i <= n; i++) {
f[1][i] = 1;
g[1][i] = g[1][i - 1] + 1;
}
for (int i = 2; i <= 4; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k < v[j].size(); k++) {
f[i][j] += (g[i - 1][v[j][k] - 1] - g[i - 1][v[j][k - 1]] + mod) % mod;
f[i][j] = (f[i][j] + mod) % mod;
}
}
for (int j = 1; j <= n; j++) {
g[i][j] = g[i][j - 1] + f[i][j];
g[i][j] = (g[i][j] + mod) % mod;
}
}
long long ans = g[4][n] * g[4][n] % mod;
long long sum = 0;
for (int i = 1; i <= n; i++) {
long long su = v[i].size() - 2;
su = n - su;
sum = (sum + f[3][i] * su % mod * su % mod + mod) % mod;
}
ans = ans * sum % mod;
cout << ans;
return 0;
}
铁路 60pts
赛时说不清的乱搞；
其实并不需要真的加点，只需要用并查集维护一下哪些点是被删掉的，然后把这个连通块连到这个新点即可；
好吧，其实原题解写的就这么简洁，所以我也不想写了
点击查看代码
#include <iostream>
#include <cstdio>
using namespace std;
int n, m;
struct sss{
int t, ne;
}e[2000005];
int h[2000005], cnt;
void add(int u, int v) {
e[++cnt].t = v;
e[cnt].ne = h[u];
h[u] = cnt;
}
int f[500005][25];
int fa[1000005], dep[1000005];
int id[1000005];
int find(int x) {
if (x != fa[x]) fa[x] = find(fa[x]);
return fa[x];
}
void dfs(int x, int faa) {
f[x][0] = faa;
dep[x] = dep[faa] + 1;
for (int i = h[x]; i; i = e[i].ne) {
int u = e[i].t;
if (u == faa) continue;
dfs(u, x);
}
}
int ans;
int lca(int x, int y) {
if (x == y) return x;
if (dep[x] < dep[y]) swap(x, y);
for (int i = 20; i >= 0; i--) {
if (dep[f[x][i]] >= dep[y]) x = f[x][i];
}
if (x == y) return x;
for (int i = 20; i >= 0; i--) {
if (f[x][i] != f[y][i]) {
x = f[x][i];
y = f[y][i];
}
}
return f[x][0];
}
void w(int x, int y, int now) {
int sum = 0;
x = id[x];
y = id[y];
int lc = find(lca(x, y));
id[now] = lc;
while(find(x) != lc) {
fa[find(x)] = lc;
x = find(f[x][0]);
sum++;
}
while(find(y) != lc) {
fa[find(y)] = lc;
y = find(f[y][0]);
sum++;
}
ans -= sum;
}
int main() {
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
int x, y;
for (int i = 1; i <= n - 1; i++) {
cin >> x >> y;
add(x, y);
add(y, x);
}
for (int i = 1; i <= n + m; i++) {
fa[i] = i;
id[i] = i;
}
dfs(1, 0);
for (int j = 1; j <= 20; j++) {
for (int i = 1; i <= n; i++) {
f[i][j] = f[f[i][j - 1]][j - 1];
}
}
ans = n;
for (int i = 1; i <= m; i++) {
cin >> x >> y;
w(x, y, n + i);
cout << ans << '\n';
}
return 0;
}
To be continued...
标签：赛记,fa,int,sum,find,dep,include,csp,模拟 From： https://www.cnblogs.com/PeppaEvenPig/p/18427844