MMOIer水杯模拟赛解题报告
1~3题
By MMOIer
CRAZY
二分快速求幂
Crazy 1
题目大意
a,b,c均为整数,sqrt(c)不是整数。
求x,y
Crazy 2
少数情况
N<3可以用公式
其他情况呢?
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%,n<=15000000
TLE
改进
多项式展开?
二项式定理?
目前没发现二项式定理对此题的作用。。。
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)
mmoier水杯解题报告 来自淘豆网m.daumloan.com转载请标明出处.
