比赛链接
比赛时的状态 be like:
- 我靠，这题怎么这么难？T1 就开始上难度了？
- 没一道题会写，不会要爆零然后遗憾离场了吧？
- （想了 2147483647 种 T1 的假做法）
- （去体检，在测血压时）等会，我好像想明白 T1 的本质了……
- （回机房）秒切 T1！
- 开 T2！也不难，想一想就会了！
- 看来这场比赛也就那样嘛！向着 T3 进发！
- 不是哥们这是什么东西啊……
- 6 点，遗憾离场。
可以说是大起大落了。不过还好，最后拿到了最近久违的两个 AC。
T1
可以想到，假如一个子串（可以为空）两边的字符相同，那么翻转这个子串，或者翻转带上两边字符的子串，得到的字符串完全相同。
进一步思考，加入我们有一个字符串形如 a#*&a~-^a （a 中间的是任意的字符），那么 a#*&a、a-^a 和 a#*&a~-^a 就会被重复计算。归纳可得，设字符串中某个字符出现了 \(n\) 次，那么重复计算的次数就是 \(\frac{(1 + n) n}{2}\) ——对于每个字母都是同理的。
所以，我们统计每个字母的出现次数（别忘了英文字母有 \(26\) 个啊喂——不然小心 10 pts），然后设字符串长度为 \(l\)，那么最终答案就是 \(\frac{(1+n)n}{2} + \sum_{i = 1}^{26}\frac{(1+n_i)n_i}{2}\)。
#include <bits/stdc++.h>
#define int long long
typedef long long ll;
const int N = 1e5+10;
ll ans;
std::string str;
int times[30];signed main() {freopen("spring.in", "r", stdin);freopen("spring.out", "w", stdout);std::cin >> str;int n = str.size();str = " " + str;for (int i = 1; i <= n; i++) {times[str[i] - 'a' + 1]++;}ans = (1 + n) * n / 2;for (int i = 1; i <= 26; i++) {ans -= (1 + times[i]) * times[i] / 2;}std::cout << ans + 1 << '\n';return 0;
}
T2
首先，如果 \(a_1\) 被修改，那么就无可救药了，因为根据规则，显然 \(a_1\) 必须为 \(0\)。此外，如果 \(a_i\) 被修改，那么下标为 \(i\) 的因数和倍数的地方要受牵连。进一步分析可得，\(i\) 的最大的质因数的所有倍数都要被修改（\(i\) 本身除外）。可以用试除法对 \(i\) 分解质因数，时间复杂度 \(O(\sqrt{n})\)。
#include <bits/stdc++.h>
typedef long long ll;
const int N = 1e5+10;
int n, q;int getMaxFactor(int x) {int ans = 0;for (int i = 2; i <= std::sqrt(x); i++) {while (x % i == 0) {ans = std::max(ans, i);x /= i;}}if (x > 1) {ans = std::max(ans, x);}return ans;
}signed main() {freopen("summer.in", "r", stdin);freopen("summer.out", "w", stdout);std::cin >> n >> q; while (q--) {int x;std::cin >> x;if (x == 1) {std::cout << "-1\n";continue;}int maxFactor = getMaxFactor(x);int ans = n / maxFactor - 1;std::cout << ans << '\n';}return 0;
}
T3
这题正解太难了，这里只讨论可以得 50 pts 的反悔贪心做法。（aoao 太强了！）
设处理第 \(i\) 个位置的糖果需要的费用为 \(V_i\)，分多、少两种情况讨论：
- 若少了，既可以花 \(X\) 费用解决，即 \(V_i = X\)，还可以向前面位置为 \(j\) 处要糖果，花费 \(Z|i-j|\) 费用，并且还要把之前的糖的贡献减去，总费用为 \(Z|i-j|-V_j\)，所以 \(V_i = \min(X, Z|i-j|-V_j)\)。
- 若多了，同理，\(V_i = \min(Y, Z|i-j|-V_j)\)。
此时时间复杂度是 \(O(n^2)\)，但对于拿 50 分显然还不够，考虑优化。
我们可以拆贡献：
可见，要让 \(V_i\) 最小，我们需要让 \((-jZ - V_j)\) 最小。
可以开两个小根堆，一个存本来少了糖的单位糖的 \((-jZ-V_j)\)，可以用来更新现在糖果多了的地方；另一个存本来多了单位糖的 \((-jZ-V_j)\)，可以用来更新现在多了糖果的地方。得到处理当前糖果的费用后把 \((-iZ-V_i)\) 存进堆里，供后面的答案更新。
时间复杂度为 \(O(n\log n)\)。
以上内容基本贺自洛谷题解。
#include <bits/stdc++.h>
typedef long long ll;
const int N = 5e5+10;
int n, x, y, z, a[N], b[N];
std::priority_queue<ll, std::vector<ll>, std::greater<ll> > more, less;
ll v[N], ans;signed main() {freopen("autumn.in", "r", stdin);freopen("autumn.out", "w", stdout);std::ios::sync_with_stdio(false);std::cin >> n >> x >> y >> z;for (int i = 1; i <= n; i++) {std::cin >> a[i] >> b[i];for (int j = 1; j <= a[i] - b[i]; j++) {v[i] = y;if (!more.empty()) {v[i] = std::min(v[i], i * z + more.top());more.pop();}less.push(-v[i] - i * z);ans += v[i];}for (int j = 1; j <= b[i] - a[i]; j++) {v[i] = x;if (!less.empty()) {v[i] = std::min(v[i], i * z + less.top());less.pop();}more.push(-v[i] - i * z);ans += v[i];}}std::cout << ans << '\n';return 0;
}
总结
这次考试最大的经验就是没有被看似困难的题面打倒，而是沉住心分析问题的本质。如果我上周六能有这样的态度，就肯定不会 T2 空着了。
当然，比较高级的东西还要多学，争取拿更多分！