【孤*执】#2019SX# 最后der省选模板总结 ——BY.hss

部分参照这一篇   【浮*光】 #noip总复习#  BY.hss 

 

注意省选题常见的思路：

三分极值 / 二分答案

贪心 + 多数组的转移转化

正逆序处理：倒推法

找规律，确定单调性

多区间问题的处理：倍增法（RMQ）

 

【重点中的重点】

 

（1）离散化

int kt[N],a[N]; //辅助数组kt[]int main(){for(int i=1;i<=n;i++) cin>>a[i],kt[i]=a[i];sort(kt+1,kt+n+1); //辅助数组进行排序m=unique(kt+1,kt+n+1)-kt-1; //注意要-kt-1for(int i=1;i<=n;i++) //↓↓第一个大于等于a[i]的位置a[i]=lower_bound(kt+1,kt+m+1,a[i])-kt; //注意只用-kt
}

 

（2）线段树

struct SegmentTree{ int l,r,sum; }tree[4*N];void PushUp(int rt){ tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum; }void build(int l,int r,int rt){ //【建树】tree[rt].l=l; tree[rt].r=r; //建立标号与区间的关系if(l==r){ scanf("%d",&tree[rt].sum); return; } //叶子节点int mid=(l+r)/2; build(l,mid,rt<<1),build(mid+1,r,rt<<1|1);PushUp(rt); //将修改值向上传递
}void add(int p,int rt){ //【单点修改】if(tree[rt].l==tree[rt].r){ tree[rt].sum+=y; return; } //叶子节点int mid=(tree[rt].l+tree[rt].r)>>1;if(p<=mid) add(p,rt<<1); else add(p,rt<<1|1);tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum; //pushup
}void query(int p,int rt){ //【单点查询】if(tree[rt].l==tree[rt].r){ ans=tree[rt].sum; return; } //叶子节点int mid=(tree[rt].l+tree[rt].r)>>1;if(p<=mid) query(p,rt<<1); else query(p,rt<<1|1);
}void sum(int rt){ //【区间查询求和】if(tree[rt].l>=x&&tree[rt].r<=y) //区间完全包含{ ans+=tree[rt].sum; return; }int mid=(tree[rt].l+tree[rt].r)>>1;if(x<=mid) sum(rt<<1); //区间部分重叠，递归左右if(y>=mid+1) sum(rt<<1|1);
}

 

void PushDown(int l,int r,int rt){ //tag是区间修改的标记int mid=(l+r)>>1; if(tree[rt].tag==-1||l==r) return;tree[rt<<1].tag=tree[rt<<1|1].tag=tree[rt].tag,tree[rt<<1].ans=(tree[rt].tag==0)?(mid-l+1):0;tree[rt<<1|1].ans=(tree[rt].tag==0)?(r-mid):0;tree[rt<<1].l=tree[rt<<1].r=tree[rt<<1].ans;tree[rt<<1|1].l=tree[rt<<1|1].r=tree[rt<<1|1].ans;tree[rt].tag=-1; //标记每次下移一位，并清空上一位置的标记
}

比较复杂的push_down（【p2894】酒店）

 

（3）树状数组

void add(ll x,ll k) //单点修改、维护前缀和{ for(i=x;i<=n;i+=i&-i) c[i]+=k; }ll query(ll x) //区间查询、查询前缀和{ ll sum=0; for(i=x;i>0;i-=i&-i) sum+=c[i]; return sum; }

 

（4）主席树

主程序中： for(int i=1;i<=n;i++) //对应颜色的位置上+1reads(col[i]),update(rt[i-1],rt[i],1,MAX,col[i],1);void update(int las_,int &now_,int l,int r,int val,int op){now_=++node_cnt; //主席树动态开点：寻找新值val的位置，建出这条新链ls[now_]=ls[las_],rs[now_]=rs[las_],sum[now_]=sum[las_]+op;if(l==r) return; int mid=(l+r)>>1;if(val<=mid) update(ls[las_],ls[now_],l,mid,val,op);else update(rs[las_],rs[now_],mid+1,r,val,op);
}int query(int u,int v,int l,int r,int k){ //查询区间中颜色k的个数if(l==r) return sum[v]-sum[u]; int mid=(l+r)>>1;if(k<=mid) return query(ls[u],ls[v],l,mid,k);else return query(rs[u],rs[v],mid+1,r,k); //递归子树寻找位置k
} //query(rt[l-1],rt[r],1,MAX,k) //寻找区间[l,r]中颜色k的个数

 

（5）Trie

bool tail[SIZE]; //标记串尾元素
int trie[SIZE][26],tot=1; //SIZE:字符串最大长度（层数）
//tot为节点编号,用它可以在trie数组中表示某层的某字母是否存在void insert(char* ss){ //插入一个字符串int len=strlen(ss),p=1; //p初始化为根节点1for(int k=0;k){int ch=ss[k]-'a'; //小写字符组成串的某个字符，变成数字if(trie[p][ch]==0) trie[p][ch]=++tot; //trie存编号tot//↑↑↑不存在此层的这个字符，新建结点，转移边p=trie[p][ch]; //指针移动，连接下一个位置} tail[p]=true; //s中字符扫描完毕，tail标记字符串的末位字符（的编号p）
}bool searchs(char* ss){ //检索字符串是否存在int len=strlen(ss),p=1; //p初始化为根节点for(int k=0;k){p=trie[p][ss[k]-'a']; //寻找下一处字符if(p==0) return false; //某层字符没有编号，不存在，即串也不存在} return tail[p]; //判断最后一个字符所在的位置是否是某单词的末尾
}

 

（6）KMP

void pre(){ //【预处理nextt[i]】nextt[1]=0; int j=0; //j指针初始化为0for(int i=1;i//a数组自我匹配，从i+1=2与1比较开始while(j>0&&a[i+1]!=a[j+1]) j=nextt[j];//↑自身无法继续匹配且j还没减到0，考虑返回匹配的剩余状态if(a[i+1]==a[j+1]) j++; //这一位匹配成功nextt[i+1]=j; //记录这一位向前的最长匹配
    }
}void kmp(){ //在b串中寻找a串出现的位置int ans=0,j=0;for(int i=0;i//扫描b,寻找a的匹配while(b[i+1]!=a[j+1]&&j>0) j=nextt[j];//↑不能继续匹配且j还没减到0（之前的匹配有剩余状态）if(b[i+1]==a[j+1]) j++; //匹配加长，j++if(j==m){ //【一定要把这个判断写在j++的后面！】printf("%d\n",i+1-m+1); //子串a的起点在母串b中的位置j=nextt[j]; //继续寻找匹配} //【↑↑巧妙↑↑这里不用返回0，只用返回上一匹配值】} //注意：如果询问串的不重叠出现次数，则j必须变成0
}

 

（7）后缀数组

