Pku online judge题目总结
作者：phylips@bmy
2009-1月
1.printf函数的使用
printf("%05d",n);//显示5位，用0补全
Printf("%*.*s",n,m,s);//＊用n,m代替
//寻循环节，打表，预先计算，递推，实数求近似
pku1001Exponentiation高精度。模拟大整数乘法求解
pku1002487-3279排序。自写快排超时，使用c++ algorithm库通过
pku1004Financial Management四舍五入
pku1012Joseph模拟打表。本地模拟求出结果，然后打表
pku1014Dividing dp。记录：可组合形成的整数，一维即可，二维保存最新状态，O(nm),n 为整数种类,m为最大和
pku1742Coins dp。类似1014，一个记录可以组成的硬币值的一维数组，一个记录上一次迭代，使用的最后一枚硬币的币值及个数的二维数组
pku1061青蛙的约会数论。ax＋by＝c，利用扩展欧几里得算法，注意求最小正整数解
pku3070Fibonacci数列。求fin数列：递推，观察利用题目中的矩阵特点，二分乘法，可以达到lgn的复杂度；求后几位（实验出最小循环节），求前几位（公式）
pku1047Round and Round We Go判断输入结束的错误：错误原因
一开始采用了如下cin逻辑判断结束
while(cin){
cin>>input;
***
}
实际应该为
cin>>input;
while(cin){
***
cin>>input;
}
pku1067取石子游戏博弈论。根据必败数列－－》发现重要的黄金分割律
另外划分的概念：两个有理数a,b,1/a+1/b=1；则a*n,b*n合成了自然数序列，且无交集
pku1284Primitive Roots数论。欧拉函数，筛选法，建立素数表，迭代法求欧拉函数，    * 1785年，勒让德证明：设l |（p-1），恰有φ(l)个模p互不同余的数对模p的次数为l
pku3090Visible Lattice Points数论。欧拉函数，求Phi(n)可以通过递归求解；表示[1,n-1]与n互质的数的个数
pku2407Relatives数论。欧拉函数简单使用
pku2478Farey Sequence数论。欧拉函数，关键在于时间优化，利用数组记忆，dp思想，在n 不是很大时(n<10 000 000)将递归形式的phi函数，转化为迭代形式。
pku2480Longge's problem数论。欧拉函数，求质因子在O(n)时间内，
程序优化全过程如下：
1.求质因子时利用，素数表判断因子是否为素数，素数表为100000长度，复杂度为nsqrt(n)
2.优化时间，比如求素数时只看奇数，
3.先求出输入数的公因子这样求欧拉函数时，判断因子时直接可以从求出的结果中寻，采用F(n)=sum(i*phi(n/i);0<i<=n
4.采用线性时间n求质因子，同时将欧拉函数的递归求解改成迭代，依旧 tle
5.利用积性函数性质，直接公式求解
6.继续优化求质因子的时间，只需要看1－sqrt(n)范围内的数即可，使其sqrt(n)时间内解决，两种情况(n为素数，n不为素数)
7.建立1－50000的素数表，分解N时直接看素数
一些错误：
tle：一开始分解因子用i*i<=n判断，原来是定义i为long型溢出了，然后分解因子导致tle，应该改成i<=n/i 。因为i有可能达到long的最大值－1，故i*i必溢出。
wa ：类似的道理，wa是因为只是定义了结果为long long型，而把保存质因子的long改成Long long，终于ok。因为后面公式中有一个，
res=res*((dividor[i]-1)*(num[i]+1)+1)；这样当N=2^31-1时，刚好为质数，则当它＊2之后，超出了Long能表示的最大正数范围。
另外关于各种类型变量的范围：确定选择合适的类型，如上题目中保存因子的数组应该为long类型，控制因子的变量也应该为long，因为素数可能大于Int的范围了，会造成溢出。如果不确定，则最好使用大范围的类型。
pku1095Trees Made to Order
pku1019 典型分段，类似于打表，当树的节点很少的情况下，可以先计算出来，保存到数组中。
pku2262Goldbach's Conjecture数论。歌德巴赫猜想，主要先利用筛选法求出1－1000000的素数表
pku2249Binomial Showdown组合数学。求组合数，借助double类型，用除法代替大整数级别的乘除
pku2506Tiling利用递推公式f(n)=f(n-1)+2*f(n-2)，f(0)=f(1)=1；另外也可考虑通过递推公式求出通向公式，该通项为f(N)=(2^(n+1)+(-1)^n)/3这样计算2^n可以直接移位
pku1503Integer Inquiry高精度。大整数相加
pku1730Perfect Pth Powers首先利用double类型的，pow(n,1/k)(可以计算指数为小数的)；计算底数的约值，然后利用乘法进一步确认幂的结果是否相等。注意直接int 转换，可能把(int)4.999=4;
pku1152An Easy Problem!数论。利用模运算的法则，将数的整除问题转化为数字之和的整除问题。另外注意：进制必然>最大数字
pku1028Web Navigation双栈
pku1182食物链并查集＋三角模型＋虚点技巧
pku2021Relative Relatives dfs。思路：根据输入构图，使用dfs计算每个人的年龄，qsort
排序
pku2352Stars树状数组的使用
wa字符串是什么pku2481Cows排序。cows qsort排序，然后利用树状数组做统计
pku2350Above Average注意%的printf格式写法,wa：printf("%.3lf%\n",(double)more*100/(double)m")；用乘法代替了除法，不用求平均数
pku1050To the Max dp。二维化为一维最大子段和
pku1083Moving Tables图着问题，求走廊的最大重合数
pku1143Number Game博弈树＋记忆化搜索
pku1401Factorial计算n!的末尾0的个数，主要是计算1--n中因子5的个数f(n)，而f(n) = n/5 + f(n/5)
pku1552Doubles hash。直接寻址法
pku1157LITTLE SHOP OF FLOWERS dp。f[i][j]，表示第i个花放置在第j个花瓶上所能达到的最大值，同时前i-1个花瓶已经安放完毕。
f[i][j] = max(f[i-1][k], 1-1<=k<=j)+a[i][j]
pku1163The Triangle dp。一维空间即可，注意：数组大小要申请为2*row，而非row，否则wa pku1657Distance on Chessboard棋盘上的移动，考虑的全面性
pku1674Sorting by Swapping组合数学。求置换的循环
pku1855Mint暴力。枚举所有四个元素组合方式的最小公倍数，
pku1862Stripies贪心。选择最大的合并，证明可以从三个元素开始，m1>m2>m3, 2 * sqrt(2*sqrt(m1,m2),m3)<2 * sqrt(2*sqrt(m1,m3),m2)，说明应当先选择m2
pku3067Japan树状数组统计，需要继续提高效率
pku1332Finding Liars dp。f[i][j]，表示取了i次，剩余j个的概率。f[i+1][j+1]=f[i][j]*(c-j)/c ，颜与剩余的j个均不同。
f[i+1][j-1]=f[i][j]*j/c  颜与其中一个相同
优化： n>1000,n = 1000 + n%2；由于i+1只与i有关，所以实际只需要一个二维数组保存i与i+1的结果即可
pku1958Strange Towers of Hanoi汉诺塔，递推方程
pku1079Ratio将精度运算转化为乘法运算，避免浮点比较
pku1699Best Sequence dfs。遍历所有排列，当当前方案的值大于已经求出的最小值时进行回溯。
pku1414Life Line dfs。枚举各个为0的点，采用广度优先遍历计算点数
pku1220NUMBER BASE CONVERSION进制转换
pku1338Ugly Numbers利用指数的组合生成，然后排序；dp根据递推,n与 n/2 n/3 n/5的关系，新的n的生成显然都是由已经生成的数乘以2,3,5得到的，1-n里最大数肯定是含有因子2或者3或者5的最大数
pku1306Combinations数学。double代替高精度运算
pku1289The Cat in the Hat数论。利用奇偶及输入属于Int，分析出要求的结果的范围及指数的范围，确定可以穷举并且不需要高精度，穷举时确定指数，借助pow函数，并且结合验证pku1142Smith Numbers数论。利用素数表分解整数质因子
pku1140Expanding Fractions分数化小数，同时查循环节
pku1131Octal Fractions进制转化。八进制小数化成十进制小数，(n+input[i])*0.125；不考虑小数点，转化为大整数乘法。
pku1060Modular multiplication of polynomials 01乘法，除法，只是加法和减法用异或
实现，无进位和借位
pku1650Integer Approximation double代替高精度，求小数近似的分数，首先确定大体范围，然后进一步检验,2305
pku2305Basic remains数论。//利用模运算运算性质，将模运算化简，避开高精度运算，因为除数不是大整数，这点可以利用
pku2413How many Fibs?高精度。大整数加法，可以结合二分查
关于堆,stl优先队列使用及自建堆
pku1442Black Box堆数据结构。综合最大堆和最小堆，采用stl::priority_queue实现
pku1877Flooded!堆数据结构。堆排序
pku2051Argus堆数据结构。相当于对register的时间倍数有序序列进行排序，而这个过程借助堆出序列的最大值
pku2424Flo's Restaurant堆数据结构。建立三个类型桌子的最小堆，保存到达时间，比较当前到达的与最早到达者，看能否加入堆。实际使用一个队列即可
字符串处理
pku1782Run Length Encoding字符串。使用了getline//过程如下：首先到一段(多个相同字符连续的，单个出现连续序列的)，然后对这段进行处理，如果是同一个字符的，则直接输出，否则判断1存在
pku1750Dictionary字符串。只需要观察相邻两个输入的相同字符数目，空格数目＝min((preBlankNum + 1) : i )
pku1760Disk Tree字符串。//排序然后根据相邻两个的关系输出
pku2601Simple calculations数学，a1=(n*a[0]+a[n+1]-2*(n*c1+(n-1)*c2+...+cn))/(n+1) pku2406Power Strings字符串。kmp的预处理函数
分段，打表
pku2606Rabbit hunt暴力。求一条经过最多点的直线，穷举，n^3
pku2323PERMS逆序数。相关，dp，递推：f(n,k)=f(n-1,k)+....+f(n-1,k-n)
pku2853Sequence Sum Possibilities
pku2140 求和为n的连续正整数数列个数
pku1056IMMEDIATE DECODABILITY字符串。判断是否存在一个是另一个的前缀：排序后判断相邻的两个是否具有包含关系，前一个是否是后一个的前缀子串。
Pku2513Colored Sticks并查集。颜为顶点，一个stick代表了一个边，实际上是在判断是否存在欧拉圈 )(图是连通的，并且不存在奇点，欧拉链，奇点数为2)。利用trie树判断颜是否已经存在，并转化为标号，并查集用来判断图的连通性。
Pku1837Balance dp。 f[i][j]表示采用前i个砝码得到和(重量与坐标乘积之和)为j的方案数目，由于j可能为负数，故需要将和处理一下加上一固定值使其>=0.f[i][j+delat] += f[i][j];
Pku1961Period字符串。
Pku1226Substrings字符串。寻n个串的公共子串
Pku3080Triangular Sums字符串。寻n个串的最长公共子串，一个最短的，枚举其子串，
用Kmp判断其是否是其他串的子串。
pku2388Who's in the Middle求中位数，第K大元素的原理
pku3253Fence Repair堆数据结构。利用最小堆实现huffman树的建立过程，注意要用long long类型，wa原因还把入堆的元素搞错
pku3349Snowflake Snow Snowflakes排序。先把数据规格化，然后用quicksort排序，另外
可尝试bst，hash等方法
pku2299Ultra-QuickSort逆序对。利用归并排序的思想统计逆序数
pku1035Spell checker暴力。优化过程：预计算word插入，删除，替换后的串，超时-> 直接
在判断时进行忽落操纵->自己的cmp该成库的strcmp.AC
pku2739Sum of Consecutive Prime Numbers数论。求出素数，然后计算前缀和
pku2499Binary Tree根据a,b大小判断左右，左的为（a+b,b）, 右为(a,a+b)；注意用除法代
替减法以加速计算。
Pku2503Babelfish字符串。简单字典查询操作，trie实现
Pku3006Dirichlet's Theorem on Arithmetic Progressions数论。筛选法求<1000 000的
素数表
Pku2001Shortest Prefixes排序。quicksort排序之后只判读处理相邻字符串
Pku2080Calendar日历问题。计算从2001.1.1之后的某天的日期，星期。注意可以采用从后
往前的方法，保证days >= 当前年或者月的即可。
for(i = 2000 ; days >= year[type(i)] ; i++)
days -= year[type(i)];
这样计算出来i既是年份。
Pku1543Perfect Cubes搜索&预计算。预先计算立方数存在数组内
pku3094Quicksum水题
pku1519Digital Roots数论。数根，快捷方法：各位之和除以九取余数，若余数为 0 则取 9。
相关的数学原理：十进制数除以九的余数等于各位之和除以九的余数。令 X=abcdefg 为十进
制数。其中 a, b, c, d, e, f, g 各代表 0-9 的一个数。则 a + b + c + d + e + f + g =    (a * 10^6) % 9 + (b * 10^5) % 9 + (c * 10^4) % 9 + (d * 10^3) % 9 + (e * 10^2) % 9
+ (f * 10^1) % 9 + (g * 10^0) % 9 =( (a * 10^6) + (b * 10^5) + (c * 10^4) + (d * 10^3)
+ (e * 10^2) + (f * 10^1) + (g * 10^0) ) % 9 + 9 * k = (这里的 k 是非负整数) abcdefg % 9 + 9 * k = X % 9 + 9 * k。
于是，取十进制数各位之和相当于将该数除以九的余数加上九的某个倍数。
重复该过程将使得后面加上的九的倍数越来越小，最终的结果肯定是：X % 9 (X % 9 != 0) 或
9 (X % 9 = 0)
注意这题的输入数可能有很多位，需要先开个字符数组。
Pku2309BST规律。首先确定该节点所在层数，然后逐步加或减2的幂次
Pku1906Three powers高精度&记忆化。首先编写乘以3的高精度，计算3的幂保存在数组，
然后实际上是在计算二进制位模式。注意n应当采用无符号64位，输出要用{}而不是()
Pku1700Crossing River过桥问题。根据数学结论，两种过桥模式进行讨论
Pku3404Bridge over a rough river过桥问题。根据数学结论，两种过桥模式进行讨论
Pku27854 Values whose Sum is 0排序。两两求和，排序后查
Pku1051P,MTHBGWB字符串。简单字符串替换
Pku2182Lost Cows逆序对。利用插入排序与逆序对的关系。首先根据输入，实际上是逆序对
个数，进行一次插入排序，然后根据插入排序后的结果确定原来元素的大小顺序。
for example：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。