A[CF1155A(1000)]
枚举相邻两项，如果存在逆序对则可以。
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; string s; cin >> s; vector<int> p(26, -1); for (int i = 0; i < n; ++i) { for (int j = s[i] - 'a' + 1; j < 26; ++j) { if (p[j] != -1) { cout << "YES" << ' '; cout << p[j] + 1 << ' ' << i + 1 << ' '; exit(0); } } p[s[i] - 'a'] = i; } cout << "NO" << ' '; }
View Code
B[CF1110B(1400)]
如果$K=N$，那么每个点自己覆盖就行。那么$K$每减少$1$，可以看作将相邻的两段合并，也就是增加一个空隙的距离，那么取走$N-K$个最小的空隙即可。
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M, K; cin >> N >> M >> K; vector<int> B(N); for (int i = 0; i < N; ++i) { cin >> B[i]; } int Ans = N; vector<int> S; for (int i = 0; i < N - 1; ++i) { S.push_back(B[i + 1] - B[i] - 1); } sort(S.begin(), S.end()); for (int i = 0; i < N - K; ++i) { Ans += S[i]; } cout << Ans << ' '; }
View Code
C[CF1025D(2100)]
对于二叉搜索树，可以把每个子树理解成一个子问题。于是可以考虑一个区间$dp[l][r][x]$表示这棵子树的根是$x$,$[l,r]$是否能被合并。仔细观察一下，发现之前的根肯定是$l-1$或$r+1$，于是可以把状态变成$dp[l][r][0/1]$表示根是$l-1$还是$r+1$，转移枚举当前子树的根即可，时间复杂度$O(N^3)$。
#pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") #include <bits/stdc++.h> using namespace std; int dp[2][705][705]; int g[705][705]; int main() { int N; cin >> N; vector<int> A(N + 1); for (int i = 0; i < N; ++i) { cin >> A[i]; } for (int i = 0; i <= N; ++i) { for (int j = 0; j <= N; ++j) { g[i][j] = __gcd(A[i], A[j]); } } for (int i = 0; i < N; ++i) { if (g[i + 1][i] >= 2) { dp[1][i][i] = 1; } if (i >= 1 && g[i - 1][i] >= 2) { dp[0][i][i] = 1; } } for (int L = 2; L <= N; ++L) { for (int i = 0; i + L - 1 < N; ++i) { int j = i + L - 1; for (int l = 0; l < 2; ++l) { for (int k = i; k <= j; ++k) { if (g[k][(l == 0 ? i - 1 : j + 1)] >= 2) { dp[l][i][j] |= ((k > i ? dp[1][i][k - 1] : 1) & (k < j ? dp[0][k + 1][j] : 1)); if (dp[l][i][j]) { break; } } } } } } if (dp[1][0][N - 1]) { cout << "Yes" << ' '; } else { cout << "No" << ' '; } }
View Code
D[CF1473E(2400)]
直接跑最短路比较困难，这里可以考虑一个类似「松弛」的操作，对于减$max$和加$min$变成选任意一条边减去和任意一条边加上。那么这样可以重新设计这张图，$dp[x][0/1][0/1]$表示到$x$点是否选了减去的和加上的，类似分层图，跑最短路即可，最终结果就是答案。最短路会在过程中自动地选上路径的最小边和最大边。
#include <bits/stdc++.h> using namespace std; const long long inf = 1000000000000000000; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<vector<pair<int, int> > > G(n); for (int i = 0; i < m; ++i) { int x, y, w; cin >> x >> y >> w; x --; y --; G[x].emplace_back(y, w); G[y].emplace_back(x, w); } vector<vector<long long> > d(n, vector<long long> (4, inf)); d[0][0] = 0; priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>> , greater<tuple<long long, int, int> > > q; q.emplace(0, 0, 0); while (!q.empty()) { auto [cur, x, s] = q.top(); q.pop(); if (cur > d[x][s]) { continue; } for (auto [y, w] : G[x]) { if (d[y][s] > d[x][s] + w) { d[y][s] = d[x][s] + w; q.emplace(d[y][s], y, s); } if (!(s & 1)) { if (d[y][s ^ 1] > d[x][s] + w + w) { d[y][s ^ 1] = d[x][s] + w + w; q.emplace(d[y][s ^ 1], y, s ^ 1); } } if (!(s & 2)) { if (d[y][s ^ 2] > d[x][s]) { d[y][s ^ 2] = d[x][s]; q.emplace(d[y][s ^ 2], y, s ^ 2); } } if (s == 0) { if (d[y][3] > d[x][s] + w) { d[y][3] = d[x][s] + w; q.emplace(d[y][3], y, 3); } } } } for (int i = 1; i < n; ++i) { cout << d[i][3] << " "[i == n - 1]; } return 0; }
View Code
最后两个题难度比较大，不过涉及的套路比较有用，代码难度不大，可以学习一下。