pku online judge题目小结【荐】.pdf

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){ cininput; *** } 实际应该为 cininput; while(cin){ *** cininput; } 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 不是很大时(n10 000 000)将递归形式的phi函数，转化为迭代形式。 pku2480Longges problem 数论。欧拉函数，求质因子在O(n)时间内， 程序优化全过程如下： 1.求质因子时利用，素数表判断因子是否为素数，素数表为100000 长度，复 杂度为nsqrt(n) 2.优化时间，比如求素数时只看奇数， 3.先求出输入数的公因子这样求欧拉函数时，判断因子时直接可以从求出的结 果中寻找，采用F(n)=sum(i*phi(n/i);0i=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