洛谷

题目大意 给定石头的高度 $h$，从第 $i$ 块石头跳到第 $j$ 块上耗费体力 $(h_i-h_j)^2$ ，求最耗体力的路径。 分析 容易猜到贪心结论，是不断的在剩余石头中最大最小的来回跳。 考虑证明结论，设 $h_i$ 是将要跳的序列，展开求和式 $$ S = \sum_{k=1}^{n-1}(h_k-h_{k+1})^2 = \sum_{k=1}^nh_k^2 - 2\sum_{k=1}^{n-1}h_kh_{k+1} $$ 注意到平方和为一个定值，重点在后半式。记 $H_k = h_{k+1}$，有 $$ \sum_{k=1}^{n-1}h_kH_k $$ 利用高中时学的排序不等式，有 $$ \text{反序和} \leqslant \text{乱序和} \leqslant \text{顺序和} $$ 于是有反序最小。双指针维护即可。 ll nn[310]; int main() { ll n = rr(); for (ll i = 1; i <= n; i++) nn[i] = rr(); sort(nn + 1, nn + n + 1); ll l = 0, r = n, sum = 0; while (l < r) { ll t1 = nn[l] - nn[r], t2 = nn[l + 1] - nn[r]; sum += t1 * t1 + t2 * t2; l++, r--; } printf("%lld\n", sum); return 0; }

题目大意 在三维空间中，HKE 只能往上走，求攀爬总长。 分析 对所有座标的 $z$ 分量排序即可。 struct POINT { double x, y, z; bool operator<(POINT p) { return z > p.z; } } nn[50010]; double dis(POINT &p1, POINT &p2) { double t1 = p1.x - p2.x, t2 = p1.y - p2.y, t3 = p1.z - p2.z; return sqrt(t1 * t1 + t2 * t2 + t3 * t3); } int main() { int n = rr(); for (ll i = 1; i <= n; i++) cin >> nn[i]....

P1095 守望者的逃离 题目大意 守望者的可以在一秒逃出 $17 {\rm m}$，或者消耗 $10$ 点魔法值闪现 $60 {\rm m}$。原地休息时每秒回复 $4$ 点魔法值。 守望者开始有 $M$ 点魔法，需要在 $T$ 秒内逃离距离 $S$。若能逃离则求最短逃离时间，否则求最远距离。 分析 设 $s_1$为一直走路，$s_2$ 为一直闪现恢复。当 $s_2$ 快了就把 $s_1$ 更新为 $s_2$。 int main() { int m = rr(), s = rr(), t = rr(); int time = t, s1 = 0, s2 = 0; while (time > 0 && s1 < s) { s1 += 17; if (m >= 10) m -= 10, s2 += 60; else m += 4; s1 = max(s1, s2); time--; } if (s1 < s) printf("No\n%d\n", s1); else printf("Yes\n%d\n", t - time); return 0; }

题目大意 赢 11 分并且压对手两分以上则一局结束，否则要追分至压对手两分。 给定 $\texttt{WL}$ 序列，分别求 11 分制和 21 分制下每场比分，$\texttt{E}$ 是结束符。 分析 这是一道比较烦的模拟题，很绕。 char ch[62510]; int solve(int win, int len) { int w = 0, l = 0; for (ll i = 0; i < len; i++) { w += ch[i] == 'W'; l += ch[i] == 'L'; if (max(w, l) >= win && abs(w - l) >= 2) { printf("%d:%d\n", w, l); w = l = 0; } } printf("%d:%d\n", w, l); } int main() { char ccc; int len = 0; while (scanf("%c", &ccc) !...

题目大意 凸 $n$ 边形中，任意三条对角线不共点，求所有对角线交点的个数。 分析 注意到一个交点对应凸多边形 $4$ 个定点，于是等价于 $n$ 个点任选 $4$ 个点的选法种数，即 $$ \binom{n}{4} = \frac{n(n-1)(n-2)(n-3)}{24} $$ 注意爆 long long，需要写成 n * (n-1) / 2 * (n-2) / 3 * (n-3) / 4。 int main() { unsigned long long n; scanf("%llu", &n); n = n * (n - 1) / 2 * (n - 2) / 3 * (n - 3) / 4; printf("%llu", n); return 0; }

题目大意 在 $n \times n$ 的方格（$n \leqslant 9$）中存在一些正整数，经过格子时获得格子上的数，但只能获得一次。 某人只能向右或向下走，从格子的左上角走到到右下角，共走两次，求最大能取得的数字。 分析 考虑把先走后走转化为两个人同时走，只需要处理遇到两次的值即可。 考虑四维 DP，用 $dp[x_1,y_1,x_2,y_2]$ 表示第一个人走到 $(x_1,y_1)$ 和第二个人走到 $(x_2,y_2)$。 再考虑转移，每一个位置仅可能从其左面或上面转移来，于是可以写出（$x_1 \ne y_1$ 或 $x_2 \ne y_2$ 时） $$ dp[x_1,y_1,x_2,y_2] = \max\left\{ \begin{matrix} dp[x_1-1,y_1,x_2-1,y_2] \\ dp[x_1,y_1-1,x_2-1,y_2] \\ dp[x_1-1,y_1,x_2,y_2-1] \\ dp[x_1,y_1-1,x_2,y_2-1] \end{matrix}\right\} + a[x_1,y_1] + a[x_2,y_2] $$ 当 $x_1=y_1,x_2=y_2$ 时，只加一次即可。到这里 $O(n^4)$ 其实已经可以过题了，但还可以优化。 注意到一些状态是不可达的，因为 $x_1+y_1 = x_2+y_2$，因此存在 $O(n^3)$ 的 DP。 考虑当前已走长度 $h=x_1+y_1=x_2+y_2$，于是可以把两个人的座标表示为 $(x_1,h-x_1)$ 和 $(x_2,h-x_2)$。 于是记状态为 $dp[h,x_1,x_2]$，当 $x_1 \ne x_2$ 时有 $$ dp[h,x_1,x_2] = \max\left\{ \begin{matrix} dp[h-1,x_1,x_2] \\ dp[h-1,x_1,x_2-1] \\ dp[h-1,x_1-1,x_2] \\ dp[h-1,x_1-1,x_2-1] \end{matrix}\right\} + a[x_1,h-x_1] + a[x_2,h-x_2] $$...