const int maxn=500019; int n,m; char s[maxn];int rank[maxn],b[maxn],sa[maxn],tp[maxn],tax[maxn],height[maxn];void qsort(){ //（1）基数排序for(int i=0;i<=m;i++) tax[i]=0;for(int i=1;i<=n;i++) tax[rank[i]]++;for(int i=1;i<=m;i++) tax[i]+=tax[i-1];for(int i=n;i>=1;i--) sa[tax[rank[tp[i]]]--]=tp[i];
}void SuffixSort(){ //（2）后缀排序for(int i=1;i<=n;i++) rank[i]=s[i],tp[i]=i;m=519; qsort(); //第一次基数排序for(int k=1;k<=n;k<<=1){int p=0; for(int i=n-k+1;i<=n;i++) tp[++p]=i;//for(int i=1;i<=k;i++) tp[++p]=n-k+i;for(int i=1;i<=n;i++) if(sa[i]>k) tp[++p]=sa[i]-k;qsort(); // swap(rank,tp); for(int i=1;i<=n;i++) //注意此处数组交换的方式b[i]=tp[i],tp[i]=rank[i],rank[i]=b[i]; rank[sa[1]]=p=1;for(int i=2;i<=n;i++)rank[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+k]==tp[sa[i-1]+k])?p:++p;if(p>=n) break; m=p;}
}void getH(){ //（3）求height[]int k=0; for(int i=1;i<=n;i++){if(k) k--; int j=sa[rank[i]-1];while(s[i+k]==s[j+k]) k++; height[rank[i]]=k;  }
} //注意：此模板字符串从1位置开始，即scanf("%s",s+1);

 

（8）树链剖分

void dfs1(ll u,ll fa_){ //第一遍dfs：求子树大小和重儿子siz[u]=1,fa[u]=fa_,dep[u]=dep[fa_]+1;for(ll i=head[u];i;i=e[i].nextt){if(e[i].ver==fa_) continue;dfs1(e[i].ver,u),siz[u]+=siz[e[i].ver]; //计算sizeif(siz[e[i].ver]>siz[son[u]]) son[u]=e[i].ver; //重儿子
    }
}void dfs2(ll u,ll fa_){ //第二遍dfs：确定dfs序和top值if(son[u]){ //先走重儿子，使重链上的各节点在线段树中的编号连续seg[son[u]]=++seg[0]; //节点编号、记入线段树中rev[seg[0]]=son[u]; //记录对应的原始编号top[son[u]]=top[u],dfs2(son[u],u); //↑↑此位置是已有的重链的节点，更新top值，继续递归} for(ll i=head[u];i;i=e[i].nextt){ //递归轻边if(top[e[i].ver]) continue; //除去u的重儿子或父亲seg[e[i].ver]=++seg[0],rev[seg[0]]=e[i].ver; //加入线段树top[e[i].ver]=e[i].ver,dfs2(e[i].ver,u);//↑↑先递归到的轻边上的点(dep值min)，所在重链的top一定是自己
    }
}ll query(ll x,ll y){ //路径询问ll fx=top[x],fy=top[y],ans=0;while(fx!=fy){ //不在同一重链上，选择深度较大的跳到重链top的faif(dep[fx]<dep[fy]) swap(x,y),swap(fx,fy); ans=ans+get(1,1,seg[0],seg[fx],seg[x]); //边跳边统计答案x=fa[fx],fx=top[x]; //往上跳、并更新当前所在点的top值(所在重链)} if(dep[x]>dep[y]) swap(x,y); //x、y已在同一条重链上 ans=ans+get(1,1,seg[0],seg[x],seg[y]); return ans; //直接统计
}

 

（9）网络流最大流

• 最小割 = 最大流 ；（有正负权值时）最大权闭合子图 = s连的正权值之和 - min_cut 。

int s,t,tot=1,n,m,ans,head[N],dep[N],cur[N]; //s为源点，t为汇点 struct node{ int nextt,ver,w; }e[M];void add(int x,int y,int z){ e[++tot].ver=y,e[tot].nextt=head[x],e[tot].w=z,head[x]=tot; }bool bfs(){memset(dep,0,sizeof(dep)); //dep记录深度 memcpy(cur,head,sizeof(head));queue<int> q; while(!q.empty()) q.pop();dep[s]=1; q.push(s);while(!q.empty()){int u=q.front(); q.pop();for(int i=head[u];i;i=e[i].nextt)if((e[i].w>0)&&(dep[e[i].ver]==0)) //分层 dep[e[i].ver]=dep[u]+1,q.push(e[i].ver);} if(dep[t]!=0) return 1;else return 0; //此时不存在分层图也不存在增广路
}int dfs(int u,int lastt){ int cnt=0;if(u==t) return lastt; //lastt：此点还剩余的流量for(int i=cur[u];i&&cnte[i].nextt){ cur[u]=i; //当前弧优化 if((dep[e[i].ver]==dep[u]+1)&&(e[i].w!=0)){int f=dfs(e[i].ver,min(lastt-cnt,e[i].w)); if(f>0){ e[i].w-=f,e[i^1].w+=f; cnt+=f; } }} if(cnt1; return cnt;
}void dinic(){ ans=0; while(bfs()) ans+=dfs(s,2e9); }

 

（10）网络流费用流

struct edge{ ll ver,nextt,flow,cost; }e[2*N];ll tot=-1,n,m,S,T,maxf=0,minc=0;ll flow[N],head[N],dist[N],inq[N],pre[N],lastt[N];void add(ll a,ll b,ll f,ll c)
{ e[++tot].nextt=head[a],head[a]=tot,e[tot].ver=b,e[tot].flow=f,e[tot].cost=c; } bool spfa(ll S,ll T){queue q;memset(inq,0,sizeof(inq));memset(flow,0x7f,sizeof(flow));memset(dist,0x7f,sizeof(dist));q.push(S),dist[S]=0,pre[T]=-1,inq[S]=1;while(!q.empty()){ll x=q.front(); q.pop(); inq[x]=0;for(ll i=head[x];i!=-1;i=e[i].nextt){if(e[i].flow>0&&dist[e[i].ver]>dist[x]+e[i].cost){dist[e[i].ver]=dist[x]+e[i].cost;pre[e[i].ver]=x,lastt[e[i].ver]=i;flow[e[i].ver]=min(flow[x],e[i].flow);if(!inq[e[i].ver])q.push(e[i].ver),inq[e[i].ver]=1;}}} return pre[T]!=-1;
}void mcmf(){while(spfa(S,T)){ll now=T; //↓↓最小费用最大流maxf+=flow[T],minc+=dist[T]*flow[T];while(now!=S){ //↓↓正边流量-，反边流量+e[lastt[now]].flow-=flow[T];e[lastt[now]^1].flow+=flow[T]; //↑↑利用xor1“成对储存”的性质now=pre[now]; //维护前向边last，前向点pre
        }}
}// 注意：tot=1，memset(head,-1,sizeof(head)); 

 

（11）二分图匹配

for(int i=1;i<=n;i++) //加入左侧每个节点，判断是否存在增广路memset(vis,false,sizeof(vis)),ans+=dfs(i); //计算最大匹配边数bool dfs(int x){for(int i=head[x];i;i=e[i].nextt) //寻找连边if(!vis[e[i].ver]){ //当前右节点在新左节点的匹配中未访问过vis[e[i].ver]=true; //标记这个未访问过的右边点if(!match[e[i].ver]||dfs(match[e[i].ver])) //如果空闲 或 原匹配的点可以让位{ match[e[i].ver]=x; return true; } //左节点x可以占用这个右节点y} return false; //无法找到匹配，即该情况下不会出现增广路
}

 

（12）基环树找环

vector<int> G[MAXN]; //基环树int fa[MAXN]; //dfs时的父亲
int dfn[MAXN], idx;  //访问的时间
int loop[MAXN], cnt; //环void get_loop(int u) {dfn[u] = ++ idx; //记录dfn序for (int i = 0; i < G[u].size(); i ++) {int v = G[u][i]; if(v == fa[u]) continue ;if(dfn[v]) { //找到了环if(dfn[v] < dfn[u]) continue ;loop[++ cnt] = v;for ( ; v != u; v = fa[v])loop[++ cnt] = fa[v];} else fa[v] = u, get_loop(v); //继续递归
    }
}

 

