Znzryb's Blog
0%

2025牛客WC4-D-Tokitsukaze and Concatenate‌ Palindrome

Posted on Edited on

思路讲解

如同这个例子一样，已经匹配好的我们就可以不管了，因为是两两匹配的，所以说回文串中心不会改变，不用担心会有什么问题

image

然后最容易想不通的就是长串内部的消除问题

image

1
2
3
4
5
6
7
8
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 就可以像下图这样将重复元素加入到对称轴两边，进而就可以抵消）

image

当（longRem < shortRem），为什么答案就是shortRem那？

说白了其实就是把这些奇数的都给搞定了，剩下的就都是偶数的，就比较好搞了（）

image

与longRem匹配完剩余是偶数的情况更简单，就不画了。

AC代码

AC

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75405249

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// 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……）