优先队列优化 时间复杂度O(mlogn) #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; struct node{ int a,b; node(int _a,int _b):a(_a),b(_b){ } node(){ } friend bool operator < (node a,node b){ retur...

kruskal算法 并查集 #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; struct node{ int a,b,c; }edge[5000]; int fa[100010],ans; bool cmp(node a,node b){ return a.c<b.c; } int get(int x){ if(x==fa[x])...

可以判环，给定胜负排名次，判断是否有唯一解 #include<stdio.h> #include<vector> #include<queue> #include<cstring> using namespace std; vector<int> v[505]; int n,m,num[505]; bool tp(){ int sum=0; priority_queue<int,vector<int>,greater<int> > q; for(int i=1;i<=n;i++...

判负环，求带负权边的最短路。 #include<stdio.h> #include<vector> #include<queue> #include<cstring> const int inf=0x3f3f3f3f; using namespace std; struct node{ int a,b; node(int _a,int _b):a(_a),b(_b){ } }; vector<node> v[1000]; int n,d[1000],m,w,num[1000]; bool vis[1000]; ...

最小割=最大流 洛谷网络最大流模板题 不断找增广路，使得最大流变大 牛 Ek 时间复杂度o（nm^2），可以处理10的三次方到10的四次方规模的网络; #include<cstdio> #include<queue> #include<algorithm> #include<cstring> using namespace std; int n,m,s,t; int head[20005]; int top=1; struct node1{ int v,val,next; }node[200005]; struct node2{ ...

前置： 有向图游戏：给定一个无环图，图中有唯一的起点，在起点上放有一枚棋子，两名玩家将这枚棋子沿有向边移动，每次可以移动一步，无法移动者判负.该游戏被称为有向图游戏，任何公平组合游戏都可以看为有向图游戏，具体方法是把每个局面看成图中的一个节点，局面的转换看成有向边. mes（S）定义为求出不属于集合S的最小非负整数的运算 sg游戏： 定义：无法操作者输. 在有向图游戏中，对于每个节点x，设从x出发共有k条有向边，分别到达节点y1,y2,y3…，定义sg(x)为x的后继节点的SG函数值的值构成的集合再执行mex运算，即： sg(x)=mex({sg(y1),sg(y2),…,sg(yk)...

巴什博奕 概述：有n个石子，每个人可以拿1-m个石子，不能拿的为败者. 易知当玩家面临m+1个石子时是必败的，所以初始为k*(m+1)个石子时先手必败，应为无论如何，后手都能调整为（k-1）*（m+1）的形式，同理，当初始为k乘(m+1)+r,r小于m大于0时，先手必胜. nim博弈 问题：n堆石子，每次从某一堆中拿若干个，无法操作者输。 结论：所有石子数异或和为0则后手胜，否则前手胜。 如果异或和不为0，则无论如何都能用数量最多的那一堆调整出异或和为0的形式 NimK博弈 问题：n堆石子轮流取，每次可以任选m堆取任意个，无法操作者输，求是否先手必胜。 结论：在二进制意义上，如果每一...

牛牛牛 hdu1848 题意：三堆石子，每次能从一堆中取斐波那契数个，最后去不了的输，问谁赢 解：sg打表版子题，每个单独看，最后异或起来求解，对于一个，打个表 #include<cstdio> #include<cstring> int f[3000],sg[3000]; void init(){ f[1]=1; f[2]=2; for(int i=3;i<1000;i++){ f[i]=f[i-1]+f[i-2]; if(f[i]>1000) break; } } void get_sg(){ for(in...

m互质的情况：中国剩余定理 洛谷 P3868 [TJOI2009]猜数字 数据比较卡，所以要优化一点. #include<cstdio> typedef long long ll; const ll mod=1e18+7; ll qmul(ll a,ll b,ll mod){ ll ans=0; while(b>0){ if(b&1) ans=(ans+a)%mod; a=(a+a)%mod; b>>=1; } return ans; } void exgcd...

洛谷模板题 求出s2在s1中所有出现的位置，以及next【i】数组 next数组是指a的前缀和以i结尾的a的后缀的最大匹配 #include<cstdio> #include<cstring> const int maxn=1000005; int next[maxn],f[maxn]; int main(){ char a[maxn],b[maxn];//b是长的，a是短的 scanf("%s%s",b+1,a+1); int n=strlen(a+1); int m=strlen(b+1); next[1]=0; for(i...

给定一个字符串，我们不断把他最后一个字符放到开头，就会得到n个字符串，求其中字典序最小的就是最小表示法 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=1000005; int main(){ char a[maxn]; scanf("%s",a+1); int n=strlen(a+1); for(int i=1;i<=n;i++) a[n+i]=a[i]; int i=1,j=...

概述：给定n个字符串，进行m次询问，每次询问给一个字符串t，问在n个字符串里有几个是字符串t的前缀. 思路：字典树，每个点记一下，以这个点结尾的字符串有几个，查询的时候，一边走，一遍加. ch登不上去，所以还没交，试了几个自己写的样例都对，就先将代码放上来 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=1e6+10; const int maxxn=1e6+10; struct node{ int end; i...

kmp求让一个字符串有两个循环节，所需要加的最少的字符. n-next【n】就是循环节. 如果n能整除循环节，说明n是循环的，循环的次数就是除法所得的商 #include<cstdio> #include<cstring> const int maxn=1000005; int next[maxn],f[maxn]; char a[maxn],b[maxn]; int main(){ int t; scanf("%d",&t); while(t--){ scanf("%s",a+1); in...

板子 计算最大匹配 遍历一个集合 时间复杂度o（nm） #include<cstdio> #include<vector> #include<cstring> using namespace std; const int maxn=100005; vector<int> v[maxn]; bool vis[maxn]; int mat[maxn]; bool dfs(int x){ for(int i=0;i<v[x].size();i++){ if(!vis[v[x][i]]){ vis[v[x][i...