首页 > 代码库 > [haoi2009]求回文串
[haoi2009]求回文串
所谓回文串,就是对于给定的字符串,正着读和反着读都一样,比如ABCBA就是一个回文串,ABCAB则不是。我们的目标是对于任意输入的字符串,不断将第i个字符和第i+1个字符交换,使得该串最终变为回文串。求最少交换次数。
题解:
有一种做法是贪心;
就是每次找到最左端的字符,然后找到这序列中最右边的一样的字符,然后把这个字符移过去,然后把最左端右移,继续以上操作;
最后的答案就是每次的移动步数加起来;
要吐槽的是,window下I64d不要忘了......
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<ctime> #include<algorithm> #include<cstdlib> #include<map> #include<set> #include<vector> #include<queue> #include<cmath> 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<LL,LL> #define piii pair<LL,pair<LL,LL> > template<typename T> inline bool chkmin(T &a,T b){return a>b?a=b,true:false;} template<typename T> inline bool chkmax(T &a,T b){return a<b?a=b,true:false;} namespace IO{ char *fs,*ft,buf[1<<15]; inline char gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;} inline LL read(){ LL x=0;LL ch=gc();bool f=0; while(ch<‘0‘||ch>‘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<LL> 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<<i))cnt++; if(cnt>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; }
[haoi2009]求回文串
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。