pku online judge题目小结

《pku online judge题目小结》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Pkuonlinejudge题目总结作者：phylips@bmy2009-1月1.printf函数的使用printf("%05d",n);//显示5位，用0补全Printf("%*.*s",n,m,s);//＊用n,m代替//寻找循环节，打表，预先计算，递推，实数求近似pku1001Exponentiation高精度。模拟大整数乘法求解pku1002487-3279排序。自写快排超时，使用c++algorithm库通过pku1004FinancialManagement四舍五入pku1012Joseph模拟打表。本地模拟求出结果，然后打表pku1014Dividingdp

2、。记录：可组合形成的整数，一维即可，二维保存最新状态，O(nm),n为整数种类,m为最大和pku1742Coinsdp。类似1014，一个记录可以组成的硬币值的一维数组，一个记录上一次迭代，使用的最后一枚硬币的币值及个数的二维数组pku1061青蛙的约会数论。ax＋by＝c，利用扩展欧几里得算法，注意求最小正整数解pku3070Fibonacci数列。求fin数列：递推，观察利用题目中的矩阵特点，二分乘法，可以达到lgn的复杂度；求后几位（实验找出最小循环节），求前几位（公式）pku1047RoundandRoundWeGo判断输入结束的错误：错误原因一开始采用了如下ci

3、n逻辑判断结束while(cin){cin>>input;***}实际应该为cin>>input;while(cin){***cin>>input;}pku1067取石子游戏博弈论。根据必败数列－－》发现重要的黄金分割律另外划分的概念：两个有理数a,b,1/a+1/b=1;则a*n,b*n合成了自然数序列，且无交集pku1284PrimitiveRoots数论。欧拉函数，筛选法，建立素数表，迭代法求欧拉函数，*1785年，勒让德证明：设l

4、（p-1），恰有φ(l)个模p互不同余的数对模p的次数为lpku3090VisibleLatticePoints数论。欧拉函数，求Ph

5、i(n)可以通过递归求解；表示[1,n-1]与n互质的数的个数pku2407Relatives数论。欧拉函数简单使用pku2478FareySequence数论。欧拉函数，关键在于时间优化，利用数组记忆，dp思想，在n不是很大时(n<10000000)将递归形式的phi函数，转化为迭代形式。pku2480Longge'sproblem数论。欧拉函数，求质因子在O(n)时间内，程序优化全过程如下：1.求质因子时利用，素数表判断因子是否为素数，素数表为100000长度，复杂度为nsqrt(n)2.优化时间，比如求素数时只看奇数，3.先求出输入数的公因子这样求欧拉函数时，判断因

6、子时直接可以从求出的结果中寻找，采用F(n)=sum(i*phi(n/i);0

7、wa是因为只是定义了结果为longlong型，而把保存质因子的long改成Longlong,终于ok。因为后面公式中有一个，res=res*((dividor[i]-1)*(num[i]+1)+1);这样当N=2^31-1时，刚好为质数，则当它＊2之后，超出了Long能表示的最大正数范围。另外关于各种类型变量的范围：确定选择合适的类型，如上题目中保存因子的数组应该为long类型，控制因子的变量也应该为long,因为素数可能大于Int的范围了，会造成溢出。如果不确定，则最好使用大范围的类型。pku1095TreesMadetoOrderpku1019典型分段，类似于打表，当

8、树的节点很少的情况下，可以先计算出来，保存到数组中。pku2262Goldbach'sConjecture数论。歌德巴赫猜想，主要先利用筛选法求出1－1000000的素数表pku2249BinomialShowdown组合数学。求组合数，借助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可以直接移位pku1503Integ