1 条题解
-
0
注意到一次操作最多可以让相邻相同字符的数量减 ,于是我们可以构造一个新的字符串,其中对于 ,如果 就把这个字符加入新的字符串中。每次操作可以把新字符串中相邻两项不同字符删除或者删除一个单独字符。把新字符串删空后还需要额外操作一步把原串整个删掉。
如果新字符串中存在一种字符出现次数超过一半,则让其他的字符与这个字符配对删除,剩下多余的字符一个一个删除是最优的。如果不存在,那么从前往后扫,如果遇到可以删除的,并且删除之后不会使得某个字符出现次数超过一半,就把它删除即可。
注意需要构造方案,使用线段树维护哪些位置没被删除即可。
#include<bits/stdc++.h> using namespace std; int n,m,pos[200001]; char s[200002],t[200001]; bool vis[200001]; int cnt['z'+1],most,sum; void findMost(){ most='z'; for(char c='a';c<'z';c++) if(cnt[c]>cnt[most])most=c; } struct SegmentTree{ struct Node{ int l,r; int sum,tag; void update(int val){ sum=(r-l+1)*val,tag=val; } }node[800001]; void pushdown(int id){ if(node[id].tag!=-1){ node[id<<1].update(node[id].tag); node[id<<1|1].update(node[id].tag); node[id].tag=-1; } } void pushup(int id){ node[id].sum=node[id<<1].sum+node[id<<1|1].sum; } void build(int id,int l,int r){ node[id].l=l,node[id].r=r; node[id].sum=0,node[id].tag=-1; if(l==r)return; int mid=l+r>>1; build(id<<1,l,mid); build(id<<1|1,mid+1,r); } void update(int id,int l,int r,int val){ if(l<=node[id].l&&node[id].r<=r) return node[id].update(val); int mid=node[id].l+node[id].r>>1; pushdown(id); if(l<=mid)update(id<<1,l,r,val); if(mid<r)update(id<<1|1,l,r,val); pushup(id); } int query(int id,int l,int r){ if(l<=node[id].l&&node[id].r<=r) return node[id].sum; int mid=node[id].l+node[id].r>>1,ret=0; pushdown(id); if(l<=mid)ret+=query(id<<1,l,r); if(mid<r)ret+=query(id<<1|1,l,r); return ret; } }_; int main(){ int T; scanf("%d",&T); while(T--){ scanf("%s",s+1); n=strlen(s+1); m=sum=0; for(int i=1;i<n;i++) if(s[i]==s[i+1])t[++m]=s[i],pos[m]=i,vis[m]=false; vector<pair<int,int>> answer; stack<int> s; for(char c='a';c<='z';c++)cnt[c]=0; for(int i=1;i<=m;i++)cnt[t[i]]++,sum++; findMost(); if(cnt[most]>sum/2){ for(int i=1;i<=m;i++){ if(t[i]==most){ if(s.empty()||t[s.top()]==t[i])s.push(i); else answer.emplace_back(s.top(),i),s.pop(); } else{ if(s.empty()||t[s.top()]!=most)s.push(i); else answer.emplace_back(s.top(),i),s.pop(); } } while(!s.empty())answer.emplace_back(s.top(),0),s.pop(); } else{ if(m&1){ answer.emplace_back(m,0); sum--,cnt[t[m]]--,m--; } for(int i=1;i<=m;i++){ if(s.empty()||t[s.top()]==t[i]){ s.push(i); continue; } sum-=2,cnt[t[s.top()]]--,cnt[t[i]]--; findMost(); if(cnt[most]>sum/2){ sum+=2,cnt[t[s.top()]]++,cnt[t[i]]++; s.push(i); } else{ vis[s.top()]=vis[i]=true; answer.emplace_back(s.top(),i),s.pop(); } } } printf("%d\n",(int)answer.size()+1); _.build(1,1,n); _.update(1,1,n,1); for(pair<int,int> i :answer){ int x=i.first,y=i.second; if(y){ int u=_.query(1,1,pos[x]+1); int v=_.query(1,1,pos[y]); printf("%d %d\n",u,v); _.update(1,pos[x]+1,pos[y],0); } else{ int u=_.query(1,1,pos[x]); printf("%d %d\n",u,u); _.update(1,pos[x],pos[x],0); } } printf("%d %d\n",1,_.query(1,1,n)); } return 0; }
- 1
信息
- ID
- 1152
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 3
- 已通过
- 1
- 上传者