比赛链接
本文发布于博客园，会跟随补题进度实时更新，若您在其他平台阅读到此文，请前往博客园获取更好的阅读体验。
跳转链接：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 | 1using 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 | 1using 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 | 1using 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 | 1using 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 | 1using 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;}