11.4-11.10做题总结

自从 CCF 出分，到得知自己考了 150pts，再到得知自己无法参加 NOIP，我的内心一直是悲痛的。

WB 老师之后让我做 LYD 做的算法进阶指南。

tx 告诉我 acwing 上有单独题单，于是一直做 acwing 的题。

AcWing 89. a^b

快速幂即可。

AcWing 5579. 增加模数

拆开。

AcWing 90. 64位整数乘法

将快速幂的乘法改为加法即可。

AcWing 998. 起床困难综合症

模拟即可吧。

AcWing 92. 递归实现指数型枚举 && AcWing 93. 递归实现组合型枚举 && AcWing 94. 递归实现排列型枚举

简单，模拟即可。

AcWing 95. 费解的开关

简单。

AcWing 96. 奇怪的汉诺塔

跟据前几天《具体数学》的学习，推出了 \(f[i] = min(f[i], 2 \times f[j] + d[i - j])\)。

AcWing 97. 约数之和

\(A\) 可以分解质因子成 \(p_1^{c_1}+p_2^{c_2}+\dots +p_n^{c_n}\)。

将 \(A^B\) 拆开，再利用乘法分配律（小学知识）合并成：

\((p_1^1+p_1^2+p_1^3+p_1^4\dots +p_1^n)(p_2^1+p_2^2+p_2^3+p_2^4\dots +p_2^n)\dots (p_n^1+p_n^2+p_n^3+p_n^4\dots +p_n^n)\)。

接下来原本可以用等比数列求和公式求出，但本着书上是啥练啥的原则，我写了递归。

求等比数列的和设为 \(sum(p,c)（p,c如上）\)。

分成两种情况：

1. \(c\) 是奇数：

答案应是 \((1+p^{\frac{c+1}{2}})\times \frac{sum(p,c-1)}{2}\)。

2. \(c\) 是偶数：

答案应是 \((1+p^{\frac{c}{2}})\times sum(p,\frac{c}{2}-1)+p^c\)。

AcWing 98. 分形之城

似乎只是题意难理解而已。

AcWing 99. 激光炸弹

二维前缀和，但细节尤为重要，动不动就 MLE 或 SF。

AcWing 100. IncDec序列

记住！！！(1. abs 自己写！2. 自己写的时候函数内加long long 否则真没意义了)

差分解决。