一.题目解析
1.机器人
输入 \(s\) 和 \(T\)，表示命令串长度和秒数。分两种情况讨论：
- \(1.\quad s<T \quad\) 这时候我们发现 \(s\) 是有周期性的，所以以 \(s\) 为周期，判断周期里的 \(x\) 和 \(y\) 是多少，然后进行计数：
L=strlen(s);
x = x * (T / L);
y = y * (T / L);
记完数之后将剩下多出来的部分枚举即可。
- \(2.\quad s>T \quad\) 枚举 \(T\) 即可。
上面两种情况的时间复杂度：\(O(L)\)。
而题面中说命令串长度 \(\leq5000\)，也就是 \(L\leq5000\)，所以能拿全分。
2.排队
100%：
计算异或前缀和，并标记，枚举终点，计数获取答案。
时间复杂度：\(O(n)\)。
我的方法：
刚开始看了 \(20\) 分钟的题，一看见 \([l,r]\)，我列出了三种做法：二分，双指针，前缀和。
这个题用二分明显不行，双指针我推了 5 minutes 没有退出 \(l\) 的自增条件，于是想到：前缀和可以做异或运算。
明确思路后，先将 num[0] = 0 //num为前缀和数组。
由于普通数组是由 \(2\) 开始遍历的，所以还要预处理 \(num[1]\)：
num[1] = (num[0] ^ a[1])
之后处理前缀和数组：num[i] = (num[i - 1] ^ a[i])
最后用二维循环枚举两端点计数即可。
时间复杂度：\(O(n^2)\)，这也就导致了我只能过 \(80%\) 的数据。
3.立方求和
100%：
若有 \(n=p_1^{q_1} \times p_1^{q_2} \times p_1^{q_3} \times p_1^{q_4} \times ··· \times p_1^{q_k}\)
则 \(n\) 的约数个数为 \((q_1+1) \times (q_2+1) \times (q_3 +1) \times ···\times (q_k+1)\)
推理得：
\(\sum\limits_{i=1}^{q_1+1}i^3 \times \sum\limits_{i=1}^{q_2+1}i^3 \times \sum\limits_{i=1}^{q_3+1}i^3 \times··· \times \sum\limits_{i=1}^{q_k+1}i^3\)
为了计算，可以利用立方和通项公式：
\(\sum\limits_{1}^n{i^3}=(\dfrac{n \times(n+1)}{2})^2\)
我的方法：
暴力枚举 \(N=A^B\) 的所有约数，计算 \(F\) 函数的值。
4.攻城掠池
对于 \(k=100\) 的数据，只能进攻一座城池。我们将所有敌对城池取最大值，然后枚举前面与多少个友好城池进行过联谊。
时间复杂度：\(O(n^2)\)。
100%：
考虑倒推法，这里发现初始军队生命值不重要，因此可以把生命值看做 \(1\)，定义 \(dp[i]\)，表示第 \(i\) 座城为起点的收益。
由于是反着推，所以我们要初始化 \(dp[n+1]\) 的值，因为没有收益，所以 dp[n + 1] = 0。
接下来分两种情况讨论：
- 第 \(i-1\) 座城池是一座友好城池，则有补充和绕过两种选择， \(dp\) 关系式为：
dp[i - 1] = max(dp[i], dp[i] * (1 + 0.01 * c) - b[i])
- 否则第 \(i-1\) 座城池是一座敌对城池，有攻打和绕过两种选择， \(dp\) 关系式为：
dp[i - 1] = max(dp[i], dp[i] * (1 - 0.01 * k) + a[i])
逆推即可求出答案。
二.总结
这次考试思维难度偏高，代码短，导致我 \(T1\) 挂了 \(40pts\)，原因是字符串长度 \(len\) 可能会为 \(1\)，而我为了求字符串长度写了 len - 1 并且做了分母使用。\(T2\) 也挂了 \(40pts\)，因为数组要求为 \(10^7\)，我开了 \(10^6\)，所以导致运行错误。