幼敏悟过人,读书辄成诵。这篇文章主要讲述AtcoerE - Papple Sort相关的知识,希望能为你提供帮助。
【题目】E - Papple Sort
【题意】给定长度为n的小写字母串,只能交换相邻字母,求形成回文串的最小步数。n<
=2*10^5。
【算法】数学
【题解】官方题解
本题题解中有以下重要的思想:
①分析多复杂因素相互干扰的问题时,先排除无关因素,然后转化关联因素为独立因素后逐个分析。
②位置移动的问题中,常用转绝对位置为相对位置,考虑两两相对的情况。
③回文的性质:嵌套。
奇数串和偶数串对做法没有影响,忽略。
首先,对于串中所有字母x,交叉移动没有任何意义,所以一定是最左-最右,次左-次右...的组合。这样我们可以将长度为n的串视为n/2对字母。
现在,考虑串中任意两对字母AA和BB的相对位置和对应交换策略:
1.[...A...A...B...B...],A作为外围字母(A移动到B右边对称位置)和B作为外围字母(B移动到A左边对称位置)移动距离一致,无影响。
2.[...A...B...A...B...],移动距离一致,无影响。
3.[...A...B...B...A...],A-A必须作为外围字母而B-B必须作为内围字母。
注意:这里很容易认为在前两种情况中,A移动还是B移动会对中间省略号的部分造成影响。但是请注意这里是只考虑A-A和B-B这两对的相对位置,从A必须相对于B-B回文而不是全局回文也可以看出。在每次移动都会牵扯很多数字的情况下,我们刻意不在所有数字都存在的全局范围内讨论移动,而是单独考虑两两对之间的位置和对应策略,这样就不会有全局的复杂关联因素。
综上所述,为了保证不会发生第三种情况的内越外,当(l1,r1)和(l2,r2)满足l1<
l2时,(l1,r2)必须是外围字母。
因此,必须从左往右做,每次将对应字母移动到回文位置,这样就能保证所有(l2,r2),l1>
l2的r2都在最外围(不会越过),而会越过所有(l2,r2),l1<
l2的r2。
提前判断无解后,统计步数用树状数组记录当前剩余元素来实现(每次都视为移动到n,移动过的元素在最外围直接删除)。
文章图片
文章图片
#include< cstdio> #include< cstring> #include< cctype> #include< cmath> #include< queue> #include< stack> #include< set> #include< vector> #include< algorithm> #define ll long long #define lowbit(x) x& -x using namespace std; int read(){ char c; int s=0,t=1; while(!isdigit(c=getchar()))if(c==‘-‘)t=-1; do{s=s*10+c-‘0‘; }while(isdigit(c=getchar())); return s*t; } int min(int a,int b){return a< b?a:b; } int max(int a,int b){return a< b?b:a; } int ab(int x){return x> 0?x:-x; } //int MO(int x){return x> =MOD?x-MOD:x; } //void insert(int u,int v){tot++; e[tot].v=v; e[tot].from=first[u]; first[u]=tot; } /*------------------------------------------------------------*/ const int inf=0x3f3f3f3f,maxn=200010; int n,c[maxn],num[maxn]; bool vis[maxn]; char s[maxn]; vector< int> v[30]; void modify(int x,int k){for(int i=x; i< =n; i+=lowbit(i))c[i]+=k; } int query(int x){int ans=0; for(int i=x; i> =1; i-=lowbit(i))ans+=c[i]; return ans; } int main(){ scanf("%s",s+1); n=strlen(s+1); for(int i=1; i< =n; i++)num[s[i]-‘a‘]++,v[s[i]-‘a‘].push_back(i); int ok=0; for(int i=0; i< 26; i++){ if(num[i]%2)ok++; } if(ok> 1){printf("-1"); return 0; } for(int i=1; i< =n+1; i++)modify(i,1); ll ans=0; for(int i=1; i< =n; i++)if(!vis[i]){ int c=s[i]-‘a‘; int x=v[c][v[c].size()-1]; if(i==x){ ans+=(query(n)-query(i))/2; } else{ ans+=(query(n)-query(x)); } modify(i,-1); modify(x,-1); vis[i]=vis[x]=1; v[c].erase(v[c].end()-1); } printf("%lld",ans); return 0; }
View Code【AtcoerE - Papple Sort】
推荐阅读
- 使用Kotlin创建Android项目
- Android-----购物车(包含侧滑删除,商品筛选,商品增加和减少,价格计算,店铺分类等)
- Android查缺补漏--Service和IntentService
- Android查缺补漏--Activity生命周期和启动模式
- Android查缺补漏--ContentProvider的使用
- AtCoder Regular Contest 088 E - Papple Sort(树状数组+结论)
- Android开发学习-四大组件
- android studio安装和配置kotlin
- There is no Action mapped for namespace [/] and action name [Login] associated