题意:
$对给定的字符串,求最少操作次数(交换任意两个字符),将字符串变为非镜像串。\\\即对于任意i,满足s[i]≠s[n−i+1]。$
思路:
$无解情况:1.长度为奇数。2.长度为偶数,但有同一字符出现次数>\frac{n}{2},一定无解。$
$求最少操作:例,对于a-a的字母对,跟其他的a-a字母对互相交换是没有意义的。\\\显而易见,如果将a-a和b-b同时交换,一定能成功,还能一举两得。\\\那如果只剩下同一种字母对了,证明是否能一次交换成功。\\\$
$证明:只需考虑前\frac{n}{2}个字母对,由于同一字符出现的次数<=\frac{n}{2},\\\所以可以保证\frac{n}{2}个位置中各至多出现一次’a’,可以每次将’a’移到未被占用的空位上。$
$综上,当种类>=2时,每次交换可以同时解决两对。当种类=1时,每次交换只能解决一对。$
$这里的思路很像$增减序列 。
解法:
$1.用堆维护字母对,每次取出两个元素并-1。不为0再放回堆中,直至堆中只剩一个元素或空。\\\再对剩余元素累加答案。\\\2.推结论,类增减序列。如果最多的相同字母对数量<sum/2。就为(sum+1)/2(上取整)。\\\否则为最大出现次数maxv。$
代码(推结论版):
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=30;
int T,n;
string s;
int cnt[N],v[N];
signed main()
{
cin>>T;
while(T--)
{
memset(cnt,0,sizeof cnt);
memset(v,0,sizeof v);
cin>>n>>s;
bool fg=true;
if(n&1) fg=false; //长度为奇 无解
for(auto x:s) cnt[x-'a']++;
for(auto x:cnt)
if(x>n/2) fg=false; //出现次数>n/2 无解
if(!fg)
{
puts("-1");
continue;
}
string rs=string(s.rbegin(),s.rend());
int maxv=0,sum=0;
for(int i=0;i<n/2;i++)
{
if(s[i]==rs[i])
{
sum++; //记录总数
v[s[i]-'a']++; //记录当前字母对
maxv=max(maxv,v[s[i]-'a']); //更新最大出现次数
}
}
int res; //推结论
if(maxv*2<sum) res=(sum+1)/2;
else res=maxv;
cout<<res<<endl;
}
return 0;
}
代码(堆):
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=30;
int T,n;
string s;
int cnt[N],v[N];
signed main()
{
cin>>T;
while(T--)
{
memset(cnt,0,sizeof cnt);
memset(v,0,sizeof v);
cin>>n>>s;
bool fg=true;
if(n&1) fg=false;
for(auto x:s) cnt[x-'a']++;
for(auto x:cnt)
if(x>n/2) fg=false;
if(!fg)
{
puts("-1");
continue;
}
string rs=string(s.rbegin(),s.rend());
for(int i=0;i<n/2;i++)
if(s[i]==rs[i]) v[s[i]-'a']++; //记录相同字母对
priority_queue<int> heap;
for(int i=0;i<26;i++)
if(v[i]) heap.push(v[i]); //把字母对放入堆
int res=0;
while(heap.size()>1)
{
int a=heap.top(); heap.pop();
int b=heap.top(); heap.pop();
a--; b--; res++; //各自-1 res++
if(a) heap.push(a); //不为0就放入
if(b) heap.push(b);
}
if(heap.size()) //还剩一个就特殊处理
{
int t=heap.top();
res+=t;
}
cout<<res<<endl;
}
return 0;
}
大佬,膜拜一下
是A
你写的代码好美,跟诗一样