（13）欧拉函数 单点值 / 线性筛法

int euler(int x){int ans=x;for(int i=2;i*i<=x;i++)if(x%i==0){ans=ans/i*(i-1);while(x%i==0) x/=i;} if(x>1) ans=ans/x*(x-1);return ans; //返回ϕ(x)的值
} // ϕ(n) = n∗∏(i=1~k)((ai-1)/ai);--------------------------------------------------------int phi[MAXN],vis[MAXN],prime[MAXN],tot=0;void GetPhi(int n){ //【phi线性筛法】phi[1]=1; //特例：ϕ(1)=1;for(int i=2;i<=n;i++){if(!vis[i]) prime[++tot]=i,phi[i]=i-1; //i是素数（1）for(int j=1;j<=tot&&i*prime[j]<=n;j++){ //枚举“i*质数”vis[i*prime[j]]=1; //标记“i*质数”为合数if(i%prime[j]==0) //（3）注意：剪枝，赋值后直接break;{phi[i*prime[j]]=phi[i]*prime[j];break;}else phi[i*prime[j]]=phi[i]*(prime[j]-1); } //（2）} for(int i=1;i<=n;i++) cout<endl;
}

 

（14）凸包

struct point{ double x,y; }a[10019];int sta[10019],top,n; double ans=0.0;double cross(point p0,point p1,point p2) //计算向量叉积{ return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x); }double dis(point p1,point p2)  //计算点p1p2的距离{ return sqrt((double)(p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y)); }bool cmp(point p1,point p2){ //进行极角排序double tmp=cross(a[0],p1,p2); if(tmp>0) return true;else if(tmp==0&&dis(a[0],p1)0],p2)) return true;else return false; //↑↑若角度相同，则距离小的在前面
}void init(){ //输入,并把最左下方的点放在a[0],进行极角排序。 point p0; scanf("%lf%lf",&a[0].x,&a[0].y);p0.x=a[0].x; p0.y=a[0].y; int k=0;for(int i=1;i"%lf%lf",&a[i].x,&a[i].y);if( (p0.y>a[i].y) || ((p0.y==a[i].y)&&(p0.x>a[i].x)) )p0.x=a[i].x,p0.y=a[i].y,k=i; //寻找左下角的点} a[k]=a[0],a[0]=p0; //把原来0位置的点放到k位置(互换位置)sort(a+1,a+n,cmp); //除去0号点，其余n-1个点进行极角排序
}     void graham(){ //极角排序法求凸包if(n==1) top=0,sta[0]=0;if(n==2) top=1,sta[0]=0,sta[1]=1;if(n>2){ top=1,sta[0]=0,sta[1]=1;for(int i=2;i){while(top>0&&cross(a[sta[top-1]],a[sta[top]],a[i])<=0) top--;top++; sta[top]=i; } //每加入新的点，判断要出栈的凹点，并将新点入栈
    }    
}    int main(){scanf("%d",&n); init(); graham(); //输入+极角排序+求凸包for(int i=0;i1]]);ans+=dis(a[sta[0]],a[sta[top]]); printf("%.2lf\n",ans); //凸包总周长
}

 

【一、搜索】

 

（1）dfs常见思路

1.确定dfs的边界（或剪枝） 2.记忆化搜索（或剪枝）

3.枚举方向（判断超界） 4.回溯（所有状态完全回溯）

vis[xx][yy]=true; dfs(xx,yy,...); vis[xx][yy]=false;

 

（2）树上dfs

------可用于 lca的pre_dfs 和 各种各样的树形dp 和 树链剖分

    void pre_dfs(int u,int fa_){for(int i=head[u];i;i=e[i].nextt){int v=e[i].ver; //找到下一条相连的边if(v==fa_) continue;dep[v]=dep[u]+1; //深度dist[v]=dist[u]+e[i].w; //距离fa[v]=u; pre_dfs(v,u); //记录father，递归}}

 

（3）bfs常见思路

1.起点入队，并标记访问（可能不止一个） 2.队首元素向外扩展：head++ 。

3.枚举方向，判断超界及可行性，标记访问，答案累加，节点入队：tail++ 。

    void bfs(int sx,int sy){ //BFS确定连通块node now1; now1.x=sx,now1.y=sy,q.push(now1);vis[sx][sy]=1,flag[sx][sy]=tot,num[tot]++;maps[tot][num[tot]]=now1; //记录每个连通块中每个点的坐标while(!q.empty()){ //进行BFSnode now=q.front(),now1;q.pop();for(int i=0;i<4;i++){ //上、下、左、右int xx=now.x+dx[i],yy=now.y+dy[i];if(!in_(xx,yy)||vis[xx][yy]||ss[xx][yy]!='X') continue;now1.x=xx,now1.y=yy,q.push(now1),vis[xx][yy]=1,flag[xx][yy]=tot;num[tot]++,maps[tot][num[tot]]=now1; //进队并记录信息
            }}}                            ---------洛谷【p3070】岛游记

 

（4）二分常见思路

1.用于最小化最大值/最大化最小值。 2.设定l、r、mid，进行二分。

3.设置checks函数，判断是否可行。 4.更新ans，缩小区间l、r。

 

• 整数二分、实数二分

    while(l<=r){ int mid=(l+r)>>1; if(check(mid)) ans=mid,r=mid-1; else l=mid+1; }

    while(r-l>1e-8){ mid=(l+r)/2.0; if(checks(mid)) l=mid; else r=mid; }

 

（5）二分图染色 / 判定

    bool dfs(int v,int c){color[v]=c; //把该点染成颜色c（1或-1）for(int i=0;i){if(color[G[v][i]]==c) return false; //当前点与相邻点同色if(color[G[v][i]]==0&&!dfs(G[v][i],-c))return false; //如果当前点的邻点还没被染色，就染成-c} return true; //连通的点全部完成染色
    }void solve(){for(int i=0;i)if(color[i]==0) if(!dfs(i,1)){ cout<<"no"<return; }cout<<"yes"<<endl;}

 

（6）二分图匹配

 

最大匹配

• 匹配：“任意两条边没有公共端点”的边的集合。
• 最大匹配：边数最多的“匹配”；完美匹配：两侧节点一一对应的匹配。
• 最大点独立集：两边点数相同时，左边节点的个数n-最大匹配边数。

 

main函数中的循环（每次清空vis数组）：

for(int i=1;i<=n;i++) //加入左侧每个节点，判断是否存在增广路memset(vis,false,sizeof(vis)),ans+=dfs(i); //计算最大匹配边数

 

dfs寻找最大匹配（bool类型，维护match数组）：

bool dfs(int x){for(int i=head[x];i;i=e[i].nextt) //寻找连边if(!vis[e[i].ver]){ //当前右节点在新左节点的匹配中未访问过vis[e[i].ver]=true; //标记这个未访问过的右边点if(!match[e[i].ver]||dfs(match[e[i].ver])) //如果空闲 或 原匹配的点可以让位{ match[e[i].ver]=x; return true; } //左节点x可以占用这个右节点y} return false; //无法找到匹配，即该情况下不会出现增广路
}

 

最小链覆盖与反链

• 反链：一个点集，其中任意两个点都不在同一条链上。
• 覆盖：所有点都能分布在链上时，需要的最小链数。

 

【最小链覆盖数 = 最长（反链）长度】【最长链长度 = 最小（反链）覆盖数】

    -------> 所以求反链可以转化为：求 最小链覆盖数 或 最长链长度。

 

