A. Is It a Cat?
去重， 把所有字符看成大写字符， 然后去重， 观察最后结果是不是“MEOW”
#include <bits/stdc++.h>
#define int long longvoid solve() {int n;std::cin >> n;std::string ans, t;std::cin >> ans;for (int i = 0; i < n; i++) {if(ans[i] >= 'a') ans[i] = ans[i] - 'a' + 'A';if(t.size() == 0) {t += ans[i];}else {if(ans[i] != t.back()) t += ans[i]; }}if(t == "MEOW") {std::cout << "YES\n";}else{std::cout << "NO\n";}
}signed main() {int t = 1;std::cin >> t;while(t--) solve();return 0;
}
B. Count the Number of Pairs
统计每一个字符， 计算可以贡献多少。计算t（最多可以操作几次）
取min(k, t) 即可
#include <bits/stdc++.h>
#define int long longvoid solve() {int n, k;std::cin >> n >> k;std::string s;std::cin >> s;std::map<char, int> mp;for (auto x : s) mp[x]++;int ans = 0, t = 0;for (char i = 'A'; i <= 'Z'; i++) {char ch = i - 'A' + 'a';ans += std::min(mp[i], mp[ch]);int x = abs(mp[i] - mp[ch]);t += x / 2;}std::cout << ans + std::min(t, k) << '\n';
}signed main() {int t = 1;std::cin >> t;while(t--) solve();return 0;
}
C2. Powering the Hero (hard version)
简单的优先队列
#include <bits/stdc++.h>
#define int long longvoid solve() {int n;std::cin >> n;std::priority_queue<int, std::vector<int>, std::less<int>> pq;int ans = 0;for (int i = 0; i < n; i++) {int x;std::cin >> x;if(x == 0) {if(pq.size()) {ans += pq.top();pq.pop();}}else pq.push(x);}std::cout << ans << '\n';
}signed main() {int t = 1;std::cin >> t;while(t--) solve();return 0;
}
D. Remove Two Letters
通过观察可以发现， 如果s[i]s[i + 1] == s[i + 1][i + 2] || s[i]s[i + 1] == s[i + 2]s[i + 1] 时， 这两种操作的结果时相同的， 遍历模拟即可
#include <bits/stdc++.h>
#define int long longvoid solve() {int n;std::cin >> n;std::string s;std::cin >> s;int ans = 0;std::string t = "";for (int i = 0; i < n - 1; i++) {std::string x = t;reverse(x.begin(), x.end());if(s.substr(i, 2) != t && s.substr(i, 2) != x) {ans++;t = s.substr(i, 2);}}std::cout << ans << '\n';
}signed main() {int t = 1;std::cin >> t;while(t--) solve();return 0;
}
E2. Unforgivable Curse (hard version)
通过理解题意， 发现可以找出所有可以相互交换的下标，归为一组，可以通过并查集。然后统计每一组s 和 t 的这些下标组成的字符种类和个数是否相同， 如果不同直接输出"NO"， 具体实现见代码
#include <bits/stdc++.h>
#define int long long
int p[200010];
int find(int x) {if(p[x] != x) p[x] = find(p[x]);return p[x];
}void solve() {int n, k;std::cin >> n >> k;std::string s, t;std::cin >> s >> t;for (int i = 0; i < n; i++) p[i] = i;for (int i = 0; i < n; i++) {if(i + k >= n) break;p[find(i)] = find(i + k);if(i + k + 1 < n) p[find(i)] = find(i + k + 1); }std::map<int, std::vector<int>> mp;for (int i = 0; i < n; i++) {mp[find(i)].push_back(i);}// std::cout << mp.size() << '\n';for (auto& [k, arr] : mp) {std::vector<int> cnt(26);for (auto& x : arr) {cnt[s[x] - 'a']++;cnt[t[x] - 'a']--;}for (int i = 0; i < 26; i++) {if(cnt[i]) {std::cout << "NO\n";return;}}}std::cout << "YES\n";
}signed main() {int t = 1;std::cin >> t;while(t--) solve();return 0;
}
F. Dasha and Nightmares
类似于前缀和， 状态压缩一下。具体看代码
很容易超时，所以不能使用map,
#include <bits/stdc++.h>
#define int long longstruct custom_hash {static uint64_t splitmix64(uint64_t x) {x += 0x9e3779b97f4a7c15;x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;x = (x ^ (x >> 27)) * 0x94d049bb133111eb;return x ^ (x >> 31);}size_t operator()(uint64_t x) const {static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();return splitmix64(x + FIXED_RANDOM);}
};void solve() {std::vector<int> target(26);for (int i = 0; i < 26; i++) {target[i] = ((1 << 26) - 1) ^ (1 << i);}int n;std::cin >> n;int ans = 0;std::unordered_map<int, int, custom_hash> mp[26];for (int i = 0; i < n; i++) {int mask = 0;std::string s;std::cin >> s;std::vector<int> cnt(26);for (auto x : s) {cnt[x - 'a']++;}for (int i = 0; i < 26; i++) {if(cnt[i] & 1) {mask |= (1 << i);}}for (int i = 0; i < 26; i++) {if(cnt[i] == 0 && mp[i].count(target[i] ^ mask)) {ans += mp[i][target[i] ^ mask];}}for (int i = 0; i < 26; i++) {if (cnt[i] == 0) {mp[i][mask]++;}}}std::cout << ans << '\n';
}signed main() {int t = 1;// std::cin >> t;while(t--) solve();return 0;
}
