漩涡梦幻-CSDN博客

原创逆元 + 费马定理 + 欧拉定理

一，逆元：先让我们考虑如何求解线性同余方程：a * x ≡ b ( mod m ) （1）（x为一个变量）。对于方程：a * x = b ，由于a存在倒数1/a ( a * y = 1，y为a的倒数) 所以我们可以很容易求解出该方程。如果在（1）模运算中也存在类似于倒数的数y，这样我们就能很快的求解出（1）方程。 x = b * y；在这里我们称y为a 的逆元，1

2015-08-26 09:33:34 2049

原创 poj 1845 Sumdiv

题目链接：http://poj.org/problem?id=1845一，题意：给定两个整数A，B，要求出A的B次幂，所有因子之和（要求%9901）。二，分析：1，我们知道每一个整数A都可以唯一的分解成若干素数幂的乘积，这些素数就是A的质因数：2，对于A 所有约数和我们有公式：3，我们在求解：是应用了二分等比数列求和法我们利用递归方法可以

2015-08-25 19:05:00 440

原创 Nim 博弈

一，题意：有n堆石子，每堆有ai个石子，Alice与Bob两人轮流取石子，每次取石子要求从非空堆中取走至少一颗石子，Alice为先手，取光所有石子的一方获胜，二，解析：该题为标准的Nim博弈，必胜态（非奇异态）：a1 ^ a2 ^ a3 …… ^an != 0;必败态（奇异态）： a1 ^ a2 ^ a3 …… ^an == 0;三，代码：#include

2015-08-24 19:10:14 653

原创 hdu 1525 Euclid's Game

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1525一，题意：给定两个整数N，M，Stan与Ollie轮流从较大的数中减去较小数的整数倍，但是该倍数不能超过较大的数，即运算后的结果不能为负数。从stan开始，若谁能将一个数变为0则其获胜。二，解析：我们分析一下对于当前状态为（a、b）怎么判断该状态是否为奇异态，我们令a>b

2015-08-24 15:38:15 528

原创 poj 2484 A Funny Game

题目：http://poj.org/problem?id=2484一，题意：n个硬币围成一个圈，Alice与Bob轮流从圈中取硬币，每次可以取一枚或者连续的两枚，硬币取走后留下的空位不用填补，空位相隔的两个硬币视为不相邻，Alice第一个开始取，取走最后一个硬币的人为胜利者，二，解析：该题为一道简单的博弈，是一道模范对手动作的博弈，先看看该博弈的奇异态 : 当该圈被取掉

2015-08-24 11:08:00 565

原创 hdu 1074 Doing Homework 压缩dp

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1074一，题意：给你N个课程，每一个课程由三部分组成名字，最后期限，完成所需时间，当你完成某一个课程在最后期限以后，会被扣分，扣的分数就是超出的的时间，并且要求当扣分相同的情况下要以字典序输出。二，分析：如果不需要以字典序输出的话我们可以用0 1背包可以解决，为了解决字典序这一

2015-08-21 16:28:46 591

原创三大经典博弈尼姆博奕 + 巴仕博弈 + 威佐夫博弈 +SG函数

第一，尼姆博奕（Nimm Game）一,特例分析有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。我们用（a，b，c）表示某种局势，首先（0，0，0）显然是奇异局势，无论谁面对奇异局势，都必然失败。第二种奇异局势是（0，n，n），只要与对手拿走一样多的物品，最后都将导致（0，0，0）。任何奇异局势（a，b，c）都有

2015-08-21 09:35:04 2842

原创 poj3254 Corn Fieldsdp 状态压缩

一，题意：给定一个N*M的矩阵，矩阵每个格子中只可能有两个数字0，1，1表示该土地肥沃可以种草放牛。0表示该土地不肥沃不可以种草放牛。且牛不能放在相邻的位置，问有多少种放牛的方法。二，解析：该题主要应用了图的位压缩成数的思想与递推的思想，即压缩dp。三，代码：#include #include #include #include using namespace

2015-08-21 09:22:39 583

原创 poj 1191 棋盘分割（压缩dp+记忆化搜索）

一，题意：中文题二，分析：主要利用压缩dp与记忆化搜索思想三，代码：#include #include #include #include #include using namespace std;const int Big=20000000;int Mat[10][10];int N;int sum[10][10];int dp[20][10][10][1

2015-08-20 12:11:49 684

原创 POJ2155 Matrix二维线段树

一，题意：给你一个全为0的N * N的矩阵，对这个矩阵有两个操作（对于矩阵只有两个状态0，1）（1）：“C x1,y1,x2,y2” 就是将左上角为x1,y1,右下角为x2,y2,的这个矩阵内的数字全部翻转。（2）：“Q x1 y1” 输出a[x1][y1]的值。二，解析：该我主要应用令二位的树状数组，一个是行，一个是列。三，代码：#include#inclu

2015-08-20 11:53:46 666

