字符串配对 qdu蓝桥训练
#include
#include
#include
#include
#include<map>
#include
#include
#include
#define IL inline
#define x first
#define y second
typedef long long ll;
using namespace std;
char s[10010];
int main()
{
int n;
cin>>n;</map>
scanf("%s",s);
bool flag=0;
int ans=0;
int kk = n-1;
for(int i=0;i<kk;i++)
for(int j=kk;j>=i;j--)
{
if(i==j)
{
if(n%2==0||flag)
{
cout<<"Impossible"<<endl;
return 0;
}
flag=true;
ans+=n/2-i;
}
else if(s[i]==s[j])
{
for(int k=j;k<kk;k++)
{
swap(s[k],s[k+1]);
ans++;
}
// cout<<ans<<endl;
kk--;
break;
}
}
cout<<ans<<endl;
return 0;
}
`
解题报告：这题我以前做过，乍一看又傻眼了，咋做呢。。我之前没看清8000长度的字符串，硬是弄成bfs然后炸了，看了网上题解好像是朴素+小贪心做，一个字符串有奇数和偶数，如果奇数那允许出现一个不匹配的字符，如果偶数那就不允许，如果我们匹配找到了两个相等的字符，我们可以默认移动右边，把他移动到最右，答案加上步数，别忘了长度要减，如果没匹配的话，如果曾经出现过不匹配字母或者该串是双数串那就impossible了，否则把不匹配的移动到中间，这时移动的次数是原来的n，你说气不气，，哎。。
