- 博客(112)
- 资源 (6)
- 收藏
- 关注
RSS订阅
原创 HDOJ-1171-Big Event in HDU 解题报告
普通母函数。题意：有最多50种不同价值的机器，每种机器的价值不超过50并且数量不超过100，现在要把这些机器分成A和B两部分，使两部分机器的价值尽可能相等且A的价值不能够小于B。 我的解题思路：可用普通母函数解题，也可用DP。DP貌似更加快，可惜我不会Orz。讲母函数的解法：这题本质上还算是母函数的水题，用价值作为x的指数求出母函数后找到与总价值（也就是最大的指数）的一半最
2015-05-21 18:56:02
742
原创 HDOJ-2152-Fruit 解题报告
普通母函数带上下界。中文题意不说了。 我的解题思路：我们可以设置水果的个数为x的指数，那么对于上下界分别为a和b的水果的母函数那一项为(x^a + x^(a+1) + ... + x^b)了。最内层循环枚举水果个数的时候根据上下界枚举，哎呀比较水也没什么好说的了。 我的解题代码：#include #include #include #inc
2015-05-20 14:08:39
903
原创 HDOJ-2069-Coin Change 解题报告
普通母函数变体。题意：有五种面值的硬币，50分，25分，10分，5分，1分。现在，比如我们有11分，那么这11分换成硬币可以是1个10分和1个1分，2个5分和1个1分，1个5分和6个1分以及11个1分这4种情况。现在告诉你我们手上拥有的钱数，问如果要换成硬币，有多少中换法。注意：总硬币数不能超过100。 我的解题思路：一般的母函数都是限制每种硬币的个数，而本题是限制所有硬币
2015-05-19 16:21:10
1457
原创 HDOJ-1709-The Balance 解题报告
普通母函数，不错的题。题意：你需要计算一份药的剂量，现在有若干砝码，问在从1到所有砝码的质量和这段区间内有那些重量是测量不出来的。 我的解题思路：砝码并不是只放在天平的一端，可以把砝码放在天平的两端，这样两边砝码的差值就是可以测量的质量数。所以对于每一个砝码，有三种情况，放天平左边，放天平右边，以及未使用。令砝码质量为x的指数，那么构造的母函数中对于一个质量为a的项为（x^
2015-05-18 17:57:50
866
原创 HDOJ-1085-Holding Bin-Laden Captive! 解题报告
普通母函数水题。题意：有三种面值的硬币，一元，两元和五元，个数分别为num_1，num_2，num_5，现在求不能一次性付清的最少钱数。比如如果你只有一个两元硬币，那么1元就是你无法一次付清的最少钱数。 我的解题思路：以钱数来做x的指数，那么这道题其实就是求指数最小的系数为0项（指数为0不算）了。 我的解题代码：#include #includ
2015-05-15 19:54:40
762
原创 HDOJ-1398-Square Coins 解题报告
普通母函数题。题意：在一个只使用平方数面值硬币的岛上（不超过17^2=289），有这些面值的硬币，1,4,9......等，现在要支付十元，有四种方式：十个1元硬币，一个4元硬币和六个1元硬币，两个4元硬币和一个1元硬币，一个9元硬币和一个1元硬币。现在告诉你需要支付的数量，请输出有多少种不同的支付方式。 我的解题思路：假设硬币的面值为x的指数，那么1元硬币的那一项
2015-05-12 15:58:32
872
原创 HDOJ-1028-Ignatius and the Princess III 解题报告
普通母函数基础题。题意：对于整数拆分问题，4有如下几种拆法4 = 44 = 3 + 14 = 2 + 24 = 2 + 1 + 14 = 1 + 1 + 1 + 1其中3 + 1和1 + 3属于同一种拆法。现在给你一个数，问这个数有几种拆法。 我的解题思路：普通母函数题，令数字为x的指数，那么可以构造出母函数(1 + x + x^2 + ...)
2015-05-07 14:41:16
698
原创 HDOJ-2082-找单词 解题报告
普通母函数基础题。把字母的价值作为x的指数然后就可以构造母函数为(1 + x + x^2 + ...)(1 + x^2 + x^4 + ...)...但是这里有一个需要注意的就是题目要求找到价值小于等于50的单词就行了，所以大于50的可以直接跳过。另外价值为0也就是没有英文字母这种不算单词。 解题代码：#include #include #include #inc
2015-05-07 14:28:13
744
原创 POJ-1833-排列 解题报告
STL全排列水题。PS：我已经水到只能做这种水题了Orz。 解题思路：没什么好说的，就是STL中的全排列。 解题代码：#include #include #include #include #include #include #include #include #include #include #include usin
2015-04-17 14:46:41
955
原创 HDOJ-1211-RSA 解题报告
同余方程或快速幂水题。题意：RSA加密算法是这样的，1.选择两个大素数p和q2.计算n = p × q，F(n) = (p - 1) × (q - 1)3.选择一个整数e(1 4.计算一个整数d，使得d × e = 1 (mod F(n))，d 就是密钥加密用这个方法C = E(m) = m^e mod n解密用这个方法M = D(c) = c^d mod n现
2015-04-09 15:23:34
803
原创 POJ-2115-C Looooops 解题报告
扩展欧几里得算法，同余方程。题意：C风格的for循环语句是这样的，for (variable = A; variable != B; variable += C)假设A、B和C在计算机中都是k位无符号整数，现在问这个for循环语句会执行几次循环。 解题思路：既然是k位无符号整数，那么假设循环n次，就有A + nC = B(mod 2^k)，这是一个同余方程，我们可以
2015-04-08 15:53:00
745
原创 HDOJ-5199-Gunner 解题报告
哈希。题意：有n个鸟分别在n棵树的顶端，第i棵树的高度为Hi，有个猎人准备开m枪打鸟，开枪的高度为Qi，可以把在Qi高度的所有鸟击落，现在请你输出每开一枪能够击落的鸟的个数。 解题思路：刚开始还以为是线段树，一看数据范围就萌萌哒了。看题解说是哈希可搞，于是就学了一下STL里面的map哈希，果然名不虚传。 解题代码：#include #inclu
2015-04-05 20:03:29
586
原创 HDOJ-5194-DZY Loves Balls 解题报告
概率水题，或者可以用搜索。题意：给你n个1和m个0，它们能组成q种不同的排列组合字符串，记p为这些字符串中出现01子串的次数，输出p/q的最简形式。 我的解题思路：用求概率的思路来推的话结果是(n×m)/(n+m)的最简分数形式，可是我不会。由于数据规模不大，所以也可以用dfs搜索来求出答案，dfs记录上一个数字，剩余1和0的个数还有已出现01串的次数就好了。
2015-03-30 19:19:37
1082
2
原创 POJ-2769-Reduced ID Numbers 解题报告
同余的应用，哈希。题意：给你G个学生的编号，编号为0~10^6的整数，请你找出最小的正整数m使得所有学生的编号对与模m不同余。 我的解题思路：从小到大枚举m然后哈希判断是否都不同余。我想到了一个小小的优化就是如果有n个学生的话，那么最小的正整数m至少是n，这个思想是基于容斥原理的。但是还是TLE了，最后看了讨论版才知道memset的优化，只memset用过的部分。优化后从T
2015-03-28 16:31:10
864
原创 HDOJ-5171-GTY's birthday gift
矩阵快速幂。题意：在一个有n个整数元素的集合S中，你可以做操作：选择集合S的两个元素a和b，把a+b放进集合S中。这种操作只能够做k次，要求做完后集合S里所有元素的和最大。输出S里所有元素的和模10000007的结果。 我的解题思路：首先肯定是选择S里面最大的两个元素合并再添加到S集合中，假设一开始S的最大两个元素是a和b。那么第一次添加到S集合的元素是a+b，第二次是a+
2015-03-25 19:45:32
880
原创 POJ-1284-Primitive Roots 解题报告
欧拉函数水题。题意：给出原根的定义，求模p的原根的个数。 我的解题思路：根据原根的性质，模p的原根个数为phi(phi(p))，直接求两次欧拉函数就好。 我的解题代码：#include #include #include #include #include #include #include using namespace std
2015-03-24 13:45:16
716
原创 POJ-2773-Happy 2006 解题报告
欧拉函数好题。题意：给你一个数m，请你输出从1开始升序排列与m互素的数列中的第k个数。 我的解题思路：根据数据范围，K最大可以达到1E，比m还大，因此很容易想到数据会超过32位整型。而且要找m的第k个与m互素的数肯定不能用暴力枚举的办法。两个互素的数a，b它们满足gcd(a,b) = 1这个条件，根据gcd的这么一个性质gcd(a,b) = gcd(b,a%b)即gcd
2015-03-15 12:30:58
837
原创 POJ-3358-Period of an Infinite Binary Expansion 解题报告
欧拉定理，同余运算性质，好题。题意：给你两个整数p和q，请输出p/q作为小数在二进制表示下的第一个循环节在第几位小数和最小循环节长度。比如1/10的二进制小数表示为0.00011001100110011......那么1/10的最小循环节是0011，长度为4，它第一次出现是在第二位小数上。 我的解题思路：首先要把p/q转化成为最简真分数，也就是说p二进制思考可能比较难懂
2015-03-09 20:14:32
791
原创 POJ-2478-Farey Sequence 解题报告
求欧拉函数表题。题意：法雷序列Fn对于任何一个大于等于2的n来说是这么一种序列，它是由最简真分数a/b构成，0 我的解题思路：水题，对于2～n中每一个数的欧拉函数之和就是答案了。 我的解题代码：#include #include #include #include #include #include using namespace
2015-02-24 16:17:51
716
原创 HDOJ-1563-Find your present! 解题报告
位运算巧解题。题意：给你n个数，n为奇数，这n个数里面除了一个数只出现一次其他数都有出现两次，请输出那个出现一次的数。 我的解题思路：根据异或运算性质，相同的数异或等于0，0与任何数异或都得任何数，异或运算满足交换律。这么以来把这所有的数都异或之后就得到了只出现一次的数了。 我的解题代码：#include #include #include
2015-02-18 11:08:55
819
原创 HDOJ-1164-Eddy's research I 解题报告
分解质因数水题。题意：所有数都能够被分解成质因数的乘积，现在给你一个数，请输出这个数的质因数分解式。 我的解题思路：就是分解质因数，只是格式不太好处理而已。除了第一个质因数前面不要输出*，其他质因数前面都输出一个*就可以了。 我的解题代码：#include #include #include #include #include #inc
2015-02-17 19:14:14
711
原创 HDOJ-1397-Goldbach's Conjecture 解题报告
哥德巴赫猜想水题。题意：根据哥德巴赫猜想，任何一个大于等于4的数都能被分解成两个素数的和，现在给你一个数，求它的分解方式有多少种，如果一个数可以被分解成a+b，那么b+a不能够再计算一次。 我的解题思路：数据范围什么的都水，先筛个素数，然后一个一个循环判断，循环到n/2就可以了。 我的解题代码：#include #include #inclu
2015-02-17 19:08:23
837
原创 HDOJ-5175-Misaki's Kiss again 解题报告
枚举和运用位运算性质。题意：给你一个数N（0 我的解题思路：首先注意数据范围已经超过32位整型了，所以要用64位整型。由于数据范围太大所以我们不能够直接枚举M然后求M与N的最大公约数是否等于M与N异或的值。不过我们可以直接枚举最大公约数，也就是枚举N的约数。因为N与M的最大公约数也是N与M异或的值，根据异或的性质：如果A XOR B = C，那么C XOR B = A，我
2015-02-16 14:24:16
551
原创 HDOJ-2608-0 or 1 解题报告
唯一分解定理，有点难，需要推理，也可以找规律。题意：定义T(n)为能整除n的所有正整数的和，S(n) = T(1) + T(2) + ... + T(n)。现在给你一个32位有符号整型范围类的数n，输出S(n)%2的值。 我的解题思路：首先根据定义T(n)为能整除n的所有正整数和，即T(n)就是n的所有正因子和。根据唯一分解定理的推论，一个整数n的唯一分解式是n = p1^
2015-02-13 15:37:16
749
原创 POJ-1365-Prime Land 解题报告
分解质因数水题。题意：给出n按照唯一分解定理分解出的质因数和幂，请输出n-1分解后的质因数和幂，注意顺序。 我的解题思路：只是输入不太方便而已，需要用字符串输入，一次输入一行，输入完以后就处理数据就行了。 我的解题代码：#include #include #include #include #include #include usi
2015-02-08 20:32:14
748
原创 HDOJ-4965-Fast Matrix Calculation 解题报告
矩阵快速幂好题。题意：给一个N×K的矩阵A和K×N的矩阵B（4 我的解题思路：矩阵C是N×N的矩阵，而N的值高达1000，因此暴力计算会超时。根据C=A×B，所以C^(n×n) = (A×B)^(n×n)。矩阵乘法满足乘法分配律，所以(A×B)^(n×n) = A×(B×A)^(n×n-1)×B，其中B×A是一个M×M的矩阵，M最多为6，这样就可以避免超时了。
2015-02-07 20:54:33
709
原创 HDOJ-1395-2^x mod n = 1 解题报告
欧拉定理，可暴力。题意：给一个整数n求满足2^x = 1(mod n)的最小x（x > 1)。 我的解题思路：根据欧拉定理及其推广，当n与2互素时2^phi(n) = 1(mod n)，因此容易得知当n为奇数时n与2互素。当n为偶数或者1时则必定不能满足2^x = 1(mod n)。另外，当n与2互素时phi(n)不一定是满足要求的最小x，但是根据欧拉定理的推广，最小x必定
2015-02-06 18:13:52
692
原创 HDOJ-5019-Revenge of GCD 解题报告
求k大GCD。题意：给三个正整数x，y和k，求x和y的第k大公约数。 我的解题思路：首先根据求最大公约数的原理，k大公约数是最大公约数的因子。那么求k大公约数就转换成为了求最大公约数的第k大因子。可以通过唯一分解定理得到最大公约数的因子个数，然后根据情况判断是否枚举。 我的解题代码：#include #include #include #i
2015-02-05 19:07:11
806
原创 POJ-3090-Visible Lattice Points 解题报告
欧拉函数题。题意：一个在第一象限的格点（x，y），x和y可以为0且x和y必须是整数。如果一条线段从原点到这个格点不经过其他格点，那么我们称这个格点是有价值的。现在给你范围n，请你求x和y不大于n的情况下有多少有价值的格点。 我的解题思路：首先，如果从原点到（x，y）这个格点的线段经过其他格点，假设这个格点为（a，b），那么容易知道x / a = y / b，假设等于c，可以
2015-02-04 15:02:04
765
原创 HDOJ-1905-Pseudoprime numbers 解题报告
快速幂和判断素数。题意：如果a^p mod p = a mod p且p不为素数，那么称p为基于a的伪素数，现在给你p和a，问p是不是基于a的伪素数。 我的解题思路：很简单，判断一下p是否为素数，然后快速幂求a^p mod p的值就行了，由于a比p小，所以a mod p肯定还是a，就不用判断是否等于a mod p了，另外必须要用64位整型，不然会溢出。
2015-02-04 14:20:32
617
原创 HDOJ-1299-Diophantus of Alexandria 解题报告
好题，用到唯一分解定理的推广。题意：给一个整数n（1 我的解题思路：因为x和y都是正整数，所以1/x和1/y都大于1，所以1/x和1/y都小于1/n，可知x和y都会大于n。那么假设x = n + a，y = n + b，这样的话将等式化为xy = n(x+y)后再代入化简就得到n^2 = ab，这样就是求a和b有多少种组合了，说白了，就是求n^2的因数个数。求一个正整数的
2015-02-03 19:13:13
552
原创 HDOJ-1920-Jackpot 解题报告
求多个数的最小公倍数，水题。题意：简单说吧，老虎机有几个转盘，每一个转盘停留在jackpot上都有一个固定的周期，如果所有转盘都停留在jackpot上，那么就可以赢钱，现在要求赢钱的周期，如果大于指定的数就要给出指定的信息。 我的解题思路：每个转盘的周期求最小公倍数就可以了，考虑一下边界情况只有一个转盘的情况就行了，另外根据题意如果最小公倍数大于10^9的话就输出“More
2015-02-03 13:59:31
659
原创 HDOJ-1787-GCD Again 解题报告
求欧拉函数单值，水题。题意：给你一个数n，求出大于0小于n的正整数中与n的最大公约数大于1的数的个数。 我的解题思路：与n的公约数大于1的数的个数就是与n不互素的数的个数。这里有个坑，首先就是小于n，因此输出应该是n - 1 - phi(n)。 我的解题代码：#include #include #include #include #inc
2015-01-31 18:17:37
605
原创 POJ-2407-Relatives 解题报告
水题，求欧拉函数单值。题意：给一个不超过10亿的数，算出不大于它且与它互素的正整数个数，就是求它的欧拉函数值。 我的解题思路：没什么好说的，就是求欧拉函数单值，数据不多，不需要打欧拉函数表。 我的解题代码：#include #include #include #include #include #include using name
2015-01-31 17:20:46
617
原创 UVaOJ-11752-The Super Powers 解题报告
不错的思考题，可找规律。人生第一次真正意义上的写证明。题意：如果一个数是两个不同的数的幂，那么这个数就称之为超级幂，比如64 = 8^2 = 4^3。因此64是一个超级幂。没有输入，请输出0到2^64-1范围内的所有超级幂。 我的解题思路：首先要找出超级幂的规律，根据样例明显会看出来超级幂不能算本身的1次幂，我们试着把数都分解成幂形式来看（1特殊）。16 = 2^4 =
2015-01-26 17:46:07
807
原创 UVaOJ-10200-Prime Time 解题报告
跟判断素数有关的题。题意：有这样一个公式，n^2 + n + 41，当0 39时这个公式的值有可能不是素数了，不过已知n 我的解题思路：反正n = 10000时公式的值还没有超过int范围，先将10002以内范围的素数都筛出来，然后用来判断区间内公式的值是否为素数，反正也就最多10000次判断，存储为前缀和的形式，最后根据输入的左右端点直接输出就行了。注意：比较坑的是四
2015-01-25 17:07:55
702
原创 POJ-3070-Fibonacci 解题报告
矩阵快速幂。人生第一次真正意义上写的矩阵快速幂题目啊！题意：Fibonacci数列的第0项为0，第1项为1，第2项也为1，此后第n项等于第n-1项与第n-2项的和。现在给你n，请你输出这个Fibonacci数列第n项的值的后4位数字（即对10000取模的结果）。 我的解题思路：标准矩阵快速幂，首先可以构造一个1×2的初值矩阵[ f(0) f(1) ]，然后可以构造这样一个2
2015-01-24 18:44:11
713
原创 UVaOJ-10168-Summation of Four Primes 解题报告
哥德巴赫猜想推广。题意：给一个数，如果它能被分解成四个素数的和，那么输出这四个素数，如果不能，输出指定信息。 我的解题思路：由于一个大于2的偶数能够被分解成两个素数的和，因此可以推出一个大于8的数必定能分解成4个素数的和。首先如果这个大于8的数是偶数，那么它能够被分解成两个偶数的和，再把这两个偶数根据哥德巴赫猜想分解，如果是奇数的话，那么它必定能分解成2，3和一个偶数的和，
2015-01-23 20:45:12
733
原创 POJ-2262-Goldbach's Conjecture 解题报告
验证哥德巴赫猜想。题意：任何一个大于4的偶数都能写成两个奇素数的和。现在给你一个大于等于6的数n，请你分解成n = a + b的形式，并且a和b都是奇素数，如果有多组分解形式，要求输出b - a最大的那种。如果不能够分解，输出指定的信息。 我的解题思路：首先，根据计算机科学家运行的结果，在ACM的世界里（64位整型范围内），哥德巴赫猜想是成立的，所以一定能够分解。因此将范围
2015-01-23 20:01:58
725
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人