一、DFS： const int maxn=100008; int head[maxn],nt[maxn],ver[maxn],edge[maxn]; bool ha[maxn]; void DFS(int x) { ha[x]=true; for(int i=head[x];i;i=nt[i]) { int y=ver[i]; if(ha[y]) continue; DFS(y); } return ; } int main(void) { //建图 memset(ha,0,sizeof(ha)); DFS(1); return 0; }  这段代码访问每个点和每条边恰好一次（如果是无向边，...

一、Dijkstra算法 二、Bellman-Ford算法 三、SPFA算法 四、Floyd算法 一、Dijkstra算法： 无负权图的单源最短路径问题。 求一张无负权图的某点到其他节点的最短距离。 1.算法思路 ①初始化dis[1]=0,其余节点的dis为正无穷大（正无穷大的一半inf/2，保证a+b<=inf， 防止相加溢出；memset(dis,0x3f,sizeof(dis)); ②找出一个未被标记的、dis[x]最小的节点x，然后标记节点x。 ③扫描节点x的所有出边（x，y，z）若dia[y]>dis[x]+z,则使用dis[x]+z更新dis[y]; ④重复上述2–3两...

一、最小生成树简介： 给定一张边带权的无向图G=（V,E），n=|V|，m=|E|。由 V 中的全部 n 个顶点和 E 中的 n-1 条边构成的无向连通子图被称为G的一棵生成树。边的权值之和最小的生成树被称为无向图G 的最小生成树（MST）。 1。任意一棵最小生成树一定包含无向图中权值最小的边。 2。给定一张无向图G=（V，E）,n=|V|，m=|E|。从E中选出 k < n-1 条边构成G 的一个生成森林。若再从剩余 的 m-k 条边中选 n-1-k 条边添加到生成森林中，使其成为G 的生成树，并且选出的边的边权之和最小，则该生成树一定包含这m-k条边中连接生成森林的两个不连通节点的边...

一、质数： 若一个正整数无法被除了1和它自身之外的任何自然数整除，则称该数为质数（或素数）， 否则称该正整数为合数。 1不是素数，2是最小的素数。 在整个自然数集合中，质数的数量不多，分布比较稀疏， 对于一个最够大的整数 N，不超过 N 的质数大约有      N    l   n   N      \frac{N}{lnN}   lnNN​个，即每lnN个数大约有1个质数。 二、素数表的获取——Eratosthenes筛法： 小于x*x的x的倍数在扫描更小的数时就已经被标记过了。 对于某一个合数，其倍数一定在某个比其小的质数（其质因数）筛掉了。 时间复杂度为O（N loglogN）接近线性。...

一、互质： 若gcd(a,b)=1,则称a,b互质。 若gcd(a,b,c)=1,则称a,b,c互质。 若gcd(a,b)=gcd(a,c)=gcd(b,c)=1,则称a,b,c两两互质。 二、欧拉函数： 1。1–N中与N互质的数的个数被成为欧拉函数。记为     φ   (   N   )    φ(N)   φ(N)。 2。通式：      φ   (   N   )   =   N   ∗   （   1   −   1   /   p   1   )   ∗   (   1   −   1   /   p   2   )   …   …   （   1   −   1   /   p ...

一、同余： 1。若整数a和整数b除以正整数m的余数相等，则称a，b模m同余，记作a≡b（mod m）。 2。费马小定理：若p是质数，则对于任意整数a，有ap ≡a（mod p）。 3。欧拉定理：若正整数a，n互质，则 aφ(n)≡1(mod n) ,其中φ(n)是欧拉函数。 4。若正整数a，n互质，则对于任意正整数b，有ab≡ab mod φ(n)(mod n)。 很多问题要求我们对一个质数p取模后输出。面对乘方算式，我们可以先把 底数对p取模（底数不是p的倍数）、指数对φ（p）取模，再计算乘方。 若a，n不一定互质且b＞φ（n）时，有ab≡ab mod φ(n) + φ(n) (mod n)...

一、快速幂： ll mypow(ll a,ll b) { ll ans=1; while(b) { if(b&1) ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; }  二、矩阵快速幂： #include<cstring> #define ll long long const int maxn=12; struct Ma { ll m[maxn][maxn]; }; Ma mul(Ma a,Ma b,int n) { Ma temp; memset(&temp,0,sizeof(temp)); for(int...

一、巴什博弈： 巴什博弈：只有一堆n个物品，两个人轮流从这堆物品中取物， 规定每次至少取一个，最多取m个。最后取光者得胜。      i   f   (   n   %   (   m   +   1   )   !   =   0   )   先   手   赢    if(n\%(m+1)!=0) 先手赢   if(n%(m+1)!=0)先手赢      e   l   s   e   后   手   赢    else 后手赢   else后手赢 二、例题： 1。Tang和Jiang轮流写数字，Tang先写，每次写的数x满足1≤x≤k，Jiang每次写的数y满足      1   ≤  ...

一、斐波那契博弈：   有一堆物品，两人轮流取物品，先手最少取一个，至多无上限，但是不能把物品取完，之后每次取的物品数不能超过上一次取的物品数的二倍且至少为1件，取走最后一件物品的人获胜。   先手胜当且仅当n不是斐波那契数（n为物品数）。

一、Ferguson游戏：   有两个盒子，一个装有m颗糖，一个装有n颗糖，表示为（m，n）   每次清空一个盒子，将另一个盒子里的糖转移一些过来，并保证两个盒子至少各有一颗糖   最后进行转移糖者获胜，无法转移糖者败。      m，n都为奇数，先手败   m，n至少一个为偶数，先手胜。

一、chomp！游戏： 1。   有一个n * m的棋盘，棋盘的每一个格子用（x，y）表示，最左上角是（1，1）   每次可以拿走一个方格，并拿走该方格右边与下边的所有方格，谁拿到（1，1），谁败。   除了n=m=1先手败，其余先手胜。   三维的除了（1，1，1）先手败，其余的先手胜。 2。   桌子上有n个数字，1–n。   两人轮流选择一个桌子上的数x，然后将x与x的约数都拿走，拿走最后一个数的人胜出。   先手必胜。 二、策梅洛定理： 策梅洛定理,表明在二人参与的游戏/博弈中，如果满足： --------游戏的步骤数有限 --------信息完备(二人都了解游戏规则，了解游戏曾经所发...

一、公平组合游戏ICG：   若一个游戏满足：   --------由两名玩家交替行动   --------在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关   --------不能行动的玩家判负   则称该游戏为一个公平组合游戏。 二、有向图游戏：   给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动着判负。该游戏称为有向图游戏。   任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向 沿着合法行动能够到达的下一个局面连有向边。      mex运...

一、P/N分析法：   P点：即 必败点，某玩家位于此点，只要对方无失误，则必败。   N点：即 必胜点，某晚接位于此点，只要自己无失误，则必胜。   必败态：一定输。   必胜态：一定赢。   奇异局势：必败态局势。   非奇异局势：必胜态局势。 P/N点满足三个定理： （1） 所有终结点都是必败点P（游戏中，轮到某玩家拿牌，还剩0张牌的时候，此人就输了，因为无牌可取）。 （2）所有一步能走到必败点P的就是N点。 （3）所有一步操作只能到N点的就是P点。 取石子：每人取1—3个，共九个   0   1   2   3  4  5  6  7   8   9   P  N  N  N  P  ...