【求最小链覆盖（最长反链）】二分图求最大匹配。

相当于把每个点拆成两个点，求最大点独立集的大小。

两边点数相同时，最大点独立集大小=左边点数n-最大匹配数。

 

【输出最小链覆盖的方案】整体思路是考虑合并原来拆开的两个点。

用vis数组来标记被右边的某个点匹配上了的左边点。

那么在左边却没有匹配上的点，肯定是某条链的端点（这个点最多只有一条边在链上）。

dfs每个在左边并且没有匹配上的点 i，找它在右边的对应端点 i（合并拆成的两个点）。

寻找右边的 i 有没有匹配（找链的连向...），dfs，直到右边的某个 x 没有匹配，

那么就说明到了此链的另一个端点。过程中输出选点情况即可。

 

void dfs2(int now){ //最小链覆盖的方案if(!match[now]){ printf("%d ",now); return; }dfs2(match[now]); printf("%d ",now); //↓↓即最小链覆盖的方案
} //相当于将一开始分开的两个点合并起来，按照匹配路径，寻找每条链的链长

 

（7）归并排序-逆序对模板

int a[maxn],ranks[maxn],ans=0; //ans记录逆序对的数量void Merge(int l,int r){ //归并排序if(l==r) return;int mid=(l+r)/2; //分治思想Merge(l,mid); Merge(mid+1,r); //递归实现int i=l,j=mid+1,k=l;while(i<=mid&&j<=r){if(a[i]>a[j]){ranks[k++]=a[j++];ans+=mid-i+1; //逆序对的个数} else ranks[k++]=a[i++];} while(i<=mid) ranks[k++]=a[i++];while(j<=r) ranks[k++]=a[j++];for(int i=l;i<=r;i++) a[i]=ranks[i]; //排序数组传入原a数组中
}

 

（8）离散化模板

int kt[N],a[N]; //辅助数组kt[]int main(){for(int i=1;i<=n;i++) cin>>a[i],kt[i]=a[i];sort(kt+1,kt+n+1); //辅助数组进行排序m=unique(kt+1,kt+n+1)-kt-1; //注意要-kt-1for(int i=1;i<=n;i++) //↓↓第一个大于等于a[i]的位置a[i]=lower_bound(kt+1,kt+m+1,a[i])-kt; //注意只用-kt
}

 

【二、字符串】

 https://www.cnblogs.com/FloraLOVERyuuji/p/10574154.html

（1）字符串哈希

H(C)=(c1*b^(m-1)+c2*b^(m-2)+....+cm*b^0) mod h。

• b为基数（base），H(C)的处理相当于把字符串看成b进制数。

 

预处理的过程通过递归计算：H(C,k)=H(C,k-1)*b+ck。

 

判断某段字符与另一匹配串是否匹配，即判断：

（↑↑某段字符：从位置k+1开始的长度为n的子串C’=ck+1 ck+2 .... ck+n;）

             H(C’) =H(C,k+n)-H(C,k)*b^n 与 H(S) 的关系。

 

判断回文：正反hash。反hash要倒序预处理，注意左右边界。

 

ull自然溢出：powers数组设成ull类型，超出ull时会自然溢出（省时）。

 

哈希散列表：取余法，用链表记录每个hash值所在的位置（即对应的余数）。

 

（2）KMP模式匹配

题目：给你两个字符串，寻找其中一个字符串是否包含另一个字符串。

 

   

原短字符串a的【自我匹配】

void pre(){ //【预处理nextt[i]】nextt[1]=0; int j=0; //j指针初始化为0for(int i=1;i//a数组自我匹配，从i+1=2与1比较开始while(j>0&&a[i+1]!=a[j+1]) j=nextt[j];//↑自身无法继续匹配且j还没减到0，考虑返回匹配的剩余状态if(a[i+1]==a[j+1]) j++; //这一位匹配成功nextt[i+1]=j; //记录这一位向前的最长匹配
    }
}

 

    【原串a与询问串b】的匹配

 

• 在b串中寻找a串出现的位置：

void kmp(){ //在b串中寻找a串出现的位置int ans=0,j=0;for(int i=0;i//扫描b,寻找a的匹配while(b[i+1]!=a[j+1]&&j>0) j=nextt[j];//↑不能继续匹配且j还没减到0（之前的匹配有剩余状态）if(b[i+1]==a[j+1]) j++; //匹配加长，j++if(j==m){ //【一定要把这个判断写在j++的后面！】printf("%d\n",i+1-m+1); //子串a的起点在母串b中的位置j=nextt[j]; //继续寻找匹配} //【↑↑巧妙↑↑这里不用返回0，只用返回上一匹配值】} //注意：如果询问串的不重叠出现次数，则j必须变成0
}

 

• 求b串与a串匹配的最大长度：

int kmp(){ int j=0; //求f[i]数组for(int i=0;i//扫描长串bwhile(( j==m || b[i+1]!=a[j+1] ) && j>0) j=nextt[j];//↑不能继续匹配且j还没减到0（之前的匹配有剩余状态）或 a在b中找到完全匹配if(b[i+1]==a[j+1]) j++; //匹配加长，j++f[i+1]=j; //此位置及之前与原串组成的最长匹配// (if(f[i+1]==m),此时a在b中找到完全匹配)
}

 

【拓展】循环同构串的最小表示法 （kmp思想）

 

（3）Trie字典树

Trie树：一种用于实现字符串快速检索的多叉树结构。

bool tail[SIZE]; //标记串尾元素
int trie[SIZE][26],tot=1; //SIZE:字符串最大长度（层数）
//tot为节点编号,用它可以在trie数组中表示某层的某字母是否存在void insert(char* ss){ //插入一个字符串int len=strlen(ss),p=1; //p初始化为根节点1for(int k=0;k){int ch=ss[k]-'a'; //小写字符组成串的某个字符，变成数字if(trie[p][ch]==0) trie[p][ch]=++tot; //trie存编号tot//↑↑↑不存在此层的这个字符，新建结点，转移边p=trie[p][ch]; //指针移动，连接下一个位置} tail[p]=true; //s中字符扫描完毕，tail标记字符串的末位字符（的编号p）
}bool searchs(char* ss){ //检索字符串是否存在int len=strlen(ss),p=1; //p初始化为根节点for(int k=0;k){p=trie[p][ss[k]-'a']; //寻找下一处字符if(p==0) return false; //某层字符没有编号，不存在，即串也不存在} return tail[p]; //判断最后一个字符所在的位置是否是某单词的末尾
}

 

• 难题：【bzoj4260】按位异或（trie树维护异或前缀和）
• 难题：【p3065】第一（拓扑排序+trie树）

 

（4）AC自动机

