【CF1073A】Diverse Substring(签到)
2024-09-29 17:43:24
题意:给定一个由小写字母组成的串,要求找出一个子串使得其中出现最多的字母不超过它长度的一半下取整
n<=1e3
思路:
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef vector<int> VI;
#define fi first
#define se second
#define MP make_pair
#define N 11000
#define MOD 1000000007
#define eps 1e-8
#define pi acos(-1) int s[N][];
char ch[N]; int main()
{
int n;
scanf("%d",&n);
scanf("%s",ch+);
for(int i=;i<=n;i++)
{
for(int j=;j<=;j++) s[i][j]=s[i-][j];
s[i][ch[i]-'a'+]++;
}
int x=;
int y=;
for(int i=;i<=n;i++)
for(int j=i;j<=n;j++)
if(x+y==)
{
int len=j-i+;
int tmp=;
for(int k=;k<=;k++) tmp=max(tmp,s[j][k]-s[i-][k]);
if(tmp<=len/){x=i; y=j;}
} if(x+y>)
{
printf("YES\n");
for(int i=x;i<=y;i++) printf("%c",ch[i]);
}
else printf("NO\n");
return ;
}
最新文章
- 【WCF】使用“用户名/密码”验证的合理方法
- Leetcode Insert Interval
- 【dubbo】zookeeper搭建
- mongoDB研究笔记:分片集群的工作机制
- 实现服务器端与客户端的实时通信 SignalR(1)
- SQL Server里如何随机记录集
- 大概了解了flexbox
- 数据结构 《6》----堆 ( Heap )
- Golang中解析json,构造json
- python 3.5 购物小程序
- Spring流程
- Android加载图片的策略
- 030.Zabbix分布式部署
- maven私服的使用
- zabbix系列之监控类型及方式
- linux笔记_day11_shell编程
- xml &; <; 需要转义
- pageadmin CMS网站建设教程:网页设计的常用参数
- select子句排列顺序与聚集函数
- CentOS7中永久保存systemd日志