题单完成情况：
- 2025.7.2 9/11
- 2025.7.3 9/15
- 2025.7.4 4/4+2/8
- 2025.7.5 10/16
- 2025.7.6 5/15 （这真的是需要写完的吗）
- 2025.7.7 1/4+5/9（一天两场模拟赛，懒得喷了）
- 2025.7.8 5/14
- 2025.7.9 2/12
- 2025.7.10 放假了！
- 2025.7.11 3/4 1/8（模拟赛，没看输出格式，光荣保龄）
- 2025.7.12 4/8
- 2025.7.13 6/9
- 2025.7.14 3/4+1/6
真的写不完啊！
闲话
2025.7.2-2025.7.5：实话说印象不深了，不知道摆烂的时候干了些啥了。
2025.7.6：下午课间打球，晚饭没吃打球，真打爽了。（为啥俩月没打羽毛球技术不降反增啊）
2025.7.7：上午模拟赛，中午打球，下午模拟赛，晚饭随便吃了点去打球。（已经懒得记录了，明天对我好一点）
2025.7.8：课间还被ban了，只能打 20 分钟了。
2025.7.9：今天下雨了，不打算打球了。最终还是选择打球了
2025.7.10：放假了，打了一天第五人格。
2025.7.11：xfy学长组了一组很好的noip模拟赛，可惜我没有noip的水平。
2025.7.12：扫描线专题，还算能接受吧。
2025.7.13：树上技巧，还是可以接受。
2025.7.14：又是一场noip模拟赛，还是欠缺 dp 的训练啊。
2025.7.2
STL+单调队列/栈+并查集
STL讲了 set 和基于 set 实现的珂朵莉树。没有万众瞩目的 bitset `(>﹏<)′
珂朵莉树 [模板](Problem - 896C - Codeforces)
只有看完代码那一刻，才知道多么暴力……
复杂度依赖于区间推平，思路是将相同的值缩成一个点。
具体的，开一个结构体，形如：
struct node{
ll l,r;
mutable ll v;
node(ll l,ll r=0,ll v=0): l(l),r(r),v(v){}
bool operator < (const node &a) const{
return l<a.l;
}
};
set<node> s;
最关键的就是分离操作，这应该也是珂朵莉树最有脑子的地方。
将我们需要的 $pos$ 位置的区间分成 $l,pos-1$ 与 $pos,r$
其实也不是很有脑啊。
auto split(int pos){
auto it=s.lower_bound(node(pos));
if(it!=s.end() && it->l == pos) return it;
it--;
if(it->r < pos) return s.end();
ll l=it->l,r=it->r,v=it->;
s.erase(it);
s.insert(node(l,pos-1,v));
return s.insert(node(pos,r,v)).first;
}
注意：insert 的返回值是个 pair，第一个值是迭代器。
auto 大法好！
然后是珂朵莉树剩余的操作就是先拆出操作区间，然后暴力。
以推平操作为例：
void assign(ll l,ll r,ll x){
auto itr=split(r+1),itl=split(l);
s.erase(itl,itr);
s.insert(node(l,r,x));
}
注意，此处要先进行 r+1 的split，再进行 l 的split。
不然会RE。
#include<bits/stdc++.h>
#define int long long
#define p 1000000007
using namespace std;
const int N=1e5+10;
int n,m,seed,V,a[N];
int rnd(){
int res=seed;
seed=(seed*7+13)%p;
return res;
}
struct node{
int l,r;//相同元素段的起终点
mutable int v;//元素值
node(int l,int r=0,int v=0):l(l),r(r),v(v){}
bool operator < (const node &a)const {
return l < a.l;
}
};
set<node> s;
auto split(int pos){
auto it=s.lower_bound(node(pos));
if(it!=s.end() && it->l==pos) return it;//如果恰好是 l
it--;
if(it->r < pos) return s.end();//如果是最后一块
int l=it->l,r=it->r,v=it->v;
s.erase(it);
s.insert(node(l,pos-1,v));
return s.insert(node(pos,r,v)).first;//insert的返回值是pair，第一位是迭代器
}
//先计算 itr,不然会神秘 RE
void add(int l,int r,int x){
auto itr=split(r+1),itl=split(l);
for(auto it=itl;it!=itr;++it){
it->v+=x;
}
}
void assign(int l,int r,int x){
auto itr=split(r+1),itl=split(l);
s.erase(itl,itr);
s.insert(node(l,r,x));
}
int qpow(int a,int b,int mod){
int res=1;a%=mod;
while(b){
if(b&1) res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res;
}
int calc(int l,int r,int x,int y){
auto itr=split(r+1),itl=split(l);
int ans=0;
for(auto it=itl;it!=itr;++it){
ans=(ans+qpow(it->v,x,y) * (it->r-it->l+1)%y)%y;
}
return ans;
}
struct Num{
int v,cnt;
bool operator < (const Num &a)const{
return v<a.v;
}
};
int rnk(int l,int r,int x){
vector<Num> vec;
auto itr=split(r+1),itl=split(l);
for(auto it=itl;it!=itr;++it){
vec.push_back({it->v,it->r-it->l+1});
}
sort(vec.begin(),vec.end());
int id;
for(id=0;id<(int)vec.size();id++){
if(vec[id].cnt<x) x-=vec[id].cnt;
else break;
}
return vec[id].v;
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m>>seed>>V;
for(int i=1;i<=n;i++){
a[i]=(rnd()%V)+1;
s.insert(node(i,i,a[i]));
}
for(int i=1,op,l,r,x,y;i<=m;i++){
op=rnd()%4+1;
l=rnd()%n+1,r=rnd()%n+1;
if(l>r) swap(l,r);
if(op==3){
x=(rnd()%(r-l+1))+1;
}else{
x=(rnd()%V)+1;
}
if(op==4){
y=rnd()%V+1;
}
if(op==1){
add(l,r,x);
}else if(op==2){
assign(l,r,x);
}else if(op==3){
cout << rnk(l,r,x) << '\n';
}else{
cout << calc(l,r,x,y) << '\n';
}
}
return 0;
}
单调栈做最大子矩形 [模板](P4147 玉蟾宫 - 洛谷)
在每个点能向上延伸多少可以用前缀和。
单调栈维护一下每一个向上延伸的块最多延伸到哪里，然后再乘上长。
最后模拟即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e3+10;
int pos[N][N];
int n,m,ans;
struct node{
int len,hei;
}sta[N];
void solve(int x){
int top=0,len=0;
for(int i=1;i<=m;i++){
len=0;
while(sta[top].hei>=pos[x][i] && top>0){
len+=sta[top].len;
ans=max(ans,sta[top--].hei*len);
}
sta[++top].hei=pos[x][i];
sta[top].len=len+1;
}
len=0;
while(top>0){
len+=sta[top].len;
ans=max(ans,sta[top--].hei*len);
}
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char ch;cin>>ch;
if(ch=='R'){
pos[i][j]=0;
}else{
pos[i][j]=pos[i-1][j]+1;
}
}
}
for(int i=1;i<=n;i++) solve(i);
cout << 3*ans;
return 0;
}
单调队列优化dp 瑰丽华尔兹 和 股票交易
单调队列优化的是区间最大最小值。（那我为什么不……）
假如 dp 方程形如：$f_i=\max_{1\le k \le j}(f_k,a_k)+a_i$ 这类，$\max$ 函数中不与 $i$ 有关的东西，都可以拿单调队列维护。
注意边界情况。
//股票交易
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3+10;
int T,P,W;
int ap[N],bp[N],as[N],bs[N];
int f[N][N],ans,l,r,que[N];
int main(){
cin>>T>>P>>W;
for(int i=1;i<=T;i++){
cin>>ap[i]>>bp[i]>>as[i]>>bs[i];
}
memset(f,128,sizeof(f));
for(int i=1;i<=T;i++){
for(int j=0;j<=as[i];j++){
f[i][j]=-j*ap[i];
}
for(int j=0;j<=P;j++){
f[i][j]=max(f[i][j],f[i-1][j]);
}
if(i-W-1<1) continue;
l=1,r=0;
for(int j=0;j<=P;j++){
while(l<=r && que[l]<j-as[i]) l++;
while(l<=r && f[i-W-1][que[r]]+que[r]*ap[i]<=f[i-W-1][j]+j*ap[i]) r--;
que[++r]=j;
if(l<=r)
f[i][j]=max(f[i][j],f[i-W-1][que[l]]+(que[l]-j)*ap[i]);
}
l=1,r=0;
for(int j=P;j>=0;j--){
while(l<=r && que[l]>j+bs[i]) l++;
while(l<=r && f[i-W-1][que[r]]+que[r]*bp[i]<=f[i-W-1][j]+j*bp[i]) r--;
que[++r]=j;
if(l<=r)
f[i][j]=max(f[i][j],f[i-W-1][que[l]]+(que[l]-j)*bp[i]);
}
}
for(int i=0;i<=P;i++){
ans=max(ans,f[T][i]);
}
cout << ans;
return 0;
}
//瑰丽华尔兹
#include<bits/stdc++.h>
using namespace std;
const int N = 210;
int n,m,x,y,k;
int mp[N][N],f[N][N];
struct node{
int val,pos;
}que[N];
int l,r,ans;
int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};
void solve(int x,int y,int len,int d){
int l=1,r=0;
for(int i=1;x>=1 && x<=n && y>=1 && y<=m;i++,x+=dx[d],y+=dy[d]){
if(mp[x][y]) l=1,r=0;
else{
while(l<=r && que[r].val+i-que[r].pos<f[x][y]) r--;
que[++r]={f[x][y],i};
while(que[r].pos-que[l].pos>len) l++;
f[x][y]=que[l].val+i-que[l].pos;
ans=max(ans,f[x][y]);
}
}
}
int main(){
cin>>n>>m>>x>>y>>k;
memset(f,128,sizeof(f));
f[x][y]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char ch;cin>>ch;
if(ch=='x'){
mp[i][j]=1;
}
}
}
for(int i=1,l,r,d;i<=k;i++){
cin>>l>>r>>d;
int len=r-l+1;
if(d==1) for(int j=1;j<=m;j++) solve(n,j,len,d);
if(d==2) for(int j=1;j<=m;j++) solve(1,j,len,d);
if(d==3) for(int j=1;j<=n;j++) solve(j,m,len,d);
if(d==4) for(int j=1;j<=n;j++) solve(j,1,len,d);
}
cout << ans;
return 0;
}
转移方程怎么推的参考题解吧。
并查集
并查集的用处太大了，拥有优秀的复杂度的同时，还支持拓展。而且拓展的性质也很好。
免费道路
这里的并查集只维护连通性。
将边降序排序能选出一定要的 1 边，升序能选出一定要的 0 边。
剩下的随便填即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e4+10;
int n,m,k,fa[N];
int find(int x){return x==fa[x] ? x : fa[x]=find(fa[x]);}
struct Edge{
int u,v,w;
}e[N<<3],ans[N<<3];
int tot,cnt,sum;
bool cmp1(Edge a,Edge b){
return a.w>b.w;
}
bool cmp2(Edge a,Edge b){
return a.w<b.w;
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=m;i++){
cin>>e[i].u>>e[i].v>>e[i].w;
}
for(int i=1;i<=n;i++){
fa[i]=i;
}
sort(e+1,e+1+m,cmp1);
for(int i=1;i<=m;i++){
int u=e[i].u,v=e[i].v;
int fu=find(u),fv=find(v);
if(fu==fv) continue;
fa[fv]=fu;sum++;
if(e[i].w==0){
e[i].w=-1;
tot++;
}
}
if(tot>k || sum!=n-1){
cout << "no solution";return 0;
}
sort(e+1,e+1+m,cmp2);
for(int i=1;i<=n;i++) fa[i]=i;
sum=0,tot=0;
for(int i=1;i<=m;i++){
int u=e[i].u,v=e[i].v;
int fu=find(u),fv=find(v);
if(fu==fv) continue;
if(e[i].w==1 || tot<k){
fa[fv]=fu,ans[++cnt]=e[i];
sum++;
if(e[i].w<1){
tot++,e[i].w=0;
}
}
}
if(tot<k || sum!=n-1){
cout << "no solution";return 0;
}
for(int i=1;i<=cnt;i++){
if(ans[i].w==-1) ans[i].w=0;
cout<<ans[i].u<<' '<<ans[i].v<<' '<<ans[i].w<<'\n';
}
return 0;
}
连通图
线段树分治还是太强大了。
对时间轴开线段树，树上维护每段时间出现了哪些边。
这个可以在输入的时候做。
然后进线段树去操作，并查集维护连通性。
从儿子出来的时候要撤销，所以需要可撤销并查集。
#include<bits/stdc++.h>
#define ls u<<1
#define rs u<<1|1
using namespace std;
const int N=2e5+10;
int n,m,k;
struct Edge{
int u,v;
}e[N<<1];
vector<int> vec[N];
vector<int> tr[N<<2];
void insert(int u,int l,int r,int x,int y,int k){
if(l>=x && r<=y){
tr[u].push_back(k);
return ;
}
int mid=(l+r)>>1;
if(x<=mid) insert(ls,l,mid,x,y,k);
if(mid<y) insert(rs,mid+1,r,x,y,k);
}
int fa[N],siz[N];
int sta[N],top;
int find(int x){return fa[x]==x ? x : find(fa[x]);}
inline void merge(int x,int y){
if(siz[x]>siz[y]) swap(x,y);
fa[x]=y;
siz[y]+=siz[x];
sta[++top]=x;
}
inline void goback(int lst){
while(top>lst){
int y=sta[top--];
siz[fa[y]]-=siz[y];
fa[y]=y;
}
}
void solve(int u,int l,int r,bool f){
int lst=top;
for(auto tim:tr[u]){
int u=e[tim].u,v=e[tim].v;
int fu=find(u),fv=find(v);
if(fu==fv) continue;
merge(fu,fv);
if(siz[find(u)]==n){
f=true;
}
}
if(l==r){
cout << (f==1 ? "Connected" : "Disconnected") << '\n';
}else{
int mid=(l+r)>>1;
solve(ls,l,mid,f);
solve(rs,mid+1,r,f);
}
goback(lst);
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>e[i].u>>e[i].v;
}
for(int i=1;i<=m;i++){
vec[i].push_back(0);
}
cin>>k;
for(int i=1;i<=k;i++){
int k;cin>>k;
for(int j=1;j<=k;j++){
int c;cin>>c;
vec[c].push_back(i);
}
}
for(int i=1;i<=m;i++){
vec[i].push_back(k+1);
}
for(int i=1;i<=m;i++){
for(int j=1;j<(int)vec[i].size();j++){
if(vec[i][j-1]+1<=vec[i][j]-1){
insert(1,1,k,vec[i][j-1]+1,vec[i][j]-1,i);
}
}
}
for(int i=1;i<=n;i++){
fa[i]=i,siz[i]=1;
}
solve(1,1,k,0);
return 0;
}
倍增优化建图 逛森林
考虑形如线段树优化建图，但不开那么大的空间。而且常数还比线段树小。
用倍增来表示某一条链，具体实现非常……
对于本题而言，可以将 2 的边连好后，判断有哪些 1 边可以被连接（并查集），再统一连 1 的边。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 1e6+10;
int n,m,s;
struct node{
int v,w;
};
struct Que{
int u,v,x,y,w;
}que[M];
int cnt,lim,tot;
vector<node> G[N*20];
vector<int> tr[N];
int fa[50010],f[N][18],dep[50010];
int in[N][18],out[N][18];
int find(int x){return fa[x]==x ? x : fa[x]=find(fa[x]);}
void dfs(int u,int father){
dep[u]=dep[father]+1;f[u][0]=father;
in[u][0]=++tot;G[tot].push_back({u,0});G[tot].push_back({father,0});
out[u][0]=++tot;G[u].push_back({tot,0});G[father].push_back({tot,0});
for(int j=1;j<=lim;j++){
f[u][j]=f[f[u][j-1]][j-1];
in[u][j]=++tot;G[tot].push_back({in[u][j-1],0});G[tot].push_back({in[f[u][j-1]][j-1],0});
out[u][j]=++tot;G[out[u][j-1]].push_back({tot,0});G[out[f[u][j-1]][j-1]].push_back({tot,0});
}
for(int v:tr[u]){
if(v==father) continue;
dfs(v,u);
}
}
void lca1(int x,int y,int k){
if(dep[x]<dep[y]) swap(x,y);
G[y].push_back({k,0});
for(int i=lim;i>=0;i--){
if(dep[f[x][i]]>=dep[y]){
G[out[x][i]].push_back({k,0});
x=f[x][i];
}
}
if(x==y) return ;
for(int i=lim;i>=0;i--){
if(f[x][i]!=f[y][i]){
G[out[x][i]].push_back({k,0});x=f[x][i];
G[out[y][i]].push_back({k,0});y=f[y][i];
}
}
G[out[x][0]].push_back({k,0});
}
void lca2(int x,int y,int k){
if(dep[x]<dep[y]) swap(x,y);
G[k].push_back({y,0});
for(int i=lim;i>=0;i--){
if(dep[f[x][i]]>=dep[y]){
G[k].push_back({in[x][i],0});
x=f[x][i];
}
}
if(x==y) return ;
for(int i=lim;i>=0;i--){
if(f[x][i]!=f[y][i]){
G[k].push_back({in[x][i],0});x=f[x][i];
G[k].push_back({in[y][i],0});y=f[y][i];
}
}
G[k].push_back({in[x][0],0});
}
struct DIJ{
int id,val;
bool operator < (const DIJ &a)const{
return val>a.val;
}
};
int dis[N*20];
bool vis[N*20];
void dijsktra(){
memset(dis,0x3f,sizeof(dis));
priority_queue<DIJ> q;
q.push({s,0});
dis[s]=0;
while(!q.empty()){
auto u=q.top();q.pop();
if(vis[u.id]) continue;
vis[u.id]=1;
for(auto to:G[u.id]){
int v=to.v,w=to.w;
if(dis[v]>dis[u.id]+w){
dis[v]=dis[u.id]+w;
q.push({v,dis[v]});
}
}
}
for(int i=1;i<=n;i++){
cout << (dis[i]==0x3f3f3f3f ? -1 : dis[i]) << ' ';
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m>>s;
while((1<<lim)<=n) ++lim;
lim--;tot=n;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1,op,u,v,w;i<=m;i++){
cin>>op>>u>>v;
if(op==1){
int x,y;
cin>>x>>y>>w;
if(find(x)!=find(y) || find(u)!=find(v)) continue;
que[++cnt]={u,v,x,y,w};
}else{
cin>>w;
int fu=find(u),fv=find(v);
if(fu==fv) continue;
tr[u].push_back(v);tr[v].push_back(u);
G[u].push_back({v,w});
G[v].push_back({u,w});
fa[fu]=fv;
}
}
for(int i=1;i<=n;i++){
if(!dep[i]) dfs(i,0);
}
for(int i=1;i<=cnt;i++){
lca1(que[i].u,que[i].v,++tot);
lca2(que[i].x,que[i].y,++tot);
G[tot-1].push_back({tot,que[i].w});
}
dijsktra();
return 0;
}
2025.7.3
Trie树+笛卡尔树+DS
Trie树
Trie树原来还有这么多好玩的性质啊。
First! G
建Trie树，因为字符总长 3e6，直接暴力check每一个字符串即可。
然后就是check，我们想让某个最大，肯定要钦定一系列大小关系。
然后根据大小关系连成图，topo判环即可。
#include<bits/stdc++.h>
using namespace std;
const int N=3e4+10;
int n,ans[N],cnt;
string s[N];
struct Trie{
struct node{
int son[26];
int cnt;
}tr[10*N];
int tot,in[26],mp[26][26];
void insert(const string &s){
int u=0;
for(char ch:s){
int &son=tr[u].son[ch-'a'];
if(!son) son=++tot;
u=son;
}
tr[u].cnt+=1;
}
void topo(){
queue<int> que;
for(int i=0;i<26;i++){
if(in[i]==0) que.push(i);
}
while(!que.empty()){
int u=que.front();que.pop();
for(int i=0;i<26;i++){
if(mp[u][i]){
in[i]--;
if(!in[i]) que.push(i);
}
}
}
}
bool check(const string &s){
memset(in,0,sizeof(in));
memset(mp,0,sizeof(mp));
int u=0;
for(char ch:s){
if(tr[u].cnt) return 0;
for(int i=0;i<26;i++){
if(tr[u].son[i] && i!=ch-'a' && !mp[ch-'a'][i]){
mp[ch-'a'][i]=1;
in[i]++;
}
}
u=tr[u].son[ch-'a'];
}
topo();
for(int i=0;i<26;i++){
if(in[i]) return 0;
}
return 1;
}
}T;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>s[i];
T.insert(s[i]);
}
for(int i=1;i<=n;i++){
if(T.check(s[i])){
ans[++cnt]=i;
}
}
cout << cnt << '\n';
for(int i=1;i<=cnt;i++){
cout << s[ans[i]] << '\n';
}
return 0;
}
电子字典
建Trie树，然后接下来考虑在 Trie 上走。
字符串长度小于 20，暴力 DFS 即可。
下面长度指匹配的字符串在第几位。
增：任意到达这个节点的儿子，长度不增。
删：保留当前节点，长度增加。
改：任意匹配这个节点的儿子，长度增加。
然后就没了，DFS即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
struct node{
int son[26];
int cnt;
}tr[20*N];
bool vis[20*N];
int n,m,tot,ans,vx[N],len;
string s;
void insert(const string &s){
int u=0;
for(char ch:s){
int &son=tr[u].son[ch-'a'];
if(!son) son=++tot;
u=son;
}
tr[u].cnt++;
}
bool flag=0;
void dfs(int u,int l,bool f){
if(tr[u].cnt && l==len && !f){
flag=1;return;
}
if(tr[u].cnt && l==len && f){
if(!vis[u]){
vx[++ans]=u;
vis[u]=1;
}
return;
}
int ch=s[l]-'a';
if(!f){
if(l<len) dfs(u,l+1,1);
for(int i=0;i<26;i++){
if(tr[u].son[i]){
dfs(tr[u].son[i],l,1);
if(i!=ch) dfs(tr[u].son[i],l+1,1);
}
}
}
if(l>=len) return;
if(tr[u].son[ch]) dfs(tr[u].son[ch],l+1,f);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s;
insert(s);
}
for(int i=1;i<=m;i++){
cin>>s;len=s.length();
dfs(0,0,0);
if(flag) cout << "-1\n";
else cout << ans << '\n';
while(ans) vis[vx[ans--]]=0;
flag=0;
}
return 0;
}
Type Printer
先无脑建出Trie树，然后考虑怎么走最优。
发现是著名贪心结论，先走散链，再走最长链。
读入时比较长度保留最长链，然后给最长链上标记。
然后DFS一遍即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
int n,tot;
string s,mx;
struct node{
int son[26];
int cnt;
bool vis;
}tr[N];
void insert(const string &s,bool op){
if(op==1){
int u=0;
for(char ch:s){
u=tr[u].son[ch-'a'];
tr[u].vis=1;
}
return ;
}
int u=0;
for(char ch : s){
int &son=tr[u].son[ch-'a'];
if(!son) son=++tot;
u=son;
}
tr[u].cnt++;
}
char ans[N<<1];
int cnt;
bool f=false;
void dfs(int u){
int v=-1;
if(tr[u].cnt){
for(int i=1;i<=tr[u].cnt;i++) ans[++cnt]='P';
}
for(int i=0;i<26;i++){
if(tr[tr[u].son[i]].vis) v=i;
else if(tr[u].son[i]){
ans[++cnt]=i+'a';
dfs(tr[u].son[i]);
}
}
if(v!=-1){
ans[++cnt]=v+'a';
dfs(tr[u].son[v]);
}
if(v==-1 && tr[u].vis){
f=true;
}
if(!f){
ans[++cnt]='-';
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>s;
insert(s,0);
if(s.length()>mx.length()){
mx=s;
}
}
insert(mx,1);
dfs(0);
cout << cnt << '\n';
for(int i=1;i<=cnt;i++){
cout << ans[i] << '\n';
}
return 0;
}
最大异或和
可持久化 01 Trie，写法形如主席树即可。
询问的时候贪心一下，走相反的。
#include<bits/stdc++.h>
using namespace std;
const int N=6e5+10;
int n,m,a[N];
int rt[N],tr[N<<5];
int son[N<<5][2];
int tot=1;
void insert(int now,int pre,int t,int x){
if(t<0) return ;
int i=(x>>t)&1;
son[now][!i]=son[pre][!i];
son[now][i]=tot++;
tr[son[now][i]]=tr[son[pre][i]]+1;
insert(son[now][i],son[pre][i],t-1,x);
}
int query(int now,int pre,int t,int x){
if(t<0) return 0;
int i=(x>>t)&1;
if(tr[son[pre][!i]]>tr[son[now][!i]]){
return (1<<t)+query(son[now][!i],son[pre][!i],t-1,x);
}else{
return query(son[now][i],son[pre][i],t-1,x);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
rt[0]=tot++;
insert(rt[0],0,25,0);
for(int i=1;i<=n;i++){
int b;cin>>b;
a[i]=a[i-1]^b;
rt[i]=tot++;
insert(rt[i],rt[i-1],25,a[i]);
}
for(int i=1;i<=m;i++){
char op;
cin>>op;
if(op=='A'){
int x;cin>>x;
n++;
a[n]=a[n-1]^x;
rt[n]=tot++;
insert(rt[n],rt[n-1],25,a[n]);
}else{
int l,r,x;
cin>>l>>r>>x;
l--,r--;
if(l==0) cout << query(0,rt[r],25,x^a[n]) << '\n';
else cout << query(rt[l-1],rt[r],25,x^a[n]) << '\n';
}
}
return 0;
}
异或粽子
拼好题，把最大异或和的代码贺下来，询问改成回答位置。拼上超级钢琴即可。
#include<bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;
const int N = 5e5+10;
int n,m,rt[N],tot;
ll a[N],ans;
struct Trie{
int son[2],sum,id;
}tr[40*N];
void insert(int &now,int pre,int t,int id,ll x){
now=++tot;tr[now]=tr[pre];tr[now].sum++;
if(t==-1){tr[now].id=id;return;}
int i=(x>>t)&1;
insert(tr[now].son[i],tr[pre].son[i],t-1,id,x);
}
int query(int l,int r,int t,ll x){
if(t==-1) return tr[r].id;
int i=(x>>t)&1;
if(tr[tr[r].son[i^1]].sum>tr[tr[l].son[i^1]].sum) return query(tr[l].son[i^1],tr[r].son[i^1],t-1,x);
else return query(tr[l].son[i],tr[r].son[i],t-1,x);
}
struct Num{
int l,r,x,id;
ll val;
Num(int nl=0,int nr=0,int nx=0){
l=nl;r=nr;x=nx;
id=query(rt[l-1],rt[r],32,a[x]);
val=a[x]^a[id-1];
}
bool operator < (const Num &a)const{
return val<a.val;
}
};
priority_queue<Num> que;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
int b;cin>>b;
a[i]=a[i-1]^b;
}
for(int i=1;i<=n;i++){
rt[i]=rt[i-1];
insert(rt[i],rt[i],32,i,a[i-1]);
}
for(int i=1;i<=n;i++){
que.push(Num(1,i,i));
}
for(int i=1;i<=m;i++){
Num u=que.top();que.pop();
ans+=u.val;
if(u.l<u.id) que.push(Num(u.l,u.id-1,u.x));
if(u.id<u.r) que.push(Num(u.id+1,u.r,u.x));
}
cout << ans;
return 0;
}
笛卡尔树
其实没听懂，只能全文背诵了，先【TBD】了。
DS
有……大家要一起吃啊！
超级钢琴
先来个比较有好的。
对前缀和做 ST 表解决区间不定长最大子段和。
然后扔入堆里，每次取的时候，把原区间劈成两半再放入堆里。
取 k 个就是答案。代码有点古老了，凑合看吧。
#include<bits/stdc++.h>
using namespace std;
int n,k,L,R;
int a[501000];
int st[501000][50];
int d[501000][50];
int lg2[501000];
int arr[501000];
struct node{
int sum,sd,id;
//sum=当前的字段和
//sd=开始的点
//id=l-r区间内选的最小值的点
int ll,rr;
//ll=以st为末尾长度为ll
//rr=以st为末尾长度为rr
friend bool operator < (struct node a,struct node b) {
return a.sum < b.sum;
}
};
priority_queue<node,vector<node>,less<node> > q;
int ask2(int l,int r){
int j=lg2[r-l+1];
if(st[l][j]>st[r-(1<<j)+1][j]){
return d[l][j];
}else{
return d[r-(1<<j)+1][j];
}
}
void init(){
cin>>n>>k>>L>>R;
for(int i=1;i<=n;i++){cin>>a[i];arr[i]=arr[i-1]+a[i];d[i][0]=i;if(i>=2) lg2[i]=lg2[i/2]+1;}
for(int i=1;i<=n;i++) st[i][0]=arr[i];
for(int j=1;(1<<j)<=n;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
if(st[i][j-1]<st[i+(1<<(j-1))][j-1]){
st[i][j]=st[i+(1<<(j-1))][j-1];
d[i][j]=d[i+(1<<(j-1))][j-1];
}else{
st[i][j]=st[i][j-1];
d[i][j]=d[i][j-1];
}
}
}
return;
}
void add(int w,int i,int l,int r){
node d;
d.sum=arr[w]-arr[i-1];
d.rr=r;d.ll=l;
d.id=i;d.sd=w;
q.push(d);
}
int main(){
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
init();
for(int i=1;i+L-1<=n;i++){
add(ask2(i+L-1,min(i+R-1,n)),i,i+L-1,min(i+R-1,n));
}
long long ans=0;
for(int i=1;i<=k;i++){
node k=q.top();
q.pop();
ans+=k.sum;
int st=k.sd,j=k.id;
int l=k.ll,r=k.rr;
if(st>l){
add(ask2(l,st-1),j,l,st-1);
}
if(st<r){
add(ask2(st+1,r),j,st+1,r);
}
}
cout<<ans;
return 0;
}
/*做前缀和后求最大不定长字段和（利用st表）
利用优先队列存可能的最优解
每次取队头的值进行累加
*/
Sasha and Array
Tmbcan：听我说，我那个结论一定是对的，就是要卡常而已。
众所周知，斐波那契可以拿矩阵维护，直接扔线段树上。
节点存矩阵，加法操作变成给维护的矩阵乘上 $x$ 次幂。
代码太屎了。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+10;
const int p = 1e9+7;
int n,m,a[N];
struct Matrix{
int a[5][5];
void clear(){
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
a[i][j]=0;
}
void init(){
for(int i=0;i<4;i++) a[i][i]=1;
}
bool empty(){
if(a[1][1]!=1) return 0;
if(a[1][2]!=0) return 0;
if(a[2][1]!=0) return 0;
if(a[2][2]!=1) return 0;
return 1;
}
Matrix operator + (const Matrix &b)const{
Matrix res;res.clear();
for(int i=1;i<=2;i++){
for(int j=1;j<=2;j++){
res.a[i][j]=(a[i][j]+b.a[i][j])%p;
}
}
return res;
}
Matrix operator * (const Matrix &b)const{
Matrix res;res.init();res.clear();
for(int k=1;k<=2;k++){
for(int i=1;i<=2;i++){
for(int j=1;j<=2;j++){
res.a[i][j]=(res.a[i][j]+1ll*a[i][k]*b.a[k][j]%p)%p;
}
}
}
return res;
}
};
Matrix qpow(Matrix a,int b){
Matrix res;res.clear();res.init();
while(b){
if(b&1) res=res*a;
a=a*a;
b>>=1;
}
return res;
}
Matrix g,F;
struct SegTree{
#define ls u<<1
#define rs u<<1|1
#define mid ((l+r)>>1)
struct Tree{
Matrix sum,tag;
}tr[N<<2];
void pushup(int u){
tr[u].sum=tr[ls].sum+tr[rs].sum;
}
void upd(int u,Matrix k){
tr[u].sum=tr[u].sum*k;
tr[u].tag=tr[u].tag*k;
}
void pushdown(int u){
if(tr[u].tag.empty()) return ;
upd(ls,tr[u].tag);
upd(rs,tr[u].tag);
tr[u].tag.clear();
tr[u].tag.init();
}
void build(int u,int l,int r){
tr[u].sum.clear();tr[u].tag.clear();
tr[u].tag.init();
if(l==r){
tr[u].sum=F*qpow(g,a[l]-1);
return;
}
build(ls,l,mid);build(rs,mid+1,r);pushup(u);
}
void modify(int u,int l,int r,int x,int y,Matrix k){
if(l>=x && r<=y){upd(u,k);return;}
pushdown(u);
if(x<=mid) modify(ls,l,mid,x,y,k);
if(mid<y) modify(rs,mid+1,r,x,y,k);
pushup(u);
}
Matrix query_sum(int u,int l,int r,int x,int y){
if(l>=x && r<=y) return tr[u].sum;
pushdown(u);
Matrix res;res.clear();
if(x<=mid) res=res+query_sum(ls,l,mid,x,y);
if(mid<y) res=res+query_sum(rs,mid+1,r,x,y);
return res;
}
}Tr;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
g.clear();F.clear();
g.a[1][1]=g.a[1][2]=g.a[2][1]=1;g.a[2][2]=0;
F.a[1][1]=F.a[1][2]=1;F.a[2][1]=F.a[2][2]=0;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
Tr.build(1,1,n);
for(int i=1,op,l,r;i<=m;i++){
cin>>op>>l>>r;
if(op==1){
int x;cin>>x;
Tr.modify(1,1,n,l,r,qpow(g,x));
}else{
cout << Tr.query_sum(1,1,n,l,r).a[1][2]%p << '\n';
}
}
return 0;
}
2025.7.4
上午模拟赛，质量是这几次最好的一场了。（如果没有原题的话）
T2 我记得要两次背包，边界被 dbg 卡飞了+写丑了 成功死完了。
导致 lcx 拿到 rk1，我谢罪。
T4 是原，直接全文背诵了，看两版代码的编辑距离不超 50 字符。
T1
小奥数学题，没推出来觉得 T2 能冲正解。
边界先扔一边，注意到每次创造后只需要补 $m-k$ 个就可以再次创造。
而每次创造剩的 $m$ 个没有用，所以直接攻击。
总计要创造 $\frac{h}{m}$ 次，最后还会剩一点点，可以补足创造，也可以直接攻击。
然后几个比较自然的边界不讨论了。
有个方便的方法，再计算前先让 $h=h-m-k$ ，这样后续就不用考虑很多边角。
#include<iostream>
using namespace std;
int T,k,m,h;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--){
cin>>m>>k>>h;
if(h<=m){
cout << h << '\n';continue;
}
if(m<=k || h<m+k){
cout << m << '\n';continue;
}
h-=m+k;
cout << h/m*(m-k)+m+min(h%m,m-k) << '\n';
}
return 0;
}
T2
dbg 学长认真随的数据。
开题前一个小时没有读到 无限 太痛了。
背包体积反正是 $m$，我们贪心的想，同价值下肯定希望“金辉石”越多越好，所以先做一个完全背包。
定义 $f_{j}$ 表示质量为 $j$ 的物品含有最大的“金辉石”质量。
$$f_j=\max(f_{j},f_{j-w_i}+v_i)$$
直接把物品全替换掉。
然后再做一次完全背包就是答案。
两次背包的trick要记住了。
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=3e3+10;
int T,val[15],n,m;
struct Num{
int w,v;
}a[N];
int bel(int a,int b){
return val[((b*10-1)/a)+1]*a;
}
int c[N],f[N];
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>T;
while(T--){
memset(f,0,sizeof(f));memset(c,-0x3f,sizeof(c));
for(int i=1;i<=10;i++) cin>>val[i];
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i].w>>a[i].v;
}
f[0]=c[0]=0;
for(int i=1;i<=n;i++){
for(int j=a[i].w;j<=m;j++){
c[j]=max(c[j],c[j-a[i].w]+a[i].v);
}
}
for(int i=1;i<=m;i++){
for(int j=i;j<=m;j++){
if(c[i]>0) f[j]=max(f[j],f[j-i]+bel(i,c[i]));
}
}
cout << f[m] << '\n';
}
return 0;
}
T3
从未见过的 trick，太强了。
我们不在乎字符串的每一位是什么，只在乎它的格式或者形态或者相对位置。
维护相同值上一次出现的距离差，就直接维护了这个字符串的形态/格式。
然后做 KMP 或者 hash 即可。
#include<bits/stdc++.h>
#define N 1000010
using namespace std;
int T,C,cnt;
int n,m,a[N],b[N],s1[N],s2[N],lst[N],ans[N],nxt[N];
int is(int x,int l){return x<l ? x : 0;}
void init(){
cnt=0;
memset(s1,0,sizeof(s1));
memset(s2,0,sizeof(s2));
memset(ans,0,sizeof(ans));
memset(nxt,0,sizeof(nxt));
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>T>>C;
while(T--){
cin>>n>>m;
init();
memset(lst,0,sizeof(lst));
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
if(!lst[a[i]]) s1[i]=i;
else s1[i]=i-lst[a[i]];
lst[a[i]]=i;
}
memset(lst,0,sizeof(lst));
for(int i=1;i<=m;i++){
cin>>b[i];
}
for(int i=1;i<=m;i++){
if(!lst[b[i]]) s2[i]=i;
else s2[i]=i-lst[b[i]];
lst[b[i]]=i;
}
for(int i=2,j=0;i<=m;i++){
while(j && is(s2[i],j+1)!=is(s2[j+1],j+1)) j=nxt[j];
if(is(s2[i],j+1)==is(s2[j+1],j+1)) j++;
nxt[i]=j;
}
for(int i=1,j=0;i<=n;i++){
while(j && is(s1[i],j+1)!=is(s2[j+1],j+1)) j=nxt[j];
if(is(s1[i],j+1)==is(s2[j+1],j+1)) j++;
if(j==m){
ans[++cnt]=i-j+1;
j=nxt[j];
}
}
cout << cnt << '\n';
for(int i=1;i<=cnt;i++){
cout << ans[i] << ' ';
}cout << '\n';
}
return 0;
}
T4
扔个这个自己讲题的时候也憋不住笑了吗
题解我发 S2OJ 了，这里的是 copy 的。
观察题目可以发现，我们能想出两种暴力做法：
暴力模拟所有操作，询问时搜索，单次是 $O(1)$ 和 $O(n)$ 的。
离线询问按降序排序，每次回答时重跑时间轴之前的操作，然后拿可撤销并查集维护连通性，单次是 $O(n\log n)$ 和 $O(\log n)$ 的。
发现这两种暴力从截然不同的角度出发，一个枚举边，一个枚举询问。
复杂度分别是 $O(1)$ 修改，$O(n)$ 查询 和 $O(n\log n)$ 修改，$O(\log n)$ 查询。
所以我们使用分块将这平衡一下。
简单而言，定义一个阈值 $B$，当积压的操作达到 $B$ 的时候处理当前所有操作，同样使用可撤销并查集维护一下。
我们会把操作分成 $\frac{q}{B}$ 块，每块最多 $B$ 个操作。
每个操作有 $O(B)$ 条边将被修改，所以修改的复杂度是 $O(B\log n)$ 的。
有 $O(B)$ 次查询，复杂度是 $O(B\log n)$ 的。
同时需要把无影响的边按边权顺序放入并查集，这个是 $O(m\log n)$ 的。
将 B 带入上面的暴力复杂度，得到最后式子是 $O(qB\log n + \frac{qm\log m}{B})$ ，$B$ 取个 $\sqrt {mlogn}$ 据说跑的飞快，但是我 $B$ 取了个附近的定值，也跑过了。
同学说第一条暴力对下文没有关联，也跟算法没有关联。
其实是有的，分块平衡复杂度的必要条件应该是可以 $O(1)$ 修改和 $O(n)$ 查询的同时，能做到 $O(n)$ 修改和 $O(1)$ 查询。
注：这里的 $O(1)$ 广泛地指能接受的复杂度，像上文第二个暴力带 log 的原因是要上并查集。
目前没见到条件以外能用分块的题。
两个暴力是有联系的，两个暴力的复杂度互相依赖。
比如第二个暴力的复杂度可以认为是修改 n 次，也就是 n 次 $O(1)$ 。
分块平衡了其中一个暴力的复杂度
不过第一条暴力对下文确实没啥关联，因为我们的操作分块是对第二个暴力做平衡。
直白地说，如果你第一个暴力的修改是 $O(k)$ 的，对应的第二个暴力的复杂度是 $O(nk)$ 的，如果 $k$ 很大，你怎么分块平衡它。
2025.7.5
hash+kmp+Manacher
hash
前面一个小时被 hash 各种创飞……
PAL-Palindromes
发现如果 AB 是可行解的话，那么 BA 也是可行解。
令 a 的哈希值为 a，长度为 lena，b 的哈希值为 b，长度为 lenb。
所以有 $a\times p^{lenb}+b=b\times p^{lena}+a$
移项，然后可以得到 $\frac{a}{p^{lena}-1}=\frac{b}{p^{lenb}-1}$
把这个扔进桶里，计数即可。
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define ll long long
using namespace std;
using namespace __gnu_pbds;
int n,l;
string s;
ll ans;
constexpr int P=131,p1=998244353,p2=1e9+7;
int qpow(int a,int b,const int &p){
int res=1;
while(b){
if(b&1) res=(ll)res*a%p;
b>>=1,a=(ll)a*a%p;
}
return res;
}
int hash1(const string &s){
ll a=0,b=1;
for(char ch:s){
b=b*P%p1;
a=(a*P+ch)%p1;
}
return a*qpow(b-1,p1-2,p1)%p1;
}
int hash2(const string &s){
ll a=0,b=1;
for(char ch:s){
b=b*P%p2;
a=(a*P+ch)%p2;
}
return a*qpow(b-1,p2-2,p2)%p2;
}
struct pair_hash{
size_t operator()(const pair<int,int> &x)const{
size_t seed=0;
seed^=hash<int>{}(x.first)+0x9e3779b9+(seed<<6)+(seed>>2);
seed^=hash<int>{}(x.second)+0x9e3779b9+(seed<<6)+(seed>>2);
return seed;
}
};
gp_hash_table<pair<int,int>,int,pair_hash> mp;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>l>>s;
ans+=mp[make_pair(hash1(s),hash2(s))]++;
}
cout << 2*ans+n;
return 0;
}
OKR-A Horrible Poem
周期要求是恰好匹配的，所以对于一个长度的因数是较小的，粗略是根号的。
所以线性筛，筛出所有质因数，然后直接分解枚举所有长度就行。
复杂度是 $q\sqrt n$ ，不知道咋能过的。
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
constexpr int N = 5e5+10;
constexpr int base = 37;
vector<int> pri;
bool prime[N];
int g[N];
ull table[N],fac[N];
void init(){
for(int i=2;i<=5e5+1;i++){
if(!prime[i]){
pri.push_back(i);
g[i]=i;
}
for(int p:pri){
if(p*i>5e5+1) break;
prime[i*p]=1;
g[p*i]=p;
if(i%p==0) break;
}
}
}
int n,m,ans,len;
string s;
int query(int l,int r){
return table[r]-table[l-1]*fac[r-l+1];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
init();
cin>>n>>s;s=' '+s;
fac[0]=1;
for(int i=1;i<=n;i++){
table[i]=table[i-1]*base+s[i]-'a'+1;
}
for(int i=1;i<=n;i++){
fac[i]=base*fac[i-1];
}
cin>>m;
for(int i=1;i<=m;i++){
int l,r;
cin>>l>>r;
ans=len=r-l+1;
while(len>1){
if(query(l+ans/g[len],r)==query(l,r-ans/g[len]))
ans/=g[len];
len/=g[len];
}
cout << ans << '\n';
}
return 0;
}
等差子序列
发现如果在权值的角度看，不满足条件的情况只有插入一个值时，值的两侧是回文串。
那么把哈希值扔权值线段树上维护一下，维护从左至右和从右至左两种hash值，直接比对就行。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+10;
const int base=13331;
const int p=1e9+7;
int T,n,a[N];
ll pw[N];
struct Tree{
#define ls u<<1
#define rs u<<1|1
ll tr[N<<2][2];
ll len=0;
void init(){
memset(tr,0,sizeof(tr));
}
void pushup(int u,int l,int r){
int mid=(l+r)>>1;
tr[u][0]=(tr[ls][0]*pw[r-mid]%p+tr[rs][0])%p;
tr[u][1]=(tr[ls][1]+tr[rs][1]*pw[mid-l+1]%p)%p;
}
void update(int u,int l,int r,int x){
if(l==r){
tr[u][0]=tr[u][1]=1;
return ;
}
int mid=(l+r)>>1;
if(x<=mid) update(ls,l,mid,x);
else update(rs,mid+1,r,x);
pushup(u,l,r);
}
ll query(int u,int l,int r,int x,int y,int opt){
ll res=0;
if(l>=x && r<=y){
res=(res+tr[u][opt]*pw[len]%p)%p;
len+=(r-l+1);
return res;
}
int mid=(l+r)>>1;
if(opt==0){
if(mid<y) res=(res+query(rs,mid+1,r,x,y,opt))%p;
if(x<=mid) res=(res+query(ls,l,mid,x,y,opt))%p;
}else{
if(x<=mid) res=(res+query(ls,l,mid,x,y,opt))%p;
if(mid<y) res=(res+query(rs,mid+1,r,x,y,opt))%p;
}
return res;
}
}Tr;
int main(){
cin>>T;
pw[0]=1;
for(int i=1;i<=5e5;i++){
pw[i]=pw[i-1]*base%p;
}
while(T--){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
bool f=false;
for(int i=1;i<=n;i++){
Tr.update(1,1,n,a[i]);
int l=min(a[i],n-a[i]+1);
Tr.len=0;
ll res1=Tr.query(1,1,n,a[i]-l+1,a[i]+l-1,0);
Tr.len=0;
ll res2=Tr.query(1,1,n,a[i]-l+1,a[i]+l-1,1);
if(res1!=res2){
f=true;
break;
}
}
if(f) cout << "Y\n";
else cout << "N\n";
Tr.init();
}
return 0;
}
Tasowanie
二分+hash
去二分下一个不同的位置的hash，判断大小，然后贪心即可。
但这个太不优雅了，我们选择更自然地方法：后缀数组。
后缀数组能维护每一个后缀的排名，刚好是我们需要的信息。
中间分割两个字符串的要是大于字符集的，要不然就加到序列里去了。
#include<bits/stdc++.h>
using namespace std;
const int N = 4e5+10;
int n,m;
struct SufArr{
int x[N],y[N],s[N],cnt[N],sa[N],rk[N],len;
void build(){
for(int i=1;i<=len;i++){
x[i]=s[i];
cnt[x[i]]++;
}
for(int i=2;i<=3001;i++){
cnt[i]+=cnt[i-1];
}
for(int i=len;i>=1;i--){
sa[cnt[x[i]]--]=i;
}
for(int k=1;k<=len;k<<=1){
int num=0;
for(int i=len-k+1;i<=len;i++){
y[++num]=i;
}
for(int i=1;i<=len;i++){
if(sa[i]>k){
y[++num]=sa[i]-k;
}
}
for(int i=1;i<=m;i++) cnt[i]=0;
for(int i=1;i<=len;i++) cnt[x[i]]++;
for(int i=2;i<=m;i++) cnt[i]+=cnt[i-1];
for(int i=len;i>=1;i--){
sa[cnt[x[y[i]]]--]=y[i];
y[i]=0;
}
swap(x,y);
x[sa[1]]=1,num=1;
for(int i=2;i<=len;i++)
x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) ? num : ++num;
if(num==len) break;
m=num;
}
for(int i=1;i<=len;i++){
rk[sa[i]]=i;
}
}
}SA;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>SA.s[i];
}
cin>>m;
for(int i=1;i<=m;i++){
cin>>SA.s[i+n+1];
}
SA.s[1+n]=3001;
SA.s[2+m+n]=3001;
SA.len=n+m+2;
SA.build();
int id1=1,id2=n+2;
for(int i=1;i<SA.len;i++){
if(SA.rk[id1]<SA.rk[id2]){cout << SA.s[id1] << ' ';id1++;}
else {cout << SA.s[id2] <<' ';id2++;}
if(id1==n+1){
for(int j=id2;j<SA.len;j++){
cout << SA.s[j] << ' ';
}break;
}
if(id2==SA.len+1){
for(int j=id1;j<=n;j++){
cout << SA.s[j] << ' ';
}break;
}
}
return 0;
}
headless_piston 的 hash+二分 跑到最优解了？我直接贺一个 $O(n)$ 的后缀数组来！
常数太大，仍旧跑不过……
KMP
String Set Queries
不知道把这个扔这里合不合适啊。
题解是 启发式合并AC自动机 我瞎取的
就是把删除的串扔进新的 AC 自动机，利用 AC 自动机可减性。
当两个AC自动机大小相同时，暴力合并。
全局最多 $\log m$ 个AC自动机，复杂度可以接受。
但这显然不是我们想要的。
我们发现关键性质：字符串总长不超过 3e5。
对于所有字符串，大于 $\sqrt n$ 的只有 $\sqrt n$ 个，而小于 $\sqrt n$ 的我们能接受直接遍历。
所以！将小于 $\sqrt n$ 的扔 Trie 上，大于 $\sqrt n$ 的挨个 KMP 一下。
那么本题我们就用优美的根号分治做完了。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e5+10;
int n;
struct Trie{
struct node{
int son[26];
int cnt;
}tr[N];
int tot=0;
void insert(char *s,int val){
int u=0;
for(int i=0;s[i];i++){
char ch=s[i];
int &son=tr[u].son[ch-'a'];
if(!son) son=++tot;
u=son;
}
tr[u].cnt+=val;
}
int query(char *s){
int u=0,res=0;
for(int i=0;s[i];i++){
int c=s[i]-'a';
if(!tr[u].son[c]) break;
u=tr[u].son[c];
res+=tr[u].cnt;
}
return res;
}
}T;
struct KMP{
int nxt[N];
void build(const string &s,int len){
memset(nxt,0,sizeof(nxt));
int i=0,j=-1;nxt[0]=-1;
while(i<len){
if(j==-1 || s[i]==s[j]) nxt[++i]=++j;
else j=nxt[j];
}
}
int query(string s,char *qry){
int res=0;
int lens=s.size(),len=strlen(qry);
build(s,s.size());
for(int i=0,j=0;i<len;i++){
while(j>0 && qry[i]!=s[j]) j=nxt[j];
if(qry[i]==s[j]) j++;
if(j==lens){
res++;
j=nxt[j];
}
}
return res;
}
}kmp;
string que[50];
char s[N];
int cnt,val[50];
int main(){
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
scanf("%d",&n);
for(int i=1,op;i<=n;i++){
scanf("%d%s",&op,s);
int len=strlen(s);
if(op==1 || op==2){
int v=(op==1 ? 1 : -1);
if(len<=1000){
T.insert(s,v);
}else{
que[cnt]=string(s);
val[cnt++]=v;
}
}else{
ll ans=0;
for(int i=0;i<len;i++){
ans+=T.query(s+i);
}
for(int i=0;i<cnt;i++){
if(que[i].length()>len) continue;
ans+=kmp.query(que[i],s)*val[i];
}
printf("%lld\n",ans);
fflush(stdout);
}
}
return 0;
}
SZA-Template
我们定义 $f_i$ 表示第 $i$ 个位置至少需要多长的印章。
发现我们只有两种转移：$f_i=i$ 或者 $f_i=f_{nxt_i}$
要么全印了，要么之前有一个 nxt 可以覆盖到。
第二个取到的条件 $i_{nxt_i}\to i$ 中有值，所以开个桶，看看能不能覆盖到即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
string s;
int n,f[N],vis[N],nxt[N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>s;
s=' '+s;
n=s.length()-1;
for(int i=2,j=0;i<=n;i++){
while(j>0 && s[j+1]!=s[i]) j=nxt[j];
if(s[j+1]==s[i]) j++;
nxt[i]=j;
}
f[1]=1;vis[1]=1;
for(int i=2;i<=n;i++){
f[i]=i;
if(vis[f[nxt[i]]]>=i-nxt[i]) f[i]=f[nxt[i]];
vis[f[i]]=i;
}
cout << f[n];
return 0;
}
GT考试
我们定义 $f_{i,j}$ 表示在第 $i$ 个位置上匹配的串长度变成 $j$ 的方案数。
然后定义 $g_{k,j}$ 表示从长度为 $k$ 的匹配串变成长度为 $j$ 的匹配串的方案数。
有转移：$f_{i,j}=\sum_{k=0}^{m-1}f_{i-1,k}\times g_{k,j}$
$g$ 可以用 KMP 求出。
然后发现是矩阵，直接上快速幂优化一下即可。
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int N=25;
int n,m,p;
char s[N];
int nxt[N];
int ans=0;
void update(int &x,int y){
x+=y;
while(x>=p) x-=p;
}
struct node{
int n,a[N][N];
node(int m=0){n=m,memset(a,0,sizeof(a));}
void operator ! (){
for(int i=0;i<n;i++) a[i][i]=1;
}
node operator * (const node &b) const{
node res(n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
for(int k=0;k<n;k++){
update(res.a[i][k],1ll*a[i][j]*b.a[j][k]%p);
}
}
}
return res;
}
node operator ^ (ll b) const{
node ret(n),x=*this;!ret;
for(ll p=b;p;p>>=1,x=x*x) if(p&1) ret=ret*x;
return ret;
}
};
node kmp(){
nxt[1]=0;
int j=0;
for(int i=2;i<=m;i++){
while(j>0 && s[j+1]!=s[i]) j=nxt[j];
if(s[j+1]==s[i]) j++;
nxt[i]=j;
}
node res(m);
for(int i=0;i<m;i++){
for(char c='0';c<='9';c++){
int j=i;
while(j && s[j+1]!=c) j=nxt[j];
if(s[j+1]==c) ++j;
res.a[i][j]++;
}
}
return res;
}
void print(node res){
for(int i=0;i<m;i++){
for(int j=0;j<m;j++){
cout<<res.a[i][j]<<' ';
}cout<<'\n';
}
}
int main(){
cin>>n>>m>>p;
for(int i=1;i<=m;i++){
cin>>s[i];
}
node a=kmp();
a=a^n;
// print(a);
for(int i=0;i<m;i++) update(ans,a.a[0][i]);
cout<<ans;
return 0;
}
Manacher
拉拉队排练
因为要求奇回文串，所以不添加额外字符做 Manacher 即可。
然后拿个桶计数，倒着扫一遍然后快速幂一下。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
constexpr int N = 1e6+10;
constexpr int p = 19930726;
ll n,pos[N<<1],vis[N<<1];
ll sum,ans=1,k;
string s;
ll qpow(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=res*a%p;
b>>=1;a=a*a%p;
}
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>k>>s;
s=' '+s;
for(ll i=1,r=0,mid=0;i<(int)s.length();i++){
if(i<=r) pos[i]=min(pos[mid*2-i],r-i);
while(s[i-pos[i]]==s[i+pos[i]]) ++pos[i];
if(pos[i]+i-1>r) r=pos[i]+i-1,mid=i;
vis[pos[i]*2-1]++;
}
if(n%2==0) n--;
for(ll i=n;i>=1;i-=2){
sum+=vis[i];
if(sum>k){
ans=ans*qpow(i,k)%p;
break;
}else{
ans=ans*qpow(i,sum)%p;
k-=sum;
}
}
if(sum<k) cout << -1;
else cout << ans;
return 0;
}
最长双回文串
Manacher 的时候记一下以 $i$ 为左端点的最长回文串和以 $i$ 为右端点的最长回文串。
最后答案就是这俩拼起来。
Manacher 的途中跟随统计一下就行。
最后需要在重新扫一遍。
#include<bits/stdc++.h>
#define B 600
using namespace std;
const int N = 3e5+10;
char s[N<<1];
int cnt,pos[N];
int nl[N],nr[N],ans;
void read(){
char c=getchar();
s[0]='!';
s[++cnt]='#';
while(c<'a' || c>'z') c=getchar();
while(c>='a' && c<='z'){
s[++cnt]=c;
s[++cnt]='#';
c=getchar();
}
s[++cnt]='$';
}
void manacher(){
for(int i=1,r=0,mid=0;i<=cnt;i++){
if(i<r) pos[i]=min(pos[mid*2-i],r-i);
else pos[i]=1;
while(s[i-pos[i]]==s[i+pos[i]]) ++pos[i];
if(pos[i]+i>r) r=pos[i]+i,mid=i;
nr[i+pos[i]-1] = max(nr[i+pos[i]-1],pos[i]-1);
nl[i-pos[i]+1] = max(nl[i-pos[i]+1],pos[i]-1);
}
}
int main(){
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
read();
manacher();
for(int i=cnt;i>=1;i-=2) nr[i]=max(nr[i],nr[i+2]-2);
for(int i=1;i<=cnt;i+=2) nl[i]=max(nl[i],nl[i-2]-2);
for(int i=1;i<=cnt;i+=2) if(nl[i]&&nr[i]) ans=max(ans,nl[i]+nr[i]);
cout << ans;
return 0;
}
2025.7.6
搜索专题
不想写了，感觉有用的也就 Astar 和 折半搜索。
觉得考场上有这个思想就很好了，别说写了，都不知道啥时候考。
各种剪枝技巧也没法扩展啊，还是重在思想吧。
给 dbg 学长都讲无语了。
所以我拒绝了吃屎，选择学习：扫描线
2025.7.7
今天就当没发生过，我也没在今天活着。
2025.7.8
最小生成树+拓扑+最短路
P3645 雅加达的摩天楼
最短路，但是没有用到除 BFS 以外的任何算法。
直接连边然后 01 BFS 肯定炸空间，那么不连边只保留状态（用bitset）。
发现我们做完了。其实是根号分治，具体分析可以参考我 根号算法 那篇文章。
P4180 严格次小生成树
先最小生成树，然后尝试替换掉某一条树边。
发现只保留最大值是不够的，还需要保留次大值。
无修改，所以倍增维护一下最大值和次大值即可。
#include<bits/stdc++.h>
#define ll long long
#define inf 2e9
using namespace std;
const int N = 1e5+10;
int n,m,fa[N];
ll sum,ans=1e18;
int find(int x){return fa[x]==x ? x : fa[x]=find(fa[x]);}
struct Edge{
int u,v,w;
bool operator <(const Edge &a)const{
return w<a.w;
}
}e[N<<3];
bool vis[N<<3];
struct node{
int v,w;
};
vector<node> G[N];
void Kruskal(){
for(int i=1;i<=n;i++) fa[i]=i;
sort(e+1,e+1+m);
for(int i=1;i<=m;i++){
int x=e[i].u,y=e[i].v;
int fx=find(x),fy=find(y);
if(fx==fy) continue;
sum+=e[i].w;vis[i]=1;
G[e[i].u].push_back({e[i].v,e[i].w});
G[e[i].v].push_back({e[i].u,e[i].w});
fa[fy]=fx;
}
}
int f[N][30],g[N][30],h[N][30],dep[N];
void dfs(int u,int father,int w){
dep[u]=dep[father]+1;
f[u][0]=father;
g[u][0]=w;h[u][0]=-inf;
for(int i=1;i<=20;i++){
f[u][i]=f[f[u][i-1]][i-1];
g[u][i]=max(g[u][i-1],g[f[u][i-1]][i-1]);
h[u][i]=max(h[u][i-1],h[f[u][i-1]][i-1]);
if(g[u][i-1]>g[f[u][i-1]][i-1]) h[u][i]=max(h[u][i],g[f[u][i-1]][i-1]);
else if(g[u][i-1]<g[f[u][i-1]][i-1]) h[u][i]=max(h[u][i],g[u][i-1]);
}
for(auto to:G[u]){
int v=to.v,w=to.w;
if(v==father) continue;
dfs(v,u,w);
}
}
int LCA(int x,int y){
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 qmax(int x,int y,int mx){
int res=-inf;
for(int i=19;i>=0;i--){
if(dep[f[x][i]]>=dep[y]){
if(g[x][i]!=mx) res=max(res,g[x][i]);
else res=max(res,h[x][i]);
x=f[x][i];
}
}
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1,u,v,w;i<=m;i++){
cin>>u>>v>>w;
e[i]={u,v,w};
}
Kruskal();
dfs(1,0,0);
for(int i=1;i<=m;i++){
if(vis[i]) continue;
int u=e[i].u,v=e[i].v,w=e[i].w;
int lca=LCA(u,v);
int mx1=qmax(u,lca,w);
int mx2=qmax(v,lca,w);
ans=min(ans,sum-max(mx1,mx2)+w);
}
cout << ans;
return 0;
}
P4197 Peaks
Tips：主席树开 32 倍空间及以上，变量名避免使用 tr 和 rt……
Kruskal 重构树。
边权从小到大排序，然后重构树。一棵子树的所有叶子节点都是能到达的山。
所以考虑倍增维护一下最高能到哪个节点，然后主席树维护区间第 k 大值即可。
#include<bits/stdc++.h>
#define N 100010
#define M 500010
using namespace std;
int n,m,q,h[N],b[N];
struct Edge{
int u,v,w;
bool operator < (const Edge &a)const{
return w<a.w;
}
}e[M];
int val[N<<1],fa[N<<1],tot;
int find(int x){return fa[x]==x ? x : fa[x]=find(fa[x]);}
vector<int> G[N<<1];
int f[N<<1][30];
void kruskal(){
for(int i=1;i<=2*n;i++) fa[i]=i;
sort(e+1,e+1+m);tot=n;
for(int i=1;i<=m;i++){
int fx=find(e[i].u),fy=find(e[i].v);
if(fx==fy) continue;
fa[fx]=fa[fy]=++tot;
G[tot].push_back(fx);G[tot].push_back(fy);
f[fx][0]=f[fy][0]=tot;val[tot]=e[i].w;
}
}
int ls[N<<5],rs[N<<5],rt[N<<5],tr[N<<5],cnt,num,len,L[N<<1],R[N<<1];
void update(int &now,int pre,int l,int r,int x){
if(!now) now=++cnt;tr[now]=tr[pre]+1;
if(l==r) return;
int mid=(l+r)>>1;
if(x<=mid){rs[now]=rs[pre];update(ls[now],ls[pre],l,mid,x);}
else{ls[now]=ls[pre];update(rs[now],rs[pre],mid+1,r,x);}
}
int query(int u,int lim,int k){
int l=1,r=len;
for(int i=19;i>=0;i--){
if(f[u][i] && val[f[u][i]]<=lim) u=f[u][i];
}
int x=rt[L[u]-1],y=rt[R[u]];
if(tr[y]-tr[x]<k) return -1;
while(l<r){
int tmp=tr[rs[y]]-tr[rs[x]];
int mid=(l+r)>>1;
if(tmp>=k) x=rs[x],y=rs[y],l=mid+1;
else x=ls[x],y=ls[y],r=mid,k-=tmp;
}
return b[r];
}
void dfs(int u){
for(int i=1;i<=20;i++){
f[u][i]=f[f[u][i-1]][i-1];
}
L[u]=++num;
if(u<=n) update(rt[num],rt[num-1],1,len,h[u]);
else rt[num]=rt[num-1];
for(int v:G[u]) dfs(v);
R[u]=num;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=n;i++){cin>>h[i];b[i]=h[i];}
for(int i=1;i<=m;i++){
int u,v,w;cin>>u>>v>>w;
e[i]={u,v,w};
}
sort(b+1,b+1+n);
len=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;i++){h[i]=lower_bound(b+1,b+1+len,h[i])-b;}
kruskal();
for(int i=1;i<=tot;i++) if(!L[i]) dfs(find(i));
for(int i=1,u,x,k;i<=q;i++){
cin>>u>>x>>k;
cout << query(u,x,k) << '\n';
}
return 0;
}
P2272 最大半连通子图
Trick：tarjan 缩点后的序列编号是逆序拓扑。
为数不多的码量较小的题。
先缩点然后变成 DAG。
DAG 上 dp 找 最长链就是对的。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+10;
int n,m,p;
vector<int> G1[N],G2[N];
int dfn[N],dfx,low[N],scc,bel[N],siz[N];
bool vis[N];
stack<int> sta;
void tarjan(int u){
dfn[u]=low[u]=++dfx;
vis[u]=1;sta.push(u);
for(int v:G1[u]){
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}else if(vis[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
scc++;
while(sta.top()!=u){
int t=sta.top();sta.pop();
vis[t]=0;
bel[t]=scc;
siz[scc]++;
}
vis[u]=0;bel[u]=scc;siz[scc]++;sta.pop();
}
}
int f[N],g[N],use[N],ans1,ans2;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m>>p;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
G1[u].push_back(v);
}
for(int i=1;i<=n;i++){
if(!dfn[i]) tarjan(i);
}
for(int u=1;u<=n;u++){
f[u]=siz[u];g[u]=1;
for(int v:G1[u]){
if(bel[u]==bel[v]) continue;
G2[bel[u]].push_back(bel[v]);
}
}
for(int u=scc;u>=1;u--){
for(int v:G2[u]){
if(use[v]==u) continue;
use[v]=u;
if(f[v]<f[u]+siz[v]){
f[v]=f[u]+siz[v];
g[v]=g[u];
}else if(f[v]==f[u]+siz[v]){
g[v]+=g[u];
g[v]%=p;
}
}
}
for(int i=1;i<=scc;i++){
if(f[i]>ans1){
ans1=f[i];
ans2=g[i];
}else if(f[i]==ans1){
ans2+=g[i];
ans2%=p;
}
}
cout << ans1<<'\n'<<ans2;
return 0;
}
2025.7.9
今天不打算写太多题了，想写写笔记整理一下。
P4819 杀人游戏
缩点后 DAG 上询问入度为 0 的点显然正确。
但是有特殊情况：如果有一个入度为 0 的孤点，我们就没必要去询问他。
因为我们可以使用排除法给它排除掉。所以这为啥是紫？
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3e5+10;
int n,m;
map<pair<int,int>,bool> mp;
vector<int> vec[N];
vector<int> G[N];
int low[N],dfn[N],tot,cnt,scc[N],siz[N],in[N];
stack<int> sta;
struct Edge{
int u,v;
}e[N];
bool vis[N];
void tarjan(int u){
low[u]=dfn[u]=++tot;
vis[u] = 1;
sta.push(u);
for(int v:vec[u]){
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}else if(vis[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
cnt++;
// vis[u]=0;
// scc[u]=cnt;
// siz[cnt]++;
while(sta.top()!=u){
scc[sta.top()]=cnt;
vis[sta.top()]=0;
siz[cnt]++;
sta.pop();
}
vis[u]=0;
scc[u]=cnt;
siz[cnt]++;
sta.pop();
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
e[i].u=u,e[i].v=v;
if(mp[make_pair(u,v)]) continue;
mp[make_pair(u,v)]=1;
vec[u].push_back(v);
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
tarjan(i);
}
}
mp.clear();
for(int i=1;i<=m;i++){
int u=scc[e[i].u],v=scc[e[i].v];
if(u!=v){
if(mp[make_pair(u,v)]) continue;
mp[make_pair(u,v)]=1;
G[u].push_back(v);
in[v]++;
}
}
double ans=0;
for(int i=1;i<=cnt;i++){
if(in[i]==0) ans++;
}
for(int i=1;i<=cnt;i++){
if(in[i]==0 && siz[i]==1){
bool f=true;
for(int v:G[i]){
if(in[v]<=1){
f=false;
break;
}
}
if(f){
ans--;
break;
}
}
}
cout<<fixed<<setprecision(6)<<(1.0-ans/(1.0*n));
return 0;
}
本阶段总结
就以不同学长讲课划分阶段吧。
第一阶段的学长是：Acestar 学长。让我们感谢学长的陪伴与教导。
内容
单调队列优化dp+并查集+字符串+数据结构+图论+搜索。怎么还在讲搜索啊？！
感觉学了很多题，也有很多新 trick，收获最大的可能就是根号分治的相关内容吧。
下次做题一定先想根号复杂度。
2025.7.10
放假了，宅家打了一上午洲和一下午第五人格。
空调开着太潮了，关了太热了。
还没过崩铁新剧情。
2025.7.11
回来就是模拟赛，撒尼姆啊？
T1 是奇妙栈题，下次得多考虑这些奇妙的东西了。
T2 是树形 dp，没看出来，确实还得多练。
T3 是概率计数，根本不会啊。
T4 是边分治+李超树维护斜率。
题单没做，一道题是规程。
2025.7.12
扫描线啊，根本不会啊。做的全是原题，就不在此赘述了。
晚上没教练，高强度刷知乎半个晚自习。
2025.7.13
树上技巧，听懂的最多的一次。
P5290 十二省联考 2019 春节十二响
形式化题意：树上染色，链上的颜色不能重复，染一种颜色的代价是相同颜色的最大点权。最小化整棵树染色代价之和。
什么情况下是最优的：一个节点的所有儿子节点的子树的颜色集合应当尽量重合。
直接开个堆，然后做启发式合并即可。
PS：有个想法来个老哥实现或者hack，我不会。
颜色数量上限是最长链，提出最长链，给最长链上的点权排序。
然后散链依次在最长链上二分插入一些位置。
可能是个大分讨，也非常的史，不如启发式合并优美。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5+10;
int n,w[N],f[N];
ll ans=0;
vector<int> G[N],tmp;
priority_queue<int> q[N];
void merge(int x,int y){
if(q[x].size()<q[y].size()) swap(q[x],q[y]);
while(!q[y].empty()){
tmp.push_back(max(q[y].top(),q[x].top()));
q[y].pop();q[x].pop();
}
while(tmp.size()){
q[x].push(tmp.back());tmp.pop_back();
}
}
void dfs(int u){
for(int v:G[u]){
dfs(v);
merge(u,v);
}
q[u].push(w[u]);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>w[i];
}
for(int i=2;i<=n;i++){
cin>>f[i];
G[f[i]].push_back(i);
}
dfs(1);
while(!q[1].empty()) ans+=q[1].top(),q[1].pop();
cout << ans;
return 0;
}
P3979 遥远的国度
画画图，类似换根的操作把树划分开，然后发现以 1 为定根就行。
需要刨出 rt 到 1 的点，用树剖然后操作一下就行。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+10;
int n,m,a[N],rt;
vector<int> G[N];
int fa[N],dfn[N],siz[N],hson[N],dfx,top[N],dep[N],rnk[N];
void dfs1(int u){
dep[u]=dep[fa[u]]+1;siz[u]=1;
for(int v:G[u]){
if(v==fa[u]) continue;
fa[v]=u;
dfs1(v);
siz[u]+=siz[v];
if(siz[hson[u]]<siz[v]) hson[u]=v;
}
}
void dfs2(int u,int tp){
top[u]=tp;dfn[u]=++dfx,rnk[dfx]=u;
if(!hson[u]) return ;
dfs2(hson[u],tp);
for(int v:G[u]){
if(v==hson[u] || v==fa[u]) continue;
dfs2(v,v);
}
}
struct SegTree{
#define ls u<<1
#define rs u<<1|1
#define mid ((l+r)>>1)
ll tr[N<<2],tag[N<<2];
void pushup(int u){
tr[u]=min(tr[ls],tr[rs]);
}
void upd(int u,ll k){
tr[u]=tag[u]=k;
}
void build(int u,int l,int r){
if(l==r){tr[u]=a[rnk[l]];return;}
build(ls,l,mid);build(rs,mid+1,r);
pushup(u);
}
void pushdown(int u){
if(!tag[u]) return ;
upd(ls,tag[u]);upd(rs,tag[u]);
tag[u]=0;
}
void modify(int u,int l,int r,int x,int y,ll k){
if(l>=x && r<=y){upd(u,k);return;}
pushdown(u);
if(x<=mid) modify(ls,l,mid,x,y,k);
if(mid<y) modify(rs,mid+1,r,x,y,k);
pushup(u);
}
ll query(int u,int l,int r,int x,int y){
if(l>=x && r<=y) return tr[u];
pushdown(u);
ll res=1e18;
if(x<=mid) res=min(res,query(ls,l,mid,x,y));
if(mid<y) res=min(res,query(rs,mid+1,r,x,y));
return res;
}
#undef ls
#undef rs
#undef mid
}Tr;
void modify(int x,int y,int k){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
Tr.modify(1,1,n,dfn[top[x]],dfn[x],k);
x=fa[top[x]];
}
if(dfn[x]>dfn[y]) swap(x,y);
Tr.modify(1,1,n,dfn[x],dfn[y],k);
}
int find(int x){
if(x==rt) return -1;
if(dfn[x]>=dfn[rt] || dfn[x]+siz[x]-1 < dfn[rt]) return 0;
int u=rt;
while(top[u]!=top[x]){
if(fa[top[u]]==x) return top[u];
u=fa[top[u]];
}
return hson[x];
}
ll query(int x){
int u=find(x);
if(u==-1) return Tr.tr[1];
else if(u==0) return Tr.query(1,1,n,dfn[x],dfn[x]+siz[x]-1);
else{
ll ans=Tr.query(1,1,n,1,dfn[u]-1);
if(dfn[u]+siz[u]-1!=n) ans=min(ans,Tr.query(1,1,n,dfn[u]+siz[u],n));
return ans;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1,u,v;i<n;i++){
cin>>u>>v;
G[u].push_back(v);G[v].push_back(u);
}
for(int i=1;i<=n;i++) cin>>a[i];
cin>>rt;dfs1(rt);dfs2(rt,rt);
Tr.build(1,1,n);
for(int i=1,op,x;i<=m;i++){
cin>>op>>x;
if(op==1){
rt=x;
}else if(op==2){
int y,v;cin>>y>>v;
modify(x,y,v);
}else{
cout << query(x) << '\n';
}
}
return 0;
}
P7735 NOI2021 轻重边
史诗级史题，超级无敌难写。
首先题意转化：给点颜色覆盖，求相邻的点的相同颜色的数量。
然后就可以写了，发现一堆细节。然后就一直调调调吧，注意一下链的合并的左右顺序。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+10;
int T,n,m;
vector<int> G[N];
int dep[N],fa[N],dfn[N],dfx,top[N],siz[N],hson[N];
void dfs1(int u){
dep[u]=dep[fa[u]]+1;
siz[u]=1;
for(int v:G[u]){
if(v==fa[u]) continue;
fa[v]=u;
dfs1(v);
siz[u]+=siz[v];
if(siz[hson[u]]<siz[v]) hson[u]=v;
}
}
void dfs2(int u,int tp){
top[u]=tp;dfn[u]=++dfx;
if(!hson[u]) return ;
dfs2(hson[u],tp);
for(int v:G[u]){
if(v==fa[u] || v==hson[u]) continue;
dfs2(v,v);
}
}
struct Tree{
int sum,lc,rc;
Tree(int s=0,int l=0,int r=0):sum(s),lc(l),rc(r){}
}tr[N<<2];
struct SegTree{
#define ls u<<1
#define rs u<<1|1
#define mid ((l+r)>>1)
int tag[N<<2];
void init(){
memset(tag,0,sizeof(tag));
for(int i=0;i<(N<<2);i++) tr[i]=Tree();
}
void upd(int u,int k,int len){
tr[u]=Tree(len,k,k);
tag[u]=k;
}
void pushdown(int u,int l,int r){
if(!tag[u]) return;
upd(ls,tag[u],mid-l);
upd(rs,tag[u],r-mid-1);
tag[u]=0;
}
void modify(int u,int l,int r,int x,int y,int k){
if(l>=x && r<=y){
upd(u,k,r-l);return;
}
pushdown(u,l,r);
if(x<=mid) modify(ls,l,mid,x,y,k);
if(mid<y) modify(rs,mid+1,r,x,y,k);
tr[u]=Tree(tr[ls].sum+tr[rs].sum+(tr[ls].rc==tr[rs].lc),tr[ls].lc,tr[rs].rc);
}
Tree query(int u,int l,int r,int x,int y){
if(l>=x && r<=y){
return tr[u];
}
Tree r1=Tree(),r2=Tree();
pushdown(u,l,r);
if(x<=mid) r1=query(ls,l,mid,x,y);
if(mid<y) r2=query(rs,mid+1,r,x,y);
if(y<=mid) return r1;
else if(x>mid) return r2;
else return Tree(r1.sum+r2.sum+(r1.rc==r2.lc),r1.lc,r2.rc);
}
void print(){
for(int i=1;i<n<<2;i++){
cout << tr[i].lc << ' ';
}cout << '\n';
}
}Tr;
void init(){
memset(dep,0,sizeof(dep));
memset(fa,0,sizeof(fa));
memset(dfn,0,sizeof(dfn));
memset(top,0,sizeof(top));
memset(hson,0,sizeof(hson));
memset(siz,0,sizeof(siz));
dfx=0;
for(int i=1;i<N;i++) G[i].clear();
}
void modify(int x,int y,int k){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
Tr.modify(1,1,n,dfn[top[x]],dfn[x],k);
x=fa[top[x]];
}
if(dfn[x]>dfn[y]) swap(x,y);
Tr.modify(1,1,n,dfn[x],dfn[y],k);
}
int query(int x,int y){
bool f=0;
Tree ans1=Tree(),ans2=Tree(),tmp=Tree();
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y),f=!f;
tmp=Tr.query(1,1,n,dfn[top[x]],dfn[x]);
if(f){
ans2=Tree(tmp.sum+ans2.sum+(tmp.rc==ans2.lc),tmp.lc,ans2.rc);
}else{
ans1=Tree(ans1.sum+tmp.sum+(ans1.rc==tmp.rc),ans1.lc,tmp.lc);
}
x=fa[top[x]];
}
if(dep[x]<dep[y]) swap(x,y),f=!f;
tmp=Tr.query(1,1,n,dfn[y],dfn[x]);
if(f){
ans2=Tree(tmp.sum+ans2.sum+(tmp.rc==ans2.lc),tmp.lc,ans2.rc);
}else{
ans1=Tree(ans1.sum+tmp.sum+(ans1.rc==tmp.rc),ans1.lc,tmp.lc);
}
return ans1.sum+ans2.sum+(ans1.rc==ans2.lc);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--){
cin>>n>>m;
for(int i=1,u,v;i<n;i++){
cin>>u>>v;
G[u].push_back(v);G[v].push_back(u);
}
dfs1(1);dfs2(1,1);
Tr.init();
for(int i=1;i<=n;i++){Tr.modify(1,1,n,dfn[i],dfn[i],-i);}
for(int i=1,op,a,b;i<=m;i++){
cin>>op>>a>>b;
if(op==1){
modify(a,b,i);
}else{
cout << query(a,b) << '\n';
}
}
init();
}
return 0;
}
2025.7.14
上午模拟赛
T1 看出结论了但是写的跟依托，最终于暴力老哥同分。（不对，我甚至没看见模 1e9+7）
T2 图论建模，当成 DS 写也是没谁了，最终拿满了暴力分。
T3 读错了一半题，很 Trick 的背包，将一个放入状态，最优化另一个的思路。
T4 AGC F题，原题是黑？那我问你那我问你，你是想让我们场切吗？
具体题解不写了，还得多练，不能每次看所有题都是新题。
下午改题，改了 1 2 3 就这样吧。
还有 DS 题单，但今天可能就只能写一道题了。