https://codeforces.com/contest/1800
E. Unforgivable Curse
题意：输入两个字符串s,t , 每次修改可以交换相距k或k+1位置的字母，能否将将s修改为t。
方法：首先，两个字符串必须由相同元素，且每种元素的个数相等。其次，元素可以先移动k+1个位置，再往回移动k个位置，实现移动1的操作，就可以移动到任意位置上，所以每个待修改的可交换位置必须要在字符串范围内就一定可行并且无法修改的位置元素相同，就输出YES，否则输出NO。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
void solve(){
int n,k;
cin>>n>>k;
string s,t;
cin>>s>>t;
map<char,int> mp, ap;
for(int i=0;i<n;i++){
mp[s[i]] ++;
ap[t[i]] ++;
}
int flag = 1;
for(auto it: mp){
if(it.second != ap[it.first]){
flag = 0;
break;
}
}
if(!flag){
cout<<"NO"<<'\n';
return;
}
for(int i=0;i<n;i++){
if(s[i] != t[i]&&max(i,n - i - 1)<k){
flag = 0;
break;
}
}
if(flag) cout<<"YES"<<'\n';
else cout<<"NO"<<'\n';
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cin.tie(0);
int T;
cin>>T;
while(T--){
solve();
}
return 0;
}
F. Dasha and Nightmares
题意：输入 n 个由小写字母构成的字符串，选择两个字符串，要求满足三个条件：
1.拼接后的长度是奇数。
2.拼接后字符种类是25.
3.拼接后每个字符出现的次数是奇数。
输出有多少对（i，j）
方法：只要满足条件2，3，就会满足条件1.
异或哈希
对于每个字符串都构建两个长度为26的二进制字符串a[i],b[i]
当出现了字符ch，就将a[i]第ch - 'a'位置设为1
当字符出现过奇数次，就将、b[i]第ch - 'a'位置设为1
然后就枚举缺少的字符
每次枚举s[i],找出有多少个s[j],使s[i] + s[j] 符合要求
s[i] -> b[i] == k, s[j] -> b[j] == p, s[i]+s[j] -> b[i] == k^p;
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int a[N], b[N], cnt[1<<26],n;
string s;
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>s;
int len = s.size();
for(int j=0;j<len;j++){
a[i] |= (1<<(s[j] - 'a'));
b[i] ^= (1<<(s[j] - 'a'));
}
}
long long ans = 0;
for(int i=0;i<26;i++){
int s = (1<<26) - 1 - (1<<i); //枚举缺少的字符i + 'a'
for(int j=1;j<=n;j++){
if(!(a[j]>>i&1)){ // 检查第j个字符串中是否存在s
cnt[b[j]] ++;
ans += cnt[b[j]^s];
}
}
for(int j=1;j<=n;j++)
if(!(a[j]>>i&1)) cnt[b[j]] --;
}
cout<<ans<<'\n';
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T;
//cin>>T;
T = 1;
while(T--){
solve();
}
return 0;
}