当前位置: 首页 > news >正文

ARC113E Rvom and Rsrev

看看样例,发现要对 \(a\)\(b\) 的位置和数量分讨。

\(A\) 表示一段极长连续 \(a\)\(B\) 表示一段极长连续 \(b\)。答案只有三种情况:

  1. \(A\) 或者 \(B\)
  2. \(aB\)
  3. \(BA\)
  4. \(BaB\)

我们要做的操作是尽量把 \(b\) 向前挪动,直到挪不了或者挪了不优的时候才留下 \(a\)

考虑最终答案对应的 \(S\) 的情况。


\(A\)\(B\)

如果 \(S\) 里字母相同,什么都不做是最优的,否则会使字母数量变少。

\(S\) 不满足前面的所有条件。如果 \(S=\dots b\)\(a\) 有偶数个,我们要让 \(b\) 尽量向前挪动,直接把 \(a\) 删完即可。


\(aB\)

\(S\) 不满足前面的所有条件。如果 \(S = AB\),且 \(a\) 为奇数时,\(a\) 删不完,让 \(b\) 尽量向前挪动,那就剩下一个 \(a\) 最优。


\(BA\)

此时的答案,当 \(B\) 确定时,我们应该让 \(A\) 可能长。

\(S\) 结尾是 \(a\)

\(S\) 不满足前面的所有条件。如果 \(S\) 结尾是 \(a\),那么我们操作会是一直删 \(a\) 使 \(b\) 向前挪,并且末尾留下 \(A\) 尽量长。

先除去最后一段 \(A\),设剩下的 \(|A|=1\) 的段有 \(w_1\) 个,\(|A|>1\) 的段有 \(w_2\) 个。

我们每次操作,取最后一段 \(A\) 和第一段 \(A\) 的第一个位置,把第一段 \(A\) 拼到最后一段,把最后一段 \(B\) 转到前面。
这样会删掉 \(2 \times w_2\)\(a\),使得 \(S\) 中除了最后一段 \(A\) 只剩下 \(|A|=1\) 的段。

我们为了使剩下末尾的 \(A\) 尽量长,就让 \(|A|=1\) 的两两删,不够了再从末尾的 \(A\) 里拿一个出来,这样操作会减掉 \(2 \times \lceil \frac{w_1}{2} \rceil\)\(a\)

最后 \(S\) 中的 \(b\) 个数不变且被挪到了最前面,\(a\) 减少了\(2 \times (w_2 + \lceil \frac{w_1}{2} \rceil)\) 个。

\(S\) 结尾是 \(b\)

\(S\) 不满足前面的所有条件。如果 \(S\) 结尾是 \(b\) 且有奇数个 \(a\),假如我们直接先删 \(a\) 使 \(S=BaB\),那么我们再删两个 \(b\)\(a\) 挪到后面更优。

也就是说我们为了把后面的 \(b\) 挪到前面去,一定会删掉两个 \(b\)。那我们可以先删 \(b\),把一段 \(a\) 挪到末尾,然后将 \(b\) 向前挪并让末尾的 \(A\) 尽可能长,这对于先删 \(a\) 来说一定不劣。

我们选择操作一段 \(A\) 的前后两个 \(b\),把这段 \(A\) 转到最后,然后就和上面 \(S\) 结尾是 \(a\) 的情况相同了。

注意如果 \(S\) 开头不为 \(b\),那么我们无法让第一段 \(A\) 转到最后。

如果 \(S = \dots B_1aB_2\),且 \(|B_2| \le 2\),那么我们不能挪动中间的 \(a\)。因为如果操作完之后更优,应该满足 \(|B_1|-1+|B_2|-1 > |B_1|\)
此时我们把前面的 \(a\) 两两删掉,留下最后的一个 \(a\) 即可。
对应答案 \(BAB\)

代码

