KMP系列题目。 1.KMP最常用的用法：查找一个字符串在另一个字符串中的位置。复杂度O（m+n)  P3375模板题 下面上代码：  #include<bits/stdc++.h> using namespace std; string a,b; const int N=1e6+5; int f[N]; void fun(string a){ int l=a.size(),j=0; for(int i=1;i<l;i++) { while(j&&a[i]!=a[j]) j=f[j-1]; if(a[i]==a[j]) j++; f[i]=j; } } voi...

树与图论的相关题目 1.树上求和.    因为是一棵树,从任意一点为根节点搜索都可以搜索完所有边。这里以1为根节点搜索。递归保存每个边的贡献次数。按贡献的次数从小到大排序，然后权值从n-1 到1相乘求和即可。 一个重要的知识点：U—V的边的贡献次数 = size(以V为边的子树结点数目)*(N-size)  #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; ll n,ans[N],cnt; vector<int>g[N]; ll dfs(int u,...

几个常见的DP类型. 1.路径DP. 例题1.P1216 [USACO1.5][IOI1994]数字三角形 Number 题目传送门  本题每个点路径选择只有两种，很好写dp，具体解释见下面代码。  #include<bits/stdc++.h> using namespace std; const int N=1e3+5; int n,dp[N][N],a[N][N];//状态的确立：dp[i][j]表示终点为第i行第j列的最大值  int main(){ cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=i;j++...

组合数学相关练习 1.Count The Blocks  题目传送门：ECR 84 E 题意：给定n，求从0到 10^n-1 的所有长度为 i（i从1到n)的个数。每个数均为n位数（不足补前导0）   下面上代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+5,mod=998244353; ll f[N],n; int main(){ cin>>n; f[0]=1; for(int i=1;i<=n;i++) f[i]=(f[i-1]*10)%...

模拟退火相关题目 1.计算函数最值（非单峰函数） 1.Strange fuction  题目传送门HDU2899   思路：本题的状态函数就是题目中的数学函数，因为是求最小值，所以每次取最小即可，其他细节见代码。  #include<bits/stdc++.h>  using namespace std; const double eps=1e-8;//终止温度  double y; double fun(double x){ //计算函数结果  return 6*pow(x,7.0)+8*pow(x,6.0)+7*pow(x,3.0)+5*pow(x,2.0)-y*x; } do...

最长递增子序列的三种解法（LIS） 1.用LCS(求LIS) 时间复杂度O(n^2)  思路：将原序列a排序后产生一个新的序列b，比较a和b最长公共子序 结果就是LIS.  #include<bits/stdc++.h> using namespace std; const int N=1e4+5; int dp[2][N];//滚动数组优化  string a,b; int LCS(){ int la=a.size(),lb=b.size(); for(int i=1;i<=la;i++) for(int j=1;j<=lb;j++) if(a[i-1]==b[j-1...

二分题目及其总结. 1.银行贷款  题目传送门：P1163 思路：找到函数单调性，进行二分查找。下面是分析。    #include<bits/stdc++.h> using namespace std; double n,m; int k; bool find(double x){ return (pow(1.0/(1.0+x),k)>=1-(n/m)*x);//如果大于 向左查找，反之向右查找  } int main(){ cin>>n>>m>>k; double l=0,r=10; while(r-l>=1e-4){ //二分 ...

SG函数和SG定理的运用  SG函数和SG定理常用于解决博弈论的相关问题。其中SG函数的求解主要根据MEX运算。什么是MEX运算？MEX（ minimal excludant ） 字面上意思是最小除外的那个数。 MEX是对一个集合的运算。指得是对于一个集合 s={a1,a2,an) 集合中未出现的最小非负整数。 举个例子：比如 s={1,2,3} 则MEX(s)=0, 如果s={0,1,2,4},则MEX(s)=3. SG定理：博弈论中游戏和的SG值等于各个游戏的SG值的Nim和。Nim和也就是我们所说的按位异或运算下面上例题。  1.Fibonacci again and again  题目...

莫比乌斯函数   μ(n) ——默比乌斯函数，是关于非平方数的质因子数目，若n=1,μ(n) =1，若n存在有大于1的平方数因数（如4(2平方)，9（3的平方)，16（4的平方）……），则μ(n) =0，否则μ(n) 的结果取决于n根据算数基本定理分解的质因数个数的奇偶性来判断。比如n=3，5，7就只有一个质因数所以为μ(n)=-1，n=6,15,21，μ(n)就为1。   性质1：若gcd(m,n)=1，则u(mn)=u(m)*u(n) ，（即u(n)为积性函数) ，若gcd(m,n)>1,则u(mn)=0. 简单分析下：若m,n为两个互质的整数，所以m的质因数和n的质因数一定不会相重...

Codeforces Round #629 (Div. 3) D. Carousel (贪心）    下面是AC代码 #include<bits/stdc++.h> using namespace std; const int N=2e5+5; int a[N],t,n,fi,be; //a[i]储存答案 fi(first)表示第一个数 ,be(before)表示当前数的前一个数.  int main(){ cin>>t; while(t--){ cin>>n; cin>>fi; int vis=0,k=1;//初始颜色种类k=1.  a[1]=...

Codeforces Round #629 (Div. 3) E.Tree Queries (DFS)  思路：若ai 在路径上 ，则ai的父结点一定在路径上，若ai是路径上某个结点的子结点，则ai的父结点一定在路径上，综上只需考虑ai的父节点就行了。对每个ai判断一下ai-1是否能到达ai,若存一个不行则输出NO，反之输出YES. 用f[i]存储父结点，用dfs[i]记录访问顺序，用sz[i]保存 子树结点数。详情见代码  #include<bits/stdc++.h> using namespace std; const int N=2e5+5; int n,m,h[N],sz...

标题Codeforces Round #629 (Div. 3)F. Make k Equal （前后缀和+讨论) 下图来自某博客园大佬，我认为写的很赞。  下面是AC代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll N=2e5+5,inf=1e15; ll a[N],n,k,pre[N],suf[N],ans=inf; int main(){ cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]; s...

Nowcoder practice 60 D.斩杀线计算大师(扩展欧几里得）  思路：  #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; #define mst(a) memset(a,0,sizeof a) void egcd(ll a,ll b,ll &x,ll &y){ if(b==0){ x=1,y=0; return; } egcd(b,a%b,x,y); ll tmp=x; x=y; y=tmp-a/b*y; } int main(...

dsu on tee相关题目练习（DFS)  1.U41492 树上数颜色  dsu on tree 裸题，具体看代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; vector<int>v[N]; int col[N],hev[N],sz[N],cnt[N],mx,son,n; ll sum,ans[N]; void dfs1(int u,int fa){ sz[u]=1; for(int i=0;i<v[u].size();i++) {...