比赛链接
本文发布于博客园，会跟随补题进度实时更新，若您在其他平台阅读到此文，请前往博客园获取更好的阅读体验。
跳转链接：https://www.cnblogs.com/TianTianChaoFangDe/p/18869039
开题 + 补题情况
最近一直在准备期中考试，好久没写代码了，这场有点糖，前一个小时一题没开，实属红温，尤其是 1007，想了好久好久。
下周打南昌，自己第一次参加全国性的比赛，希望自己加油发挥吧！
1010 - 绳子切割
此题考查并查集（实际暴力也可以）。
我们删点是从大到小删，那么倒过来就是加点，加点就是从小到大加。
对于每一个点，连向比它小的结点的连通块，看是否能和 (0) 在同一块，如果不在，那么直接输出 (0)，因为这个时候，它不和横梁同属一个连通块，说明它到 (0) 之间有点被删除了，进而导致该点被提前删除了。
点击查看代码
#include <bits/stdc++.h> #define inf32 1e9 #define inf64 2e18 #define ls o << 1 #define rs o << 1 | 1 using i64 = long long; using u64 = unsigned long long; using u32 = unsigned int; const int N = 2e5 + 9; struct DSU { std::vector<int> fa; DSU(int n) { fa.resize(n + 1); std::iota(fa.begin(), fa.end(), 0); } int root(int x) { return (fa[x] == x) ? x : (fa[x] = root(fa[x])); } void merge(int u, int v) { if(root(u) == 0) { fa[root(v)] = root(fa[u]); } else { fa[root(u)] = root(fa[v]); } } }; void solve() { int n, m;std::cin >> n >> m; DSU dsu(n); std::vector<std::vector<int>> g(n + 1); for(int i = 1;i <= m;i ++) { int u, v;std::cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } for(int i = 1;i <= n;i ++) { for(auto &x : g[i]) { if(i < x)continue; dsu.merge(i, x); } if(dsu.root(i) != 0) { std::cout << 0 << 'n'; return; } } std::cout << 1 << 'n'; } int main() { std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0); int t = 1;std::cin >> t; while(t --)solve(); return 0; } 1004 - 储值购物
这个题，先上结论，每次取 (W / 2 + 1)，一定最优。
简单证明如下：
若某次取了 (leq W / 2)，那么这次剩下的，一定 (geq W / 2)，那么，当下次取 (W / 2) 的时候，会继续使用当前这个卡，若取更多，则可以均摊给上次取的，这样的话最后二者都会取到 (W / 2 + 1)。
因此，每次取 (W / 2 + 1)，当取不够了的时候，判断是新加一张卡还是使用现有的。
点击查看代码
#include <bits/stdc++.h> #define inf32 1e9 #define inf64 2e18 #define ls o << 1 #define rs o << 1 | 1 using i64 = long long; using u64 = unsigned long long; using u32 = unsigned int; const int N = 2e5 + 9; template<typename T> T up(T x, T y) { return (x + y - 1) / y; } void solve() { int v, w;std::cin >> v >> w; int h = w / 2 + 1; int l = w - h; int sum = v / h; v -= sum * h; int ans = 0; if(sum) { if(v > l)ans = sum + 1; else ans = sum; } else { ans = 1; } std::cout << ans << 'n'; } int main() { std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0); int t = 1;std::cin >> t; while(t --)solve(); return 0; } 1005 - 真爱口上
这个题看似是一个非常恶心的模拟题，但是题目有一个很重要的信息：所有的字符串都是符合规则的音节序列。也就意味着我们不需要判断串的合法性，只需要根据特征计数就行了。
- 基本音节结构：不难发现，一定是以元音结尾，因此只需要计算元音有多少个即可。
- 鼻音：单算
nn相连的情况，特别注意比如nnna的情况，此时不能算为两个鼻音。 - 促音：计算
ppttkkss的数量即可。
点击查看代码
#include <bits/stdc++.h> #define inf32 1e9 #define inf64 2e18 #define ls o << 1 #define rs o << 1 | 1 using i64 = long long; using u64 = unsigned long long; using u32 = unsigned int; const int N = 2e5 + 9; bool isyun(char c) { return c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o'; } bool isptks(char c) { return c == 'p' || c == 't' || c == 'k' || c == 's'; } int getans(std::string &s) { int n = s.size(); int res = 0; int pre = -1; for(int i = 0;i < n;i ++) { if(isyun(s[i])) { res ++; } if(isptks(s[i])) { if(i - 1 >= 0 && s[i - 1] == s[i]) { res ++; } } if(s[i] == 'n') { if(i - 1 >= 0 && s[i - 1] == s[i] && pre != i - 1) { res ++; pre = i; } } } return res; } void solve() { std::string s, t;std::cin >> s >> t; std::cout << getans(s) << ' ' << getans(t) << 'n'; } int main() { std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0); int t = 1;std::cin >> t; while(t --)solve(); return 0; } 1007 - 扑克洗牌
你没有看错，这是我过的……第四个题……
真的红温了，这题一直没想到思路，但是过的人又那么多，后面猛地想到了。
首先要明晰一件事，对于移动了的牌，它一定是移动且仅移动一次！
为什么？
因为我们可以把它插入任何位置，那么我们就可以直接把它插入到应该处在的位置，并且不要去动它。
然后呢，我们就要考虑，对于目标序列，我们要如何移动得到。
对于原串，所有数字都是连续的，相邻的。
对于移动，是只能从两头进行移动的。
那么就可以得出以下结论：我们最终的目标串，一定是原串某个连续子串，插入两边的扑克牌得到的。
对于原串中的这个子串，它是不需要移动的，因为它是被插入的对象。
所以要让移动次数最小，那么就是要让选择的这个原串子串长度，尽可能的大。
这个长度，我们用简单的 dp 可以很快计算出来。
记 (dp_i) 为以数字 (i) 结尾的最长连续子序列的长度。
那么有以下转移：
- 当 (i - 1) 没有出现过时，(dp_i = 1)。
- 当 (i - 1) 出现过时，(dp_i = dp_{i - 1} + 1)。
对每个 (dp_i) 执行 (n - dp_i)，对所有答案取最小值即可。
点击查看代码
#include <bits/stdc++.h> #define inf32 1e9 #define inf64 2e18 #define ls o << 1 #define rs o << 1 | 1 using i64 = long long; using u64 = unsigned long long; using u32 = unsigned int; const int N = 2e5 + 9; void solve() { int n;std::cin >> n; std::vector<int> a(n + 1); std::vector<int> vis(n + 1); std::vector<int> dp(n + 1); for(int i = 1;i <= n;i ++) { std::cin >> a[i]; } vis[0] = true; for(int i = 1;i <= n;i ++) { if(vis[a[i] - 1]) { dp[a[i]] = dp[a[i] - 1] + 1; } else { dp[a[i]] = 1; } vis[a[i]] = true; } int ans = inf32; for(int i = 1;i <= n;i ++) { ans = std::min(ans, n - dp[i]); } std::cout << ans << 'n'; } int main() { std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0); int t = 1;std::cin >> t; while(t --)solve(); return 0; } 1002 - 折线绘制
马拉车算法板子题，只不过从回文关系变成了中心对称关系。
为了方便计数，可以插入无关数字 (-1) 来把奇数长度区间和偶数长度区间的情况统一化。
点击查看代码
#include <bits/stdc++.h> #define inf32 1e9 #define inf64 2e18 #define int long long #define ls o << 1 #define rs o << 1 | 1 using i64 = long long; using u64 = unsigned long long; using u32 = unsigned int; const int N = 2e5 + 9; void solve() { int n;std::cin >> n; std::vector<int> a(n); for(auto &x : a) { std::cin >> x; } std::vector<int> b(2 * n + 1); int idx = 0; b[idx ++] = -1; for(auto &x : a) { b[idx ++] = x; b[idx ++] = -1; } n = (int)b.size(); std::vector<int> d(n); auto check = [&](int x, int y, int sum) -> bool { if(x < 0 || y >= n) { return false; } if(b[x] == -1 && b[y] == -1) { return true; } if(b[x] + b[y] == sum) { return true; } return false; }; int ans = 0; for(int i = 0, l = 0, r = -1;i < n;i ++) { int k = ((i > r) ? 1 : std::min(r - i + 1, d[l + r - i])); int now = -1; if(b[i] == -1 && i - 1 >= 0 && i + 1 < n) { now = b[i - 1] + b[i + 1]; } if(b[i] != -1) { now = b[i] * 2; } while(check(i - k, i + k, now)) { k ++; } d[i] = k --; if(i + k > r)l = i - k, r = i + k; if(b[i] == -1) { ans += k / 2; } else { ans += d[i] / 2; } } std::cout << ans << 'n'; } signed main() { std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0); int t = 1;std::cin >> t; while(t --)solve(); return 0; } 
![洛谷 P11345 [KTSC 2023 R2] 基地简化 题解](http://www.itfaba.com/wp-content/themes/kemi/timthumb.php?src=http://www.itfaba.com/wp-content/themes/kemi/img/random/1.jpg&w=218&h=124&zc=1)