inline int w(int w1,int w2){return 2*w2+w1+(w1&1);
}
inline void solve(){int len = strlen(s+1);for(int i=1;i<=len;++i){cnta[i] = cnta[i-1]+(s[i]=='a');cntb[i] = cntb[i-1]+(s[i]=='b');}if(!cnta[len] || !cntb[len]){for(int i=1;i<=len;++i) putchar(s[i]);return ;}if(s[len]=='b' && !(cnta[len]&1)){for(int i=1;i<=cntb[len];++i) putchar('b');return ;}if(cnta[len-cntb[len]]==cnta[len] && (cnta[len]&1)){putchar('a');for(int i=1;i<=cntb[len];++i) putchar('b');return ;}if(s[len]=='b'){int lasa = len;for(int i=len;i;--i){if(s[i]^'b'){lasa = i;break;}}if(len-lasa<=2){for(int i=1;i<=cntb[lasa];++i) putchar('b');putchar('a');for(int i=cntb[lasa]+1;i<=cntb[len];++i) putchar('b');return ;}}int las = 0,w1 = 0,w2 = 0;for(int i=1;i<=len;++i){if(s[i]=='b'){if(i-1-(las+1)+1==1) ++w1;else if(i-1-(las+1)+1>1) ++w2;las = i;}}if(s[len]=='a'){for(int i=1;i<=cntb[len];++i) putchar('b');for(int i=1;i<=cnta[len]-w(w1,w2);++i) putchar('a');return ;}int tw = 0;if(s[1]=='b')tw = Min(w(w1-1,w2),w(w1,w2-1));else{int f = -1;for(int i=1;i<=len;++i){if(s[i]=='b'){f = (i>3);break;}}if(f){if(w2==1) tw = w(w1-1,w2);else tw = Min(w(w1-1,w2),w(w1,w2-1));}else{if(w1==1) tw = w(w1,w2-1);else tw = Min(w(w1-1,w2),w(w1,w2-1));}}for(int i=1;i<=cntb[len]-2;++i) putchar('b');for(int i=1;i<=cnta[len]-tw;++i) putchar('a');
}
http://www.hskmm.com/?act=detail&tid=22121

相关文章:

  • 2025年西咸新区高端楼盘,西安刚需楼盘,沣东改善楼盘住宅口碑推荐,地建嘉信臻境3分钟通达高新,区位优势明显
  • P12704 Retribution
  • Sunny Pro 网络验证- 仅需一键,即可为您的exe添加高强度防破加密!
  • 一条mysql数据库更新语句
  • 浅谈递归入门(1) - 指南
  • python+uniapp基于微信小工具的医院陪诊预约系统
  • [深度学习] 大模型学习5-高效微调框架Unsloth使用指北
  • 【APK安全】组件安全核心风险与防御指南 - 详解
  • 前端-JavaScript简介JavaScript模块化 - 努力-
  • 基本地址变换机构
  • 2025工业网线厂家权威推荐榜:千兆/拖链/高柔/网线/六类/超五类/6类/超5类/千兆/超六类/8芯/4芯/成品/相机/视觉数据工业网线高强屏蔽与稳定传输实力之选
  • gitee 使用安装教程
  • VisualMimic——基于视觉的人形行走-操作控制:低层策略负责平衡控制且跟踪高层下发的指令、高层策略则基于自我中心视觉输入生成任务跟踪指令 - 实践
  • 基本分页存储管理的基本概念
  • luogu P6503 [COCI 2010/2011 #3] DIFERENCIJA
  • 详细介绍:自动化接口框架搭建分享-pytest第三部分
  • Solon Plugin 自动装配机制详解
  • 2025宅基地纠纷律所权威推荐榜:专业调解与胜诉保障实力之选
  • 2025上海骨灰盒哪里买优质厂家权威推荐榜:匠心工艺与品质服务之选
  • 实用指南:华为 HCIA-Datacom 备考:VRP 通用路由平台原理-实操
  • Voice Agent Camp 结营!完整项目名单公布丨超音速计划 2025
  • 2025上海寿衣哪里买权威推荐:优质供货商与暖心服务之选
  • AI 真能胜任专业工程师的工作吗?
  • 容器中与内存相关的几个参数
  • 第一次软工作业
  • OpenWRT中备份多个docker容器的脚本 -
  • 动态分区分配算法
  • 上海殡葬一条龙服务权威推荐:寿衣、骨灰盒购买定制服务暖心陪伴与专业仪式之选
  • potplayer截图
  • OpenAI发布提示词集