2025牛客WC4-D-Tokitsukaze and Concatenate Palindrome · znzryb
## 思路讲解
如同这个例子一样，已经匹配好的我们就可以不管了，因为是两两匹配的，所以说回文串中心不会改变，不用担心会有什么问题
然后最容易想不通的就是长串内部的消除问题
```cpp
FOR(i,0,25){
if(cnta[i]>=cntb[i]) cnta[i]-=cntb[i];
else shortRem+=cntb[i]-cnta[i],cntb[i]-=cnta[i],cnta[i]=0;
}
ll longRem=0;
FOR(i,0,25){
if(cnta[i]%2==1) ++longRem;
}
```
abgfhh 和abcdeee的匹配过程（longRem ≥ shortRem 就可以像下图这样将重复元素加入到对称轴两边，进而就可以抵消）
当（longRem < shortRem），为什么答案就是shortRem那？
说白了其实就是把这些奇数的都给搞定了，剩下的就都是偶数的，就比较好搞了（）
与longRem匹配完剩余是偶数的情况更简单，就不画了。
## AC代码
AC
[https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75405249](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75405249)
```cpp
// Problem: Tokitsukaze and Concatenate Palindrome
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95336/D
// Memory Limit: 512 MB
// Time Limit: 4000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;
ll N,M,T;
char Ao[MAXN],Bo[MAXN],A[MAXN],B[MAXN];
ll cnta[29],cntb[29];
inline void solve(){
cin>>N>>M;
FOR(i,1,N){
cin>>A[i];
}
FOR(i,1,M){
cin>>B[i];
}
FOR(i,0,27){
cnta[i]=0;
cntb[i]=0;
}
if(N<M){
FOR(i,1,M){
swap(A[i],B[i]);
}
swap(N,M);
}
FOR(i,1,N){
cnta[A[i]-'a']+=1;
}
FOR(i,1,M){
cntb[B[i]-'a']+=1;
}
ll shortRem=0;
FOR(i,0,25){
if(cnta[i]>=cntb[i]) cnta[i]-=cntb[i];
else shortRem+=cntb[i]-cnta[i],cntb[i]-=cnta[i],cnta[i]=0;
}
ll longRem=0;
FOR(i,0,25){
if(cnta[i]%2==1) ++longRem;
}
if(shortRem>longRem){
cout<<shortRem<<'\n';
}else{
// if((N+M)%2!=0) longRem= longRem==0?0:longRem-1;
cout<<shortRem+(longRem-shortRem)/2<<'\n';
}
// FOR(i,1,N){
// cerr<<A[i]<<' ';
// }
// cerr<<'\n';
// FOR(i,1,M){
// cerr<<B[i]<<' ';
// }
// cerr<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--){
solve();
}
return 0;
}
/*
*/
```
## 心路历程（WA，TLE，MLE……）