//统计在文本串中出现次数最多的单词。int n,cnt=0,q[100019]; string tmp[100019];struct node{ int fail,end,ch[30]; }trie[100019];struct Result{ int num,pos; }ans[100019]; //所有单词的出现次数bool operator <(Result a,Result b){if(a.num!=b.num) return a.num>b.num;else return a.pos<b.pos;
}void make_trie(string tmp,int id){ //Trie树int len=tmp.length(),p=0;for(int i=0;i){int s=tmp[i]-'a';if(!trie[p].ch[s]) trie[p].ch[s]=++cnt;p=trie[p].ch[s];} trie[p].end=id;
}void get_fail(){int l=0,r=0; //广搜head、tail指针for(int i=0;i<26;i++) if(trie[0].ch[i]!=0)trie[trie[0].ch[i]].fail=0,q[++r]=trie[0].ch[i];while(lint p=q[++l];for(int i=0;i<26;i++){ int v=trie[p].ch[i];if(v) trie[v].fail=trie[trie[p].fail].ch[i],q[++r]=v; //记录fail指针else trie[p].ch[i]=trie[trie[p].fail].ch[i]; //“虚指针”
        }}
}void AC(string tmp){ //文本串匹配int len=tmp.length(),p=0;for(int i=0;i){p=trie[p].ch[tmp[i]-'a']; int v=p;while(v) ans[trie[v].end].num++,v=trie[v].fail;}
}int main(){while(519){ cin>>n; if(n==0) break;cnt=0; memset(trie,0,sizeof(trie));for(int i=1;i<=n;i++){ cin>>tmp[i];ans[i].num=0,ans[i].pos=i,make_trie(tmp[i],i); }trie[0].fail=0; get_fail();cin>>tmp[0]; AC(tmp[0]);sort(&ans[1],&ans[n+1]); //按出现次数从大到小排序 cout<1].num<1].pos]<<endl;for(int i=2;i<=n;i++){ //出现次数相同的所有单词if(ans[i].num!=ans[i-1].num) break;cout<endl;}}
}

 

（5）Manacher算法

void Manacher(){ //求最长回文子串的长度t[0]='$',t[1]='#'; //【1】加入'#'for(int i=0;i2+2]=ss[i],t[i*2+3]='#';n=n*2+2,t[n]='%'; //更新字符串长度int last_max=0,last_id=0; //【2】求出p[]数组for(int i=1;i//↓↓继承i关于id的对称点j的最长匹配长度p[i]=(last_max>i)?min(p[2*last_id-i],last_max-i):1;while(t[i+p[i]]==t[i-p[i]]) p[i]++; //然后p[i]自身进行拓展if(last_max//更新mx和idans_Len=max(ans_Len,p[i]-1); //最长回文子串的长度
    }
}

 

（6）后缀数组

https://www.cnblogs.com/FloraLOVERyuuji/p/10382408.html

const int maxn=500019; int n,m; char s[maxn];int rank[maxn],b[maxn],sa[maxn],tp[maxn],tax[maxn],height[maxn];void qsort(){ //（1）基数排序for(int i=0;i<=m;i++) tax[i]=0;for(int i=1;i<=n;i++) tax[rank[i]]++;for(int i=1;i<=m;i++) tax[i]+=tax[i-1];for(int i=n;i>=1;i--) sa[tax[rank[tp[i]]]--]=tp[i];
}void SuffixSort(){ //（2）后缀排序for(int i=1;i<=n;i++) rank[i]=s[i],tp[i]=i;m=519; qsort(); //第一次基数排序for(int k=1;k<=n;k<<=1){int p=0; for(int i=n-k+1;i<=n;i++) tp[++p]=i;//for(int i=1;i<=k;i++) tp[++p]=n-k+i;for(int i=1;i<=n;i++) if(sa[i]>k) tp[++p]=sa[i]-k;qsort(); // swap(rank,tp); for(int i=1;i<=n;i++) //注意此处数组交换的方式b[i]=tp[i],tp[i]=rank[i],rank[i]=b[i]; rank[sa[1]]=p=1;for(int i=2;i<=n;i++)rank[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+k]==tp[sa[i-1]+k])?p:++p;if(p>=n) break; m=p;}
}void getH(){ //（3）求height[]int k=0; for(int i=1;i<=n;i++){if(k) k--; int j=sa[rank[i]-1];while(s[i+k]==s[j+k]) k++; height[rank[i]]=k;  }
} //注意：此模板字符串从1位置开始，即scanf("%s",s+1);

 

【三、数据结构】

 

（1）树状数组

 

单点修改，区间查询：ans=query(y)-query(x-1)。

void add(ll x,ll k) //单点修改、维护前缀和{ for(i=x;i<=n;i+=i&-i) c[i]+=k; }ll query(ll x) //区间查询、查询前缀和{ ll sum=0; for(i=x;i>0;i-=i&-i) sum+=c[i]; return sum; }

 

区间修改，单点查询：c[x]被设置为差分数组前缀和，初始化为0。

区间修改：add(x,k),add(y+1,-k); 单点查询：ans=a[x]+query(x);

 

区间修改，区间查询：维护两个数组的前缀和。

sum1[i]=d[i]; sum2[i]=d[i]∗i; (d是差分数组)

直接把a数组处理成前缀和的形式（省略sum数组）：

scanf("%lld",&a[i]),a[i]+=a[i-1];

区间修改：add(x,k),add(y+1,-k);

区间查询：query(y)-query(x-1)+a[y]-a[x-1];

 

每次用【差分】思路修改时：sum1[x]+k,sum1[y+1]-k ; sum2[x]+x*k,sum2[y+1]-(y+1)*k。

void add(ll x,ll k) //维护(差分数组的)区间前缀和{ for(int i=x;i<=n;i+=i&-i) sum1[i]+=k,sum2[i]+=x*k; }

 

查询位置x的差分前缀和即：(x+1)*sum1数组中p的前缀和-sum2数组中p的前缀和。

ll query(ll x) //查询(差分数组的)区间前缀和{ ll sum=0; for(int i=x;i>0;i-=i&-i) sum+=(x+1)*sum1[i]-sum2[i]; return sum; }

 

二维 —— 单点修改，区间查询

void add(ll x,ll y,ll k){ //【单点修改】for(int i=x;i<=n;i+=i&-i)for(int j=y;j<=m;j+=j&-j) c[i][j]+=k;
} //【维护二维前缀和】
 
ll query(ll x,ll y){ //【查询二维前缀和】ll sum=0; //即：从左上角的(1,1)到(x,y)的矩阵和for(int i=x;i>=1;i-=i&-i)for(int j=y;j>=1;j-=j&-j) sum+=c[i][j];return sum; //返回二维前缀和
}

 

二维 —— 区间修改，单点查询

修改时：add(x,y,k),add(xx+1,yy+1,k),add(xx+1,y,-k),add(x,yy+1,-k);

修改时用到了差分的思想，查询时直接 a[x][y]+query(x,y) 即可。

 

（2）单调队列

 

1、维护队首可行性，head++；

2、维护队尾单调性，并插入当前元素；

3、取出队头的最优解，进行DP转移。

 

int head=1,tail=1; //【滑动窗口·区间max】
 
q[1].x=a[1]; q[1].id=1; //初始点为1for(int i=2;i<=n;i++){ //从2开始循环while(head<=tail && q[head].id1) head++; //id的作用：判断区间长度if(i>=m) printf("%d\n",q[head].x); //每一次的队头都是当前段最大值while(head<=tail && q[tail].x<=a[i]) tail--;//↑↑新数比前几个大，前几个不可能再成为最大值（可能不止一个）q[++tail].x=a[i]; q[tail].id=i; //a[i]加入队尾//即：维护一个单调递减队列，如果后方有数更大，前面就全部删除。
}

 

（3）线段树

 

