Solution to the palindrome string (Luogu p5041 haoi2009)

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

1. In exchange for L and Z become SHLZLSHZS
2. In exchange for L and Z become SHZLLSHZS
3. In exchange for L and S become SHZLSLHZS
4. 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!

Solve the inverse logarithm https://blog.csdn.net/way_back/article/details/122808163?spm=1001.2014.3001.5501

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 ！