分虽然好看但是还是有些失误。
A 越狱
给出一个字符串
一个显然的暴力是,考虑已经确定了
这个东西可以用个数据结构维护一下。复杂度是
感谢 yijan 学长教我
假设
不过还是有可能因为
贴个 yijan 的代码吧。
void solve( ) {
cin >> n >> k;
scanf("%s",ch + 1);
rep( i , 1 , n ) {
++ s[ch[i] - 'a'];
int w = i;
rep( k , 0 , ch[i] - 'a' ) w -= s[k];
ps[ch[i] - 'a'].pb( w );
}
rep( i , 0 , 25 ) reverse( all( ps[i] ) );
rep( i , 1 , n ) {
int ok = 0;
for( int t = 0 ; t < 26 ; ++ t ) {
if( ps[t].size() && ps[t].back() - kl[t] <= k ) {
k -= ps[t].back() - kl[t];
ps[t].pop_back();
re[i] = t + 'a';
++ del[t];
ok = 1;
rep( tr , 0 , t - 1 ) ++ kl[tr];
break;
}
}
if( !ok ) {
int j = i;
rep( t , 1 , n ) {
-- del[ch[t] - 'a'];
if( del[ch[t] - 'a'] < 0 ) re[j ++] = ch[t];
}
break;
}
}
puts(re + 1);
}
B 骑行
给出一棵树。询问树上有多少个有序点对
考虑枚举点
那么,路径可以被分为若干类。第一类是子树内的点到子树内的点,第二类是子树内的点到子树外的点。
up and down,记
时间复杂度
typedef long long ll;
const int MAXN = 300000 + 10;
int n, f[MAXN][2], g[MAXN][2];
ll ans;
vector<int> e[MAXN];
void dfs1(int u, int fr) {
for (auto v : e[u]) if (v != fr) {
dfs1(v, u);
if (v < u) {
ans += 1ll * f[u][0] * (f[v][0] + 1);
f[u][0] += f[v][0] + 1;
}
else {
// ans += 1ll * g[u][0] * (g[v][0] + 1);
g[u][0] += g[v][0] + 1;
}
}
}
void dfs2(int u, int fr) {
for (auto v : e[u]) if (v != fr) {
if (u > v) g[v][1] = g[u][1] + g[u][0] + 1;
else f[v][1] = f[u][1] + f[u][0] + 1;
dfs2(v, u);
}
}
int main() {
#ifdef LOCAL
freopen("ex_ride3.in", "r", stdin);
#endif
IO::read(n);
rep(i, 1, n - 1) {
int u, v; IO::read(u), IO::read(v);
e[u].push_back(v), e[v].push_back(u);
}
dfs1(1, 0);
dfs2(1, 0);
// rep(i, 1, n) printf("%d %d %d %d\n", f[i][0], g[i][0], f[i][1], g[i][1]);
rep(u, 1, n) {
ans += 1ll * f[u][0] * f[u][1];
}
printf("%lld\n", 2ll * ans);
return 0;
}
C 道路
给出一张图,边权为
CSP-J 2019 T4 的多源版本。
考虑把点拆成经过奇数条边到该点,偶数条边到该点。bfs 处理出最短路。
注意判断一个孤立点到自身的最短路,存在当且仅当
时间复杂度
typedef pair<int, int> pii;
int dis[MAXN][MAXN][2], vis[MAXN][2];
void bfs(int s) {
memset(vis, 0, sizeof vis);
rep(i, 1, n) dis[s][i][0] = dis[s][i][1] = INT_MAX;
dis[s][s][0] = 0;
queue<pii> q;
q.push(make_pair(s, 0));
while (!q.empty()) {
pii u = q.front(); q.pop();
for (auto v : e[u.first]) {
if (dis[s][v][u.second ^ 1] > dis[s][u.first][u.second] + 1) {
dis[s][v][u.second ^ 1] = dis[s][u.first][u.second] + 1;
q.push(make_pair(v, u.second ^ 1));
}
}
}
}
void solve() {
rep(i, 1, n) bfs(i);
rep(i, 1, q) {
int u, v, d; IO::read(u), IO::read(v), IO::read(d);
if (u == v && e[u].empty()) puts(d == 0 ? "Yes" : "No");
else if (d < min(dis[u][v][0], dis[u][v][1])) puts("No");
else {
bool ok = false;
if (d >= dis[u][v][1]) ok |= ((d - dis[u][v][1]) % 2 == 0);
if (d >= dis[u][v][0]) ok |= ((d - dis[u][v][0]) % 2 == 0);
puts(ok ? "Yes" : "No");
}
}
}
D 一道树题
给出一个有
定义一组匹配为,将
定义两个匹配是不同的,当且仅当存在某个点,在两个匹配中与他同组的点不同。
定义一组匹配的权值为
对于所有匹配组成的集合
化化式子。
由于第二个和号里头
考虑分开算两个部分。
方便起见,记
第一部分
就是
考虑每对匹配的系数,就是
所以第一部就是
第二部分
容斥。
由于有两个点(即两组路径完全重合)是公共点的方案在
仅有一个点是重复的方案数在
没有重复的则在
所以第二部分就是
现在考虑如何求出
记
考虑换根,给
加入子树
删除子树
把上面的加号改成减号就好。
typedef long long ll;
const int MAXN = 300000 + 10;
const int P = 998244353;
const int INV2 = 998244354 >> 1;
int n;
vector<int> e[MAXN];
ll sz[MAXN], f[MAXN], g[MAXN], A, B, C;
inline void add(int u, int v) { sz[u] += sz[v], f[u] = (f[u] + f[v] + sz[v]) % P, g[u] = (g[u] + g[v] + 2ll * f[v] % P + sz[v]) % P; }
inline void del(int u, int v) { sz[u] -= sz[v], f[u] = ((f[u] - f[v] - sz[v]) % P + P) % P, g[u] = ((g[u] - g[v] - 2ll * f[v] % P - sz[v]) % P + P) % P; }
void dfs1(int u, int fr) {
sz[u] = 1;
for (int v : e[u]) if (v != fr) dfs1(v, u), add(u, v);
}
void dfs2(int u, int fr) {
A = (A + f[u]) % P, B = (B + g[u]) % P, C = (C + 1ll * f[u] * f[u] % P) % P;
for (int v : e[u]) if (v != fr) del(u, v), add(v, u), dfs2(v, u), del(v, u), add(u, v);
}
ll F(int x) { ll ret = 1; rep(i, 1, x) ret = 1ll * ret * (2 * i - 1) % P; return ret; }
int main() {
IO::read(n);
rep(i, 1, n - 1) {
int u, v; IO::read(u), IO::read(v);
e[u].push_back(v), e[v].push_back(u);
}
dfs1(1, 0), dfs2(1, 0); ll ans = 0;
B = 1ll * B * INV2 % P, A = 1ll * A * INV2 % P;
ans += 1ll * B * F(n / 2 - 1) % P;
ll cnt = F(n / 2 - 2);
if (n > 2) (ans += 1ll * cnt * (1ll * A * A % P) % P) %= P, (ans += 1ll * cnt * B % P) %= P, ans = ((ans - 1ll * cnt * C % P) % P + P) % P;
printf("%lld\n", ans);
return 0;
}
复盘
本次考试共 4h。
开场看题,看了 46min。
0h16min:T1 有了个
0h46min:T2 T3 都看了看,没啥思路(事实上两道题都看错了部分题意。尤其是 T3 对题目理解偏差很大)。决定码 T1。
1h42min:写完了 T1。期间各种奇怪的错误,以及开始没想清楚怎么搞导致写了很久。
2h13min:会 T2 了(虽然这个时候对于题目还是有点小误解)。
2h48min:调过了 T2。因为对于题目的小误解导致调试有点久。
2h58min:T3 rush 了一个 30 pts 的暴力。
3h07min:T3 补到了 45 pts。开始检查之前的题。
3h31min:突然会了 T3。开始码。
3h49min:T3 过了样例。此后 10min 一直在检查。
感觉自己大概都是一道题 1h 能写出来。挺稳定。这次也没怎么挂分(主要记得有大样例了)。不过至少有 1h 的时间是不必要花费的:T1 开始的时候没想清楚,导致写了很久,自己码力也不太狗。T2 存在一些小误解,没发现自己读错题了。T3 没能秒掉很可惜。
还有 T3 没特判,规避这个只能如果想到某个东西要特判提前写在纸上提醒自己了。
还有提升和努力的空间,在保证正确性的基础上加快自己做题的速度。