struct SegmentTree{ int l,r,sum; }tree[4*N];void PushUp(int rt){ tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum; }void build(int l,int r,int rt){ //【建树】tree[rt].l=l; tree[rt].r=r; //建立标号与区间的关系if(l==r){ scanf("%d",&tree[rt].sum); return; } //叶子节点int mid=(l+r)/2; build(l,mid,rt<<1),build(mid+1,r,rt<<1|1);PushUp(rt); //将修改值向上传递
}void add(int p,int rt){ //【单点修改】if(tree[rt].l==tree[rt].r){ tree[rt].sum+=y; return; } //叶子节点int mid=(tree[rt].l+tree[rt].r)>>1;if(p<=mid) add(p,rt<<1); else add(p,rt<<1|1);tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum; //pushup
}void query(int p,int rt){ //【单点查询】if(tree[rt].l==tree[rt].r){ ans=tree[rt].sum; return; } //叶子节点int mid=(tree[rt].l+tree[rt].r)>>1;if(p<=mid) query(p,rt<<1); else query(p,rt<<1|1);
}void sum(int rt){ //【区间查询求和】if(tree[rt].l>=x&&tree[rt].r<=y) //区间完全包含{ ans+=tree[rt].sum; return; }int mid=(tree[rt].l+tree[rt].r)>>1;if(x<=mid) sum(rt<<1); //区间部分重叠，递归左右if(y>=mid+1) sum(rt<<1|1);
}

 

（4）点分治

 

主程序中： root=0; sum=f[0]=n; //一开始，root初始化为0，用于找重心 
                   getroot(1,0); solve(root); //从重心开始点分治

 

int n,m,k,head[N],cnt; //head[]和cnt(=tot)int root,sum; //当前查询的根，当前递归的这棵树的大小 int vis[N]; //某一个点是否被当做根过 int sz[N]; //每个点下面子树的大小 
int f[N]; //每个点为根时，最大子树大小 int dep[N]; //每个点的深度(此时是与根节点的距离) 
int o[N]; //每个点的深度(继承dep[]，用于排序，进而用于二分)int ans; //最终统计的答案 void getroot(int u,int fa){ //dfs求【重心】和【子树大小】sz[u]=1; f[u]=0;for(int i=head[u];i;i=e[i].nextt){int v=e[i].ver; if(v==fa||vis[v]) continue;getroot(v,u); sz[u]+=sz[v]; f[u]=max(f[u],sz[v]);} f[u]=max(f[u],sum-sz[u]); //注意：可能是另外一半的树if(f[u]//更新重心
}void getdeep(int u,int fa){ //dfs求出与根节点的【距离dep】o[++cnt]=dep[u]; //用于排序for(int i=head[u];i;i=e[i].nextt){int v=e[i].ver; if(v==fa||vis[v]) continue;dep[v]=dep[u]+e[i].w; getdeep(v,u);}
}int calc(int u,int d0){ 
//↑↑↑此时以u为根节点，统计子树中符合条件的点对个数cnt=0; dep[u]=d0; getdeep(u,0);sort(o+1,o+cnt+1); //排序，便于二分int l=1,r=cnt,res=0;while(l<r){ if(o[l]+o[r]<=k) res+=r-l,l++;else r--; //二分求符合条件的点对个数} return res;
}void solve(int u){ans+=calc(u,0); vis[u]=1;//↑↑会产生非法路径（被u的某个子树完全包含，路径不能合并）for(int i=head[u];i;i=e[i].nextt){ //递归子树int v=e[i].ver; if(vis[v]) continue; //faans-=calc(v,e[i].w); //容斥原理去除非法答案//↑↑在处理子树时，将初始长度设为连接边长e[i].w;//这样做就相当于给子树的每个组合都加上了u—>..的路径。sum=sz[v]; root=0; //重设当前总树大小，寻找新的分治点getroot(v,0); solve(root); //递归新的分治点（重心）
    }
}

 

（5）分块&莫队

https://www.cnblogs.com/FloraLOVERyuuji/p/10428197.html

 

while(l>q[i].l) add(col[--l]);
while(rr]);
while(l]);
while(r>q[i].r) del(col[r--]);
//↑↑q[i].l/r即正在处理的询问区间的两个端点

 

int block=(int)sqrt(n); //分块
for(int i=1;i<=n;i++) pos[i]=(i-1)/block+1;
for(int i=1;i<=m;i++) reads(q[i].l),reads(q[i].r),q[i].id=i;
sort(q+1,q+m+1,cmp); solve(); //离线，进行莫队算法
sort(q+1,q+m+1,cmp_id); //复原询问的编号

 

（6）树链剖分 / 平衡树 / 左偏树（可并堆） / 主席树 见上面

 

【四、图论】

 

（1）Tarjan缩点

 

int dfn[N],low[N],stack[N],vis[N];int dfn_=0,top_=0,sum=0,col[N];//dfn序，栈中位置top，强连通个数sum，每点所属连通块编号col[i]for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);void tarjan(int u){ //dfn_记录当前dfs序到达的数字
    dfn[u]=low[u]=++dfn_,vis[u]=1,stack[++top_]=u; //步骤一：初始化for(int i=head[u];i;i=e[i].nextt){ //步骤二：枚举连向点，递归更新if(!dfn[e[i].ver]) tarjan(e[i].ver),low[u]=min(low[u],low[e[i].ver]);else if(vis[e[i].ver]) low[u]=min(low[u],dfn[e[i].ver]); //这里写dfn或low都可以} //↑↑步骤三：已经到达过，判断是否在当前栈内（栈内都是当前情况下能相连的点）if(dfn[u]==low[u]){col[u]=++sum; vis[u]=0;while(stack[top_]!=u){ //u上方的节点是可以保留的col[stack[top_]]=sum;vis[stack[top_]]=0,top_--;} top_--; //col数组记录每个点所在连通块的编号
    }
}int times[N],du[N]; //times数组/du数组记录每个强连通分量的大小/入度for(int u=1;u<=n;u++){for(int i=head[u];i;i=e[i].nextt)if(col[e[i].ver]!=col[u]) du[col[e[i].ver]]++;times[col[u]]++; //记录强连通分量大小
}

 

（2）拓扑排序

 

queue<int>q; //给出n个顺序关系，问是否合法。bool tp_sort(){ //拓扑排序判环for(int i=1;i<=n;i++)if(rd[i]==0) q.push(i);while(!q.empty()){x=q.front(),q.pop(),cnt++;for(int i=head[x];i;i=e[i].nextt){rd[e[i].ver]--; //rd--，相当于‘删边’if(rd[e[i].ver]==0) q.push(e[i].ver);}} if(cnt==n) return true; return false;
} //拓扑判环

 

（3）差分约束

 

• 给出一些形如x-y<=b不等式的约束，问你满足条件是否有解。

方法：找适当的方式建边（一般是在x,y之间建立长度为b的边），转换成最短路问题。

建边：1.b-a<=-c，w(b,a)=-c; 2.w(a,b)=c; 3.w(a,b)=w(b,a)=0。

因为随便值为多少，所以从0向1~n每个点连边w[0,i]=0。用SPFA求最短路，出现环则No。

 

（4）2-sat 问题 

 

 

• 对于每个要求(a∨b)，转换为 （ ¬a→b ）∧（¬b→a ） ，

 

• 即：「若 a 假则 b 必真，若 b 假则 a 必真」。

• 然后按照箭头的方向建有向边，进行相关的缩点、拓扑排序操作。

 

 

#include
#include
#include
#include
#include
#include
#include
#include
#include

【p4782】2-sat问题

 

 

（5）割点

 

