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;
}
