poj 1854 Evil Straw Warts Live 变成回文要几次
2024-08-31 14:00:45
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 1799 | Accepted: 523 |
Description
A palindrome is a string of symbols that is equal to itself when reversed. Given an input string, not necessarily a palindrome, compute the number of swaps necessary to transform the string into a palindrome. By swap we mean reversing the order of two adjacent symbols. For example, the string "mamad" may be transformed into the palindrome "madam" with 3 swaps:
swap "ad" to yield "mamda"
swap "md" to yield "madma"
swap "ma" to yield "madam"
swap "ad" to yield "mamda"
swap "md" to yield "madma"
swap "ma" to yield "madam"
Input
The
first line of input gives n, the number of test cases. For each test
case, one line of input follows, containing a string of up to 8000
lowercase letters.
first line of input gives n, the number of test cases. For each test
case, one line of input follows, containing a string of up to 8000
lowercase letters.
Output
Output
consists of one line per test case. This line will contain the number
of swaps, or "Impossible" if it is not possible to transform the input
to a palindrome.
consists of one line per test case. This line will contain the number
of swaps, or "Impossible" if it is not possible to transform the input
to a palindrome.
Sample Input
3
mamad
asflkj
aabb
Sample Output
3
Impossible
2 题意:一个字符串变成回文最少要几次 题解:
1、用回文的性质判断是否可以变成回文:个数为奇数的字母出现的次数小于等于1
2、从字符串的两端出发(l,r),在字符串两端同时找能使s[l]==s[r]的位置,
3、取使左右两端相等步数最少的那一端,并从内到外交换位置(若从外到内交换会疯狂WA)
#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
#include<vector>
#include<stack>
#include<math.h>
#define mod 998244353
#define ll long long
#define MAX 0x3f3f3f3f
using namespace std;
int vis[];
string s; int check(string ss)
{
int cnt=;
memset(vis,,sizeof(vis));
for(int i=;i<ss.length();i++)
vis[ss[i]-'a']++;
for(int i=;i<;i++)
{
if(vis[i]%==)
cnt++;
}
if(cnt>)
return ;
else
return ;
}
int main()
{ int n,ans;
cin>>n;
while(n--)
{
ans=;
cin>>s;
if(check(s))
cout<<"Impossible"<<endl;
else
{
int len=s.length(),l,r,j,mid,x=MAX,y=MAX; for(int i=;i<len/;i++)
{
l=i;
r=len--i;
if(s[l]!=s[r])
{
for(j=l+;s[j]!=s[r];j++);
x=j;
for(j=r-;s[j]!=s[l];j--);
y=j;
if(x-l>r-y)
{
ans=ans+r-y;
for(int j=y;j<r;j++)
s[j]=s[j+];
}
else
{
ans=ans+x-l;
for(int j=x;j>l;j--)
s[j]=s[j-];
}
}
}
cout<<ans<<endl; }
}
return ;
}
最新文章
- Android-armebi-v7a、arm64-v8a、armebi的坑
- 使用mvc时,在视图view中使用强类型视图,在web.config文件中添加命名空间namespace的引用不起作用,解决方法
- soanar,jenkins
- 53. Android常用工具类
- SqlServer建表规范
- 有关collection中的一些数据结构
- HoG SVM 目标检测分析
- 安装好maven后,在cmd中运行mvn报一下的错误
- hdu4712 Hamming Distance
- Windows10 Apache2.4 PHP7 MySQL 5.7安装教程
- JSON数据传递
- PHP实现二维数组排序(按照数组中的某个字段)
- 对Spring事务的一些误解
- 从零开始学习前端JAVASCRIPT — 14、闭包与继承
- mysql配置外部允许外部连接
- 如何转换cdr文件
- react-native 集成极光推送jpush-react-native时的小问题
- Spring Boot Shiro 权限管理 【转】
- Dockerfile中ENTRYPOINT 和 CMD的区别
- java压缩流