Codeforces Round 855 (Div. 3)（A~F）

A. Is It a Cat?

定义满足条件的字符串为：其中仅可能含有meow四种字母的大小写，而且相同种类的字母必须挨在一起，四种字母的顺序必须按照meow排列。给出一个字母串，求是否满足条件。

思路：感觉是个很麻烦的模拟。首先把大小写全都转为小写字母，再把相同的字母合并，最后判断一下字母的种类和顺序。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 1e6 + 5;
int t, n;
std::string s;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> t;while(t --) {std::cin >> n >> s;std::vector<char> vec;char c;if(s[0] >= 'A' && s[0] <= 'Z')vec.push_back((char)(s[0] - 'A' + 'a')), c = (char)(s[0] - 'A' + 'a');elsevec.push_back(s[0]), c = s[0];for(int i = 1; i < n; i ++) {if(s[i] >= 'A' && s[i] <= 'Z')s[i] = (char)(s[i] - 'A' + 'a');if(s[i] != c)vec.push_back(s[i]), c = s[i];}if(vec.size() == 4 && vec[0] == 'm' && vec[1] == 'e' && vec[2] == 'o' && vec[3] == 'w')std::cout << "YES" << '\n';elsestd::cout << "NO" << '\n';}return 0;
}

B. Count the Number of Pairs

给出一个字符串，对于同一种字母，一个大写一个小写可以凑成一对；给出k次操作，可以将任意一个字母大小写翻转，问给出的字符串中最多可以有多少对字母。

思路：统计字符串中大小写字母的个数，先统计不经过修改可以得到多少串，然后拥挤通过修改可以最多得到多少对即可。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 1e6 + 5;
int t, n, k;
std::string s;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> t;while(t --) {std::cin >> n >> k >> s;int ans = 0;std::unordered_map<char, int> mpl, mpu;for(int i = 0; i < n; i ++) {if(s[i] >= 'a' && s[i] <= 'z')mpl[s[i]] ++;elsempu[s[i]] ++;}for(auto [x, y] : mpl) {if(y && mpu[x - 'a' + 'A']) {ans += std::min(y, mpu[x - 'a' + 'A']);mpl[x] -= std::min(y, mpu[x - 'a' + 'A']);mpu[x - 'a' + 'A'] -= y, mpu[x - 'a' + 'A'];}}for(auto [x, y] : mpl) {if(y >= 2) {int res = std::min(k, y / 2);ans += res, k -= res, y -= res * 2;}}for(auto [x, y] : mpu) {if(y >= 2) {int res = std::min(k, y / 2);y -= res * 2, ans += res, k -= res;}}std::cout << ans << '\n';}return 0;
}

C. Powering the Hero

给出一个数组，其中非0的数字可以被存下来，放在一堆中；为0的数可以加上现有的非0数中的一个数。求所有的为0的值，通过修改得到的和最大是多少。

思路：优先队列即可，每次遇到一个非0的数，就将其放进队列中，遇到为0的数就取出队列中最大的数加入答案，并pop出队列，easy版本做法与hard版本相同，时间复杂度O(nlogn)，能过。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 1e6 + 5;
int t, n;
ll a[N];int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> t;while(t --) {std::cin >> n;std::priority_queue<ll> pq;ll ans = 0;for(int i = 1; i <= n; i ++) {std::cin >> a[i];if(a[i])pq.push(a[i]);if(!a[i] && !pq.empty()) {ans += pq.top();pq.pop();}}std::cout << ans << '\n';}return 0;
}

D. Remove Two Letters

在字符串中去掉任意两个相连的字母，剩下的串相连，求可以得到多少种不同的字符串。

思路：一开始想hash，但是又不太会hash，又感觉hash很容易被卡。可以这样考虑，从头开始，每次向后转移去掉的两个字母，就是加上上一对字母的前一个，去掉后一对字母的后一个，那直接比较这两个字母即可，只要不同，就对答案有贡献。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 1e6 + 5;
int t, n;
std::string s;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> t;while(t --) {std::cin >> n >> s;int ans = 0;for(int i = 1; i < n - 1; i ++) {if(s[i - 1] != s[i + 1]) {ans ++;}}std::cout << ans + 1 << '\n';}return 0;
}

E. Unforgivable Curse

给出两个字符串s和t，目标是把s修改为t，每次修改可以交换相距k或k+1位置的字母，问是否能修改成功。

思路：很显然，如果某个字符需要修改，但是它距离左右边界的距离都小于k，那必然没法修改。对于其他的位置，我们一定可以找到两个位置互换的方法，即可以通过中间字符修改，而顺着修改的顺序逆着回去，可以复原原来在正确位置的字母。easy版本与hard版本相同。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 1e6 + 5;
int T, n, k;
std::string s, t;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> T;while(T --) {std::cin >> n >> k;std::cin >> s >> t;std::map<char, int> mp, mpp;for(int i = 0; i < n; i ++) {mp[s[i]] ++;mpp[t[i]] ++;}bool flag = true;for(auto [x, y] : mp) {if(y != mpp[x]) {flag = false;break;}}if(!flag) {std::cout << "NO" << '\n';continue;}for(int i = 0; i < n; i ++) {if(s[i] != t[i] && std::max(i, n - i - 1) < k) {flag = false;break;}}std::cout << (flag ? "YES" : "NO") << '\n';}return 0;
}

F. Dasha and Nightmares

给出n个字符串，问有多少对不同的字符串，使得两个字符串连接起来满足以下条件：字符串中包含25个不同的字母；每个字母的个数为奇数个；字符串长度为奇数。

思路：思路来自cup_cpp佬。考虑哈希。但是显然STL自带的哈希表很容易会被卡掉，就需要一些高端方法自定义哈希表，因为是奇数，所以可以采用位运算实现代码。用二进制下的26位数字存所有的目标字符串，开26个哈希表存对于每个字母不存在时满足条件的方案数。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
#define int long long
const int N = 2e5 + 5;
int n;
int num[30], cnt[30];
std::string s;struct 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);}
};signed main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> n;for(int i = 0; i < 26; i ++) {num[i] = ((1 << 26) - 1) ^ (1 << i);}std::unordered_map<int, int, custom_hash> mp[26];for(int i = 0; i < 26; i ++)mp[i].reserve(n);int ans = 0;for(int i = 0; i < n; i ++) {std::cin >> s;int mask = 0;memset(cnt, 0, sizeof(cnt));for(auto u : s)cnt[u - '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] && mp[i].count(mask ^ num[i]))ans += mp[i][mask ^ num[i]];}for(int i = 0; i < 26; i ++) {if(!cnt[i])mp[i][mask] ++;}}std::cout << ans << '\n';return 0;
}