【比赛链接】
点击打开链接【题解链接】
点击打开链接【C】K-th Substring
【思路要点】
注意到\(K\)很小，我们考虑每次找到该字符串最小的子串，并在后续的过程中不再考虑该子串。对于以\(i\)号字符开头的子串\(S_{i,i}\)，\(S_{i,i+1}\)，\(S_{i,i+2}\)……，显然有\(S_{i,i}<S_{i,i+1},S_{i,i+2}<……\)。因此，在每一轮中，我们只需要考虑以每个位置开头的，尚未被找到过的最短的子串。在这些子串中暴力找到字典序最小的即可。时间复杂度\(O(min\{K^2N,KN^2\})\)。【代码】
#include<bits/stdc++.h> using namespace std; const int MAXN = 100005; template <typename T> void chkmax(T &x, T y) {x = max(x, y); } template <typename T> void chkmin(T &x, T y) {x = min(x, y); } template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void writeln(T x) { write(x); puts(""); } char s[MAXN]; int n, k, now[MAXN]; bool better(int a, int lena, int b, int lenb) { if (lena == -1) return false; if (lenb == -1) return true; int len = min(lena, lenb); for (int i = 1; i <= len; i++) { if (s[a + i - 1] < s[b + i - 1]) return true; if (s[a + i - 1] > s[b + i - 1]) return false; } return lena < lenb; } bool equal(int a, int b, int len) { for (int i = 1; i <= len; i++) if (s[a + i - 1] != s[b + i - 1]) return false; return true; } int main() { scanf("%s", s + 1); n = strlen(s + 1); read(k); for (int i = 1; i <= n; i++) now[i] = 1; while (true) { int pos = 0, len = -1; for (int i = 1; i <= n; i++) if (better(i, now[i], pos, len)) pos = i, len = now[i]; for (int i = 1; i <= n; i++) if (len == now[i] && equal(pos, i, len)) { now[i]++; if (i + now[i] - 1 > n) now[i] = -1; } if (--k == 0) { for (int i = 1; i <= len; i++) printf("%c", s[pos + i - 1]); printf("\n"); return 0; } } return 0; }【D】Equals
【思路要点】
显然每一个联通块内部\(p_i\)的位置是可以任意排布的。计算每个联通块内\(p_i\)和\(i\)的出现集合，求解所有联通块中两个集合的交集大小的和即为答案。时间复杂度\(O(NLogN)\)。【代码】
#include<bits/stdc++.h> using namespace std; const int MAXN = 100005; template <typename T> void chkmax(T &x, T y) {x = max(x, y); } template <typename T> void chkmin(T &x, T y) {x = min(x, y); } template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void writeln(T x) { write(x); puts(""); } set <int> st[MAXN]; int n, m, p[MAXN], f[MAXN]; int F(int x) { if (f[x] == x) return x; else return f[x] = F(f[x]); } int main() { read(n), read(m); for (int i = 1; i <= n; i++) read(p[i]), f[i] = i; for (int i = 1; i <= m; i++) { int x, y; read(x), read(y); f[F(x)] = F(y); } for (int i = 1; i <= n; i++) st[F(i)].insert(p[i]); int ans = 0; for (int i = 1; i <= n; i++) ans += st[F(i)].count(i); writeln(ans); return 0; }【E】Sorted and Sorted
【思路要点】
首先考虑只有一种颜色的球的情况，我们发现在最优方案中每交换一次逆序对的数量就会减一，因此答案即为排列的逆序数。回到有两种颜色球的情况，我们可以将问题转化成：我们现在要给两种颜色的球确定一种大小关系，要求同种颜色的球数值较小的较小，不同种颜色的球没有额外的限制，要最小化给定排列的逆序数。可以用动态规划解决：记\(dp_{i,j}\)表示已经使用了\(i\)以内的黑球和\(j\)以内的白球，不同种类的球之间产生的逆序数的最小值。那么\(dp_{i,j}=min\{dp_{i-1,j}+fb_{i,j},dp_{i,j-1}+fw_{j,i}\}\)。其中\(fb_{i,j}\)表示在\(i\)号黑球后出现的\(j\)以内白球的数量，\(fw_{i,j}\)表示在\(i\)号白球后出现的\(j\)以内黑球的数量。预处理\(fb\)和\(fw\)，时间复杂度\(O(N^2)\)。【代码】
#include<bits/stdc++.h> using namespace std; const int MAXN = 2005; const int INF = 1e9; template <typename T> void chkmax(T &x, T y) {x = max(x, y); } template <typename T> void chkmin(T &x, T y) {x = min(x, y); } template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void writeln(T x) { write(x); puts(""); } int n, a[MAXN * 2]; int fb[MAXN][MAXN], fw[MAXN][MAXN], dp[MAXN][MAXN]; char type[MAXN * 2]; int main() { read(n); int tans = 0; for (int i = 1; i <= 2 * n; i++) { char opt = getchar(); while (opt != 'B' && opt != 'W') opt = getchar(); type[i] = opt; read(a[i]); for (int j = 1; j <= i - 1; j++) tans += type[i] == type[j] && a[i] < a[j]; } static bool eb[MAXN], ew[MAXN]; for (int i = 2 * n; i >= 1; i--) { if (type[i] == 'B') { for (int j = 1; j <= n; j++) fb[a[i]][j] = fb[a[i]][j - 1] + ew[j]; } else { for (int j = 1; j <= n; j++) fw[a[i]][j] = fw[a[i]][j - 1] + eb[j]; } if (type[i] == 'B') eb[a[i]] = true; else ew[a[i]] = true; } for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) { if (i == 0 && j == 0) dp[i][j] = 0; else dp[i][j] = INF; if (i != 0) chkmin(dp[i][j], dp[i - 1][j] + fb[i][j]); if (j != 0) chkmin(dp[i][j], dp[i][j - 1] + fw[j][i]); } writeln(dp[n][n] + tans); return 0; }【F】Monochrome Cat
【思路要点】
若原树中存在一个黑色的叶子，那么我们可以将其删去而不影响答案。重复这个过程，我们会得到一棵仅包含白色叶子的树，显然，这棵树中所有的节点都会被访问至少一次。対该树进行树形DP，记：\(dp_{i,0}\)表示从\(i\)号点的父亲出发，完成对\(i\)子树的访问后回到\(i\)号点的父亲的最小用时。\(dp_{i,1}\)表示从\(i\)号点的父亲出发，完成对\(i\)子树的访问后停在\(i\)号点的子树内部的最小用时。\(dp_{i,2}\)表示从\(i\)号点出发，完成对\(i\)号点父亲所在的\(i\)号点的子树的访问后回到\(i\)号点的最小用时。获取答案时枚举路径两端的LCA，通过上述DP结果更新答案。时间复杂度\(O(N)\)。【代码】
#include<bits/stdc++.h> using namespace std; const int MAXN = 100005; const long long INF = 1e18; template <typename T> void chkmax(T &x, T y) {x = max(x, y); } template <typename T> void chkmin(T &x, T y) {x = min(x, y); } template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void writeln(T x) { write(x); puts(""); } vector <int> a[MAXN], b[MAXN]; int n, d[MAXN]; char col[MAXN]; long long dp[MAXN][3], ans; bool vis[MAXN]; void work(int pos, int fa) { for (unsigned i = 0; i < a[pos].size(); i++) if (fa != a[pos][i] && !vis[a[pos][i]]) work(a[pos][i], pos); bool now = col[pos] == 'B'; long long tans = 2; for (unsigned i = 0; i < a[pos].size(); i++) if (fa != a[pos][i] && !vis[a[pos][i]]) { tans += dp[a[pos][i]][0]; now ^= true; } dp[pos][0] = tans + now; dp[pos][1] = tans + now - 1; for (unsigned i = 0; i < a[pos].size(); i++) if (fa != a[pos][i] && !vis[a[pos][i]]) { chkmin(dp[pos][1], tans + !now - 1 - dp[a[pos][i]][0] + dp[a[pos][i]][1]); } } void getans(int pos, int fa) { if (fa == 0) { bool now = col[pos] == 'W'; int cnt = 0; long long tans = 0; for (unsigned i = 0; i < a[pos].size(); i++) if (fa != a[pos][i] && !vis[a[pos][i]]) { tans += dp[a[pos][i]][0]; now ^= true; cnt++; } for (unsigned i = 0; i < a[pos].size(); i++) if (fa != a[pos][i] && !vis[a[pos][i]]) { dp[a[pos][i]][2] = dp[pos][0] - dp[a[pos][i]][0] - !now + now; getans(a[pos][i], pos); } if (cnt == 1) { for (unsigned i = 0; i < a[pos].size(); i++) if (fa != a[pos][i] && !vis[a[pos][i]]) { chkmin(ans, dp[a[pos][i]][1] + 1); return; } } chkmin(ans, tans + now); long long Max = -1e18, Nax = -1e18; for (unsigned i = 0; i < a[pos].size(); i++) if (fa != a[pos][i] && !vis[a[pos][i]]) { long long tmp = dp[a[pos][i]][0] - dp[a[pos][i]][1]; if (tmp > Max) { Nax = Max; Max = tmp; } else chkmax(Nax, tmp); } chkmin(ans, 1 + tans + !now - Max - Nax); } else { for (unsigned i = 0; i < a[pos].size(); i++) if (fa != a[pos][i] && !vis[a[pos][i]]) { dp[a[pos][i]][2] = dp[pos][0] - dp[a[pos][i]][0] + dp[pos][2]; getans(a[pos][i], pos); } bool now = col[pos] == 'B'; long long tans = dp[pos][2]; for (unsigned i = 0; i < a[pos].size(); i++) if (fa != a[pos][i] && !vis[a[pos][i]]) { tans += dp[a[pos][i]][0]; now ^= true; } chkmin(ans, tans + now); long long Max = -1e18, Nax = -1e18; for (unsigned i = 0; i < a[pos].size(); i++) if (fa != a[pos][i] && !vis[a[pos][i]]) { long long tmp = dp[a[pos][i]][0] - dp[a[pos][i]][1]; if (tmp > Max) { Nax = Max; Max = tmp; } else chkmax(Nax, tmp); } chkmin(ans, 1 + tans + !now - Max - Nax); } } int main() { read(n); for (int i = 1; i <= n - 1; i++) { int x, y; read(x), read(y); d[x]++, d[y]++; a[x].push_back(y); a[y].push_back(x); } scanf("%s", col + 1); static int q[MAXN]; int l = 0, r = -1; for (int i = 1; i <= n; i++) if (d[i] <= 1) q[++r] = i; while (l <= r) { int tmp = q[l++]; if (col[tmp] == 'B') { vis[tmp] = true; for (unsigned i = 0; i < a[tmp].size(); i++) if (--d[a[tmp][i]] == 1) q[++r] = a[tmp][i]; } } for (int i = 1; i <= n; i++) if (!vis[i]) { work(i, 0); ans = INF; getans(i, 0); writeln(ans); return 0; } printf("0\n"); return 0; }