MMOIer水杯解题报告.ppt

1~3题 By MMOIer CRAZY 二分快速求幂 Crazy 1 题目大意 a,b,c均为整数，sqrt（c）不是整数。 求x,y Crazy 2 少数情况 N3可以用公式 其他情况呢？ Crazy 3 递推 (a+b*sqrt[i])*(c+d*sqrt[i]) =a*c+a*d*sqrt[i]+b*c*sqrt[i]+ b*d*sqrt[i]*sqrt[i] =(ac+bdi)+(ad+bc)*sqrt[i] 一步步递推 (a+b*sqrt[i])* (a+b*sqrt[i])… =(a’+b’*sqrt[i])*… Crazy 4 O(n).对于50%，n=150000 对于100%,nTLE 改进 多项式展开？ 二项式定理？ 目前没发现二项式定理对此题的作用。。。 Crazy 5 满足结合律 二分 F(x)^n//n为偶数，为奇数时类似。 =(F(x)^(n/2))^2 O(logN).完全没问题 DINNER 枚举 Dinner 1 题目大意 感觉写不清楚 省略。。 Dinner 2 枚举 先枚举对应第一个字母的人 接下去寻找可能的组合 条件1：直接寻找可能下一个字符 条件2：一定是找到的第一个 条件3：不会找到前面去。 O(n)*O(n)=O(n^2) Dinner 3 具体实现参见代码 代码很丑 LOST 数学方法 Lost 1 题目大意 1 求a/b的第k位 2 模拟最后的位置。 Lost 2 第1~3个点。 模拟。 简化的高精度除法。 第4~5个点。 利用循环节。 哈希表判重 Lost 3 恶心。 还有50%怎么办？ 对高精度没有什么情感。 数学分析 Lost 3 考虑一个数乘以10： 0.123*10=1.230 小数点右移一位！ 那么乘以10^(n-1)， 小数第1位刚好是原来的小数第n位。 Lost 4 一个数的小数部分 a÷b=q……r，a=b*q+r (b*q+r)/b=q+r/b 只有r影响小数部分。 故a*10^(n-1)mod b / b的第一位小数即为所求 边除边取模即可，不用高精 Lost 5 又是二分法求幂，O(n*log(k)) 模拟部分： 常量数组，直接累计即可。 O(n*log(k)),AC NO1 动态规划 No1 1 动态规划 带路径输出 方法很多，各种复杂度都有。 原题是N,M,K1000 对于此题的范围，应该不难过。 注意字典序 没有了。。? 谢谢观赏 THANK YOU Be Calm and Indomitable.