原创线段树模板（区间最小值优化版）（RMQ with Shifts）

题意：#include #include #include #include #include using namespace std;const int maxn =100010;int RMQ[maxn<<2];int str[maxn];int N,M;char ctr[35];int total[35],cnt;int build(int first,int

2015-08-20 09:16:09 622

原创树状数组求最大值（RMQ with Shifts）

代码：#include #include #include #include using namespace std;const int Max=200010;int RMQ[Max+10];int total[Max];int sum[35];int N,M,cnt;char ctr[35];int bit(int x){//每个下标管辖的范围 return

2015-08-19 22:07:13 790

原创 poj1222 EXTENDED LIGHTS OUT （高斯消元）

题目链接：http://poj.org/problem?id=1222一，题意：有一个5 * 6 的矩阵矩阵里面每一个格子都有一个开关，开关只有两种状态，开与关。我们用1表示开，0表示关，每一个开关的状态变化都会影起其上下左右开关的变化。我们开始给出矩阵中所有开关的初始状态，问改变多少个开关的状态能使得所有开关变成关。我们用1表示改变，用0表示不变。输出所有开关改变状态。

2015-08-17 21:31:15 544

原创高斯消元模板

高斯消元：其实就是用矩阵初等变换解线性方程组，只是他要求每次选取的主元一定要是最大值。模板#include #include #include #include using namespace std;const int MAXN=10000;int a[MAXN][MAXN];//增广矩阵int x[MAXN];//解集bool free_x[MAXN];//标记是否

2015-08-16 19:40:12 544

原创 poj 1830 开关问题 (高斯消元)

题目链接：http://poj.org/problem?id=1830一，题意：该题是中文提，题意我就不解释了。二，解析：该题我们先的建立一个图，我们以开关为节点，若开关x的变化会影响y开关，则连一条x到y的有向边。然后我们用邻接矩阵来存储该图。则邻接矩阵中0表示不影响，1表示反转。例如：样例一，开始状态为 0 0 0 最终状态为： 1 1 1

2015-08-16 16:29:09 683

原创 hdu 2476 区间dp

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2476一：题意：给定你两个字符串str1与str2，str1为初始串，str2是目标串。要你将str1变成str2串，你能做的操作只有：在str1中选取一段连续的区间将其变成全都变成同一个字母（任意一个小写字母）。问你str1最少要经过多少次这样的操作能变成str2.二，解析：我

2015-08-16 10:24:43 673

原创 hdu 2255奔小康赚大钱 KM算法模板

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2255一，KM算法：（借助这个题写一下个人对km的理解与km模板）KM算法主要是用来求解图的最优匹配的。1，带权二分图：在二分图中每一条边（x，y）对应一个权值Wi这种二分图叫带权二分图。一个匹配的权值就是该匹配中所有边的权值之和。2，最优匹配：权值最大的一个完美匹配，叫做最

2015-08-14 08:22:58 956

原创 hdu 2063 过山车二分图+最大匹配+匈牙利算法

一，二分图概念：1，二分图：二分图又称为二部图，它是图论中特殊的一种模型，令G=(v，E)是一个图，若该图中节点能被分成两个不相交的两个子集：A，B。即： (AU B) =V (A ⋂B)=ϕ。且图中每一条边（x，y）所关联的两个顶点x，y分别属于A，B两个集合内。则称G为二分图。2，匹配：在图论中，匹配是图中的一个边集，在该边集中任何两条边没有共公共端点，(1)

2015-08-12 19:58:11 433

原创 POJ3186：Treats for the Cows 区间DP

题目链接：http://poj.org/problem?id=3186一：题意：给定一个序列，序列中有N个元素，我们每次都可以从序列最前面或者最后面取出一个数，假设按照上面的方法取完所有原序列的数，形成新的序列为a1，a2，，，an，我们为这个序列定义一个权值：W=a1 * 1 + a2 * 2 + ，，，，，+an*n。题目要求，求出最大的权值。二，解析：dp[i][j]

2015-08-12 16:15:10 438

原创 POJ 2096 Collecting Bugs 期望DP

题目链接：http://poj.org/problem?id=2096一，题意：一个软件有m个子系统，n种bug，有个人每一天都能在该系统中找到一个bug。每一bug都等可能的属于n种bug中的一种，也等概率的属于m个子系统中的一个。要求，在这个软件中找齐 n 种 bug，并且每个子系统中至少包含一个 bug 的时间的期望值（单位：天）。二，解析：1，我们定义dp[i][j

2015-08-12 14:33:21 360

原创 HDU 3853 LOOPS（期望DP）（第一篇期望dp）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3853一：题意：说一个叫Homura的人被困在了一个迷宫里，该迷宫是一个矩行，矩阵的大小为R*C。刚开始Homura 在(1，1)位置，迷宫的出口在(R，C)，对于Homura 当他在每一个格子中都可以费 2 个魔法值开启传送通道，该通道可以通向三个方向，原地，向右走一格，向下走一

