SNOI2024 游记
sunkuangzheng
·
·
个人记录
UPD
D1T2 二维差分变量名写错，-10。
D1T3 多测不清空，-5。
D2T1 单哈希被卡，-15。
陕西是全国最早举办省选的省份，但是没有人知道为什么要这个时候省选。
全国的联合省选定在 $3$ 月 $2$ 日。 陕西不愿意参加。
有学校请求推迟省选。陕西不愿意推迟。
陕西可是“天下第一省”！！！1
---
$8$ 点半开考，大概在 $8$ 点 $25$ 开了题。
---
### T1 树 $\text V$ 图
给 $n$ 个点的树，树上有 $k$ 个关键点 $a_1,a_2,\ldots,a_k$，定义 $f(u)$ 表示距离 $u$ 最近的关键点的下标 $i$，如果有多个取 $i$ 最小的。（而不是 $a_i$）
给定树和 $f(1) \sim f(n)$ 的值，问有多少个可能的序列 $a_1,a_2,\ldots,a_k$，模 $998244353$。
$k \le n \le 3000,f(i) \le k$。
### T2 矩阵
给定 $n \times n$ 的矩阵，$q$ 次操作，支持子矩阵逆时针旋转 $90$ 度和子矩阵加 $k$，输出最终矩阵。
$n,q \le 3000$。
### T3 拉丁方
定义一个 $n \times n$ 的矩阵是好的，当且仅当每一行每一列都是 $1 \sim n$ 的排列。给你一个矩阵的左上角 $r \times c$ 的子矩阵，补全矩阵让矩阵成为好的，或报告无解。
$r,c \le n \le 500$。
---
读明白题大概是在 $\text{8:45}$。大概觉得 T1 是神秘组合计数，T2 是平衡树，T3 是神秘构造。一道不会，决定先去想 T3 的构造，毕竟说不定想法和出题人撞上就做出来了呢！
想图论建模。网格图行列连边转二分图后感觉也没啥好的性质，网络流也建不出来图。$\text{9:15}$ 的时候弃掉了这题。
那就去看 T1 部分分吧！部分分有“一条链”和 $k=2$。一条链上 dp 是简单的，$k=2$ 可以直接枚举关键点 $\mathcal O(1)$ 检查。想了一会怎么检查，然后发现这是简单的。
决定先把这两部分写了，有足足 $40$ 分。链的部分写完直接测大样例，过了！然而小样例没过（）发现是没判 $1\sim k$ 是否都出现过，改完就过了。
$k = 2$ 的部分调了一会也就过了。
到这里其实我也基本会正解了——只要把 dp 和树上 $k=2$ 的做法拼起来略作修改。大概 $\text{11:30}$ 写完了，$\text{11:45}$ 左右小样例都过了。
但是样例 $3$ 永远过不了。
$\text{12:05}$ 的时候写了 T2 的 $20$ 分，然后继续调 T1。
修了点锅，但是还是过不了样例 $3$。
$\text{12:50}$ 的时候花了几分钟写了 $5$ 分 T3。
$\text{13:00}$ 考试结束了。
$40+20+5=65$。T3 有 $20$ 分爆搜，但我因为时间不够没拿到。
机房人说大众分 $100+$ /cf /cf
唉，还是我太菜了 /kel
---
赛后聊做法，T1 我的 dp 大概是正解，T2 平衡树可做但似乎卡常，有优秀的链表做法，T3 不知道正解是啥 qwq。
---
D2。打得比 D1 还好！！！1
---
### T1 平方数
查询数组 $a$ 有多少个区间乘积是完全平方数。
$n \le 5 \times 10^5,a_i \le 10^{36}$。
### T2 公交线路
给 $n$ 个点的树，问有多少个路径集合 $P$ 满足：
- 每一条路径 $u,v$ 满足 $u \ne v$。
- 考虑一张只有 $n$ 个点，没有边的新图 $G$。如果 $u,v$ 同时在 $P$ 中的某一条路径上，则 $u,v$ 连一条无向边。要求连完所有边后，$G$ 中任意点对距离不超过 $2$。
模 $998244353$。
$n \le 3000$。
### T3 字符树
给你一棵 01-trie，记 $S_u$ 表示根到 $u$ 的路径上边上的字符拼成的串。每个点有点权 $a_i,val_i$。对于每个点 $u$ 求出：
> 对于每个 $i(0 \le i \le |S_u|)$，找到点权最大的 $val_v$，满足：
- $S_u$ 是 $S_v$ 的后缀。
- $\operatorname{LCP}(S_u,S_v) \ge i$。
- $a_v \le i$。
你只需要对于每个点 $u$，计算所有 $i$ 的答案的和。
$n \le 5 \times 10^5,val_i \le 10^9,0 \le a_i \le n$。
---
T1 开始就胡了个 $\mathcal O(n \sqrt{a_i})$ 的做法，以为切了，结果 $a_i \le 10^{36}$，嗯。
T2 没啥思路，不知道为什么联想到了 NOI2020 命运，感觉像神秘 dp？打了个爆搜，加了点神秘剪枝。赛后感觉剪枝好像假了，$30 \to 15$。
T3 就很难绷了。第一次读错题，以为 $S_i$ 是 $S_v$ 的后缀，上来码了 4k 树套树 + 树上后缀排序。发现假了以后复杂度多了个 $n$，变成 $\mathcal O(n^2\log^2 n)$ 的，但是随机数据跑的效率也许还可以。
和 D1 神似，这题写 + 调了 3h，小样例和手搓的都能过，大样例就过不去。
$30+15+0=45$，乐。
听说有人两天 $280+190=470$ /bx /bx
附：场上 D2T3 的代码，5k，$0$ 分。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5,mod = 1e9+9;//duoce qingkong !!!!!!
using ll = long long;
int T,fa[N][22],n,ch[N],dep[N],ti,dfn[N],siz[N],tot,val[N],a[N],pw[N],hsh[N],sa[N],rk[N],ok[N],rt[N*20],st[N][19],h[N];
vector<int> g[N];ll ans[N];
int t[N*289],ls[N*289],rs[N*289];vector<tuple<int,int,int>> q;
struct ddtr{
void upd(int &s,int l,int r,int x,int k){
if(!s) s = ++tot; t[s] = max(t[s],k);
if(l == r) return void();
int mid = (l + r) / 2;
if(x <= mid) upd(ls[s],l,mid,x,k); else upd(rs[s],mid+1,r,x,k);
}int qry(int s,int l,int r,int ql,int qr){
if(ql <= l && r <= qr) return t[s];
int mid = (l + r) / 2,ans = 0;
if(ql <= mid) ans = max(ans,qry(ls[s],l,mid,ql,qr));
if(qr > mid) ans = max(ans,qry(rs[s],mid+1,r,ql,qr));
return ans;
}
}tr;
//struct yet_another_ds{
// ll t[N],re;
// void upd_(int x,int p){for(;x <= n + 1;x += x & -x) t[x] += p;}
// ll qry(int x){for(re = 0;x;x -= x & -x) re += t[x];return re;}
// void upd(int l,int r,int p){upd_(l,p),upd_(r+1,-p);}
//}ft;
void upd(int s,int l,int r,int x,int y,int k){
tr.upd(rt[s],1,n,y,k); int mid = (l + r) / 2;
if(l == r) return ;
if(x <= mid) upd(s*2,l,mid,x,y,k); else upd(s*2+1,mid+1,r,x,y,k);
}int qry(int s,int l,int r,int ql,int qr,int ml,int mr){
if(ql <= l && r <= qr) return tr.qry(rt[s],1,n,ml,mr);
int mid = (l + r) / 2,ans = 0;
if(ql <= mid) ans = max(ans,qry(s*2,l,mid,ql,qr,ml,mr));
if(qr > mid) ans = max(ans,qry(s*2+1,mid+1,r,ql,qr,ml,mr));
return ans;
}void dfs(int u){
dfn[u] = ++ti,siz[u] = 1;
for(int v : g[u]) dfs(v),siz[u] += siz[v];
}void init(){
memset(fa,0,sizeof(fa)),memset(ok,0,sizeof(ok)),memset(rk,0,sizeof(rk)),memset(ans,0,sizeof(ans)),memset(rt,0,sizeof(rt));
memset(ls,0,sizeof(ls)),memset(rs,0,sizeof(rs)),memset(t,0,sizeof(t)),tot = ti = 0,memset(h,0,sizeof(h));
for(int i = 1;i <= n;i ++) g[i].clear();
}void work(){
cin >> n,init();
ch[1] = -1,ch[0] = 2,dep[1] = 1,pw[0] = 1;
for(int i = 2;i <= n;i ++) cin >> fa[i][0] >> ch[i],g[fa[i][0]].push_back(i),dep[i] = dep[fa[i][0]] + 1,hsh[i] = (3ll * hsh[fa[i][0]] + ch[i] + 1) % mod;
// for(int i = 1;i <= n;i ++) cout << hsh[i] << " ";cout << "\n";
for(int i = 1;i <= n;i ++) cin >> val[i],pw[i] = 3ll * pw[i - 1] % mod;
for(int i = 1;i <= n;i ++) cin >> a[i];dfs(1);
for(int j = 1;j <= __lg(n);j ++) for(int i = 1;i <= n;i ++) fa[i][j] = fa[fa[i][j-1]][j-1];
for(int i = 1;i <= n;i ++) sa[i] = i,rk[i] = ch[i];
for(int j = 1;j <= __lg(n);j ++){
for(int i = 1;i <= n;i ++) ok[i] = rk[i]; int p = 0;
sort(sa+1,sa+n+1,[&](int x,int y){return rk[x] < rk[y] || rk[x] == rk[y] && rk[fa[x][j]] < rk[fa[y][j]];});
auto cmp = [&](int x,int y){return ok[x] == ok[y] && ok[fa[x][j]] == ok[fa[y][j]];};
for(int i = 1;i <= n;i ++) if(cmp(sa[i],sa[i-1])) rk[sa[i]] = p; else rk[sa[i]] = ++p; if(p == n) break;
}for(int i = 1;i <= n;i ++) q.emplace_back(a[i],-i,0);
auto kfa = [&](int u,int k){
if(k > dep[u]) return 0;
for(int i = 19;i >= 0;i --) if((k >> i) & 1) u = fa[u][i];
return u;
};
for(int i = 1;i <= n;i ++) for(int j = 1;j <= dep[i];j ++) q.emplace_back(dep[i]-j,i,kfa(i,j-1));
auto ghsh = [&](int l,int r){
return (hsh[r] - 1ll * hsh[fa[l][0]] * pw[dep[r] - dep[l] + 1] % mod + mod) % mod;
};
for(int i = 2;i <= n;i ++){
int l = 1,r = min(dep[sa[i]],dep[sa[i - 1]]);
while(l <= r){
int mid = (l + r) / 2;
if(ghsh(kfa(sa[i],mid-1),sa[i]) == ghsh(kfa(sa[i-1],mid-1),sa[i-1])) l = mid + 1; else r = mid - 1;
}h[i] = l - 1;//,cout << h[i] << " ";
}//cout << "\n";
for(int i = 1;i <= n;i ++) st[i][0] = h[i];
for(int j = 1;j <= __lg(n);j ++) for(int i = 1;i + (1 << j) - 1 <= n;i ++)
st[i][j] = min(st[i][j-1],st[i+(1<<j-1)][j-1]);
auto lcp = [&](int i,int j){
if(i == j) return n;
int k = __lg(j - i);
return min(st[i+1][k],st[j-(1<<k)+1][k]);
};
sort(q.begin(),q.end());
// cout << q.size();
// for(int i = 1;i <= n;i ++) cout << h[i] << " ";
for(auto [a,u,s] : q){
if(u < 0) u = -u,upd(1,1,n,dfn[u],rk[u],val[u]);
else{
int l,r,ql,qr,k = rk[u];
for(l = 1,r = k;l <= r;){
int mid = (l + r) / 2;
if(lcp(mid,k) >= dep[u] - 1) r = mid - 1; else l = mid + 1;
}ql = r + 1;
for(l = k,r = n;l <= r;){
int mid = (l + r) / 2;
if(lcp(k,mid) >= dep[u] - 1) l = mid + 1; else r = mid - 1;
}qr = l - 1;
// cout << ql << " " << qr << "\n";
//cout << s << "\n";
// cout << dfn[s] << " " << dfn[s] + siz[s] - 1 << "\n";
int ans_ = qry(1,1,n,dfn[s],dfn[s] + siz[s] - 1,ql,qr);
// cout << u << " " << ans << "\n";
// ft.upd(dfn[u],dfn[u] + siz[u] - 1,ans);
ans[u] += ans_;
}
}
for(int i = 1;i <= n;i ++) cout << ans[i] << " ";
cout << "\n";
}signed main(){
freopen("tree.in","r",stdin),freopen("tree.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
for(cin >> T;T --;) work();
}
```
**UPD** 赛后发现上面的代码有两个问题：一是 SA 倍增应从 $2^0$ 开始，而不是 $ 2^1$；二是 $q$ 没有清空。改完就有 $20 $ 分了。本来估计 $35$ 分，但是被卡常，没过 /fn /fn