POJ 1854 - Evil Straw Warts Live
2024-09-20 08:13:37
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.
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.
Sample Input
3
mamad
asflkj
aabb
Sample Output
3
Impossible
2
Source
输入一串字符,先判断是否可以通过变换顺序变成回文串,不是的话输出impossible。
然后如果possible,定义一次swap相邻两个字母为一步,计算这个字符串经过最少多少次swap可以变为回文串。
具体思维:使用分治的方法……
每次搞定最左边和最右边的两个字母,也就是从外向内一层层做成回文串。
比如 abcbac 这个,先看最左边的“a”,从最右边开始遍历字符串,找到的第一个“a”就可以经过最少次数把右边变成“a”,
再看最右边的“c”,同样的,从最左边遍历字符串,找到的第一个“c”就可以经过最少次数把右边变成“c”,
比较一下是把最外层变成两个a还是两个c……哪个划算,就加上这个步数,把字符串最外层排好:“abcbca”,then去掉最外层变成:“bcbc”,继续重复上面的工作……
#include<cstring>
#include<string>
using namespace std;
void swap_palindrome(char s[],int begin,int end,int &step)
{
if(end-begin<=) return;
int i,left_distance,right_distance;
for(i=begin;i<end;i++) if(s[i]==s[end]) break;
left_distance=i-begin;
for(i=end;i>begin;i--) if(s[i]==s[begin]) break;
right_distance=end-i;
if(left_distance<right_distance){
step+=left_distance;
for(int i=left_distance+begin;i>begin;i--) swap(s[i],s[i-]);
}else{
step+=right_distance;
for(int i=end-right_distance;i<end;i++) swap(s[i],s[i+]);
}
swap_palindrome(s,begin+,end-,step);
}
int is_palindrome(char s[])
{
int letter[]={},len=strlen(s);
for(int i=;i<len;i++) letter[ (s[i]-'a') ]++;
int count=;
for(int i=;i<;i++){
if(letter[i]%==) count++;
}
if(count>) return ;
else return ;
}
int main()
{
int n;scanf("%d",&n);
char s[];
while(n--){
scanf("%s",s);
if(!is_palindrome(s)) printf("Impossible\n");
else{
int begin=,end=strlen(s)-,step=;
swap_palindrome(s,begin,end,step);
printf("%d\n",step);
}
}
return ;
}
另外……这题,刚开始我用了string类型,cin输入,迭代器遍历……就time limit exceeded……
最新文章
- jQuery浏览器类型判断和分辨率判断
- 《AngularJS权威教程》中关于指令双向数据绑定的理解
- Go的基本示例
- 委托、匿名委托、Lambda 表达式、Expression表达式树之刨根问底
- shmget() -- 建立共享内存
- 设计模式之 Factory Method 工厂方法
- Cinder-1 TinderBox
- stagefright框架(五)-Video Rendering
- win32使用ATL显示C#COM窗体
- 微软2017MVP大礼包拆箱攻略
- 使用RocketMQ实现分布式事务
- 纪念一下我对Kalman的无限崇拜之情
- Windows10卡顿,磁盘 内存占用100%或比较多
- Python开发【笔记】:pymsyql 插入一条数据同时获取新插数据的自增id的两种方式
- session进行增删改查操作
- linux shell 命令常用快捷键
- Linux内存管理Swap和Buffer Cache机制
- shell条件测试和流程控制
- webpack环境搭建开发环境,JavaScript面向对象的详解,UML类图的使用
- [置顶]
 Deep Learning 学习笔记
热门文章
- Failed to execute goal org.mybatis.generator:mybatis-generator-maven-plugin:1.3.2:generate
- 【Java】数组不能通过toString方法转为字符串
- Mac下必备快捷键的符号所对应的按键
- EasyUI 的 combotree 加载数据后折叠起来,并且只允许单击子节点的写法
- Json返回结果为null属性不显示解决方法
- DIOCP-DIOCPv5的处理能力
- 网络协议TCP/IP、IPX/SPX、NETBEUI简介
- 【转】WPF自定义控件与样式(2)-自定义按钮FButton
- Spring配置-数据库连接池proxool[转]
- Redhat6.5——解决yum功能不能正常使用