当年作为OIer期间的学习历程,现在作为回忆放在这里
【说不定以后还用得上呢】
索引:
第一题:P3379 【模板】最近公共祖先
第二题:P3386 【模板】二分图匹配
第三题:P3387 【模板】缩点
第四题:P3388 【模板】割点
第五题:P4782 【模板】2-SAT问题
第六题:P1939 【模板】矩阵加速(数列)
第七题:P1082 同余方程
第八题:P2613 【模板】有理数取余
第九题:需要求树的直径(或重心)的一类问题
第十题:P2731 骑马修栅栏(欧拉回路类问题)
第十一题:P3128 最大流Max Flow(树上差分类问题)
第十二题:SP116 Intervals(差分约束类问题)
第十三题:P2580 于是他错误的点名开始了(Trie树)
第十四题:P3796 【模板】AC自动机(加强版)
第十五题:STL的妙用
第十六题:常用板子
题解思路:LCA算法
在历经了两次失败以后,我今天终于在这位巨佬的帮助下学会了LCA(没错我就是这么废,要人教才能学会)
咳咳,废话不多说,我们开始讲LCA吧
LCA的朴素算法相信大家都会写,但是朴素算法肯定会T掉,所以我们就把目光投向了倍增,这也是我们今天的重点——倍增求LCA
所谓倍增,就是按2的倍数来增大,也就是跳 1,2,4,8,16,32…… 不过在这我们不是按从小到大跳,而是从大向小跳,即按……32,16,8,4,2,1来跳,如果大的跳不过去,再把它调小。这是因为从小开始跳,可能会出现“悔棋”的现象。拿 5 为例,从小向大跳,5≠1+2+4,所以我们还要回溯一步,然后才能得出5=1+4;而从大向小跳,直接可以得出5=4+1。这也可以拿二进制为例,5(101),从高位向低位填很简单,如果填了这位之后比原数大了,那我就不填,这个过程是很好操作的。
具体操作看代码吧:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
| #include<cstdio> #include<iostream> using namespace std; int n,m,s,cnt; int head[500010],fa[500010][25],dep[500010]; struct Edge { int nst,to; }edge[1000010]; void add(int a,int b) { edge[++cnt].nst=head[a]; edge[cnt].to=b; head[a]=cnt; } void dfs(int x,int y) { dep[x]=dep[y]+1; fa[x][0]=y; for(int i=0;i<=20;i++) { fa[x][i+1]=fa[fa[x][i]][i]; } for(int i=head[x];i;i=edge[i].nst) { int v=edge[i].to; if(v!=y) { dfs(v,x); } } } int lca(int x,int y) { if(dep[x]<dep[y])swap(x,y); for(int i=20;i>=0;i--) { if(dep[y]<=dep[fa[x][i]])x=fa[x][i]; if(x==y)return x; } for(int i=20;i>=0;i--) { if(fa[x][i]!=fa[y][i]) { x=fa[x][i]; y=fa[y][i]; } } return fa[x][0]; } int main() { scanf("%d%d%d",&n,&m,&s); int a,b; for(int i=1;i<=n-1;i++) { scanf("%d%d",&a,&b); add(a,b); add(b,a); } dfs(s,0); for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); printf("%d\n",lca(a,b)); } return 0; }
|
接下来介绍另一种求LCA的方式:树剖求LCA
两篇详解:树链剖分求LCA 和 树链剖分求LCA(最近公共祖先)
树剖求LCA的速度很快,O(n)预处理,O(log(n))查询,相较于倍增LCA更快,而且求LCA那部分更好写,但是dfs部分比较难写.
整个算法流程就是先两个dfs预处理,然后一个判断u与v是否在同一条重链,不在就往上跳,最后得到LCA.
至于为什么查询是O(log(n))的,因为我们可以证明重链只有log(n)条,所以是O(n)的.
找重链的方法:取每个节点u的所有子节点中,子树最大的子节点v,然后将边(u,v)作为重边,其余边作为轻边,重边构成的链就是重链
具体过程是两遍深搜,第一遍建树,第二遍构造重链:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
| #include<cstdio> #include<iostream> #define maxn 500010 using namespace std; inline int read() { int x=0,fu=1;char o=getchar(); while(o>'9'||o<'0'){if(o=='-')fu=-1;o=getchar();} while(o>='0'&&o<='9'){x=(x<<3)+(x<<1)+(o^48);o=getchar();} return x*fu; } struct Edge { int to,dis,nst; }edge[maxn<<1]; int cnt,head[maxn],fa[maxn],top[maxn]; int dep[maxn],siz[maxn],son[maxn],val[maxn]; inline void add(int a,int b,int c) { edge[++cnt].nst=head[a]; edge[cnt].to=b; edge[cnt].dis=c; head[a]=cnt; } void dfs1(int x) { dep[x]=dep[fa[x]]+1; siz[x]=1; for(int i=head[x];i;i=edge[i].nst) { int v=edge[i].to; if(fa[x]!=v&&!fa[v]) { val[v]=edge[i].dis; fa[v]=x; dfs1(v); siz[x]+=siz[v]; if(siz[son[x]]<siz[v])son[x]=v; } } } void dfs2(int x) { if(x==son[fa[x]])top[x]=top[fa[x]]; else top[x]=x; for(int i=head[x];i;i=edge[i].nst) if(fa[edge[i].to]==x)dfs2(edge[i].to); } int query(int x,int y) { while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]])swap(x,y); x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); return x; } int n,m,s,x,y,v; int main() { n=read();m=read();s=read(); for(int i=1;i<n;i++) { x=read();y=read(); add(x,y,0);add(y,x,0); } dfs1(s);dfs2(s); for(int i=1;i<=m;i++) { x=read();y=read(); printf("%d\n",query(x,y)); } return 0; }
|
题解思路1:匈牙利算法
我也不想细讲思路了,去看这篇博客和这篇博客吧
以下是我的代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| #include<cstdio> #include<cstring> #include<iostream> using namespace std; int n,m,e,ans,match[1001]; bool a[1001][1001],vis[1001]; bool dfs(int x) { for(int i=1;i<=m;i++) if(!vis[i]&&a[x][i]) { vis[i]=1; if(!match[i]||dfs(match[i])) { match[i]=x; return 1; } } return 0; } int main() { scanf("%d%d%d",&n,&m,&e); for(int i=1;i<=e;i++) { int u,v; scanf("%d%d",&u,&v); if(v<=m)a[u][v]=1; } for(int i=1;i<=n;i++) { ans+=dfs(i); memset(vis,0,sizeof(vis)); } printf("%d",ans); return 0; }
|
题解思路2:网络最大流Dinic
去看我的这篇博客,当然上文的第一篇博客里也讲了Dinic,比较着看看吧
代码……就不放了(反正NOIP不考网络流)
题解思路:tarjan缩点+拓扑排序+DP
安利一下这两篇博客,把tarjan的思路讲得很详细:原理解析,模板详解
(update on 2019/9/22)对于无向图的tarjan,我们需要在dfs函数上多加一个记录父节点的参数来保证不会再双向边上打转,具体做法看代码里的注释部分
那么具体思路我就不赘述了(我可真懒),详解看代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147
| #include<queue> #include<stack> #include<cstdio> #include<iostream> using namespace std; const int maxn=10015; int n,m,p[maxn]; int tim,sd[maxn],dfn[maxn],low[maxn],vis[maxn];
int in[maxn],dist[maxn];
int head[maxn],h[maxn],cnt,num; struct Edge { int to,from,nst; }edge[maxn*10],e[maxn*10]; void add(int a,int b) { edge[++cnt].nst=head[a]; edge[cnt].from=a; edge[cnt].to=b; head[a]=cnt; } stack <int> s; void tarjan(int x) { low[x]=dfn[x]=++tim; s.push(x); vis[x]=1; for(int i=head[x];i;i=edge[i].nst) { int v=edge[i].to; if(!dfn[v]) { tarjan(v); low[x]=min(low[x],low[v]); } else if(vis[v]) { low[x]=min(low[x],dfn[v]); } } if(dfn[x]==low[x]) { int u; while(u=s.top()) { s.pop(); sd[u]=x; vis[u]=0; p[x]+=p[u]; if(u==x)break; } } }
int dp() { queue <int> q; int tot=0; for(int i=1;i<=n;i++) if(sd[i]==i&&!in[i]) { q.push(i); dist[i]=p[i]; } while(!q.empty()) { int u=q.front(); q.pop(); for(int i=h[u];i;i=e[i].nst) { int v=e[i].to; dist[v]=max(dist[v],dist[u]+p[v]); in[v]--; if(!in[v])q.push(v); } } int ans=0; for(int i=1;i<=n;i++) ans=max(ans,dist[i]); return ans; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&p[i]); int a,b; for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); add(a,b); } for(int i=1;i<=n;i++) if(!dfn[i])tarjan(i); for(int i=1;i<=m;i++) { a=sd[edge[i].from]; b=sd[edge[i].to]; if(a!=b) { e[++num].nst=h[a]; e[num].to=b; e[num].from=a; h[a]=num; in[b]++; } } printf("%d",dp()); return 0; }
|
题解思路:tarjan割点
为什么又是tarjan
tarjan割点算法与tarjan缩点算法有相似之处,这篇博客详细的讲述了这个算法,我就不赘述了……(我又懒了)
以下是AC代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
| #include<cstdio> #include<iostream> using namespace std; struct Edge { int nst,to; }edge[200010]; int n,m,cnt,tot,tim; int head[100010],dfn[100010],low[100010]; bool vis[100010]; void add(int a,int b) { edge[++cnt].nst=head[a]; edge[cnt].to=b; head[a]=cnt; } void tarjan(int x,int fa) { dfn[x]=low[x]=++tim; int child=0; for(int i=head[x];i;i=edge[i].nst) { int v=edge[i].to; if(!dfn[v]) { tarjan(v,fa); low[x]=min(low[x],low[v]); if(low[v]>=dfn[x]&&x!=fa)vis[x]=1; if(x==fa)child++; } low[x]=min(low[x],dfn[v]); } if(child>=2&&x==fa) vis[x]=1; }
int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int a,b; scanf("%d%d",&a,&b); add(a,b); add(b,a); } for(int i=1;i<=n;i++) if(!dfn[i])tarjan(i,i); for(int i=1;i<=n;i++) if(vis[i])tot++; printf("%d\n",tot); for(int i=1;i<=n;i++) if(vis[i])printf("%d ",i); return 0; }
|
题解思路:位运算建图+tarjan缩点
2-SAT问题其实是SAT问题的特例,所以它并非NP问题,是可以用巧妙的方法求解的。
再次安利:算法详解(笔者的懒癌已经病入骨膏了……)
但是有一点需要说明:笔者代码里的建图方向与博客里相反,顾笔者使用的是col[i]>col[i+n]
而且博客里有一点没有说明:为什么拓扑序大的应为真呢?因为若x0→x1,那么x0的拓扑序显然比x1小,如果使x0为真,则x1里的值也必须全选,这样会造成矛盾,故我们拓扑序大的为真。因为tarjan求出来的点都是按拓扑逆序排列的,所以若sd[i]<sd[i+n],则应选i,又因为i代表x为真,故输出1。
以下是源代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
| #include<queue> #include<cstdio> #include<iostream> using namespace std; const int maxn=2000005; struct Edge { int nst,to,from; }edge[2*maxn]; int dfn[maxn],vis[maxn],stack[maxn],low[maxn],sd[maxn],top,tim,num; int n,m,head[maxn],cnt; inline void add(int a,int b) { edge[++cnt].nst=head[a]; edge[cnt].to=b; edge[cnt].from=a; head[a]=cnt; } void tarjan(int x) { low[x]=dfn[x]=++tim; stack[++top]=x; vis[x]=1; for(int i=head[x];i;i=edge[i].nst) { int v=edge[i].to; if(!dfn[v]) { tarjan(v); low[x]=min(low[x],low[v]); } else if(vis[v]) { low[x]=min(low[x],dfn[v]); } } if(dfn[x]==low[x]) { int u; num++; while(u=stack[top--]) { sd[u]=num; vis[u]=0; if(u==x)break; } } } int main() { scanf("%d%d",&n,&m); int x,a,y,b; for(register int i=1;i<=m;i++) { scanf("%d%d%d%d",&x,&a,&y,&b); add(x+!a*n,y+b*n); add(y+!b*n,x+a*n); } for(register int i=1;i<=2*n;i++) if(!dfn[i])tarjan(i); for(int i=1;i<=n;i++) if(sd[i]==sd[i+n]){printf("IMPOSSIBLE\n");return 0;} printf("POSSIBLE\n"); for(int i=1;i<=n;i++) printf("%d ",sd[i]>sd[i+n]); return 0; }
|
题解思路:矩阵快速幂
安利:矩阵快速幂
以下是代码君:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
| #include<cstdio> #include<cstring> #include<iostream> #define ll long long using namespace std; const int p=1e9+7; struct mat { ll m[5][5]; }ans,base; inline void init() { memset(ans.m,0,sizeof(ans.m)); for(int i=1;i<=3;i++) ans.m[i][i]=1; memset(base.m,0,sizeof(base.m)); base.m[1][1]=base.m[1][3]=base.m[2][1]=base.m[3][2]=1; } inline mat mul(mat a,mat b) { mat res; memset(res.m,0,sizeof(res.m)); for(int i=1;i<=3;i++){ for(int j=1;j<=3;j++){ for(int k=1;k<=3;k++){ res.m[i][j]+=(a.m[i][k]%p)*(b.m[k][j]%p); res.m[i][j]%=p; } } } return res; } inline void qmat_pow(int p) { while(p) { if(p&1)ans=mul(ans,base); base=mul(base,base); p>>=1; } } int t,n; int main() { scanf("%d",&t); while(t--) { scanf("%d",&n); if(n<=3) { printf("1\n"); continue; } init(); qmat_pow(n); printf("%lld\n",ans.m[2][1]); } return 0; }
|
第七题:P1082 同余方程
这就是个用拓展欧几里得算法求解同余方程的模板题
(一般来说exgcd背背代码就可以了,但是如果想要详细了解可以看这篇题解)
以下是代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| #include<cstdio> #include<iostream> #define ll long long using namespace std; ll a,b,x,y; void exgcd(ll a,ll b,ll &x,ll &y) { if(!b){x=1;y=0;return;} exgcd(b,a%b,x,y); ll tmp=x; x=y; y=tmp-a/b*y; } int main() { scanf("%lld%lld",&a,&b); exgcd(a,b,x,y); x=(x+b)%b; printf("%lld",x); return 0; }
|
用拓欧求逆元,进而求有理数取余,详细过程可以看这篇题解
以下是代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| #include<cstdio> #include<iostream> #define ll long long using namespace std; ll a,b,x,y; const int p=19260817; inline int read() { int x=0,fu=1;char o=getchar(); while(o>'9'||o<'0'){if(o=='-')fu=-1;o=getchar();} while(o>='0'&&o<='9'){x=((x<<3)+(x<<1)+(o^48))%p;o=getchar();} return x*fu; } void exgcd(ll a,ll b) { if(!b){x=1;y=0;return;} exgcd(b,a%b); ll tmp=x; x=y; y=tmp-a/b*y; } int main() { a=read();b=read(); if(b==0){printf("Angry!\n");return 0;} exgcd(b,p); x=(x%p+p)%p; printf("%lld",a*x%p); return 0; }
|
第九题:需要求树的直径(或重心)的一类问题
题解思路:树上DP
部分援引:树的直径和重心
我们设d[x]代表 从x开始走 能到达 在以x为根的子树里的最远的点 的距离,那么就有DP方程:d[x]=max(d[x],d[v]+dis(x,v))
我们设f[x]代表经过x点的最长链的长度,树的直径就是最大的f[x]
我们知道,对于任意两个节点u、v,经过x的最长链由四部分构成:d[u],d[v],u到x的距离,v到x的距离
那我们就能得到DP方程:f[x]=max(f[x],f[u]+f[v]+dis(u,x)+dis(v,x)
以下是参考代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
| #include<cstdio> #include<iostream> using namespace std; const int maxn=100010; inline int read() { int x=0,fu=1;char o=getchar(); while(o>'9'||o<'0'){if(o=='-')fu=-1;o=getchar();} while(o>='0'&&o<='9'){x=(x<<3)+(x<<1)+(o^48);o=getchar();} return x*fu; } struct Edge { int nst,to,dis; }edge[maxn<<1]; int n,head[maxn],dis[maxn],ans; int vis[maxn]; inline void add(int a,int b,int c) { edge[++cnt].nst=head[a]; edge[cnt].to=b; edge[cnt].dis=c; head[a]=cnt; } void dp(int x) { vis[x]=1; for(register int i=head[x];i;i=edge[i].nst) { int v=edge[i].to; if(vis[v])continue; dp(v); ans=max(ans,dis[x]+dis[v]+edge[i].dis); dis[x]=max(dis[x],dis[v]+edge[i].dis); } } int main() { n=read(); int x,y; for(int i=1;i<n;i++) { x=read();y=read(); add(x,y,1);add(y,x,1); } dp(1); printf("%d",ans); return 0; }
|
第十题:P2731 骑马修栅栏(欧拉回路类问题)
夹议:一些定义
一、基本概念:
欧拉路:欧拉路是指从图中任意一个点开始到图中任意一个点结束的路径,并且图中每条边通过的且只通过一次。
欧拉回路:欧拉回路是指起点和终点相同的欧拉路。
二、存在欧拉路的条件:
1.无向连通图存在欧拉路的条件:
所有点度都是偶数,或者恰好有两个点度是奇数,则有欧拉路。若有奇数点度,则奇数点度点一定是欧拉路的起点和终点,否则可取任意一点作为起点。
2.有向连通图存在欧拉路的条件:
每个点的入度等于出度,则存在欧拉回路(任意一点有度的点都可以作为起点)
除两点外,所有入度等于出度。这两点中一点的出度比入度大,另一点的出度比入度小,则存在欧拉路。取出度大者为起点,入度大者为终点。
题解思路:Hierholzer算法求欧拉回路
Hierholzer算法,又称逐步插入回路法,可以求无向图中的欧拉回路
所谓逐步插入回路,就是从入度为奇数的点开始找回路,找到以后就回溯,走其他没有走过的路径,直至找不到回路(貌似并不是很清晰,这篇博客里有图示说明,可以自行理解)
以下是参考代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
| #include<stack> #include<cstdio> #include<cstring> #include<iostream> using namespace std; const int maxn=1005; int a[maxn][maxn],rudu[maxn],n,m; stack <int> s; void dfs(int u) { for(int v=1;v<=n;v++) if(a[u][v]) { a[u][v]-=1; a[v][u]-=1; dfs(v); } s.push(u); } inline void print() { if(!s.empty()) { printf("%d",s.top()); s.pop(); } printf("\n"); } inline void init() { memset(rudu,0,sizeof(rudu)); memset(a,0,sizeof(a)); } int main() { while(~scanf("%d %d",&n,&m)) { init(); int u,v; for(int i=1;i<=m;i++) { scanf("%d%d",&u,&v); a[u][v]+=1;a[v][u]+=1; rudu[u]^=1;rudu[v]^=1; } for(u=1;u<=n;u++)if(rudu[u])break; if(u==n+1)dfs(1); else dfs(u); print(); } return 0; }
|
题解思路:树上点差分
有一类题,它会给你在一棵树,让你把树上两点u,v间的所有边都加一个值x。对于这种题目,显然,暴力做法是不可取的,于是就有了树上差分。
差分,顾名思义(这名字好像也看不出啥),就是把对一个区间的操作转化成对一个点的操作,在点上记录变化量。区间差分的常规做法就是:对于“将区间[x,y]间的每一个数都加上u”,我们使“val[x]+=u,val[v+1]−=u”,最后用前缀和扫一遍即可。
树上差分与其类似,对于第一段说的那种题目,我们只需将"val[u]+=x,val[v]+=x,val[lca(u,v)]−=2∗x",然后就可以从树根开始前缀和了。这就叫树上边差分
但是这个题是树上点差分。我们只需要将"val[lca(u,v)]−=x,val[fa[lca(u,v)]]−=x"即可
原理其实很简单:我们在该路径上每个点都加x时,分别从u和v给lca加了两个x,所以我们对lca-=x,保证lca只比原来大x;为了把影响只限制在u到v的路径,我们对lca的父节点减x即可
树上差分适用于修改多而询问少的情况。
(参考了Sagittarius大佬的这篇博客)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
| #include<cstdio> #include<iostream> #define maxn 50010 using namespace std; inline int read() { int x=0,fu=1;char o=getchar(); while(o>'9'||o<'0'){if(o=='-')fu=-1;o=getchar();} while(o>='0'&&o<='9'){x=(x<<3)+(x<<1)+(o^48);o=getchar();} return x*fu; } struct Edge { int to,dis,nst; }edge[maxn<<1]; int n,m,x,y; int ans,cnt,head[maxn],fa[maxn],top[maxn]; int dep[maxn],siz[maxn],son[maxn],val[maxn]; inline void add(int a,int b,int c) { edge[++cnt].nst=head[a]; edge[cnt].to=b; edge[cnt].dis=c; head[a]=cnt; } void dfs1(int x) { dep[x]=dep[fa[x]]+1; siz[x]=1; for(int i=head[x];i;i=edge[i].nst) { int v=edge[i].to; if(fa[x]!=v&&!fa[v]) { val[v]=edge[i].dis; fa[v]=x; dfs1(v); siz[x]+=siz[v]; if(siz[son[x]]<siz[v])son[x]=v; } } } void dfs2(int x) { if(x==son[fa[x]])top[x]=top[fa[x]]; else top[x]=x; for(int i=head[x];i;i=edge[i].nst) if(fa[edge[i].to]==x)dfs2(edge[i].to); } int query(int x,int y) { while(top[x]!=top[y]) { dep[top[x]]>dep[top[y]]?x=fa[top[x]]:y=fa[top[y]]; } return dep[x]<dep[y]?x:y; } void getans(int x,int fa) { for(int i=head[x];i;i=edge[i].nst) { int v=edge[i].to; if(v==fa)continue; getans(v,x); val[x]+=val[v]; } ans=max(val[x],ans); } int main() { n=read();m=read(); for(int i=1;i<n;i++) { x=read();y=read(); add(x,y,0);add(y,x,0); } dfs1(1);dfs2(1); for(int i=1;i<=m;i++) { x=read();y=read(); int lca=query(x,y); val[x]++;val[y]++;val[lca]--;val[fa[lca]]--; } getans(1,0); printf("%d",ans); return 0; }
|
第十二题:SP116 Intervals(差分约束类问题)
题解思路:差分约束系统
做了这几道差分约束系统的题(P3275 SP116 UVA1723)以后,我觉得差分约束系统是利用题面中给出的约束条件,和题干中隐藏的约束条件建图,之后求解最短(长)路的过程。但是我们在建图的过程中要关注具体问题,若求的是两个变量差的最大值,那么将所有不等式转变成"<="的形式并且在建图后求最短路;反之则转换成">="的形式,并且求最长路
辣么,对于这个题,我们设d[i]代表在区间[0,i]上取d[i]个数,则根据题意,就有d[bi]−d[ai−1]>=ci
但是只有这一个约束条件还不够,所以我们还要去挖掘题目中的隐含条件。首先,显然,d[i]肯定大于等于d[i−1],所以我们有d[i]−d[i−1]>=0。然后我们发现,题目中有一句话很关键:每个数只能取一次,所以我们可以得到另一个约束条件:d[i]−d[i−1]只能等于0或1,因此就得到了差分约束方程组:
d[i]−d[i−1]>=0
d[i−1]−d[i]>=−1
d[bi]−d[ai−1]>=ci
所以,我们在建图时要做到这三步:
- 在ai−1和bi间连一条边权为ci有向边
- 在i和i-1之间连一条边权为0的有向边
- 在i-1和i之间连一条边权为-1的有向边
然后以0为起点,用spfa跑最长路,输出d[maxx]即可
以下是AC代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
| #include<queue> #include<cstdio> #include<cstring> #include<iostream> using namespace std; int n,t,cnt,maxx; struct Edge { int nst,to,dis; }edge[500010]; int head[50010],dis[50010],vis[50010]; void add(int a,int b,int c) { edge[++cnt].nst=head[a]; edge[cnt].to=b; edge[cnt].dis=c; head[a]=cnt; } void spfa() { queue <int> q; for(int i=1;i<=maxx+1;i++) { dis[i]=-1e9; vis[i]=0; } dis[0]=0; vis[0]=1; q.push(0); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i;i=edge[i].nst) { int v=edge[i].to; if(dis[v]<dis[u]+edge[i].dis) { dis[v]=dis[u]+edge[i].dis; if(!vis[v]) { q.push(v); vis[v]=1; } } } } } int main() { scanf("%d",&t); while(t--) { maxx=-1; cnt=0; memset(edge,0,sizeof(edge)); memset(head,0,sizeof(head)); scanf("%d",&n); int a,b,c; for(int i=1;i<=n;i++) { scanf("%d%d%d",&a,&b,&c); add(a-1,b,c); maxx=max(maxx,b); } for(int i=1;i<=maxx+1;i++) { add(i-1,i,0); add(i,i-1,-1); } spfa(); printf("%d\n",dis[maxx+1]); } return 0; }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
| #include<cstdio> #include<string> #include<cstring> #include<iostream> #define maxn 1000010 using namespace std; struct Trie { int ch[maxn][26],val[maxn],mark[26],sz; Trie() { sz=1; memset(ch[0],0,sizeof(ch[0])); memset(val,0,sizeof(val)); } int idx(char c){return c-'a';} void insert(char s[],int v) { int u=0,len=strlen(s); for(int i=0;i<len;i++) { int c=idx(s[i]); if(!ch[u][c]) { memset(ch[sz],0,sizeof(ch[sz])); val[sz]=0; ch[u][c]=sz++; } u=ch[u][c]; } val[u]=v; } int search(char s[]) { int u=0,len=strlen(s); for(int i=0;i<len;i++) { int c=idx(s[i]); if(!ch[u][c])return -1; u=ch[u][c]; } return val[u]; } }tree; int n,m; char o[50]; char s[maxn]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { cin>>o; tree.insert(o,1); } for(int i=1;i<=m;i++) { cin>>s; printf("%d\n",tree.search(s)); } return 0; }
|
一篇优秀的算法讲解:AC自动机
求Fail(以下援引自 hyfhaha 奆佬的博客)
首先我们可以确定,每一个点i的Fail指针指向的点的深度一定是比i小的。(Fail指的是后缀啊)
第一层的Fail一定指的是root。(比深度1还浅的只有root了)
点i的父亲fa的Fail指针指的是fafail,那么如果fafail有和i值相同的儿子j,那么i的Fail就指向j。这里可能比较难理解一点,不过等会转换成代码就很好理解了。
由于我们在处理i的情况必须要先处理好fa的情况,所以求Fail我们使用BFS来实现。
实现的一些细节:
-
刚开始我们不是要初始化第一层的fail指针为root,其实我们可以建一个虚节点0号节点,将0的所有儿子指向root(编号为1),然后root的fail指向0就OK了。效果是一样的。
-
如果不存在一个节点i,那么我们可以将那个节点设为fafail的值和i相同的儿子。保证存在性,就算是0也可以成功返回到根,因为0的所有儿子都是根。
-
无论fafail存不存在和i值相同的儿子j,我们都可以将i的fail指向j。因为在处理i的时候j已经处理好了,如果出现这种情况,j的值是第2种情况,也是有实际值的,所以没有问题。
-
实现时不记父亲,我们直接让父亲更新儿子
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
| struct AC_Auto_Machine { void init() { for(int i=1;i<=n;i++)vis[i]=0; for(int i=0;i<=cnt;i++)t[i].clear(); cnt=1;ans=0; } void insert(char *s,int num) { int u=1,len=strlen(s); for(int i=0;i<len;i++) { int v=s[i]-'a'; if(!t[u].son[v])t[u].son[v]=++cnt; u=t[u].son[v]; }
if(!t[u].flag)t[u].flag=num; map[num]=t[u].flag; } void getfail() { for(int i=0;i<26;i++)t[0].son[i]=1; q.push(1); t[1].fail=0; while(!q.empty()) { int u=q.front(); q.pop(); int fail=t[u].fail; for(int i=0;i<26;i++) { int v=t[u].son[i]; if(!v){t[u].son[i]=t[fail].son[i];continue;} t[v].fail=t[fail].son[i]; q.push(v); } } } int query2(char *s) { int u=1,len=strlen(s); for(int i=0;i<len;i++) { int v=s[i]-'a'; int k=t[u].son[v]; while(k>1&&t[k].flag!=-1) { ans+=t[k].flag; t[k].flag=-1; k=t[k].fail; } u=t[u].son[v]; } return ans; } void query1(char *ss) { int u=1,len=strlen(ss); for(int i=0;i<len;i++) { int v=ss[i]-'a'; int k=t[u].son[v]; while(k>1) { if(t[k].flag)vis[t[k].flag]++; k=t[k].fail; } u=t[u].son[v]; } for(int i=1;i<=n;i++) ans=max(ans,vis[i]); printf("%d\n",ans); for(int i=1;i<=n;i++) if(vis[i]==ans) printf("%s\n",s[i]); } void query(char *ss) { int u=1,len=strlen(ss); for(int i=0;i<len;i++) { int v=ss[i]-'a'; int k=t[u].son[v]; while(k>1) { if(t[k].flag)vis[t[k].flag]++; k=t[k].fail; } u=t[u].son[v]; } for(int i=1;i<=n;i++) printf("%d\n",vis[map[i]]); } };
|
第十五题:STL的妙用
1.upper_bound()和lower_bound()
两个二分函数,用法:
1 2
| upper_bound(a+1,a+1+n,k)-a; lower_bound(a+1,a+1+n,k)-a;
|
前者返回序列中第一个大于k的数的下标(不减数组名的话会返回一个指针)
后者返回序列中第一个不大于k的数的下标
2.nth_element和stable_sort
两个排序函数,用法:
1 2
| nth_element(a+1,a+1+k,a+1+n); stable_sort(a+1,a+1+n);
|
前者使无重复元素的序列的第k个位置上保存序列中第k小的数
后者是一个稳定的sort函数(和sort用法基本一样,不过复杂度稳定在O(nlog2n),实现本质是归并排序)
3.unique()
一个去重函数,用法:
1 2
| unique(a+1,a+1+n); unique(a+1,a+1+n)-a-1;
|
前者是一般用法,后者是返回去重后的数组大小
如何用unique函数和sort函数进行快速的离散化
1 2 3 4 5 6 7 8 9
| sort(a+1,a+1+n) int m=unique(a+1,a+1+n)-a-1;
int q(int x) { return lower_bound(a+1,a+1+m,x)-m; }
|
当然这样离散化查询时会有O(logm)的小常数,不过它好写且方便啊!!!
4.random_shuffle()
随机化排列函数,用法:
1
| random_shuffle(a+1,a+1+n);
|
对指定范围内的数随机排列
5.vector
STL自带链表,本机亲测1s内可插入105个点,可删除3∗105个点,可以水过平衡树
6.map
7.set
8.next_permutation()
枚举下一个全排列的函数,工作原理似乎是交换末尾的几个数,所以最好在序列有序的情况下用,用法:
1
| next_permutation(a+1,a+1+n);
|
9.clock()
ctime库的函数,系统不同返回值的类型不同,用法:
1 2 3 4
| int tim=CLOCKS_PER_SEC; tim=tim*0.95; if(clock()>tim)break; if(!(i&2047))if(clock()>tim)break;
|
10.cstring库内的函数:
- strstr 寻找字符子串的首次出现
- strlen 返回给定字符串的长度
- strcmp 比较两个字符串
- strcat 连接两个字符串
- strchr 寻找字符的首次出现
- strrchr 寻找字符的最后一次出现
- strcpy 复制一个字符串给另一个
具体用法:
1 2 3 4 5 6 7 8 9
| char s[1001],o[1001]; int len=strlen(s); strcpy(o,s); strcat(o,s); strcmp(o,s); char* t=strstr(s,o); printf("%s",t); t=strchr(s,'o'); printf("%s",t);
|
第十六题:常用板子
(先咕一会,下次再补完)
Prim
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
| #include<cstdio> #include<iostream> using namespace std; inline int read() { int fu=1,x=0;char o=getchar(); while(o<'0'||o>'9'){if(o=='-')fu=-1;o=getchar();} while(o>='0'&&o<='9'){x=(x<<1)+(x<<3)+(o^48);o=getchar();} return x*fu; } const int maxn=1000; const int inf=0x7f7f7f7f; int n,m,ans=inf,map[maxn][maxn]; int low[maxn]; int mst[maxn]; void prim(int u) { int tot=0; for(int i=1;i<=n;i++) { low[i]=map[u][i]; mst[i]=u; } mst[u]=-1; for(int i=1;i<n;i++) { int minn=inf,v=-1; for(int j=1;j<=n;j++) { if(mst[j]!=-1&&low[j]<minn) { v=j; minn=low[j]; } } if(v) { mst[v]=-1; tot+=low[v]; for(int j=1;j<=n;j++) { if(mst[j]!=-1&&low[j]>map[v][j]) { low[j]=map[v][j]; mst[j]=v; } } } } ans=min(ans,tot); } int main() { m=read();n=read(); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { map[i][j]=read(); if(!map[i][j])map[i][j]=m; if(map[i][j]>m)map[i][j]=m; } } prim(1); printf("%d",ans+m); return 0; }
|
Prim的随机化改进
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
| struct Edge { int u,v; }past[1000],e,e2; bool operator < (struct edge a, struct edge b) { return map[a.u][a.v]>map[b.u][b.v]; } int cnt=0,vis[1000]={0}; void random_prim(int u) { priority_queue <Edge> q; vis[u]=1; int tot=0; for(int i=1;i<=n;i++) { if(map[u][i]<inf) { e.u=u;e.v=i; q.push(e); } } for(int i=1;i<n;i++) { e=q.top();q.pop(); while(q.size()&&(vis[e.v]||rand()%(n)<1)) { if(!vis[e.v])past[++cnt]=e; e=q.top();q.pop(); } vis[e.v]=1; if(cnt) { for(;cnt>=1;cnt--) { q.push(past[cnt]); } }cnt=0; for(int i=1;i<=n;i++) { if(map[e.v][i]<inf&&!vis[i]) { e2.u=e.v;e2.v=i; q.push(e2); } } cost+=map[e.u][e.v]; } }
|
Kruscal
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| void kruscal() { tot=0;num=0; sort(edge+1,edge+1+m,cmp); for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=m;i++) { int u=edge[i].from,v=edge[i].to; u=find(u);v=find(v); if(u!=v) { fa[u]=v; num++; tot+=edge[i].dis; } if(num>=n-1)break; } }
|
LCA
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| struct Tree_Chain_Partition { Edge edge[maxn]; int cnt,head[maxn]; int dep[maxn],siz[maxn],son[maxn],fa[maxn],top[maxn]; inline void add(int a,int b) { edge[++cnt].nst=head[a]; edge[cnt].to=b; head[a]=cnt; } void dfs1(int x) { dep[x]=dep[fa[x]]+1; siz[x]=1; for(int i=head[x];i;i=edge[i].nst) { int v=edge[i].to; if(fa[x]!=v&&!fa[v]) { fa[v]=x; dfs1(v); siz[x]+=siz[v]; if(siz[son[x]]<siz[v])son[x]=v; } } } void dfs2(int x) { if(x==son[fa[x]])top[x]=top[fa[x]]; else top[x]=x; for(int i=head[x];i;i=edge[i].nst) if(fa[edge[i].to]==x)dfs2(edge[i].to); } int query(int x,int y) { while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]])swap(x,y); x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); return x; } };
|
Spfa & Dijkstra
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
| struct Spfa_Dijkstra { Edge edge[maxn]; int cnt,head[maxn]; int dis[maxn],vis[maxn]; inline void add(int a,int b) { edge[++cnt].nst=head[a]; edge[cnt].to=b; head[a]=cnt; } void spfa(int s) { queue <int> q; memset(vis,0,sizeof(vis)); memset(dis,0x3f,sizeof(dis)); q.push(s); vis[s]=1;dis[s]=0; while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i;i=edge[i].nst) { int v=edge[i].to; if(dis[v]>dis[u]+edge[i].dis) { dis[v]=dis[u]+edge[i].dis; if(!vis[v]){q.push(v);vis[v]=1;} } } } } void dijkstra(int s) { priority_queue <pair <int,int> > q; memset(vis,0,sizeof(vis)); memset(dis,0x3f,sizeof(dis)); q.push(make_pair(0,s)); dis[s]=0; while(q.size()) { int u=q.top().second; q.pop(); if(vis[u])continue; vis[u]=1; for(int i=head[u];i;i=edge[i].nst) { int v=edge[i].to; if(dis[v]>dis[u]+edge[i].dis) { dis[v]=dis[u]+edge[i].dis; q.push(make_pair(-dis[v],v)); } } } } };
|
树状数组
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| struct Tree_Array { int t[maxn<<1]; int lowbit(int x){return x&(-x);} void add(int x,int y){for(x;x<=n;x+=x&-x)t[x]+=y;} int sum(int x) { int ans=0; for(x;x;x-=x&-x)ans+=t[x]; return ans; } int query(int x,int y) { return sum(y)-sum(x-1); } };
|
线段树
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
| struct Section_Tree { int t[maxn<<2],add[maxn]; void build(int k,int l,int r) { if(l==r){t[k]=a[l];return;} int mid=l+r>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); t[k]=t[k<<1]+t[k<<1|1]; } void Add(int k,int l,int r,int v) { add[k]+=v; t[k]+=v*(r-l+1); } void pushdown(int k,int l,int r) { if(!add[k])return; int mid=l+r>>1; Add(k<<1,l,mid,add[k]); Add(k<<1|1,mid+1,r,add[k]); add[k]=0; } void query(int k,int l,int r,int x,int y) { if(l>=x&&r<=y)return t[k]; int mid=l+r>>1; int ans=0; pushdown(k,l,r); if(x<=mid)ans+=query(k<<1,l,mid,x,y); if(y>mid)ans+=query(k<<1|1,mid+1,r,x,y); return ans; } void modify(int k,int l,int r,int x,int y,int v) { if(l>=x&&r<=y)return Add(k,l,r,v); int mid=l+r>>1; pushdown(k,l,r); if(x<=mid)modify(k<<1,l,mid,x,y,v); if(y>mid)modify(k<<1|1,mid+1,r,x,y,v); t[k]=t[k<<1]+t[k<<1|1]; } };
|
OI基础数学合集
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
| struct Math { int oula(int x) { int res=x; for(int i=2;i*i<=x;i++) if(!(x%i)) { res=res-res/i; x/=i; while(!(x%i)) x/=i; } if(x>1)res=res-res/x; return res; } int count(int x) { int cnt=0; while(x) { cnt++; x=x&(x-1); } return cnt; } int p[maxn],cnt; bool m[maxn]; void prime() { cnt=0; for(int i=2;i<=n;i++) { if(!m[i])p[++cnt]=i; for(int j=1;j<=cnt&&i*p[j]<=n;j++) { m[i*p[j]]=1; if(i%p[j]==0)break; } } } int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } int lcm(int a,int b) { int c=gcd(a,b); a=a/c;b=b/c; return a*b*c; } int qpow(int a,int b,int p) { int res=1%p; while(b) { if(b&1)res=res*a%p; b>>=1; a=a*a%p; } return res; } int exgcd(int a,int b,int &x,int &y) { int t; if(b==0){x=1;y=0;return a;} t=x;x=y;y=t-(a/b)*y; return exgcd(b,a%b,x,y); } };
|
高精度
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
| struct High_Precision { void read(int* a) { int cnt=0;char b[10010]; scanf("%s",b); for(int i=strlen(b)-1;i>=0;i--) a[++cnt]=b[i]-'0'; a[0]=cnt; } void write(int* a) { for(int i=a[0];i>=1;i--) printf("%d",a[i]); printf("\n"); } void add(int* a,int* b,int* c) { int k=0; c[0]=max(a[0],b[0]); for(int i=1;i<=c[0];i++) { c[i]=a[i]+b[i]+k; k=c[i]/10; c[i]%=10; } if(k){c[0]++;c[c[0]]+=k;} } void subtract(int* a,int* b,int* c) { int k=0; if(b[0]>a[0])swap(a,b); c[0]=a[0]; for(int i=1;i<=c[0];i++) { c[i]=a[i]-b[i]-k; k=0; if(c[i]<0)c[i]+=10,k++; } while(!c[c[0]])c[0]--; } void multiply(int* a,int b,int* c) { int k=0; c[0]=a[0]; for(int i=1;i<=c[0];i++) { c[i]=a[i]*b+k; k=c[i]/10; c[i]%=10; } while(k){c[0]++;c[c[0]]+=(k%10);k/=10;} } void divide(int* a,int b,int* c) { int k=0; memcpy(c,a,sizeof(a)*10010); for(int i=c[0];i>=1;i--) { k*=10;k+=c[i];c[i]=0; if(k>=b) { c[i]=k/b; k=k%b; } } while(!c[c[0]])c[0]--; } };
|