当前位置:网站首页>Solution to the palindrome string (Luogu p5041 haoi2009)
Solution to the palindrome string (Luogu p5041 haoi2009)
2022-07-05 05:26:00 【Korloa】
Let's start with the topic :
Title Description
The so-called palindrome string , For a given string , It's the same to read forward and reverse , such as ABCBA It's a palindrome string ,ABCAB It is not . Our goal is for arbitrary input strings , Continue to i Characters and the i+1 Character exchange , Make this string finally become palindrome string . Find the minimum number of exchanges .
Input format
A string of uppercase letters .
Output format
If you can change the original string into palindrome string after a limited number of operations , Then the minimum number of operations is output ; Otherwise output -1
.
I/o sample
Input #1 Copy
SHLLZSHZS
Output #1 Copy
4
explain / Tips
Sample explanation
- In exchange for L and Z become SHLZLSHZS
- In exchange for L and Z become SHZLLSHZS
- In exchange for L and S become SHZLSLHZS
- In exchange for H and Z become SHZLSLZHS
Data range
40% The data of , length \≤50000
100% The data of , length 10^6
Answer key :
Ideas :
greedy + Reverse alignment
Let's first judge the situation without solution , Let's count the number of times each letter appears in the string , There can only be one odd number , Because in pairs , When it comes to 1 An odd number of times , The sequence length is odd , The middle position can be filled with this extra unmatched array , Ensure the conditions of palindromes , Where to put more !
Minimum number of exchanges , It occurred to me that the reverse order was right . But this is a string , This is not a sequence . That right , We can mark each character of this string , As shown in the figure :
If the final order is :
So we sort the subscripts , Just find the inverse logarithm .
So how to get the final order , How to ensure that the best result is arranged ?
Let me tell you the answer first :
Build array Ans,Ans What will be stored is the subscript positions that we finally ordered .
If the sequence length is odd , Then first put the subscript of the letter in the middle of the odd number of letters in Ans The middle of the array , Maybe a little wordy , Last picture :
Let's start from the leftmost part of the original sequence , Mark the rightmost letter in the original sequence with it , As Ans The two most extreme values of the array . Keep repeating this process .( Two are not marked )
As shown in the figure :
Why is this right , Why can't I put the middle B Move to the left , Think about us exchanging adjacent elements , It passed the rightmost B, It costs more for the same journey , The star is not the best
Realization :
The code is long , But we can divide it into 3 Stages :
1. Data utilization stage
2.Ans Array solving stage
3. The solution phase of the reverse pair
1. Data utilization stage .
Input only one string , First, we need to convert the string into the corresponding number , namely A-Z Turn into 1-26, use int Array storage of type . This is convenient for our specific operation .
Define a bool An array of types , Used to mark elements that have been accessed ;
The key : Define a two-dimensional array Pos, In the first dimension, we only use [1,26] The range of , The second digit stores the positions where the letter appears .
For convenience , We use it Vector Definition .
vector<int>pos[100000];
So clearly , Letter X The quantity of is pos[X].size() Letter X The leftmost position that appears is pos[X][0]; The rightmost position is pos[X][pos[X].end-1];
2.Ans Array solving stage
Define shaping Left and right, respectively Ans Where are the left and right sides of the array filled .
Filter from the original sequence from left to right i, If letter i Marked , Skip this number ;
If not marked , Find the right most subscript that is the same as straight
Ans[left]=i;
Ans[right]=pos[i][pos[i].end()-1]
left++;right++
Just repeat ; The termination condition is :i>len or left>right, This means Ans Array construction is complete
3 Solution stage of array in reverse order
There are two algorithms
1. Sort based on merge (O:nlogn)
2. Bubble based sorting (O:n^2)
We use merge sort , Bubbling encounters so much data directly TLE, Pull back .
Detailed explanation of merge sort and bubble sort ,Please click here!
AC code
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
char str[1000002];
int strto[1000002];
int ans[1000002];
int t[1000002];
bool vis[1000002];
vector<int>pos[100000];
int snum=0;
int spos;
unsigned long long tot=0;
void solve(int l,int r){
if(l==r)
return;
int mid=(l+r)/2;
solve(l,mid);
solve(mid+1,r);
int la=l;
int k=l;
int rb=mid+1;
while(la<=mid && rb<=r){
if(ans[la]<=ans[rb]){
t[k]=ans[la];
k++;
la++;
}
else{
t[k]=ans[rb];
k++;
rb++;
tot+=mid-la+1;
}
}
while(la<=mid){
t[k]=ans[la];
la++;
k++;
}
while(rb<=r){
t[k]=ans[rb];
k++;
rb++;
}
for(int i=l;i<=r;i++){
ans[i]=t[i];
}
}
int main(){
scanf("%s",str+1);
memset(vis,true,sizeof(vis));
int len=strlen(str+1);
for(int i=1;i<=len;i++){
strto[i]=str[i]-'A'+1;
pos[strto[i]].push_back(i);
}
for(int i=1;i<=26;i++){
if(pos[i].size()%2==1){
snum++;
if(snum>1){
putchar('-');
putchar('1');
return 0;
}
spos=pos[i][pos[i].size()/2];
vis[spos]=false;
ans[len/2+1]=spos;
}
}
int start=1;
int left=1;
int right=len;
while(start<=len && left<=right){
if(!vis[start]){
start++;
continue;
}
ans[left]=start;
vis[start]=false;
left++;
ans[right]=pos[strto[start]][pos[strto[start]].size()-1];
vis[ans[right]]=false;
pos[strto[start]].erase(pos[strto[start]].end()-1);
right--;
start++;
}
solve(1,len);
printf("%llu",tot);
return 0;
}
End~~~
Writing is not easy to , Thank you for your support !
边栏推荐
- [allocation problem] 455 Distribute cookies
- PMP考生,请查收7月PMP考试注意事项
- Haut OJ 1316: sister choice buys candy III
- MySQL数据库(一)
- PMP candidates, please check the precautions for PMP examination in July
- 小程序直播+電商,想做新零售電商就用它吧!
- Web APIs DOM节点
- High precision subtraction
- [转]MySQL操作实战(三):表联结
- Reverse one-way linked list of interview questions
猜你喜欢
随机推荐
[paper notes] multi goal reinforcement learning: challenging robotics environments and request for research
Solon Logging 插件的添加器级别控制和日志器的级别控制
Solon 框架如何方便获取每个请求的响应时间?
JVM call not used once in ten years
支持多模多态 GBase 8c数据库持续创新重磅升级
PMP candidates, please check the precautions for PMP examination in July
Improvement of pointnet++
Haut OJ 1218: maximum continuous sub segment sum
Reader writer model
Acwing 4301. Truncated sequence
【ES实战】ES上的native realm安全方式使用
Solon Logging 插件的添加器级别控制和日志器的级别控制
Use of snippets in vscode (code template)
C language Essay 1
Bubble sort summary
Count sort
Acwing 4300. Two operations
Gbase database helps the development of digital finance in the Bay Area
二十六、文件系统API(设备在应用间的共享;目录和文件API)
[allocation problem] 135 Distribute candy