/*【p3225】矿场搭建 *///【标签】数学统计 + 分情况讨论 + 割点 + 无向图双连通分量/* 割点：在一个【无向图】中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割点【集合】。  */// 双连通分量：无向图中的强连通分量，去掉任意一个节点都不会改变连通性/*【tarjan算法求割点】
1.判断根节点：计算其子树数量，如果有2棵即以上的子树，就是割点。
2.回顾一下low[i]的定义：u及其子树中的点，能够连向到的dfn最小的点的dfn值。
2.对于边(u,v)，如果low[v]>=dfn[u]，那么low[v]没有返祖边，此时u就是割点。*//*【思路】统计每个双连通分量里的割点的个数，并分情况讨论。
1.若该连通分量里割点>=2，可以通过其他割点跑到其他的双连通分量里。
2.若该连通分量里割点=1，所以要在任意一个非割点处建一个出口。
3.若该连通分量里割点=0，说明它与外界完全不连通，需要建两个出口以防万一。*/
const int N=519;int n,m,tot=0,head[N],dfn[N],low[N],cut[N],vis[N],root;int dfn_=0,sum,cnt,cut_num; //连通块数sum，当前连通块节点数、割点数int kase=0; ll ans1,ans2; //选点数，方案数struct node{ int ver,nextt; }e[N*2];void add(int u,int v){ e[++tot].ver=v,e[tot].nextt=head[u],head[u]=tot; }void tarjan(int u,int fa){ //【tarjan求割点】
    dfn[u]=low[u]=++dfn_; int child=0;//fa是子树的根节点，如果儿子数>=2则是割点for(int i=head[u];i;i=e[i].nextt){if(!dfn[e[i].ver]){ tarjan(e[i].ver,u),low[u]=min(low[u],low[e[i].ver]);if(low[e[i].ver]>=dfn[u]&&u!=root) cut[u]=true;if(u==root) child++; //root节点的儿子数++} low[u]=min(low[u],dfn[e[i].ver]);} if(child>=2&&u==root) cut[u]=true;
}void dfs(int u){ //遍历每个连通块vis[u]=sum; cnt++; //节点数cnt++for(int i=head[u];i;i=e[i].nextt){if(cut[e[i].ver]&&vis[e[i].ver]!=sum) cut_num++,vis[e[i].ver]=sum; //e[i].ver是割点if(!vis[e[i].ver]) dfs(e[i].ver); //非割点
    }
}void init(){memset(head,0,sizeof(head));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(cut,0,sizeof(cut));memset(vis,0,sizeof(vis));dfn_=n=tot=sum=ans1=0,ans2=1;
}int main(/*hs_love_wjy*/){while(scanf("%d",&m)==1&&m){init(); //日常清零for(int i=1,u,v;i<=m;i++){reads(u),reads(v),n=max(n,max(u,v));add(u,v),add(v,u); //↑↑记录点的总个数n} for(int i=1;i<=n;i++) if(!dfn[i]) root=i,tarjan(i,0);for(int i=1;i<=n;i++) if(!vis[i]&&!cut[i]){sum++; cnt=cut_num=0; dfs(i); //到达一个新的连通块if(!cut_num) ans1+=2,ans2*=cnt*(cnt-1)/2; //建两个if(cut_num==1) ans1++,ans2*=cnt; //建一个} printf("Case %d: %lld %lld\n",++kase,ans1,ans2);}
}

 

【五、网络流】

 

（1）最大流 / 最小割

 网络流最小割  最小割 = 最大流 。注意拆点操作。

（有正负权值时）最大权闭合子图 = s连的正权值之和 - min_cut 。

int s,t,tot=1,n,m,ans,head[N],dep[N],cur[N]; //s为源点，t为汇点 struct node{ int nextt,ver,w; }e[M];void add(int x,int y,int z){ e[++tot].ver=y,e[tot].nextt=head[x],e[tot].w=z,head[x]=tot; }bool bfs(){memset(dep,0,sizeof(dep)); //dep记录深度 memcpy(cur,head,sizeof(head));queue<int> q; while(!q.empty()) q.pop();dep[s]=1; q.push(s);while(!q.empty()){int u=q.front(); q.pop();for(int i=head[u];i;i=e[i].nextt)if((e[i].w>0)&&(dep[e[i].ver]==0)) //分层 dep[e[i].ver]=dep[u]+1,q.push(e[i].ver);} if(dep[t]!=0) return 1;else return 0; //此时不存在分层图也不存在增广路
}int dfs(int u,int lastt){ int cnt=0;if(u==t) return lastt; //lastt：此点还剩余的流量for(int i=cur[u];i&&cnte[i].nextt){ cur[u]=i; //当前弧优化 if((dep[e[i].ver]==dep[u]+1)&&(e[i].w!=0)){int f=dfs(e[i].ver,min(lastt-cnt,e[i].w)); if(f>0){ e[i].w-=f,e[i^1].w+=f; cnt+=f; } }} if(cnt1; return cnt;
}void dinic(){ ans=0; while(bfs()) ans+=dfs(s,2e9); }

 

（2）最小费用最大流

 

struct edge{ ll ver,nextt,flow,cost; }e[2*N];ll tot=-1,n,m,S,T,maxf=0,minc=0;ll flow[N],head[N],dist[N],inq[N],pre[N],lastt[N];void add(ll a,ll b,ll f,ll c)
{ e[++tot].nextt=head[a],head[a]=tot,e[tot].ver=b,e[tot].flow=f,e[tot].cost=c; } bool spfa(ll S,ll T){queue q;memset(inq,0,sizeof(inq));memset(flow,0x7f,sizeof(flow));memset(dist,0x7f,sizeof(dist));q.push(S),dist[S]=0,pre[T]=-1,inq[S]=1;while(!q.empty()){ll x=q.front(); q.pop(); inq[x]=0;for(ll i=head[x];i!=-1;i=e[i].nextt){if(e[i].flow>0&&dist[e[i].ver]>dist[x]+e[i].cost){dist[e[i].ver]=dist[x]+e[i].cost;pre[e[i].ver]=x,lastt[e[i].ver]=i;flow[e[i].ver]=min(flow[x],e[i].flow);if(!inq[e[i].ver])q.push(e[i].ver),inq[e[i].ver]=1;}}} return pre[T]!=-1;
}void mcmf(){while(spfa(S,T)){ll now=T; //↓↓最小费用最大流maxf+=flow[T],minc+=dist[T]*flow[T];while(now!=S){ //↓↓正边流量-，反边流量+e[lastt[now]].flow-=flow[T];e[lastt[now]^1].flow+=flow[T]; //↑↑利用xor1“成对储存”的性质now=pre[now]; //维护前向边last，前向点pre
        }}
}//注意：tot=1，memset(head,-1,sizeof(head)); 

 

【六、动态规划】

 

（1）树形DP

https://www.cnblogs.com/FloraLOVERyuuji/p/10560021.html

 

（2）基环树DP

 https://www.cnblogs.com/FloraLOVERyuuji/p/10419674.html

 

（3）状压DP

https://www.cnblogs.com/FloraLOVERyuuji/p/10601568.html

 

（4）矩阵优化DP

https://www.cnblogs.com/FloraLOVERyuuji/p/10512899.html

 

（5）斜率优化DP

• 对于每个斜率方程 (Y(j2)-Y(j1))/(X(j2)-X(j1))：

    1.将数据进行预处理(求sum等操作)，优化序列。

    2.写状态转移方程，如果是二维，要使用二维单调队列。

    3.推导不等式，化成斜率的一般式，一般使用化除为乘。

    4.从而得到X,Y的定义式，用double类型表示出来。

    5.建立一个类似优先队列的斜率单调队列。

    6.维护头尾可行性以及斜率单调性，队头为最优答案。

 

【七、数论】

 

（1）欧拉函数

https://www.cnblogs.com/FloraLOVERyuuji/p/10423022.html

 

 