2015-08-12 08:53:47 503

原创 hdu 4455 Substrings dp+线段数组

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4455一，题意：给定一个序列ai，序列中元素个数为n。再给定一个整数w，w表示的是字串长度。要求你求出给定序列中所有长度为w的子串中不同元素个数之和。二，解析：该题我们主要用：dp+线段树。1，在这里线段数组主要用于快速求和，使得dp递推效率更高。2，dp[i]表示区间长度为

2015-08-11 18:19:28 486

原创 hdu3586 Information Disturbing（树状DP+二分查找）

一，题意给定 n 个敌方据点，n 个点相连构成一棵树，1 为司令部，树中每条边都有一个权值 cost 表示破坏这条边的费用。叶子节点为前线。现要切断前线和司令部的联系，要求你截断所有叶子节点的信息通过切断树中的一些边。每次切断边的费用不能超过上限 limit，切断所有前线与司令部联系所花费的总费用要少于 m 要求最小的 limit。二，解析：该题主要应用了，树状DP的建树与思

2015-08-11 08:17:20 445

原创 hdu 4734 F(x) 数位DP

一，题意：该题定义了一个函数 : F(x)=An * 2n-1 + An-1 * 2n-2 + ... + A2 * 2 + A1 * 1。现在他给定两个数，A，B，要求你求出在区间[0，B] 有多少个x ，使得F(x)二，解析：该题主要应用了，数位dp的思想+记录状态dp的思想。1，数位dp思想主要数是用数组来存储数，通过对数组每一位进行枚举（0，1，2，，，9），

2015-08-10 20:58:36 521

原创 HDU 2089 （不要62）数位DP入门

一，题意：给定一个区间[n,m]，要求求出该区间所有含4与62的数的个数。二，解析：这跟hdu3555，非常相似，介意先看hdu3555，看懂了hdu3555那么这题就是小菜令， hdu3555的详细解析在：点击打开链接唯一不同是一个是要求包含 "49" 数的个数，一个是求不含 " 4 "和 " 62 " 数的个数，这只需要改变DFS边界就行了。还有一个不同是两个题的区间不

2015-08-10 18:59:51 417

原创 HDU 3555 Bomb 数位DP

一：题意给定一个N，要求你求出[0,N]内所有含有49的数字个数，其中N (1 二：解析 1，对于这一类数位dp，需要扫描[0，N]区间所有数的每一位，为了避免对每一个数取出每位数。我们利用数组来存储区间[0,N]的每一个数，数组的长度为N的位数 x (即最大位数) ，对于没有x位的数来说，我们在前位数面补0即可，这样我们只要扫描该最长数组，枚举数组每一位可能取的数（0，1，，，

2015-08-10 17:22:34 480 1

原创 poj 2478 Farey Sequence 线性筛法优化的欧拉函数

一：题意：给定一个数n，求在[1,n]这个范围内两两互质的组合数，该题其实就是求，[2,n]分区间内的所以数组的欧拉函数之和，其中n (2 <= n <= 106)。二：欧拉函数的概念 1，欧拉函数：对于一个正整数n，小于n且和n互质的正整数（包括1）的个数，叫做该数的欧拉函数，记作φ(n) 。例如φ(8)=4，因为1,3,5,7均和8互质。 2，欧拉函数计算： (1) 通式

2015-08-10 15:51:35 550

原创 poj1061（青蛙的约会）（欧几里得扩展原理应用）

一：题意：该题是poj上稀有的中文提，他说得是，有两个青蛙在赤道上跳跃，走环路。起始位置分别为x，y。每次跳跃距离分别为m，n。赤道长度为L。两青蛙跳跃方向与次数相同的情况下，问两青蛙是否有方法跳跃到同一点。输出最少跳跃次数。二：解析假设两只青蛙跳z不后相遇，所以就有：(x+m*z) - (y+n*z) =k*L(1) (其中看为一常数) 我们要求的是就是z，且k是个变量，

2015-08-10 11:22:35 413

原创欧几里得算法与欧几里的扩展算法

一：欧几里得算法 1，欧几里德算法又称为辗转相除法，主要用于计算两个整数a,b的最大公约数。 2，原理：//递归写法int gcd(int a,int b){ if(b==0) return a; return gcd(b,a%b);}//非递归的int gcd(int a,int b){ while(b) { int

2015-08-10 10:40:23 535

原创 Hdu 3579 Hello Kiki（同余模方程组）

题意：要求求解出H，其中H%Mi=Ai ; 其中i=1，2，，，，，N；样例说明： T N M1，M2，，，，，Mn A1，A2，，，，，，An 其实该题是要求我们解这样一个方程组：首先先介绍一下同于方程组的解发；一：解二元一次非其次方程组令方程组为： ax + by = c (1) 看到这式子我们首先要想到的就是欧几里得扩展原里，即若c为a与b的最大公

2015-08-09 22:37:10 1080 2

漩涡梦幻