我是靠谱客的博主 虚幻汉堡,这篇文章主要介绍【浮*光】 #noip总复习# hss_2018noip_rp++,现在分享给大家,希望可以做个参考。

广搜复习题 https://www.luogu.org/problemnew/show/P2324

√ 线段树复习题 https://www.luogu.org/problemnew/show/P4041

√ 最短路+dp复习题 https://www.luogu.org/problemnew/show/P1772

√ 并查集复习题 https://www.luogu.org/problemnew/show/P1661

√ dp复习题 https://www.luogu.org/problemnew/show/P3891

√ 差分约束复习题 https://www.luogu.org/problemnew/show/P3275

缩点复习题 https://www.luogu.org/problemnew/show/P3627


【零. 序言】

------头文件

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<cmath> #include<set> #include<vector> #include<map> #include<queue> using namespace std; typedef long long ll;

------读入优化

复制代码
1
2
3
4
5
6
void reads(int &x){ int fx=1;x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')fx=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} x=x*fx; //正负号 }

------并查集

复制代码
1
int find_fa(int x){ return fa[x]=(fa[x]==x)?x:find_fa(fa[x]); }

------建边

复制代码
1
2
struct node{ int nextt,ver,w; }e[M*2]; int tot=0,head[N]; void add(int x,int y,int z){ e[++tot].nextt=head[x],e[tot].ver=y,e[tot].w=z,head[x]=tot; }

------dis函数

复制代码
1
2
3
4
double dis(int i,int j){ /*注意结构体的使用*/ return sqrt((double)(S[i].x-S[j].x)*(S[i].x-S[j].x) +(double)(S[i].y-S[j].y)*(S[i].y-S[j].y)); }

------快速幂

复制代码
1
2
3
4
5
6
7
ll power(ll a,ll b,ll mod){ ll anss=1; //注意初始化为1 while(b>0){ //求a的b次方%mod if(b&1) anss=anss*a%mod; a=a*a%mod; b>>=1; } return anss; }

------埃式筛法

复制代码
1
2
3
4
5
6
7
8
9
int vis[N],primes[N],cnt=0; void init(int x){ for(int i=2;i<=x;i++) if(!vis[i]){ primes[cnt++]=i; for(int j=i+i;j<=x;j+=i) vis[j]=1; } }

------质因数分解

复制代码
1
2
3
4
5
void init(int x){ int cnt=0; for(int i=2;i*i<=x;i++) while(x%i==0) primes[++cnt]=i,x/=i; if(x>1) primes[++cnt]=x; }

------因数分解

复制代码
1
2
3
4
5
6
7
int factor[2519],cnt=0; for(int i=1;i*i<=n;i++){ if(n%i==0){ factor[++cnt]=i; if(i!=n/i) factor[++cnt]=n/i; } }

------乘法逆元

复制代码
1
2
3
4
5
6
7
8
ll inv1(ll a,ll mod){ //扩展欧几里得求逆元 ll x,y; ll d=exgcd(a,mod,x,y); if(d==1) return (x%mod+mod)%mod; return -1; } ll inv2(ll a,ll mod){ return ksm(a,mod-2,mod); } //费马小定理 void inv3(ll mod){ inv[1]=1; //线性递推求逆元 for(int i=2;i<=mod-1;i++) //求1~n的逆元 inv[i]=(mod-mod/i)*inv[mod%i]%mod,cout<<inv[i]<<" "; }

------Dijkstra

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
priority_queue < pair<int,int> > q; void dijkstra(int s){ for(int i=1;i<=n;i++) dist[i]=(int)1e9; dist[s]=0,q.push(make_pair(0,s)); //dist的相反数和出发点的编号 while(q.size()!=0){ //while(!q.empty()) int x=q.top().second; q.pop(); if(vis[x]!=0) continue; vis[x]=1; for(int i=head[x];i;i=e[i].nextt){ if(dist[e[i].ver]>dist[x]+e[i].w){ dist[e[i].ver]=dist[x]+e[i].w; q.push(make_pair(-dist[e[i].ver],e[i].ver)); } } } }

------SPFA

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void spfa(int s){ queue<int>q; //普通队列(也可以写成循环队列) for(int i=1;i<=n;i++) dist[i]=1e9; q.push(s); vis[s]=true; dist[s]=0; while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=false; for(int i=head[u];i;i=e[i].nextt) if(dist[u]+e[i].w<dist[e[i].ver]){ dist[e[i].ver]=dist[u]+e[i].w; if(!vis[e[i].ver]) //SPFA和dij的区别 vis[e[i].ver]=true,q.push(e[i].ver); } } }

------Prim

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
int a[5019][5019],dist[5019],n,w,ans=0; //↑↑↑把二维的距离数组a、在每次循环中、判断转为一维的距离数组dist bool vis[5019]; //vis数组标记点是否访问过 void prim(){ memset(dist,0x3f,sizeof(dist)); //0x3f=1061109567 memset(vis,0,sizeof(vis)); dist[1]=0; //注意设置起点 for(int i=1;i<n;i++){ //注意:树只有n-1条边 int x=0; for(int j=1;j<=n;j++) if(!vis[j]&&(x==0||dist[j]<dist[x])) x=j; vis[x]=1; for(int y=1;y<=n;y++) if(!vis[y]) dist[y]=min(dist[y],a[x][y]); } //每次寻找当前状态下、到达任意未访问点需要的最短边,并更新 }

------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
void pre_dfs(int u,int fa_){ for(int i=0;i<=19;i++) f[u][i+1]=f[f[u][i]][i], w[u][i+1]=min(w[u][i],w[f[u][i]][i]); //↑↑维护lca路径上的最小值,注意w数组不需要初始化 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; //距离 f[v][0]=u,w[v][0]=e[i].w,pre_dfs(v,u); } } int lca(int x,int y){ //找lca的主程序 int anss=(int)1e9; //找到lca路径上的最短边 if(dep[x]<dep[y]) swap(x,y); //保证dep[x]>dep[y] for(int i=20;i>=0;i--){ //注意:这里的20和上面的19都是log2n的近似取值 if(dep[f[x][i]]>=dep[y]) anss=min(anss,w[x][i]),x=f[x][i]; //↑↑↑i的2^k辈祖先的结点仍比y深,令x=f[x,i],继续向上跳 if(x==y) return anss; //若x=y,则已经找到了lca } for(int i=20;i>=0;i--) //↓↓↓未找到lca时的倍增跳法 if(f[x][i]!=f[y][i]) //更新次路径上的最短边,并继续向上跳 anss=min(anss,min(w[x][i],w[y][i])),x=f[x][i],y=f[y][i]; lca=f[x][0]; //如果只需要找lca,直接返回f[x][0]即可 return anss=min(anss,min(w[x][0],w[y][0])); //路径上的最小边 }

------trie树

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool tail[SIZE]; //标记串尾元素 int trie[SIZE][26],tot=1; //SIZE:字符串最大长度(层数) //tot为节点编号,用它可以在trie数组中表示某层的某字母是否存在 void insert(char* ss){ //插入一个字符串 int len=strlen(ss),p=1; //p初始化为根节点1 for(int k=0;k<len;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<len;k++){ p=trie[p][ss[k]-'a']; //寻找下一处字符 if(p==0) return false; //某层字符没有编号,不存在,即串也不存在 } return tail[p]; //判断最后一个字符所在的位置是否是某单词的末尾 }

------KMP匹配

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void pre(){ //【预处理nextt[i]】 nextt[1]=0; int j=0; //j指针初始化为0 for(int i=1;i<m;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<n;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("%dn",i+1-m+1); //子串a的起点在母串b中的位置 j=nextt[j]; //继续寻找匹配 } //【↑↑巧妙↑↑这里不用返回0,只用返回上一匹配值】 } //注意:如果询问串的不重叠出现次数,则j必须变成0 }

------高精度

 add:将两个高精度加数倒序,每次相加并%10,判断进位和前导0,答案倒序。

div:倒序,每次相减(-owe)、并判断这一位的owe,判断前导0、注意答案为0的情况,答案倒序。

mul:高精*单精,倒序,直接*该数,处理进位,答案倒序;高精*高精:

复制代码
1
2
3
4
5
6
7
8
len=len1+len2; //初始化答案的总长度 for(i=0;i<len1;i++) for(j=0;j<len2;j++) //↓b,c数组已经倒序 a_int[i+j]+=b_int[i]*c_int[j]; for(i=0;i<len;i++) if(a_int[i]>9) a_int[i+1]+=a_int[i]/10,a_int[i]=a_int[i]%10; while(a_int[len-1]==0) len--; //---再将a数组倒序

【一. 搜索】

         ------dfs

(1)dfs常见思路

(2)树上dfs

         ------bfs

------二分

(1)二分常见思路

(2)整数二分、实数二分

(3)二分图染色(判定)

(4)二分图匹配

------贪心

------归并排序

(1)归并排序-逆序对模板

(2)逆序对个数为k的全排列数量

(3)归并排序-平面最近点对

------离散化

【二. 字符串】

------字符串哈希

------KMP模式匹配

------Trie字典树

------AC自动机

------Manacher算法

【三. 图论】

------最小生成树

<1> Prim算法

<2> Kruskal算法

------最短路

<1> Floyd

<2> Dijkstra

<3> SPFA

<4> 统计路径条数

<5> 最短路径问题拓展

------差分约束

------强连通分量

------拓扑排序

------LCA

【四. 数据结构】

------树状数组

------线段树

------分块

【五. 动态规划】

------线性DP

------背包DP

------区间DP

------环形DP

------树形DP

------数位DP

------状压DP

------单调队列优化DP

------斜率优化DP

【六. 数论】

<1> 取整除法求和

<2> N的正约数集合

<3> 最大公约数GCD

<4> 求解不定方程---EXGCD

<5> 埃式筛质数

<6> 分解质因数

<7> 快速幂

<8> 乘法逆元

<9> 组合数

<10> Lucas定理

<11> Nim游戏


【一. 搜索】

------dfs

(1)dfs常见思路

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

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

复制代码
1
vis[xx][yy]=true; dfs(xx,yy,...); vis[xx][yy]=false;

(2)树上dfs

                          ------可用于lca的pre_dfs

复制代码
1
2
3
4
5
6
7
8
9
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,递归 } }

 ------bfs

1.起点入队,并标记访问(可能不止一个) 2.队首元素向外扩展:head++

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

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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()){ //进行BFS node 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】岛游记

------二分

(1)二分常见思路

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

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

(2)整数二分、实数二分

复制代码
1
2
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; }

(3)二分图染色(判定)

 

------------------------------详细的分析看 这里

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool dfs(int v,int c){ color[v]=c; //把该点染成颜色c(1或-1) for(int i=0;i<G[v].size();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<V;i++) if(color[i]==0) if(!dfs(i,1)) { cout<<"no"<<endl; return; } cout<<"yes"<<endl; }

(4)二分图匹配

<1>最大匹配

匹配:“任意两条边没有公共端点”的边的集合。

最大匹配:边数最多的“匹配”;完美匹配:两侧节点一一对应的匹配。

最大点独立集:两边点数相同时,左边节点的个数n-最大匹配边数。

  • main函数中的循环(每次清空vis数组):
复制代码
1
2
for(int i=1;i<=n;i++) //加入左侧每个节点,判断是否存在增广路 memset(vis,false,sizeof(vis)),ans+=dfs(i); //计算最大匹配边数
  • dfs寻找最大匹配(bool类型,维护match数组):
复制代码
1
2
3
4
5
6
7
8
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; //无法找到匹配,即该情况下不会出现增广路 }

<2>最小链覆盖与反链

反链:一个点集,其中任意两个点都不在同一条链上。

覆盖:所有点都能分布在链上时,需要的最小链数。

【最小链覆盖数 = 最长(反链)长度】【最长链长度 = 最小(反链)覆盖数】

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

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

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

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

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

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

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

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

寻找右边的 i 有没有匹配(找链的连向...),dfs,直到右边的某个 x 没有匹配,

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

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

------贪心

(1)平均数:均分纸牌问题...

(2)中位数:货仓选址问题...

  • 变式:二维转化为两个一维考虑,分别取中位数求值。
  • 动态中位数:对顶堆。判断中位数区间:+1/-1维护前缀和。

(3)排序:最小转化次数...

  • 方法:逆序对 or 每次把最大的放在最后面 or 倒序找逆序个数。

(4)拆分法:把一种物品拆成多个单个物品

  • 例题:【p3049】园林绿化。转化为01背包问题。

(5)区间问题:区间覆盖,区间选点...

  • 方法:维护左右端点,进行排序等操作。
  • 区间类型不同时(如有电压、灯管...),常把n+m个区间一起排序。

------归并排序

(1)归并排序-逆序对模板

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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数组中 }

(2)逆序对个数为k的全排列数量

DP转移:f[i][j]为前i个数字(即1~i)构成逆序对数为j的方案总数。

全排列逆序对结论:在第k个位置放第i个数,单步得到的逆序对数为 max(0,i-k)

判断i的插入位置,得到转移方程:f[i][j]=∑(f[i-1][j-i+1...j-1])。

f[i-1][]的求和可以用前缀和数组维护,同时第一维可以省略(且不需要倒序)。

(3)归并排序-平面最近点对

  • 思路:先按x坐标排序,再用分治法处理y。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
double merge(int l,int r){ double min_dist=INF; if(l==r) return min_dist; if(l+1==r) return dist(l,r); int mid=(l+r)>>1; //分治 double d1=merge(l,mid),d2=merge(mid+1,r); min_dist=min(d1,d2); int i,j,k=0; for(i=l;i<=r;i++) if(fabs(S[mid].x-S[i].x)<=min_dist) ranks[k++]=i; sort(ranks,ranks+k,cmps); for(i=0;i<k;i++) //注意这里使用的是0G for(j=i+1;j<k&&S[ranks[j]].y-S[ranks[i]].y<min_dist;j++) min_dist=min(min_dist,dist(ranks[i],ranks[j])); return min_dist; //平面最近点对 }

------离散化

(1)使用 lower_bound排序+去重

复制代码
1
2
3
4
5
6
7
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-1 for(int i=1;i<=n;i++) //↓↓第一个大于等于a[i]的位置 a[i]=lower_bound(kt+1,kt+m+1,a[i])-kt; //注意只用-kt }

(2)使用 结构体,可以 记录原编号

复制代码
1
2
3
4
5
6
7
struct node{ int x,id; }a[N]; int n,rank[N]; bool cmp(node aa,node bb){ return aa.x<bb.x; } int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i].v,a[i].id=i; sort(a+1,a+n+1,cmp); //↓↓得到原顺序下每个数的排名 for(int i=1;i<=n;i++) rank[a[i].id]=i; }

【二. 字符串】

------字符串哈希

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

b为基数,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值所在的位置(即对应的余数)。


------KMP模式匹配

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

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

  • nextt[i]:原字符串的 最长前缀 和 (以i结尾的)最长后缀 相同的长度。
复制代码
1
2
3
4
5
6
7
8
9
void pre(){ //【预处理nextt[i]】 nextt[1]=0; int j=0; //j指针初始化为0 for(int i=1;i<m;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; //记录这一位向前的最长匹配 } }

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

  • 在b串中寻找a串出现的位置:
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
void kmp(){ //在b串中寻找a串出现的位置 int ans=0,j=0; for(int i=0;i<n;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("%dn",i+1-m+1); //子串a的起点在母串b中的位置 j=nextt[j]; //继续寻找匹配 } //【↑↑巧妙↑↑这里不用返回0,只用返回上一匹配值】 } //注意:如果询问串的不重叠出现次数,则j必须变成0 }
  • 求b串与a串匹配的最大长度:
复制代码
1
2
3
4
5
6
7
8
int kmp(){ int j=0; //求f[i]数组 for(int i=0;i<n;i++){ //扫描长串b while(( 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思想)


------Trie字典树

  • Trie树:一种用于实现字符串快速检索的多叉树结构。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool tail[SIZE]; //标记串尾元素 int trie[SIZE][26],tot=1; //SIZE:字符串最大长度(层数) //tot为节点编号,用它可以在trie数组中表示某层的某字母是否存在 void insert(char* ss){ //插入一个字符串 int len=strlen(ss),p=1; //p初始化为根节点1 for(int k=0;k<len;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<len;k++){ p=trie[p][ss[k]-'a']; //寻找下一处字符 if(p==0) return false; //某层字符没有编号,不存在,即串也不存在 } return tail[p]; //判断最后一个字符所在的位置是否是某单词的末尾 }
  • 难题:【bzoj4260】按位异或(trie树维护异或前缀和)
  • 难题:【p3065】第一(拓扑排序+trie树)

------AC自动机

思想是kmp+trie树,具体的我还不会...


------Manacher算法

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
void Manacher(){ //求最长回文子串的长度 t[0]='$',t[1]='#'; //【1】加入'#' for(int i=0;i<n;i++) t[i*2+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<n;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<i+p[i]) last_max=i+p[i],last_id=i; //更新mx和id ans_Len=max(ans_Len,p[i]-1); //最长回文子串的长度 } }

【三. 图论】

------最小生成树

<1> Prim算法

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
int a[5019][5019],dist[5019],n,w,ans=0; //↑↑↑把二维的距离数组a、在每次循环中、判断转为一维的距离数组dist bool vis[5019]; //vis数组标记点是否访问过 void prim(){ memset(dist,0x3f,sizeof(dist)); //0x3f=1061109567 memset(vis,0,sizeof(vis)); dist[1]=0; //注意设置起点 for(int i=1;i<n;i++){ //注意:树只有n-1条边 int x=0; for(int j=1;j<=n;j++) if(!vis[j]&&(x==0||dist[j]<dist[x])) x=j; vis[x]=1; for(int y=1;y<=n;y++) if(!vis[y]) dist[y]=min(dist[y],a[x][y]); } //每次寻找当前状态下、到达任意未访问点需要的最短边,并更新 }

<2> Kruskal算法

复制代码
1
2
3
4
5
6
7
8
for(int i=1;i<=m;i++) //存边 reads(e[i].x),reads(e[i].y),reads(e[i].w); for(int i=1;i<=n;i++) fa[i]=i; //初始化 sort(e+1,e+m+1,cmp); //边权从小到大排序 for(int i=1;i<=m;i++){ int fx=find_fa(e[i].x),fy=find_fa(e[i].y); if(fx!=fy) fa[fx]=fy,ans+=e[i].w; //ans=min/max(ans,e[i].w); } //也可以统计已加入的边数,如果达到n-1条边就退出
  • 难题:【CF76A】国王的礼物(二维+思维+增量最小生成树)

------最短路

<1> Floyd

  • 用途:推导关系、传递闭包。
复制代码
1
2
3
4
5
for(int k=1;k<=n;k++) //过渡层一定要放在最外面 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]); //d[i][j]|=d[i][k]&d[k][j];(传递闭包)

<2> Dijkstra

  • 用途:最短路的快速算法(优先队列优化)。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
priority_queue < pair<int,int> > q; void dijkstra(int s){ for(int i=1;i<=n;i++) dist[i]=(int)1e9; dist[s]=0,q.push(make_pair(0,s)); //dist的相反数和出发点的编号 while(q.size()!=0){ //while(!q.empty()) int x=q.top().second; q.pop(); if(vis[x]!=0) continue; vis[x]=1; for(int i=head[x];i;i=e[i].nextt){ if(dist[e[i].ver]>dist[x]+e[i].w){ dist[e[i].ver]=dist[x]+e[i].w; q.push(make_pair(-dist[e[i].ver],e[i].ver)); } } } }

<3> SPFA

  • 用途:判负环,差分约束(队列)。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void spfa(int s){ queue<int>q; //普通队列(也可以写成循环队列) for(int i=1;i<=n;i++) dist[i]=1e9; q.push(s); vis[s]=true; dist[s]=0; while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=false; for(int i=head[u];i;i=e[i].nextt) if(dist[u]+e[i].w<dist[e[i].ver]){ dist[e[i].ver]=dist[u]+e[i].w; if(!vis[e[i].ver]) //SPFA和dij的区别 vis[e[i].ver]=true,q.push(e[i].ver); } } }

<4> 统计路径条数

  • 如:【p2047】社交网络/【p1144】最短路计数
  • 相同大小时,累加(floyd累乘);更优时,重新计算。

<5> 最短路径问题拓展

1.【p2832】行路难,统计权值时要考虑点权。

2. 许多题目需要建立反图,巧妙处理起点终点的关系。

3.【p1027】Car的旅行路线,多个起点的最短路算法。

4.【p2939】改造路,分层图最短路。


------差分约束

对于式子x-y<=b在x,y之间建立长度为b的边,转换成最短路问题

建边:1.a-b>=c,w(b,a)=-c; 2.a-b<=c,w(a,b)=c;

3.a=b,w(a,b)=w(b,a)=0; 4.a-b>c,w(b,a)=-c-1; 5.a-b<c,w(a,b)=c-1;

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

处理:SPFA判负环cnt[v]=cnt[u]+1; if(cnt[v]>n) ...

<2> 给出一些形如x-y<=b不等式的约束,问你满足条件的最大值

处理:直接求最短路即可。最短路--最大值;最长路--最小值。


------强连通分量

  • tarjan算法中的常用数组和变量:
复制代码
1
2
3
int dfn[N],low[N],stack[N],vis[N]; int dfn_=0,top_=0,sum=0,col[N]; //dfn序,栈中位置top,强连通个数sum,每点所属连通块编号col[i]
  • main函数中的循环:
复制代码
1
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
  • tarjan主程序:
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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数组记录每个点所在连通块的编号 } }
  • 缩点之后的统计(入度、大小):
复制代码
1
2
3
4
5
6
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]]++; //记录强连通分量大小 }
  • 无向图缩点:
复制代码
1
2
3
4
5
for(int i=head[u];i;i=e[i].nextt){ if(e[i].ver==u_fa) continue; //无向图缩点与有向图的区别 if(!dfn[e[i].ver]) tarjan(e[i].ver,u),low[u]=min(low[u],low[e[i].ver]); else if(!col[e[i].ver]) low[u]=min(low[u],dfn[e[i].ver]); //这里直接用col数组 }

------拓扑排序

① 从图中选择一个入度为0的点加入拓扑序列。
② 从图中删除该结点以及它的所有出边(即与之相邻点入度减1)。
③ 反复执行这两个步骤,直到所有结点都已经进入拓扑序列。


  • 拓扑排序判环(入队的点<n,则出现了环):
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
//给出n个顺序关系,问是否合法。 queue<int>q; 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; }

  • 将原序列进行拓扑排序,得到新顺序:
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
//给出n个名次关系,求出符合条件的排名顺序,输出字典序最小的答案。 priority_queue< int,vector<int>,greater<int> >q; //小顶堆 int tp_sort(){ //拓扑排序 for(int i=1;i<=n;i++) if(rd[i]==0) q.push(i); while(!q.empty()){ x=q.top(),q.pop(),cnt++,ans[cnt]=x; 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); } } }

------LCA

  • pre_dfs函数确定fa(即f[u][0]):
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
void pre_dfs(int u,int fa_){ for(int i=0;i<=19;i++) f[u][i+1]=f[f[u][i]][i], w[u][i+1]=min(w[u][i],w[f[u][i]][i]); //↑↑维护lca路径上的最小值,注意w数组不需要初始化 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; //距离 f[v][0]=u,w[v][0]=e[i].w,pre_dfs(v,u); } }
  • 找LCA的主程序(确定lca):
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int lca(int x,int y){ //找lca的主程序 int anss=(int)1e9; //找到lca路径上的最短边 if(dep[x]<dep[y]) swap(x,y); //保证dep[x]>dep[y] for(int i=20;i>=0;i--){ //注意:这里的20和上面的19都是log2n的近似取值 if(dep[f[x][i]]>=dep[y]) anss=min(anss,w[x][i]),x=f[x][i]; //↑↑↑i的2^k辈祖先的结点仍比y深,令x=f[x,i],继续向上跳 if(x==y) return anss; //若x=y,则已经找到了lca } for(int i=20;i>=0;i--) //↓↓↓未找到lca时的倍增跳法 if(f[x][i]!=f[y][i]) //更新次路径上的最短边,并继续向上跳 anss=min(anss,min(w[x][i],w[y][i])),x=f[x][i],y=f[y][i]; lca=f[x][0]; //如果只需要找lca,直接返回f[x][0]即可 return anss=min(anss,min(w[x][0],w[y][0])); //路径上的最小边 }

【四. 数据结构】

------树状数组

<1> 单点修改,区间查询:ans=query(y)-query(x-1)。

复制代码
1
2
3
4
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; }

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

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

<3> 区间修改,区间查询:维护两个数组的前缀和。

复制代码
1
sum1[i]=d[i]; sum2[i]=d[i]∗i; (d是差分数组)

直接把a数组处理成前缀和的形式(省略sum数组):

复制代码
1
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。

复制代码
1
2
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的前缀和。

复制代码
1
2
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; }

<4> 二维 —— 单点修改,区间查询

复制代码
1
2
3
4
5
6
7
8
9
10
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; //返回二维前缀和 }
  • ans=query(xx,yy)-query(xx,y-1)-query(x-1,yy)+query(x-1,y-1);

<5> 二维 —— 区间修改,单点查询

修改时: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) 即可。

<6> 二维 —— 区间修改,区间查询  过/于/复/杂/暂/不/简/述...


------线段树

<1> 线段树维护区间最值/区间和

线段树结构体(数组要开4倍):

复制代码
1
struct SegmentTree{ int l,r,sum; }tree[4*N];

build-建树函数:

复制代码
1
2
3
4
5
6
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); //将修改值向上传递 }

PushUp-上移函数:

复制代码
1
void PushUp(int rt){ tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum; }

add-单点修改函数:

复制代码
1
2
3
4
5
6
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;//所有包含结点rt的结点状态更新 }

query-单点查询函数:

复制代码
1
2
3
4
5
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); }

sum-区间查询函数:

复制代码
1
2
3
4
5
6
7
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); }

<2> 线段树维护最大的可行区间(【p2894】酒店)

复制代码
1
2
3
4
需要维护三个最大值: 1.这个区间内最多的连续空格的个数.ans。 2.这个区间从左端点开始向右的空格的个数.l。 3.这个区间从右端点开始向左的空格的个数.r。

结构体改成: struct node{ int l,r,tag,ans; }tree[N];

复制代码
1
2
3
4
5
6
7
void PushUp(int l,int r,int rt){ int mid=(l+r)>>1,ls=(rt<<1),rs=(rt<<1|1); tree[rt].l=(tree[ls].ans==mid-l+1)?(tree[ls].ans+tree[rs].l):tree[ls].l; tree[rt].r=(tree[rs].ans==r-mid)?(tree[rs].ans+tree[ls].r):tree[rs].r; tree[rt].ans=max(tree[ls].ans,tree[rs].ans); tree[rt].ans=max(tree[rt].ans,tree[ls].r+tree[rs].l); }

线段树中最重要的就是PushDown函数:

复制代码
1
2
3
4
5
6
7
8
9
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; //标记每次下移一位,并清空上一位置的标记 }

注意,修改函数和询问函数中,如果没有到达终点,就要不断PushDown


------分块

主要思想每整块标记tag,剩下的l、r两个边界块直接修改

分块大小:m=sqrt(n); 方式:for(i=1~n) pos[i]=(i-1)/m+1;

难题:【区间开方取整+区间求和】okk数组记录每个整块中的元素是否全部<=1。

难题:【单点插入+单点询问】暴力插入,如果某块太大,需要重新分块

难题:【查询区间最小众数】f[i][j]记录第i到j块的众数,vector存每种数出现的所有位置


【五. 动态规划】

DP =「状态」+「阶段」+「决策」

------线性DP

<1> LIS:最长上升子序列

复制代码
1
2
3
4
5
6
for(int i=1;i<=n;i++) f[i]=1; for(int i=2;i<=n;i++) for(int j=i-1;j>=f[i];j--) //↑↑↑【剪枝】j>=f[i]:如果j小于目前长度,不可能使答案更新 if(a[j]<a[i]) f[i]=max(f[i],f[j]+1); for(int i=1;i<=n;i++) ans=max(ans,f[i]);
复制代码
1
2
3
4
5
6
7
8
O(n*logn) for(int i=1;i<=n;i++) reads(a[i]); for(int i=1;i<=n;i++){ if(a[i]>list[len]) { list[++len]=a[i]; continue; } int pos=lower_bound(list+1,list+len+1,a[i])-list; list[pos]=a[i]; } printf("%dn",len);

 <2> LCS:最长公共子序列

复制代码
1
2
3
4
5
6
7
for(int i=1;i<=lens;i++) for(int j=1;j<=lent;j++){ f[i][j]=max(f[i-1][j],f[i][j-1]); if(s[i]==t[j]) //如果元素相同 f[i][j]=max(f[i][j],f[i-1][j-1]+1); } //注意:为了防止数组下标出现-1,输入时要用ss+1 printf("%dn",f[lens][lent]);
复制代码
1
2
3
4
5
6
7
8
9
10
11
O(n*logn) for(int i=1;i<=n;i++) reads(a1[i]),id[a1[i]]=i; for(int i=1;i<=n;i++) reads(a2[i]); for(int i=1;i<=n;i++){ if(id[a2[i]]>list[len]){ list[++len]=id[a2[i]]; continue; } int k=lower_bound(list+1,list+len+1,id[a2[i]])-list; list[k]=id[a2[i]]; } printf("%dn",len);

 ------背包DP

<1> 0/1背包

注意:dp数组初始化为maxx,设置起点dp[0]=0;

复制代码
1
2
3
4
for(int i=1;i<=n;i++) for(int j=m;j>=v[i];j--) //注意:一定要倒序循环 dp[j]=max(dp[j],dp[j-v[i]]+w[i]); for(int j=0;j<=m;j++) ans=max(ans,dp[j]);

<2> 完全背包

复制代码
1
2
3
4
for(int i=1;i<=n;i++) for(int j=v[i];j<=m;j++) //注意:一定要正序循环 dp[j]=max(dp[j],dp[j-v[i]]+w[i]); for(int j=0;j<=m;j++) ans=max(ans,dp[j]);

<3> 分组背包

复制代码
1
2
3
4
5
for(int i=1;i<=n;i++) //每组只能选一个 for(int j=m;j>=0;j--) //倒序 for(int k=1;k<=c[i];k++) //注意:循环顺序与多重背包相反 //↑↑↑这里的个数循环要放在容量循环的后面,才能保证唯一性 if(j>=v[i][k]) f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);

<4> 多重背包

复制代码
1
2
3
4
5
for(int i=1;i<=n;i++) for(int j=1;j<=s[i];j++) //先枚举个数 for(int k=m;k>=v[i];k--) //枚举总体积、倒序循环 dp[k]=max(dp[k],dp[k-v[i]]+w[i]); for(int j=0;j<=m;j++) ans=max(ans,dp[j]);

【拓展】多重背包的二进制拆分

  • 把多重背包的第i种物品看成独立的 k(log(s[i]))+2 个物品,转化为0/1背包。
  • p[i]=2^0+2^1+...+2^k+r[i](多余部分),用这些物品可以表示出这种物品所有<=p[i]的数量。

二进制拆分:

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void broke(){ //【多重背包的二进制拆分】 for(int i=1;i<=n;i++){ int cnt=1; //cnt=2^k while(s[i]!=0){ //没拆分完 ww[++num]=w[i]*cnt; vv[num]=v[i]*cnt; //价值和代价都要*cnt s[i]-=cnt; cnt=cnt<<1; //cnt*2 if(s[i]<cnt){ //多出来的部分(即r[i]) ww[++num]=w[i]*s[i]; vv[num]=v[i]*s[i]; break; } } } }

转化为01背包:

复制代码
1
2
for(int i=1;i<=num;i++) //拆分后的物品个数 for(int j=m;j>=vv[i];j--) f[j]=max(f[j],f[j-vv[i]]+ww[i]);

------区间DP

一个状态、由若干个比它更小、且包含于它的区间、所代表的状态转移而来。

【区间DP的状态转移方法】

  • 从小到大枚举区间长度,枚举对应长度的区间。
复制代码
1
2
3
for(int len=1;len<=N;++len) //区间长度 for(int l=1,r=len;r<=N;++l,++r) { 考虑F[l][r]的转移方式 }

基本决策(枚举断点):dp[i][j]=min{ dp[i][k]+dp[k+1][j] | i<=k<j };

【求dp[i][j]具体步骤】(p4170-涂色)

  • 当i==j时,子串明显只需要涂色一次,于是dp[i][i]=1
  • 当i!=j且s[i]==s[j]时,可以直接继承之前的状态,于是dp[i][j]=min(dp[i][j-1],dp[i+1][j])
  • 当i!=j且s[i]!=s[j]时,枚举子串的断点k,于是dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])

难题:括号配对 / p1005-矩阵取数...


------环形DP

【破环为链】for(int i=1;i<=N;i++) v[N+i]=v[i]; //注意:数组要开2*N大小。


------树形DP

<1> 0/1型树形DP

又称树的最大独立集问题。比如【p2016-战略游戏】

当前节点选或不选,父亲节点选或不选,儿子节点选或不选。

规划所有状态,递归子树,判断转移,得出最终的答案。

<2> 背包类树形DP

又称有树形依赖的背包问题。比如【p2014-选课】。

除了以 “节点编号” 作为树形DP的阶段(第一维度),

还要把当前背包的 “体积” 作为第二维状态。


------数位DP

区间可减性:ans(l,r)=sum(r)-sum(l-1);

复制代码
1
2
3
4
5
int counts(int x){ //保存上界x的每一位 int len=0; while(x) bit[len++]=x%10,x/=10; return dfs(len-1,0,true); } //注意是len-1,在dp函数中边界为:pos=-1

数位DP的主函数:

复制代码
1
2
3
4
5
6
7
8
9
int dfs(int pos,int sum,bool limit){ if(pos==-1) return (sum==0); //是否是mod的倍数 if(!limit&&f[pos][sum]) return f[pos][sum]; //记忆化 int end=(limit==1)?bit[pos]:9,ans=0; for(int i=0;i<=end;i++){ //end是当前上界 int newsum=(sum+i)%mod; //数字和 ans+=dfs(pos-1,newsum,limit&&(i==end)); } if(!limit) f[pos][sum]=ans; return ans; } //当前情况下不用判断前导0,但有些时候需要判断

------状压DP

一个集合内的元素信息作为状态、且状态总数为指数级别的DP。

(1)具体解题模式:

  • 【找状态】确定每行的M位二进制数中0、1的表示。
  • 【存已知】存入时把初始[每行]的二进制状态变为一个十进制的数,便于数位操作。
  • 【预处理】结合输入求出[每行]的[所有满足可行性]的M位二进制数。
  • 【判边界】一般行列间的关系在[起始行]并不适用,要[特殊处理]第一行的状态。
  • 【列方程】逐层枚举每行和上一行的状态,[判断行列关系],列状态转移方程。

(2)常用转移方程:

复制代码
1
2
if((s&(1<<(j-1)))&&(s&(1<<(i-1)))) //j是当前的结尾节点 f[s][j]=min(f[s][j],f[s^(1<<(j-1))][i]+cost[i][j]);

枚举最后作为结尾的结点:ans=min(f[(1<<n)-1][i]);

(3)常用的二进制操作:

1.每行选几个:取二进制状态下1的个数,用counts函数。

复制代码
1
int counts(int x){ int cnt=0; while(x) x&=(x-1),cnt++; return cnt; }

2.每行每列没有相邻的:枚举所有状态,!(i&(i<<1)) 时才是每行的可行状态,存入state[ ]中。

   初始化第一行的情况,转移时,枚举此行的状态和上一行的状态,行间需要满足:

复制代码
1
if(!(state[now]&state[last])&&j>=sum[now]) //j:前i行选的个数

------单调队列优化DP

1、维护队首可行性,head++;
2、维护队尾单调性,并插入当前元素;
3、取出队头的最优解,进行DP转移。

复制代码
1
2
3
4
5
6
7
8
9
10
int head=1,tail=1; //手写优先队列 q[1].x=a[1]; q[1].id=1; //初始点为1 for(int i=2;i<=n;i++){ //从2开始循环 while(head<=tail && q[head].id<i-m+1) head++; //id的作用:判断区间长度 if(i>=m) printf("%dn",q[head].x); //每一次的队头都是当前段最大值 while(head<=tail && q[tail].x<=a[i]) tail--; //↑↑新数比前几个大,前几个不可能再成为最大值(可能不止一个) q[++tail].x=a[i]; q[tail].id=i; //a[i]加入队尾 //单调递减队列:如果后方有数更大,前面就删除; }

------斜率优化DP

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

  • 1.将数据进行预处理(求sum等操作),优化序列。
  • 2.写状态转移方程,如果是二维,要使用二维单调队列。
  • 3.推导不等式,化成斜率的一般式,一般使用化除为乘。
  • 4.从而得到X,Y的定义式,用double类型表示出来。
  • 5.建立一个类似优先队列的斜率单调队列。
  • 6.维护头尾可行性以及斜率单调性,队头为最优答案。


【六. 数论】

<1> 取整除法求和

复制代码
1
2
3
4
5
ll ans(ll n){ //O(√n) ll anss=0,nn=sqrt(n) ; for(ll i=1;i<=nn;i++) anss+=n/i; return (anss<<1)-nn*nn; } //先处理<=√n的,剩下的用公式推出

<2> N的正约数集合

复制代码
1
2
3
4
5
6
7
int factor[2519],cnt=0; for(int i=1;i*i<=n;i++){ if(n%i==0){ factor[++cnt]=i; if(i!=n/i) factor[++cnt]=n/i; } }

<3> 最大公约数GCD

复制代码
1
int gcd(int a,int b){ return (b==0)?a:gcd(b,a%b); }

难题:高精度版最大公约数(用二进制算法)

<4> 求解不定方程---EXGCD

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
int exgcd(int a,int b,int &x,int &y){ if(b==0){ x=0; y=1; return a; } //b<=a int gcd_=exgcd(a%b,b,y,x); //gcd_是a、b的最大公约数 x-=(a/b)*y; return gcd_; //x=x0-[a/b(下取整)]*y0; y=y0; } int cal(){ //a*x+b*y=c int gcd_=exgcd(a,b,x,y); if(c%gcd_!=0) return -1; //不可能有解 x*=c/gcd_,b/=gcd_; if(b<0) b=-b; int ans=x%b; if(ans<=0) ans+=b; return ans; } //注意ans=0的情况↑↑

<5> 埃式筛质数

复制代码
1
2
3
4
5
6
7
8
9
int vis[N],primes[N],cnt=0; void init(int x){ for(int i=2;i<=x;i++) if(!vis[i]){ primes[cnt++]=i; for(int j=i+i;j<=x;j+=i) vis[j]=1; } }

<6> 分解质因数

复制代码
1
2
3
4
5
void init(int x){ int cnt=0; for(int i=2;i*i<=x;i++) while(x%i==0) primes[++cnt]=i,x/=i; if(x>1) primes[++cnt]=x; }

<7> 快速幂

复制代码
1
2
3
4
5
6
7
ll ksm(ll a,ll b,ll mod){ ll anss=1; //注意初始化为1 while(b>0){ //求a的b次方%mod if(b&1) anss=anss*a%mod; a=a*a%mod; b>>=1; } return anss; }

<8> 乘法逆元

复制代码
1
2
3
4
5
6
7
8
ll inv1(ll a,ll mod){ //扩展欧几里得求逆元 ll x,y; ll d=exgcd(a,mod,x,y); if(d==1) return (x%mod+mod)%mod; return -1; } ll inv2(ll a,ll mod){ return ksm(a,mod-2,mod); } //费马小定理 void inv3(ll mod){ inv[1]=1; //线性递推求逆元 for(int i=2;i<=mod-1;i++) //求1~n的逆元 inv[i]=(mod-mod/i)*inv[mod%i]%mod,cout<<inv[i]<<" "; }

<9> 组合数

复制代码
1
2
3
4
5
6
for(int i=0;i<=MAXN;i++) C[0][i]=0,C[i][0]=1; for(int i=1;i<=MAXN;i++) for(int j=1;j<=MAXN;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;

<10> Lucas定理

  • 公式:Lucas(C(n,m)%p)=Lucas(C(n%p,m%p)%p)*Lucas(C(n/p,m/p)%p)
复制代码
1
2
3
4
5
6
7
8
9
10
kk[0]=kk[1]=inv[0]=inv[1]=1; //阶乘数组&&逆元数组初始化 for(int i=2;i<=n;i++) kk[i]=kk[i-1]*i%p; //阶乘 for(int i=2;i<=n;i++) inv[i]=(p-p/i)*inv[p%i]%p; //线性推逆元 for(int i=2;i<=n;i++) inv[i]=inv[i-1]*inv[i]%p; //k!%p的逆元 等于 逆元的阶乘 printf("%lldn",lucas(n,m)); //调用卢卡斯函数 long long lucas(int n,int m){ if(n<m) return 0; //无法构成组合数,返回答案为0 if(n<p) return kk[n]*inv[m]*inv[n-m]%p; //n的阶乘*(m!%p的逆元)*((n-m)!%p的逆元) else return lucas(n/p,m/p)*lucas(n%p,m%p)%p; }

<11> Nim游戏

如果每一堆石子的个数异或起来的值不为0,那么先手必胜。

如果个数异或起来的值为0,那么先手必败。

复制代码
1
2
for(int i=1,x;i<=n;reads(x),ans^=x,i++); if(ans) puts("Yes"); else puts("No");

 

 

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

最后

以上就是虚幻汉堡最近收集整理的关于【浮*光】 #noip总复习# hss_2018noip_rp++的全部内容,更多相关【浮*光】内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(74)

评论列表共有 0 条评论

立即
投稿
返回
顶部