距离上次发帖有8个月了，今天的CSP-S模考难度是-黄青紫黑，咱就是说有黑题是不是有点过分了…
得分0+25+30+0=55
T1 最大内积
题目大意：
给出一个整数 n ，n 个整数 a_1,a_2,...,a_n 和 n 个整数 b_1,b_2,...,b_n
可以反转数组 a 中的一个区间，如：[1, 1, 4, 5, 1, 4, 5, 4, 1, 8, 8] 反转 [0, 4] 得到 [1, 5, 4, 1, 1, 4, 5, 4, 1, 8, 8],使得 \sum_{i=1}^n a_i \cdot b_i 最大。
AC思路：
枚举反转中点，利用双指针维护中点，将时间复杂度降至 O(n^2)。
关键代码部分
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
cin >> b[i];
cnt += a[i] * b[i];
}
ans = cnt;
for (int i = 1; i <= n; i++) {
res = cnt;
for (int l = i - 1, r = i + 1; l >= 1 && r <= n; l--, r++) {
res = res - a[l] * b[l] - a[r] * b[r] + a[l] * b[r] + a[r] * b[l];
ans = max(ans, res);
}
}
for (int i = 1; i <= n; i++) {
res = cnt;
for (int l = i, r = i + 1; l >= 1 && r <= n; l--, r++) {
res = res - a[l] * b[l] - a[r] * b[r] + a[l] * b[r] + a[r] * b[l];
ans = max(ans, res);
}
}
错误原因
将内层循环条件写成l >= 1, r <= n ，应用&&连接，惨痛爆零
T2 外卖之王
题目大意：
外卖员从0出发，将 n 单外卖从各自的起点送至各自的终点，最终走到L，每次只能带1个外卖，但是可以将外卖放在任意一个整数点，求最短的总路程。
AC思路：
赛中很难想到，因为每一单都至少要走从起点到终点的路程，因此只需优化外卖员空手时的路程即可。先计算每一单从起点到终点的路程总和，再将0和所有终点排序，L和起点排序，一一对应计算差值即可。
关键代码部分
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
ans += abs(a[i] - b[i]);
}
a[n+1] = L;
sort(a + 1, a + n + 2);
sort(b + 1, b + n + 2);
for (int i = 1; i <= n + 1; i++) {
ans += abs(a[i] - b[i]);
}
错误原因
思路滑坡
其余见下半部分