铁板铮铮♂+习题集

 

数论

快速幂

当b为偶数：a^b=a^b/2 * a^b/2

当b为奇数：a^b=a^b/2 * a^b/2 * a

核心代码：

ll quickpow(ll a,ll b) { ll ret=1; while(b) { if(b%2==1) ret=ret*a%P; a=a*a%P; b/=2; } return ret; } View Code

 

 

习题集 题目号题目名注释洛谷P1965【NOIP2013TG】转圈游戏简单推导公式洛谷P3197

【HNOI2008】越狱

与组合数学结合+容斥

 

 

 

 

 

 

线性筛

#include<iostream> using namespace std; #define maxn 10000001 int prime[maxn],v[maxn],f[maxn];//prime为素数表 //v为每个数的最小质因子 //f数组判断是否是素数 int n,m,k; void primes(int n) { k=0; for(int i=2;i<=n;i++)//从2开始 { if(v[i]==0) { v[i]=i;//i是质数，则i的最小质因子为本身 prime[++k]=i; f[i]=1; } for(int j=1;j<=k;j++) { if(prime[j]>v[i]||prime[j]*i>n) break; //如果i有比prime[j]更小的质因子 //或者超出n的范围 v[i*prime[j]]=prime[j];//prime[j]是合数i*prime[j]的最小质因子 } } } int main() { cin>>n>>m; primes(n); for(int i=1;i<=m;i++) { int x; cin>>x; if(f[x]==1) cout<<"Yes"<<endl; else cout<<"No"<<endl; } } View Code 习题集 题目号题目名注释洛谷P3383线性筛素数模板题洛谷P2926【USACO08DEC】Patting Heads 特殊筛法Codeforces 776BSherlock and his girlfriend 特判+筛法

 

 

 

 

 

 

质因数分解

