[haoi2009]求回文串-白红宇

[haoi2009]求回文串

阅读量：4946 次

发布时间：2019-06-11

本文共 1728 字，大约阅读时间需要 5 分钟。

所谓回文串，就是对于给定的字符串，正着读和反着读都一样，比如ABCBA就是一个回文串，ABCAB则不是。我们的目标是对于任意输入的字符串，不断将第i个字符和第i+1个字符交换，使得该串最终变为回文串。求最少交换次数。

题解：

有一种做法是贪心；

就是每次找到最左端的字符，然后找到这序列中最右边的一样的字符，然后把这个字符移过去，然后把最左端右移，继续以上操作；

最后的答案就是每次的移动步数加起来；

要吐槽的是，window下I64d不要忘了......

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 using namespace std;#define FILE "dealing"#define LL long long #define up(i,j,n) for(LL i=j;i<=n;i++)#define pii pair
                 
                  #define piii pair
                  
                   
                     >template
                    
                      inline bool chkmin(T &a,T b){ return a>b?a=b,true:false;}template
                     
                       inline bool chkmax(T &a,T b){ return a
                      
                       '9'){ if(ch=='-')f=1;ch=gc();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=gc();} return f?-x:x; }}using namespace IO;namespace OI{ const LL maxn(1010000),mod(10000); char s[maxn];LL n; vector
                       
                         g[27]; bool vis[maxn]; LL c[maxn]; inline LL lowbit(LL x){ return x&-x;} inline void add(LL x,LL y){ while(x<=n){c[x]+=y;x+=lowbit(x);}} inline LL get(LL x){LL sum=0;while(x>0)sum+=c[x],x-=lowbit(x);return sum;} void slove(){ scanf("%s",s+1); n=strlen(s+1);LL x=0,cnt=0; up(i,1,n)x=x^(1<<(s[i]-'A')); for(LL i=0;i<26;i++)if(x&(1<
                        
                         1){printf("-1\n");return;} up(i,1,n)g[s[i]-'A'].push_back(i); up(i,1,n)add(i,1); LL ans=0; up(i,1,n){ if(vis[i])continue; LL v=g[s[i]-'A'][g[s[i]-'A'].size()-1]; if(i==v)ans+=(get(n)-get(i))/2; else ans+=get(n)-get(v); add(i,-1);add(v,-1); vis[i]=vis[v]=1; g[s[i]-'A'].erase(g[s[i]-'A'].end()-1); } printf("%I64d\n",ans); }}int main(){ freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); using namespace OI; slove(); return 0;}

转载于:https://www.cnblogs.com/chadinblog/p/6002000.html

你可能感兴趣的文章