最近好虚啊，还是复习一下最经典的最短路吧  floyd太简单就不写了  qwq  写个堆优化dijkstra好了 堆优化dijkstra算法 O(m + nlogn） #include<iostream> #include<cstdio> #include<algorithm> #include<queue> #define pair pair<int,int> using namespace std; struct edg{ int to,next,v; }e[12410]; int head[2510],size,f[2510];...

（一）定理和性质 一、裴蜀定理 如果  a,b∈N  a , b ∈ N  ,  (a,b)=d  ( a , b ) = d  那么一定存在  x,y  x , y  使得  d|(a∗x+b∗y)  d | ( a ∗ x + b ∗ y )   证明：非常简单，鉴于可能有数论刚入门的OIer所以这里简单证明一下：  因为 (a,b)=d  ( a , b ) = d   所以我们就可以假设  a=p∗d  a = p ∗ d  ,  b=q∗d  b = q ∗ d   那么 a∗x+b∗y=p∗d∗x+q∗d∗y=d∗(p∗x+q∗y)  a ∗ x + b ∗ y = p ∗ d ∗...

Hackerrank World CodeSprint 7  Summing Pieces  传送门 题目大意：给你一个数列 把这个数列分成若干个子串 求出所有分法的权值和（权值和的计算方式为：Σ每个子串的长度*每个子串的权值和）（n<=10^6） 首先想到了一个n^2的dp  但是后来不会优化…  于是就想到了贡献法 下面是做法：  一个长度为i的数列的分法为2 ^ (i-1)种  对于位于p的位置的数，假设他左边有L个数，右边有R个数，包含它的子串的长度为n - L - R，  那么他的对答案的贡献为   但是计算一次显然是O（n^2）的 我们需要把它优化到O（1）  我们把这个式子...

vjudge传送门  题目大意：  给一个GCD为1的数列，有两个人每次选出一个数把这个数-1，然后把整个数列除以新数列的GCD，询问先手和后手哪个必胜。 Solution：  不难看出这是一道博弈论，我们可以假设没有GCD的限制，那么我们怎么做呢？求数列的sum然后判断sum-n的奇偶性就可以了。类比上述情况，当这个数列全是奇数时，每次操作必然会产生一个偶数，由于新数列的GCD一定是奇数，所以说GCD并不会影响数列的值的奇偶性，所以说如果初始数列全是奇数的话，那么后手必胜，策略很简单：先手改出一个偶数，后手再把它改回去，如此往复，先手必输。  既然我们知道只有一个偶数的话先手必赢，那么类比一...

Hackerrank hourrank 19  What Are the Odds?  传送门  题目大意：  两个人在玩一个叫做Nim game（n堆石头，每个人每次从一堆中选择一个或多个石头移走，最后不能移动的人输）的游戏，他们把这个游戏更改了一下，每次在游戏前先移除[L,R]区间内的石子(L<=R)，然后进行游戏，问有多少种方法使得后手必胜(n<=5*10^5) Solution：  刚看到题的时候想了好久必胜策略是啥，后来才知道原来这是一个经典的Nim game模型（不知道的可以百度一下，百科里面很详细），这里我就说一下结论吧，当每堆石子数的异或和为0时，后手必胜，所以说我...

传送门 题意： 有两个人，初始在不同的位置，他们需要按照顺序到一些点，求最短的最大相隔距离  n ≤ 1 0 5 n\leq 10^5 n≤105 Solution： 看到“最短的最大”，首先考虑二分，深思熟虑之后发现可以二分+dp+数据结构优化，但是这个方法太难写了，通过观察cf上其他人的做法以及机房各位神犇（orz ckw）的思路，发现了一种非常妙的做法：首先二分答案，然后我们考虑倒着往后推：对于每一个点的i所对应的[L,R]表示只考虑i-n这些点，这两个人能完成任务的区间（也可以近似的看成一个人在第i个点时另一个人可以在的区间，因为除了初始状态不在要到达的点上外其他状态一定是有一个人在要...

Codeforces875 F-Royal Questions  传送门  题意：  n个王子，m个公主，给出第i个公主可以嫁给的两个王子ai,bi以及嫁妆，每个王子只能娶一个公主，公主只能在两个中选一个，求最大嫁妆。 Solution：  这题乍一看是一个二分图匹配，但是思考良久发现不可做，于是决定转化思路，首先想到了贪心：首先按照嫁妆把这m组数排序，然后贪心的去搞，但是怎么判断具体嫁给那一个王子呢？一个很妙的想法：对于每个公主i，把ai和bi连边，表示选择ai或者bi，这样操作后我们可以发现：如果形成了的联通块中点数大于等于边数，那么那么这个方案是可行的，因为每一个边表示一种选择，每一个点...

题意：有n盏灯环形排列，顺时针依次标号为1⋯n。初始时刻为0，初始时刻第i盏灯的亮灭a[i]给定，0表示灭，1表示亮。下一时刻每盏灯的亮灭取决于当前时刻这盏灯与顺时针方向下一盏灯的亮灭。若两盏灯状态相同，则下一时刻该灯灭，否则该灯亮。求时刻t第k盏灯的状态。  （n，t，k≤1e7）  Solution：  异或可以看成不进位的二进制加法，于是我们可以先做出一个图找找规律：   可见，对于第i个数，在执行t步操作后对第一个数的贡献为（可以转化成一共走t步，每次向下或者向左下，其中有i次向左下的方案数），因为模数是2，所以如果是偶数，那么这个数相当于是没有贡献的，所以我们就得到了答案：（所有下标...

题意：  有n个商品，每件商品有一个价值，现在要把商品分组，求每组的最大价值与最小价值的价格差的和不超过m的分组种数。 Solution：  DP，朴素的dp状态（f[i][j][k]表示前i件分成j组价格差为k的方案数）发现不好转移，所以说我们考虑找一个新状态：将所有数组排序，那么每一组的最大值减最小值的差相当于是排序后的数组的一段差分和，根据这个我们可以设计转移状态：f[i][j][k]表示前i个数，其中有j组可以往里加数，价格差为k的方案数。  那么每个i和前一个的差分：cha=a[i]-a[i-1]  每次差值的增加量：add=cha*j（因为现在的j组都可以往里加数，而我们要的是差分...

Codeforces587B-Duff in Beach  传送门  题意：  给出一个有l个数的序列，序列每n个数一循环，在每个循环里取一个数，一共取1-k个数，要求取出来的子序列要递增，求方案数。n×k≤1e6 l≤1e18 Solution：  DP，f[i][j]表示取了i次，最后一项取的位置是j的方案数，我们能迅速的想到一个转移方程：     f[i][j]=∑k=0,ak≤ajn−1f[i−1][k]  f [ i ] [ j ] = ∑ k = 0 , a k ≤ a j n − 1 f [ i − 1 ] [ k ]    发现暴力转移会T，考虑优化：  然后就写了2小时树状数...

传送门  题意：  给你一个字符串s，问s最少分成几块，使得每一块在经过组合后都能成为一个回文串。（|s|≤2e5） Solution：  我们可以转化一下“回文串”这个定义，对于每个字母我们可以把它分别转化到二进制的0-25位，然后如果一段字符串是回文串，那么这段字符串每个字符的异或一定是0或者2的幂，那么这道题就可以用dp做了：f[i]表示前i个字符的被分成的最小段数，转移即为     f[i]=min(f[j]+1)(1≤j<i,a[j]a[i]=0或2的幂)(a[i]为前缀异或和)  f [ i ] = m i n ⁡ ( f [ j ] + 1 ) ( 1 ≤ j < i...

传送门  题意：  给一个区间[1,n]，再给出m个区间 [li,ri]  [ l i , r i ] 以及每个区间的维修成本 vi  v i ，问修好k个不同的整点所需的最小成本。  （n≤300，m≤1e5） Solution：  这道题首先想到了朴素的 n2m  n 2 m 的dp（按照右端点排序，f[i][j][k]表示前i个区间，选了j个点，上一个选的右端点为k的最小代价），但是显然会T，转移时O（1）的所以无法优化，所以考虑优化状态：发现m太大，那么能否优化掉m呢？考虑预处理：dis[l][r]表示一次修理l到r这段区间的最小花费（详见代码），然后就不需要枚举m了，此时我们的dp可...

传送门  一道练习综合代码能力的好题  先把被依赖的点连向依赖这个点的点，再tarjan缩点，缩点后会形成多棵树，对每棵树进行dp，最后进行一次背包即可，注意要倒着枚举。  代码： #include<cstdio> #include<iostream> #include<cstring> using namespace std; struct wp{ int v,w; }a[110],b[110]; int low[110],dfn[110]; int cnt,fa[110]; int n,m,z[110]; struct edg{ int to,next;...

传送门  题意：中文题，非权限题。 Solution：  显然不能贪心，那么考虑dp，注意到 b[i]≤7  b [ i ] ≤ 7 ，所以说可以考虑状压怎么做，再结合n<=1000，想到了一个状态：f[i][j][k]表示前i-1个人都吃过饭了，j表示后面7人和i的吃饭状态，上一个吃过饭的人是k。  转移：  f[i+1][j≫1][k]=f[i][j][k]  f [ i + 1 ] [ j ≫ 1 ] [ k ] = f [ i ] [ j ] [ k ]  (j&1==1,即i已经吃饭了)   f[i][j|(1≪t)][i+t]=f[i][j][k]+cal(i+t,k...