最近稍微写了几道紫题of历年提高组。
把得到的经验和一些题目的解法进行说明。
按年份顺序：
1.疫情控制：
传送门：GO
简单题意：给定树上一些点，用最少的步数将所有子树堵上。
解法：因为要堵上所有子树，以1为根，那么二分步数，每一个点尽量往高处走一定最优，能走到根节点就要考虑堵上其他子树，不能走到根节点就将能堵上的点堵上。处理出能上根节点的所有点还能走多少步，再处理出没堵上的最浅节点需要走的距离，两边排个序，检索一下是否能对应上即可。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int read(){ 4 int x=0,f=1; 5 char c=getchar(); 6 while(!isdigit(c)){ 7 if(c=='-') f=-1; 8 c=getchar(); 9 } 10 while(isdigit(c)){ 11 x=(x<<1)+(x<<3)+(c^48); 12 c=getchar(); 13 } 14 return x*f; 15 } 16 const int N=5e4+10; 17 struct edge{ 18 int to,nxt,w; 19 }e[N<<1]; 20 int n,m,cnt,head[N<<1],fa[N][25],dep[N][25],pos[N],na,nb; 21 int vis[N],jud[N],rb[N],rmin[N],ans=-1; 22 struct node{ 23 int idx,dis; 24 }a[N],b[N]; 25 void addedge(int from,int to,int w){ 26 e[++cnt]=(edge){to,head[from],w}; 27 head[from]=cnt; 28 } 29 bool cmp(node t1,node t2){ 30 return t1.dis>t2.dis; 31 } 32 void dfs(int u,int father){ 33 fa[u][0]=father; 34 for(int i=head[u];i;i=e[i].nxt){ 35 int v=e[i].to,w=e[i].w; 36 if(v==father) continue; 37 dep[v][0]=w; 38 dfs(v,u); 39 } 40 } 41 bool check(int u,int father){ 42 int c1=1,c2=0; 43 if(vis[u]) return 1; 44 for(int i=head[u];i;i=e[i].nxt){ 45 int v=e[i].to; 46 if(v==father) continue; 47 c2=1; 48 if(!check(v,u)){ 49 c1=0; 50 if(u==1) b[++nb]=(node){v,e[i].w}; 51 else return 0; 52 } 53 } 54 if(!c2) return 0; 55 return c1; 56 } 57 int solve(int lim){ 58 na=nb=0; 59 for(int i=1;i<=n;i++) vis[i]=rb[i]=0; 60 for(int i=1;i<=m;i++) jud[i]=0; 61 for(int i=1;i<=m;i++){ 62 int num=0,u=pos[i]; 63 for(int j=20;j>=0;j--){ 64 if(fa[u][j]>1&&num+dep[u][j]<=lim){ 65 num+=dep[u][j]; 66 u=fa[u][j]; 67 } 68 } 69 if(fa[u][0]==1&&num+dep[u][0]<=lim){ 70 a[++na]=(node){i,lim-num-dep[u][0]}; 71 if(!rb[u]||a[na].dis<rmin[u]){ 72 rb[u]=i; 73 rmin[u]=a[na].dis; 74 } 75 } 76 else vis[u]=1; 77 } 78 79 if(check(1,0)) return 1; 80 sort(a+1,a+na+1,cmp),sort(b+1,b+nb+1,cmp); 81 int now=1; 82 jud[0]=1; 83 for(int i=1;i<=nb;i++){ 84 if(!jud[rb[b[i].idx]]){ 85 jud[rb[b[i].idx]]=1; 86 continue; 87 } 88 while(now<=na&&(jud[a[now].idx]||a[now].dis<b[i].dis)) now++; 89 if(now>na) return 0; 90 jud[a[now].idx]=1; 91 } 92 return 1; 93 } 94 int main(){ 95 n=read(); 96 for(int i=1,x,y,z;i<n;i++){ 97 x=read();y=read();z=read(); 98 addedge(x,y,z); 99 addedge(y,x,z); 100 } 101 dfs(1,0); 102 for(int i=1;i<=20;i++){ 103 for(int j=1;j<=n;j++){ 104 fa[j][i]=fa[fa[j][i-1]][i-1]; 105 dep[j][i]=dep[j][i-1]+dep[fa[j][i-1]][i-1]; 106 } 107 } 108 m=read(); 109 for(int i=1;i<=m;i++){ 110 pos[i]=read(); 111 } 112 int l=0,r=500000; 113 while(l<=r){ 114 int mid=(l+r)>>1; 115 if(solve(mid))r=mid-1,ans=mid; 116 else l=mid+1; 117 } 118 printf("%d",ans); 119 return 0; 120 }
2.天天爱跑步：
传送门：GO
解法：对于一个观测点，我们知道它的出现时间，又知道一条路径是呈直线型或倒V型，因此可以推出以哪些位置为起点或终点的路径会对这个观测点做出贡献。而我们知道一个观测点，只有它所在的子树上的点才会对它做出贡献，因此在递归子树的过程中维护一个子树上的贡献即可（其实这个我也不是特别懂）。
#include<bits/stdc++.h> using namespace std; int read(){ int x=0,f=1; char c=getchar(); while(!isdigit(c)){ if(c=='-') f=-1; c=getchar(); } while(isdigit(c)){ x=(x<<1)+(x<<3)+(c^48); c=getchar(); } return x*f; } const int N=3e5+10; int n,m,cnt,cnt1,cnt2; int head[N<<1],head1[N<<1],head2[N<<1],b1[N<<1],b2[N<<1],buc[N],w[N],f[N][30],dep[N],dis[N]; int s[N],t[N],ans[N]; struct edge{ int to,next; }e[N<<1],e1[N<<1],e2[N<<1]; void addedge(int from,int to){ e[++cnt]=(edge){to,head[from]}; head[from]=cnt; } void addedge1(int from,int to){ e1[++cnt1]=(edge){to,head1[from]}; head1[from]=cnt1; } void addedge2(int from,int to){ e2[++cnt2]=(edge){to,head2[from]}; head2[from]=cnt2; } void dfs(int u,int fa){ dep[u]=dep[fa]+1; f[u][0]=fa; for(int i=head[u];i;i=e[i].next){ int v=e[i].to; if(v==fa) continue; dfs(v,u); } } int get_lca(int x,int y){ 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 dfs2(int u){ int t1=b1[w[u]+dep[u]],t2=b2[w[u]-dep[u]+N]; for(int i=head[u];i;i=e[i].next){ int v=e[i].to; if(v==f[u][0]) continue; dfs2(v); } b1[dep[u]]+=buc[u]; for(int i=head1[u];i;i=e1[i].next){ int v=e1[i].to; b2[dis[v]-dep[t[v]]+N]++; } ans[u]+=b1[w[u]+dep[u]]-t1+b2[w[u]-dep[u]+N]-t2; for(int i=head2[u];i;i=e2[i].next){ int v=e2[i].to; b1[dep[s[v]]]--; b2[dis[v]-dep[t[v]]+N]--; } } int main(){ n=read();m=read(); for(int i=1,x,y;i<n;i++){ x=read();y=read(); addedge(x,y); addedge(y,x); } for(int i=1;i<=n;i++) w[i]=read(); 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]; } } for(int i=1;i<=m;i++){ s[i]=read();t[i]=read(); int top=get_lca(s[i],t[i]); buc[s[i]]++; dis[i]=dep[s[i]]+dep[t[i]]-2*dep[top]; addedge1(t[i],i); addedge2(top,i); if(dep[top]+w[top]==dep[s[i]]) ans[top]--; } dfs2(1); for(int i=1;i<=n;i++) printf("%d ",ans[i]); return 0; }
3.保卫王国
传送门：GO
这就是个倍增dp的练手题。不讲了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 inline ll read(){ 5 ll xx=0,ff=1; 6 char c=getchar(); 7 while(!isdigit(c)){ 8 if(c=='-') ff=-1; 9 c=getchar(); 10 } 11 while(isdigit(c)){ 12 xx=(xx<<1)+(xx<<3)+(c^48); 13 c=getchar(); 14 } 15 return xx*ff; 16 } 17 const ll N=1e5+10; 18 const ll inf=1e15; 19 ll n,m,cnt=0; 20 ll head[N<<1]; 21 ll p[N]; 22 char c[5]; 23 ll f[N][2]; 24 ll g[N][2]; 25 ll h[N][30][2][2]; 26 ll lc[N][30]; 27 ll dep[N]; 28 ll fad[N]; 29 set<pair<int,int> > sea; 30 struct edge{ 31 ll to,next; 32 }e[N<<1]; 33 void addedge(ll from,ll to){e[++cnt]=(edge){to,head[from]};head[from]=cnt;} 34 void dfs(int u,int fa){ 35 dep[u]=dep[fa]+1; 36 lc[u][0]=fa; 37 f[u][1]=p[u]; 38 for(int i=head[u];i;i=e[i].next){ 39 int v=e[i].to; 40 if(v==fa) continue; 41 dfs(v,u); 42 f[u][0]+=f[v][1]; 43 f[u][1]+=min(f[v][0],f[v][1]); 44 } 45 } 46 void dfs2(int u){ 47 for(int i=head[u];i;i=e[i].next){ 48 int v=e[i].to; 49 if(v==lc[u][0]) continue; 50 g[v][0]=g[u][1]+f[u][1]-min(f[v][0],f[v][1]); 51 g[v][1]=min(g[v][0],f[u][0]+g[u][0]-f[v][1]); 52 dfs2(v); 53 } 54 } 55 56 ll solve(ll x,ll x_s,ll y,ll y_s){ 57 if(dep[x]<=dep[y]) swap(x,y),swap(x_s,y_s); 58 ll chx[2]={inf,inf},chy[2]={inf,inf}; 59 chx[x_s]=f[x][x_s]; 60 chy[y_s]=f[y][y_s]; 61 ll nowx[2],nowy[2]; 62 for(int j=20;j>=0;j--){ 63 if(dep[lc[x][j]]>=dep[y]){ 64 nowx[0]=nowx[1]=inf; 65 for(int a=0;a<2;a++){ 66 for(int b=0;b<2;b++){ 67 nowx[a]=min(nowx[a],h[x][j][b][a]+chx[b]); 68 } 69 } 70 chx[0]=nowx[0];chx[1]=nowx[1]; 71 x=lc[x][j]; 72 } 73 } 74 if(x==y) return chx[y_s]+g[x][y_s]; 75 for(int j=20;j>=0;j--){ 76 if(lc[x][j]!=lc[y][j]){ 77 nowx[0]=nowx[1]=nowy[0]=nowy[1]=inf; 78 for(int a=0;a<2;a++){ 79 for(int b=0;b<2;b++){ 80 nowx[a]=min(nowx[a],chx[b]+h[x][j][b][a]); 81 nowy[a]=min(nowy[a],chy[b]+h[y][j][b][a]); 82 } 83 } 84 chx[0]=nowx[0],chx[1]=nowx[1],chy[0]=nowy[0],chy[1]=nowy[1]; 85 x=lc[x][j],y=lc[y][j]; 86 } 87 } 88 int top=lc[x][0]; 89 ll ischose[2]; 90 ischose[1]=f[top][1]-min(f[x][0],f[x][1])-min(f[y][0],f[y][1])+min(chx[0],chx[1])+min(chy[0],chy[1])+g[top][1]; 91 ischose[0]=f[top][0]-f[x][1]-f[y][1]+chx[1]+chy[1]+g[top][0]; 92 return min(ischose[1],ischose[0]); 93 } 94 int main(){ 95 n=read();m=read(); 96 cin>>c; 97 for(int i=1;i<=n;i++){ 98 p[i]=read(); 99 } 100 for(int i=1,x,y;i<n;i++){ 101 x=read();y=read(); 102 addedge(x,y); 103 addedge(y,x); 104 sea.insert(make_pair(x,y)); 105 sea.insert(make_pair(y,x)); 106 } 107 dfs(1,0); 108 dfs2(1); 109 for(int i=1;i<=n;i++){ 110 h[i][0][1][1]=f[lc[i][0]][1]-min(f[i][0],f[i][1]); 111 h[i][0][0][1]=f[lc[i][0]][1]-min(f[i][0],f[i][1]); 112 h[i][0][1][0]=f[lc[i][0]][0]-f[i][1]; 113 h[i][0][0][0]=inf; 114 } 115 for(int j=1;j<=19;j++){ 116 for(int i=1;i<=n;i++){ 117 int tmp=lc[i][j-1]; 118 lc[i][j]=lc[tmp][j-1]; 119 for(int a=0;a<2;a++){ 120 for(int b=0;b<2;b++){ 121 h[i][j][a][b]=inf; 122 for(int d=0;d<2;d++){ 123 h[i][j][a][b]=min(h[i][j][a][b],h[i][j-1][a][d]+h[tmp][j-1][d][b]); 124 } 125 } 126 } 127 } 128 } 129 130 for(int i=1,x,y,a,b;i<=m;i++){ 131 x=read();a=read();y=read();b=read(); 132 if(!a&&!b&&sea.find(make_pair(x,y))!=sea.end()){ 133 printf("-1 "); 134 continue; 135 } 136 printf("%lld ",solve(x,a,y,b)); 137 } 138 return 0; 139 }
4.赛道修建
传送门：GO
解法：观察到每条边最多经过一次，因此对于一个点，要么有且最多只有一条从下往上穿过的道路，要么就没有。所以二分答案，将一个节点的子树按照答案尽量拼凑，将剩余中最长边向上传递，判断解的存在性即可。
1 #include<bits/stdc++.h> 2 #include<set> 3 using namespace std; 4 inline int read(){ 5 int x=0,f=1; 6 char c=getchar(); 7 while(!isdigit(c)){ 8 if(c=='-') f=-1; 9 c=getchar(); 10 } 11 while(isdigit(c)){ 12 x=(x<<1)+(x<<3)+(c^48); 13 c=getchar(); 14 } 15 return x*f; 16 } 17 const int N=5e4+10; 18 int n,m; 19 int dep[N],dest,maxdep,ans; 20 int head[N<<1],cnt; 21 struct edge{ 22 int to,next,w; 23 }e[N<<1]; 24 void addedge(int from,int to,int w){ 25 e[++cnt]=(edge){to,head[from],w}; 26 head[from]=cnt; 27 } 28 void dfs(int u,int fa){ 29 for(int i=head[u];i;i=e[i].next){ 30 int v=e[i].to,w=e[i].w; 31 if(v==fa) continue; 32 dep[v]=dep[u]+w; 33 if(maxdep<dep[v]){ 34 dest=v; 35 maxdep=dep[v]; 36 } 37 dfs(v,u); 38 } 39 } 40 multiset<int> s[N]; 41 multiset<int> ::iterator it; 42 int dfs2(int u,int fa,int lim){ 43 int siz=0; 44 s[u].clear(); 45 for(int i=head[u];i;i=e[i].next){ 46 int v=e[i].to,w=e[i].w; 47 if(v==fa) continue; 48 siz=dfs2(v,u,lim)+w; 49 if(siz>=lim) ans++; 50 else{ 51 s[u].insert(siz); 52 } 53 } 54 siz=0; 55 while(!s[u].empty()){ 56 if(s[u].size()==1){ 57 return max(siz,*s[u].begin()); 58 } 59 it=s[u].lower_bound(lim-*s[u].begin()); 60 if(it==s[u].begin()&&s[u].count(*it)==1) it++; 61 if(it==s[u].end()){ 62 siz=max(siz,*s[u].begin()); 63 s[u].erase(s[u].find(*s[u].begin())); 64 } 65 else{ 66 ans++; 67 s[u].erase(s[u].find(*it)); 68 s[u].erase(s[u].find(*s[u].begin())); 69 } 70 } 71 return siz; 72 } 73 inline bool solve(int lim){ 74 ans=0; 75 dfs2(1,0,lim); 76 return ans>=m; 77 } 78 int main(){ 79 n=read();m=read(); 80 for(register int i=1,x,y,z;i<n;i++){ 81 x=read();y=read();z=read(); 82 addedge(x,y,z); 83 addedge(y,x,z); 84 } 85 dfs(1,0); 86 maxdep=0; 87 dep[dest]=0; 88 dfs(dest,0); 89 int l=0,r=maxdep; 90 while(l<r){ 91 int mid=(l+r+1)>>1; 92 if(solve(mid)) l=mid; 93 else r=mid-1; 94 } 95 printf("%d",l); 96 return 0; 97 }
四道题的共同点：
1.需要一定灵活的思维（尤其是天天爱跑步那题）
2.没用到什么特别高级的算法，stl就能解决的类型。
3.常考图论，且有二分答案，倍增dp来增难。
注：之前还写过开车旅行，用到了双向链表求最大值与次大值的操作。
除此之外需要的就是耐心和速度了。
to be continue