int euler(int x){int ans=x;for(int i=2;i*i<=x;i++)if(x%i==0){ans=ans/i*(i-1);while(x%i==0) x/=i;} if(x>1) ans=ans/x*(x-1);return ans; //返回ϕ(x)的值
} // ϕ(n) = n∗∏(i=1~k)((ai-1)/ai);

 

 

int phi[MAXN],vis[MAXN],prime[MAXN],tot=0;void GetPhi(int n){ //【phi线性筛法】phi[1]=1; //特例：ϕ(1)=1;for(int i=2;i<=n;i++){if(!vis[i]) prime[++tot]=i,phi[i]=i-1; //i是素数（1）for(int j=1;j<=tot&&i*prime[j]<=n;j++){ //枚举“i*质数”vis[i*prime[j]]=1; //标记“i*质数”为合数if(i%prime[j]==0) //（3）注意：剪枝，赋值后直接break;{phi[i*prime[j]]=phi[i]*prime[j];break;}else phi[i*prime[j]]=phi[i]*(prime[j]-1); } //（2）} for(int i=1;i<=n;i++) cout<endl;
}

 

• 原根个数为φ(φ(m))；由于素数的φ(m)=m-1，所以素数的原根=φ(m-1)。

 

（2）欧拉定理

 

欧拉定理：

 

扩展欧拉定理：

 

#include
#include
#include
#include
#include
#include<string>
#include
#include

p5091 【模板】 扩展欧拉定理 // 求a^b mod m

 

（3）卢卡斯定理

 

• 公式：Lucas(C(n,m),p)=Lucas(C(n%p,m%p),p)*Lucas(C(n/p,m/p),p)

 

long long inv[100010],kk[100010],p;long long lucas(int x,int y){if(xreturn 0; //无法构成组合数，返回答案为0if(xreturn kk[x]*inv[y]*inv[x-y]%p; //x的阶乘*(y!%p的逆元)*((x-y)!%p的逆元)else return lucas(x/p,y/p)*lucas(x%p,y%p)%p;
}int main(){int T,n,m; scanf("%d",&T); while(T--){scanf("%d%d%lld",&n,&m,&p);inv[0]=inv[1]=kk[0]=kk[1]=1; //阶乘数组&&逆元数组初始化for(int i=2;i<=n+m;i++) kk[i]=kk[i-1]*i%p;for(int i=2;i<=n+m;i++) inv[i]=(p-p/i)*inv[p%i]%p;for(int i=2;i<=n+m;i++) inv[i]=inv[i-1]*inv[i]%p; //逆元的阶乘 等于 k!%p的逆元printf("%lld\n",lucas(n+m,m)); //调用卢卡斯函数
    }
}

 

（4）莫比乌斯反演

https://www.cnblogs.com/FloraLOVERyuuji/p/10539217.html

 

void get_mu(int n){mu[1]=1; for(int i=2;i<=n;i++){if(!vis[i]) primes[++cnt]=i,mu[i]=-1;for(int j=1;j<=cnt&&primes[j]*i<=n;j++){vis[primes[j]*i]=1;if(i%primes[j]==0) break;else mu[i*primes[j]]=-mu[i];}}}

 

（5）线性基

 

// 最大异或和：给定n个整数（数字可能重复），
//    在这些数中选取任意个，使得他们的异或和最大。

ll base[5019];int main(){ll n,tmp; scanf("%lld",&n);for(int i=1;i<=n;i++){ scanf("%lld",&tmp);for(int j=50;j>=0;--j) if(tmp&(1LL<<j)){ if(!base[j]) base[j]=tmp; tmp^=base[j]; } }ll ans=0; for(int i=50;i>=0;i--)if(ans<(ans^base[i])) ans^=base[i];printf("%lld\n",ans); return 0;
}

 

（6）矩阵乘法

 

struct Mat{ ll m[9][9]; }a,dp; //a是原始矩阵，dp是构造的矩阵

Mat mat_mul(Mat x,Mat y){ //矩阵乘：x*y=cMat c; memset(c.m,0,sizeof(c.m)); //【注意矩阵的‘清空’】for(ll i=1;i<=3;i++) for(ll j=1;j<=3;j++) for(ll k=1;k<=3;k++)c.m[i][j]=(c.m[i][j]%mod+x.m[i][k]*y.m[k][j]%mod)%mod; return c; }Mat mat_pow(Mat x,ll y) //矩阵快速幂：ans*x^y{  Mat ans; memset(ans.m,0,sizeof(ans.m)); //记得要随时清空for(ll p=1;p<=3;p++) ans.m[p][p]=1; //初始化为单位矩阵【清空】while(y){ if(y&1) ans=mat_mul(ans,x); x=mat_mul(x,x); y>>=1; } return ans; }

 

（7）Matrix-Tree定理

https://www.cnblogs.com/FloraLOVERyuuji/p/10524226.html

 

 

int Gauss(){ //高斯消元int ans=1; for(int i=1;i<=tot;i++){for(int j=i+1;j<=tot;j++) //tot是总点数while(f[j][i]){ int t=f[i][i]/f[j][i];for(int k=i;k<=tot;k++)f[i][k]=(f[i][k]-t*f[j][k]%mod+mod)%mod,swap(f[i][k],f[j][k]); ans=-ans; //辗转相除法} ans=(ans*f[i][i])%mod;} return (ans+mod)%mod; //注意ans可能为负数
}

 

 

（8）FFT

 

 

#include
#include
#include
#include
#include<string>
#include
#include
#include
#include

【p1919】A*B Problem

 

 

【八、计算几何】

（二维凸包 / 旋转卡壳  / 半平面交）

 

struct point{ double x,y; }a[10019];int sta[10019],top,n; double ans=0.0;double cross(point p0,point p1,point p2) //计算向量叉积{ return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x); }double dis(point p1,point p2)  //计算点p1p2的距离{ return sqrt((double)(p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y)); }bool cmp(point p1,point p2){ //进行极角排序double tmp=cross(a[0],p1,p2); if(tmp>0) return true;else if(tmp==0&&dis(a[0],p1)0],p2)) return true;else return false; //↑↑若角度相同，则距离小的在前面
}void init(){ //输入,并把最左下方的点放在a[0],进行极角排序。 point p0; scanf("%lf%lf",&a[0].x,&a[0].y);p0.x=a[0].x; p0.y=a[0].y; int k=0;for(int i=1;i"%lf%lf",&a[i].x,&a[i].y);if( (p0.y>a[i].y) || ((p0.y==a[i].y)&&(p0.x>a[i].x)) )p0.x=a[i].x,p0.y=a[i].y,k=i; //寻找左下角的点} a[k]=a[0],a[0]=p0; //把原来0位置的点放到k位置(互换位置)sort(a+1,a+n,cmp); //除去0号点，其余n-1个点进行极角排序
}     void graham(){ //极角排序法求凸包if(n==1) top=0,sta[0]=0;if(n==2) top=1,sta[0]=0,sta[1]=1;if(n>2){ top=1,sta[0]=0,sta[1]=1;for(int i=2;i){while(top>0&&cross(a[sta[top-1]],a[sta[top]],a[i])<=0) top--;top++; sta[top]=i; } //每加入新的点，判断要出栈的凹点，并将新点入栈
    }    
}    int main(){scanf("%d",&n); init(); graham(); //输入+极角排序+求凸包for(int i=0;i1]]);ans+=dis(a[sta[0]],a[sta[top]]); printf("%.2lf\n",ans); //凸包总周长
}

 

 

 

                                                                    ——时间划过风的轨迹，那个少年，还在等你

 

转载于:https://www.cnblogs.com/FloraLOVERyuuji/p/10638189.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！