Contestant(alt). Rank 3678. Rating +62(+262 -200).
A. Is It a Cat?
题意
给定一个字符串，转化为小写字母后，判断其是否由 \(m, e, o, w\) 组成，四个字母可以出现重复多个，但顺序不能改变，且每一个字母必须出现至少一次。如 \(MeOooOW\)。
思路
如题，我们只需用一个变量存储当前遍历到了哪个字母，若比较到某一个字母的时候，遍历的下标越界，那么输出 \(NO\)。否则，在最后判断一下四个字母是否都出现了至少一次，若满足那么 \(YES\)，否则 \(NO\)。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
int a[N];
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t;
cin >> t;
while(t --){
int n;
cin >> n;
string s;
cin >> s;
int tp = 0;
char up[4] = {'M', 'E', 'O', 'W'}, lo[4] = {'m', 'e', 'o', 'w'};
bool ok[4] = {false};
bool f = true;
for(int i=0;i<n;i++){
while(tp < 4 && s[i] != up[tp] && s[i] != lo[tp]) tp ++;
if(tp >= 4){
f = false;
break;
}
ok[tp] = true;
}
cout << (ok[0] && ok[1] && ok[2] && ok[3] && f ? "YES\n" : "NO\n");
}
}瞎模拟即可
B. Count the Number of Pairs
题意
给定一个字符串以及一个整数 \(k\)，规定同一个字母的大写和小写可以进行配对，一个字符只能出现在一对数中。定义一次操作为选择一个字符改变它的大小写，输出在小于等于 \(k\) 次的操作后，最多有多少对数。
思路
我们用两个数组解决这个问题：
令小写字母对应权值为 \(1\)，大写字母对应权值为 \(-1\)，那么加权后每种字母的总和的绝对值可以表征配对了多少对。我们记它为 \(abs(ans[i])\)。
统计每一种数出现的次数 \(cnt[i]\)。
那么，在不进行操作的前提下，我们易得最后的答案为 \(\sum \frac{(cnt[i] - abs(ans[i])}{2}\)。
若可以进行操作，那么对于一个字母剩余的数 \(ans[i]\)，我们可以配对 \(\frac{ans[i]}{2}\) 个。
因此，最后的答案即为 \(\sum \frac{(cnt[i] - abs(ans[i])}{2} + min(k, \sum \frac{ans[i]}{2})\)。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
int a[N];
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t;
cin >> t;
while(t --){
int n, k;
cin >> n >> k;
string s;
cin >> s;
int cnt[26]{}, ans[26]{};
for(int i=0;i<n;i++){
if(s[i] >= 'a' && s[i] <= 'z') {
cnt[s[i] - 'a'] ++;
ans[s[i] - 'a'] ++;
}else{
cnt[s[i] - 'A'] ++;
ans[s[i] - 'A'] --;
}
}
int res = 0, left = 0;
for(int i=0;i<26;i++){
res += (cnt[i] - abs(ans[i])) / 2;
left += abs(ans[i]) / 2;
}
cout << res + min(k, left) << '\n';
}
}总感觉类似的题哪里做过
C1. Powering the Hero (easy version)
详见C2，区别是C1的数据量更小一点
C2. Powering the Hero (hard version)
题意
给定 \(n\) 个卡牌对应的数字，从前向后遍历，若数字不为 \(0\)，那么可以选择是否将该数放在堆顶，或者将其丢弃。对于所有为 \(0\) 的数字，从堆顶拿出一个牌作为这个 \(0\) 的加分值，并将这两个牌丢弃，若堆为空则不考虑。输出最后加分的最大值。
思路
既然可以选择放或不放，那么我们一定可以让后面的 \(cnt\) 个 \(0\) 拿到前面的前 \(cnt\) 大的数。
因而，我们直接用优先队列即可。
有趣的是，困难版的数据量也无碍。
时间复杂度：最坏\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
int a[N];
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t;
cin >> t;
while(t --){
int n;
cin >> n;
priority_queue<int> q;
int ans = 0;
for(int i=0;i<n;i++) {
int cur;
cin >> cur;
if(cur != 0) q.push(cur);
else if(!q.empty()) ans += q.top(), q.pop();
}
cout << ans << '\n';
}
}赛时贪错了，吃了WA
D. Remove Two Letters
题意
给定一个字符串，输出去掉连续的两个字母后，得到的所有字符串中不同的字符串的个数。
思路
我们不妨取补集：
对于一个序列，若要出现重复的子串，那么需要满足 \(s[i] == s[i + 2]\)，这样的话，去掉 \(s[i], s[i + 1]\) 和去掉 \(s[i + 1], s[i + 2]\) 就是等价的了。
因而，我们统计出对数，用 \(n - 1\) 减去即可。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
int a[N];
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t;
cin >> t;
while(t --){
int n;
cin >> n;
string s;
cin >> s;
int ans = 0, cnt = 1;
char pre0 = s[0], pre1 = s[1];
for(int i=1;i<n-1;i++){
char cur0 = s[i], cur1 = s[i + 1];
if((pre0 == cur0 && pre1 == cur1) || pre0 == cur1 && pre1 == cur0){
cnt ++;
}else{
ans += cnt - 1;
cnt = 1;
pre0 = cur0, pre1 = cur1;
}
}
cout << n - (ans + cnt - 1) - 1 << '\n';
}
}赛时的代码居然还写的麻烦了一点（（
E1. Unforgivable Curse (easy version)
详见E2，区别是本题k=3
E2. Unforgivable Curse (hard version)
题意
给定两个长度相等的字符串 \(s, t\)，定义操作为交换 \(i, i + k\) 或 \(i, i + k + 1\) 上的数，在任意数量的操作后，输出是否可以将 \(s\) 更改为 \(t\)。
思路
首先，我们只需进行下面的操作即可将相邻数交换：
\(i, i + k + 1\)
\(i + k + 1, i + 1\)
\(i, i + k + 1\)
因而，只要可以进行上面的操作（或者向左），那么我们只需进行一定的操作，肯定可以将其换到我们需要的为止。
那么，我们也不难发现，若要向右交换，那么 \(i > k - n\)，若要想左交换，那么 \(i < k\)。
因而，只要 \([k, k - n]\) 内的字符相等，就一定有解。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
int a[N];
void solve(){
int n, k;
cin >> n >> k;
string s, t;
cin >> s >> t;
if(n <= k) cout << (s == t ? "YES\n" : "NO\n");
else{
bool f = true;
if(2 * k > n){
for(int i=n-k;i<k;i++)
if(s[i] != t[i]) f = false;
}
if(f){
sort(s.begin(), s.end());
sort(t.begin(), t.end());
f = s == t;
}
cout << (f ? "YES\n" : "NO\n");
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t;
cin >> t;
while(t --) solve();
}比赛快结束的时候就懒得写了（其实还挺好写的
F. Dasha and Nightmares
题意
给定 \(n\) 个字符串，输出有多少对字符串，满足下面的条件：
两个字符串的长度总和为奇数；
不同字母的个数为 \(25\)；
每种字母出现的次数为奇数。
思路
首先，第一个条件可以忽略，因为偶数个奇数相加，一定是奇数。
其次，第二个条件即为排除掉一个字母，需要其余的字母均出现。
考虑到 \(25\) 足够小，我们不妨用状压。
更具体地说，我们枚举不出现的字母 \(x\)，然后枚举所有字符串，对于字符串 \(s_i\)，它的所有字母的出现次数均可以预处理。但，因为我们只需考虑奇偶性，所以我们不妨令奇数状态为 \(1\)，偶数状态为 \(0\)，按照字母表顺序构建一个 \(26\) 位二进制字符串，便可以得到这个字符串的"哈希"值。
那么，考虑到异或的可逆性，对于一个排除掉 \(x\) 的拼接后的字符串，它的哈希值一定为形如 \(111...0...111\)，\(0\) 位即为 \(x\)。那么，对于这个 \(p = (1 << 26)\ XOR\ (1 << x)\)，我们可以将其和 \(s_i\) 的哈希值进行异或，得到需要和其配对的字符串的哈希值。
显然，对于第 \(i\) 个字符串，我们只需遍历前 \(i - 1\) 个字符串是否可以与其配对即可。那么，我们可以用 \(map\) 存储一个哈希值对应的字符串有多少个，最后统计总和即可。
时间复杂度：\(O(25n + m) = 1e7\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 5e6 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
int odd[N], num[N];
void solve(){
int n;
cin >> n;
for(int i=0;i<n;i++){
string cur;
cin >> cur;
for(char e : cur){
odd[i] ^= (1 << (e - 'a'));
num[i] |= (1 << (e - 'a'));
}
}
int ans = 0;
for(int i=0;i<26;i++){ //不选i
map<int, int> cnt;
int tot = ((1 << 26) - 1) ^ (1 << i);
for(int j=0;j<n;j++){
if(!(num[j] & (1 << i))){
ans += cnt[tot ^ odd[j]];
cnt[odd[j]] ++;
}
}
}
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t = 1;
//cin >> t;
while(t --) solve();
}我好若，居然想不到状压
G. Symmetree
题意
给定一棵根为 \(1\) 的树，判断其是否镜像对称。
思路
也就是说，我们需要枚举所有子树，并进行同构的配对。
暴力复杂度是 \(O(n ^ 2)\) 的，因为我们需要同步枚举对应的点，每个路径会被访问多次。
但是，如果我们将判断优化到 \(O(\log n)\)，就可以快很多了。
这里考虑树上哈希。
我们从上往下 \(\mathtt{dfs}\)，并给不同的子树用 \(map\) 的方式标号，最后每个点都会有一个子树标号的集合，我们判断所有标号中出现奇数次的树是否对称即可。
时间复杂度：\(O(n \log n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<vector<int>> e(n + 1);
for(int i=1;i<n;i++){
int u, v;
cin >> u >> v;
e[u].pb(v), e[v].pb(u);
}
map<vector<int>, int> hs;
map<int, bool> st;
int id = 0;
auto dfs = [&](auto dfs, int x, int p) -> int{
vector<int> child;
for(auto y : e[x]){
if(y == p) continue;
child.pb(dfs(dfs, y, x));
}
sort(all(child));
if(!hs.count(child)) {
map<int, int> cnt;
for (auto y: child) {
cnt[y]++;
}
int odd = 0, bad = 0;
for (auto [y, t]: cnt) {
if (t & 1) {
odd++;
if(!st[y]) bad ++;
}
}
st[++ id] = odd < 2 && bad == 0;
hs[child] = id;
}
return hs[child];
};
cout << (st[dfs(dfs, 1, -1)] ? "YES\n" : "NO\n");
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}用上哈希直接成裸题了啊（？