void divide(int x) { m=0; for(int i=2;i*i<=n;i++)//一个数至多只有一个大于根号n的质因子 //所以后面特判 前面只要到根号n { if(n%i==0)//i是质数 { p[++m]=i; c[m]=0; } while(n%i==0) { n=n/i;//除掉所有的i c[m]++; //i的指数加1 } } if(n>1)//特判大于根号n的那个 { p[++m]=n; c[m]=1; } } View Code 习题集 题目号题目名注释洛谷P1075【NOIP2012PJ】质因数分解模板题洛谷P1463【HAOI2007】反素数 搜索+约数个数

 

 

 

 

 

 

gcd与lcm

辗转相除法求gcd

int gcd(int a,int b) { if(b==0) return a; else return gcd(b,a%b); } View Code

求lcm:

a*b=gcd(a,b)*lcm(a,b)

习题集 题目号题目名注释 洛谷P1072【NOIP2009TG】Hankson的趣味题  推导

 

 

 

 

 

扩展欧几里得exgcd

void exgcd(int a,int b,int &d,int &x,int &y) { int t; if(b==0)//当b=0时 gcd(a,b)=a //因为1*a+0*0=a 所以ax+by=gcd(a,b)有一组解为 //x=1 y=0 { d=a; x=1; y=0; } else { exgcd(b,a%b,d,x,y); t=x;//推导得公式 x=y; y=t-(a/b)*y; } } View Code 习题集 题目号题目名注释洛谷P1516青蛙的约会 简单推导公式洛谷P1082【NOIP2012TG】同余方程 模板题洛谷P2421【NOI2002】荒岛野人推导公式+条件判断

 

 

 

 

 

 

乘法逆元

 对于a/b mod p（b和p互质）

First 费马小定理：

如果b和p互质 则b^p≡b（mod p）

由此可得b^p-1≡1（mod p） 结合求逆元方程b*x≡1（mod p） 得到b^p-1≡b*x（mod p)

所以x≡b^p-2（mod p）结合快速幂求出x

#include<cstdio> #define ll long long using namespace std; int n,p; inline ll ksm(ll a,ll b){ ll ans=1; a%=p; while(b){ if(b&1) ans=ans*a%p; a=a*a%p; b>>=1; } return ans%p; } void write(ll x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10);putchar(x%10^48); } int main(){ scanf("%d%d",&n,&p); for(int i=1;i<=n;i++) write(ksm(i,p-2)),putchar('\n'); return 0; } View Code

Second 解不定方程

解a*x≡1（mod p）等于解ax+py=1 

因为p是质数 所以gcd(a,p)=1;

即解ax+py=gcd(a,p) 用exgcd解x

#include<cstdio> using namespace std; int x,y; void exgcd(int a,int b){ if(!b){x=1,y=0;return ;} exgcd(b,a%b); int t=x; x=y,y=t-a/b*y; } void write(int x){ if(x>9) write(x/10); putchar(x%10^48); } int main(){ int n,p; scanf("%d%d",&n,&p); for(int i=1;i<=n;++i) exgcd(i,p),write((x%p+p)%p),putchar('\n'); return 0; } View Code

Third 线性递推

#include<cstdio> #define ll long long using namespace std; const int maxn=3e6+5; ll inv[maxn]={0,1}; int main(){ int n,p; scanf("%d%d",&n,&p); printf("1\n"); for(int i=2;i<=n;i++) inv[i]=(ll)p-(p/i)*inv[p%i]%p,printf("%d\n",inv[i]); return 0; } View Code 习题集 题目号题目名注释POJ1845Sumdiv 约数和+模板

 

 

 

 

中国剩余定理

对于多个x≡a_i(mod m_i)

M=∏ⁿ_i=1m_i    M_i=M/m_i

t_i是线性同余方程M_i*t_i≡1(mod m_i)的一个解

x=∑ⁿ_i=1a_i*M_i*t_i

int intchina(int n) { int Mi,x,y,d,ans=0; M=1; for(int i=1;i<=n;i++) M*=m[i]; for(int i=1;i<=n;i++) { Mi=M/m[i]; exgcd(Mi,m[i],d,x,y); ans=(ans+Mi*x*a[i])%M; } return (ans+M)%M; } View Code 习题集 题目号题目名注释洛谷P1495曹冲养猪 模板题UVA756Biorhythms模板+特殊解

 

 

 

 

Lucas定理

#include<iostream> #include<cstdio> using namespace std; #define LL long long LL T,n,m,p; LL quickpow(LL a,LL b) { LL ret=1; while(b) { if(b&1) ret=ret*a%p; a=a*a%p; b>>=1; } return ret; } LL C(LL n,LL m) { if(m>n) return 0; LL a=1,b=1; for(LL i=n-m+1;i<=n;i++) a=a*i%p;//计算n!/(n-m)! for(LL i=2;i<=m;i++) b=b*i%p;//计算1/m! return a*quickpow(b,p-2)%p;//费马小定理求逆元 } LL Lucas(LL n,LL m) { if(!m) return 1; else return (C(n%p,m%p)*Lucas(n/p,m/p))%p;//递推公式 } int main() { scanf("%lld",&T); while(T) { T--; scanf("%lld%lld%lld",&n,&m,&p); printf("%lld\n",Lucas(n,m)); } } View Code 习题集 题目号题目名注释洛谷P3807卢卡斯定理模板题

 

 

 

组合排列问题

组合：A(n,m)=n(n-1）*（n-2）*……*（n-m+1）= n!/(n-m)!

排列：C(n,m)=A(n,m)/m!=n!/(m!(n-m)!)

习题集 题目名题目号注释洛谷P1066【NOIP2006TG】2^k进制数复杂高精+组合推导（有点难）洛谷P2822【NOIP2016TG】组合数问题  二维前缀和+杨辉三角洛谷P1350车的放置推导矩阵公式洛谷P3166【CQOI2004】数三角形组合+GCD洛谷P2532【AHOI2012】树屋阶梯卡特兰数+高精洛谷P3200【HNOI2009】有趣的数列卡特兰数+质因数分解洛谷P1375小猫卡特兰数+逆元

 

 

 

 

 

 

 

 

 

 

 

---

 

动态规划

区间DP

枚举所有在i与j之间的k

把一段区间分成两段为两个状态

如果是环形可以考虑断环成链 开数组2n

初始化 f[i][i]=1或者权值

答案要枚举所有的左端点到后n位

核心代码：

f1[i][j]=max(f1[i][j],f1[i][k]+f1[k+1][j]+sum[j]-sum[i-1]); f2[i][j]=min(f2[i][j],f2[i][k]+f2[k+1][j]+sum[j]-sum[i-1]); View Code 习题集 题目号题目名注释洛谷P1880【NOI1995】石子合并断链成环洛谷P1063能量项链中等难度洛谷P2426删数从两边删除区间洛谷P3146【USACO160PEN】248类似2048游戏洛谷P1005【NOIP2007TG】矩阵取数游戏 高精+翻倍洛谷P3205【HNOI2010】合唱队用两个数组

 

 

 

 

 

 

 

 

 状压DP

把多个元素的状态进行压缩成阶段进行DP

一般数据规模中有一个或者几个元素的规模很小

大多可以把状态转化为二进制数 用位运算求解

习题集 题目号题目名注释洛谷P1896【SCOI2005】互不侵犯经典例题洛谷P1879【USACO06NOV】Corn Fields 基本操作 洛谷P3959【NOIP2017TG】宝藏状压+DFS

 

 

 

 

 

---

 

图论

并查集：

#include<iostream> using namespace std; int father[5001]; int n,m,p; int find(int x) { if(father[x]!=x)//路径压缩优化 father[x]=find(father[x]);//把路上的所有点祖先全部改掉 return father[x]; } void unionn(int x,int y) { father[y]=x;//y的祖先为x的祖先 //相当于合并祖先 } int main() { cin>>n>>m>>p; for(int i=1;i<=n;i++) { father[i]=i;//所有数据初始祖先为自己 //独立的一个数为一个集合 } for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; int r1,r2; r1=find(x); r2=find(y);//寻找两个数的祖先 if(r1!=r2)//如果不是同一个祖先 { unionn(r1,r2);//合并 } } for(int i=1;i<=p;i++) { int x,y; cin>>x>>y; if(find(x)==find(y))//如果是同一个祖先 { cout<<"Yes"<<endl;//是 } else cout<<"No"<<endl;//否 } } View Code 习题集 题目号题目名注释洛谷P3367【模板】并查集如题洛谷P2024

【NOI2001】食物链

搞好三者关系

洛谷P1525

关押罪犯

排序+并查集

洛谷P1111

修复公路

eazy

洛谷P1197

【JSOI2008】星球大战

逆向思维

 

 

 

 

 

 

 

 

 

最小生成树：

Kruskal

#include<iostream> #include<algorithm> using namespace std; struct edge { int l,r,w;//左端点 右端点 权值 }e[200001]; int father[5001]; int n,m,k=0,tot; bool cmp(const edge &a,const edge &b)//用权值排序 { if (a.w<b.w) return 1; else return 0; } int find(int x) { if(father[x]!=x) father[x]=find(father[x]); return father[x]; } void unionn(int x,int y) { int fa=find(x); int fb=find(y); if(fa!=fb) father[fa]=fb; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) father[i]=i; for(int i=1;i<=m;i++) { cin>>e[i].l>>e[i].r>>e[i].w; } sort(e+1,e+1+m,cmp); for(int i=1;i<=m;i++) { if(find(e[i].l)!=find(e[i].r)) { unionn(e[i].l,e[i].r); tot+=e[i].w; k++; } if(k==n-1) break;//到n-1条时退出 } cout<<tot; } View Code 习题集 题目号 题目名注释洛谷P3366【模板】最小生成树如题洛谷P1195口袋的天空处理边的关系洛谷P2330【SCOI2005】繁忙的都市记下最大值

 

 

 

 

 

强连通分量：

Tarjan

void Tarjan(int u) { dfn[u]=low[u]=++num; vis[u]=1; st[++top]=u;//入栈 for(int i=h[u];i;i=e[i].next) { int v=e[i].to; if(!dfn[v]) { Tarjan(v); low[u]=min(low[u],low[v]);//low表示u与其子孙到达的最小编号 } else if(vis[v])//判断v是否在栈中 { low[u]=min(low[u],dfn[v]); //可以改成 min(low[u],low[v]) //因为此时v的low和dfn还未修改 } } if(dfn[u]==low[u]) { col++; while(st[top+1]!=u) { co[st[top]]=col;//属于第col个强连通分量 vis[st[top--]]=0; } } } View Code

 

习题集 题目号题目名注释洛谷P2341【HAOI2006】受欢迎的牛缩点+小思想洛谷P1262间谍网络缩点+最小值洛谷P3627【APIO2009】抢掠计划缩点+SPFA

 

 

 

 

 

---

 

数据结构

线段树

带Lazy-Tag的区间修改和区间查询

#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define maxn 100007 #define ll long long ll sum[maxn<<2],add[maxn<<2],a[maxn],n,m; void build(ll l,ll r,ll k)//建树 [l,r]中 编号为k的区间 { if(l==r)//叶子节点 { sum[k]=a[l]; return; } ll mid=(l+r)>>1; build(l,mid,k<<1);//左子树 build(mid+1,r,k<<1|1);//右子树 sum[k]=sum[k<<1]+sum[k<<1|1];//更新区间和 } void Add(ll l,ll r,ll v,ll k)//给定区间[l,r]中所有的数加上v { add[k]+=v;//打标记 sum[k]+=(r-l+1)*v;//维护对应区间和 return; } void pushdown(ll l,ll r,ll mid,ll k)//标记下传 { if(add[k]==0) return;//如果没有标记 就退出 Add(l,mid,add[k],k<<1);//传给左子树 Add(mid+1,r,add[k],k<<1|1);//传给右子树 add[k]=0;//传完之后清楚标记 } void update(ll x,ll y,ll v,ll l,ll r,ll k)//更新定区间[x,y]中 区间[l,r]第k个区间 { if(l>=x&&r<=y) return Add(l,r,v,k);//当这个定区间包含区间[l,r] 则更新区间[l,r]的值 ll mid=(l+r)>>1; pushdown(l,r,mid,k);//标记下传 if(x<=mid) update(x,y,v,l,mid,k<<1);//更新左子树 if(mid<y) update(x,y,v,mid+1,r,k<<1|1);//更新右子树 sum[k]=sum[k<<1]+sum[k<<1|1];//更新下传后当前正确的sum值 } ll query(ll x,ll y,ll l,ll r,ll k)//查询定区间[x,y]中 区间[l,r]第k个区间 { if(l>=x&&r<=y) return sum[k];//当这个定区间包含区间[l,r] 返回区间[l,r]的值 ll mid=(l+r)>>1; ll res=0; pushdown(l,r,mid,k);//标记下传 if(x<=mid) res+=query(x,y,l,mid,k<<1);//如果左子树还有值 就加上左子树 if(y>mid) res+=query(x,y,mid+1,r,k<<1|1);//同上右子树 return res;//返回值 } int main() { cin>>n>>m; for(ll i=1;i<=n;i++) cin>>a[i]; build(1,n,1);//建原树 for(ll i=1;i<=m;i++) { ll x,y,z; cin>>x; if(x==1) { cin>>x>>y>>z; update(x,y,z,1,n,1);//更新值 } else { cin>>x>>y; cout<<query(x,y,1,n,1)<<endl;//查询区间 } } } View Code 习题集 题目号题目名注释洛谷P3372线段树1加法模板洛谷P3373线段树2加法+乘法洛谷P2023【AHOI2009】维护序列加法+乘法洛谷P1198【JSOI2008】最大值水题洛谷P4145花神游历各国区间开方

 

 

 

 

 

 

 

树状数组

单点修改+区间查询

#include<iostream> using namespace std; int n,m; int tree[2000010]; int lowbit(int k) { return k & -k;//补码原则 } void add(int x,int k) { while(x<=n) { tree[x]+=k; x+=lowbit(x);//根据二进制原理加上本身的lowbit等于下一个值 } } int sum(int x) { int ans=0; while(x!=0) { ans+=tree[x]; x-=lowbit(x); } return ans; } int main() { std::ios::sync_with_stdio(false);//取消cincout的时间 cin>>n>>m; for(int i=1;i<=n;i++) { int x; cin>>x; add(i,x); } for(int i=1;i<=m;i++) { int a,b,c; cin>>a>>b>>c; if(a==1) add(b,c);//在b的位置加上c if(a==2) cout<<sum(c)-sum(b-1)<<endl;//前缀和相减 } } View Code

区间修改+单点查询

#include<iostream> using namespace std; int n,m; int tree[500010]; int num[500010]; int lowbit(int k) { return k & -k;//补码原则 } void add(int x,int k) { while(x<=n) { tree[x]+=k; x+=lowbit(x);//根据二进制原理加上本身的lowbit等于下一个值 } } int sum(int x) { int ans=0; while(x!=0) { ans+=tree[x]; x-=lowbit(x); } return ans; } int main() { std::ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=n;i++) cin>>num[i]; for(int i=1;i<=m;i++) { int a; cin>>a; if(a==1) { int x,y,z; cin>>x>>y>>z; add(x,z); add(y+1,-z);//把前面加上的多余减掉 } if(a==2) { int x; cin>>x; cout<<num[x]+sum(x)<<endl;//把原来的数加上后来加的 } } } View Code

 

倍增求LCA

#include<iostream> #include<cstdio> #include<cmath> using namespace std; #define maxn 500050 #define INF 1e9+7 int n,m,cnt,ans,a,b,k,x,y; int h[maxn],dep[maxn],f[maxn][30]; struct Edge { int next; int to; }e[maxn<<1]; void add(int u,int v) { e[++cnt].to=v; e[cnt].next=h[u]; h[u]=cnt; } void deal(int u,int fa) { dep[u]=dep[fa]+1;//子节点深度等于父节点+1 for(int i=1;i<=21;i++) { f[u][i]=f[f[u][i-1]][i-1];//计算u的2^k辈祖先 } for(int i=h[u];i;i=e[i].next) { int v=e[i].to; if(v==fa) continue;//如果是父节点就退出 f[v][0]=u;//v是u的子节点 deal(v,u); } } int lca(int x,int y) { if(dep[x]<dep[y]) swap(x,y);//如果x的深度比y小 就交换 for(int i=21;i>=0;i--)//从大到小循环 先走大步 如果不行在走小步 { if(dep[f[x][i]]>=dep[y]) x=f[x][i];//当走完深度还是大于y 就走 if(x==y) return x;//当x=y时 找到LCA } for(int i=21;i>=0;i--)//此时x和y已经在同一层了 { if(f[x][i]!=f[y][i])//如果往上走之后还没有到LCA 就往上走 { x=f[x][i]; y=f[y][i]; } } return f[x][0];//返回LCA } int main() { scanf("%d%d",&n,&m); for(int i=1;i<n;i++) { scanf("%d%d",&x,&y); add(x,y); add(y,x);//无向图 } deal(1,0);//预处理 for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); printf("%d\n",lca(x,y)); } } View Code 习题集 题目号题目名注释洛谷P4180【BJWC2010】严格次小生成树kruskal+求LCA洛谷P4281【AHOI2008】紧急集合求三个点的LCAPOJ 3417Network树上差分+LCA洛谷P1967【NOIP2013TG】货车运输kruskal+求LCA

 

 

 

 

 

 

 

---

 

字符串

KMP

#include<iostream> #include<cstring> #define MAXN 1000010 using namespace std; char a[MAXN],b[MAXN]; int next[MAXN]; int la,lb,j; //j为所匹配到的最大的后缀的前缀最后一位 int main() { cin>>a+1;//从一开始存 cin>>b+1; la=strlen(a+1); lb=strlen(b+1); for(int i=2;i<=lb;i++)//匹配匹配串 { while(j&&b[j+1]!=b[i])//判j不为零因为在第一位就不用往前找了 //如果不匹配就往前找 j=next[j]; if(b[j+1]==b[i])//匹配就往下推 j++; next[i]=j; } j=0; for(int i=1;i<=la;i++)//匹配文本串 同上 { while(j&&b[j+1]!=a[i]) j=next[j]; if(b[j+1]==a[i]) j++; if(j==lb)//找到一个匹配串输出位置 cout<<i-lb+1<<endl; } for(int i=1;i<=lb;i++) cout<<next[i]<<" "; } View Code 习题集 题目号题目名注释洛谷P4319【BOI2009】Radio Transmission自我匹配UVA10298Power Strings自我匹配洛谷P3435【POI2006】OKR-Periods of Words谜之题面洛谷P2375【NOI2014】动物园对next数组的深化

转载于:https://www.cnblogs.com/BrokenString/p/9462209.html

相关资源：橙色韩国铁板小吃网页模板