CF1063A 【Oh Those Palindromes】
2024-10-15 12:14:38
考虑在一个部分串中加入字符使得最终构造的串回文子串最多的方案
考虑简单情况,对于只含一种元素的串,我们要插入其他元素
记原有元素为$a$,新加元素为$b$
考虑$b$的最优插入位置
原串$aaaa...aa$,插入$b$
设$b$在串中的插入位置为$pos$,插入后,原本的回文串$[pos-i,pos+j](i!=j)$会因此不匹配
所以这样不会使得原串匹配结果变多
所以我们要让各个元素独立才是最优方案
#include<iostream>
#include<cstdio>
using namespace std;
string s;
char ans[];
int l,cnt[],cnts;
int main()
{
cin>>l>>s;
for(int i=;i<l;i++)
cnt[s[i]-'a']++;
for(int i=;i<;i++)
for(int j=;j<=cnt[i];j++)
ans[cnts++]=i+'a';
printf("%s\n",ans);
return ;
}
最新文章
- 【原创】开源Math.NET基础数学类库使用(02)矩阵向量计算
- 三种POST和GET的提交方式
- 解决xampp端口冲突
- 常用JS效果 需要时更新。。。
- php应用路径变量问题总结
- leetcode98 Validate Binary Search Tree
- mysql查看数据库命令
- hduAnother Graph Game
- 【HDOJ】1348 Wall
- Eclipse设置Android Logcat输出字体大小
- java使用maven创建springmvc web项目
- zookeeper简单介绍
- Hibernate @Embeddable注释
- VBA /VB/VB中合成分散数据方法
- 树莓派3B+(一)
- eclipse 界面开发--windowbuilder
- jquery发起get/post请求_或_获取html页面数据
- Nginx下配置网站ssl实现https访问
- swift - self的弱引用
- Python:正则表达式概念
热门文章
- 【Vue学习笔记1】全局配置 Vue.config
- java 方法的返回类型
- JSP 获取真实IP地址的代码
- Vasya and Multisets CodeForces - 1051C(英语限制了我的想象力)
- 【刷题】BZOJ 1124 [POI2008]枪战Maf
- 【题解】Luogu P2047 社交网络总结 (Floyd算法,最短路计数)
- SP8093 JZPGYZ - Sevenk Love Oimaster 解题报告
- 洛谷 P5108 仰望半月的夜空 解题报告
- 51nod1134——(最长上升子序列)
- POJ 1502 MPI Maelstrom / UVA 432 MPI Maelstrom / SCU 1068 MPI Maelstrom / UVALive 5398 MPI Maelstrom /ZOJ 1291 MPI Maelstrom (最短路径)