首页 > 其他分享 >CF1748B题解

CF1748B题解

时间:2023-01-17 11:24:47浏览次数:66  
标签:子串 10 ch CF1748B 题解 ll le maxn

题目传送门

简要题意

给定一个长度为 \(n\) 的只由数字 \(0\) 到 \(9\) 组成的字符串 \(s\) ,求 \(s\) 中有多少个子串满足 所有数字出现次数的最大值小于等于出现的不同数字的数量 ,其中 \(n \le 10^5\) 。

分析

题目拿到手,先想暴力解法。我们可以直接枚举 \(s\) 的所有子串,并统计子串中数字 \(i\) 出现的次数(记为 \(cnt_i\) ),以及子串中出现的数字个数(记为 \(sum\) )。再记 \(maxn=\max(cnt_i)\) ,比较 \(maxn \le sum\) 并记录答案即可。

for(int i=1;i<=n;i++){
	memset(cnt,0,sizeof(cnt));
	maxn=0;
	sum=0;
	for(int j=i;j<=n;j++){
		int pos=a[j];
		if(!cnt[pos]) sum++;
		cnt[pos]++;
		maxn=max(maxn,cnt[pos])
		if(sum>=maxn) ans++;
	}
}

显然,这种 \(O(n^2)\) 的时间复杂度是过不去 \(n \le 10^5\) 的。所以我们考虑优化。

优化

显然,所有的数字个数不会超过 \(10\) ,所以 \(sum \le 10\) ,而 \(maxn \le 10^5\) ,所以可以得知符合条件的子串的长度一定不会大于 \(100\) (每个数字各出现 \(10\) 次)。所以,我们可以将

for(ll j=i;j<=n;j++)

改成

for(ll j=0;j+i<=n&&j<=100;j++)

这样就可以将我们的时间复杂度优化到 \(O(n\times 100)\) ,轻松 AC

完整代码

#include<bits/stdc++.h>
#define ll long long
#define ma 214514
using namespace std;
ll read(){
	char ch=getchar();
	ll x=0,f=1;
	while('0'>ch||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while('0'<=ch&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
ll t;
ll n;
ll cnt[10];
ll maxn;
ll a[ma];
ll ans=0;
ll sum=0;
char x;
int main(){
	t=read();
	while(t--){
		n=read();
		memset(cnt,0,sizeof(cnt));
		ans=0,sum=0;
		for(ll i=1;i<=n;i++){
			x=getchar();
			a[i]=x-'0';//读入时转化成字符读入,防止读入一长串数字
		}
		for(ll i=1;i<=n;i++){
			memset(cnt,0,sizeof(cnt));
			maxn=0;
			sum=0;
			for(ll j=0;j+i<=n&&j<=100;j++){
				ll pos=a[j+i];
				if(!cnt[pos]) sum++;
				cnt[pos]++;
				maxn=max(maxn,cnt[pos]);
				if(sum>=maxn) ans++;
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

标签:子串,10,ch,CF1748B,题解,ll,le,maxn
From: https://www.cnblogs.com/mukar/p/17057348.html

相关文章

  • CF1748B-Diverse Substrings
    长度为n的字符串,求出子串(只能从头尾依次删字符来得到子串)中,相同字符出现的最高次数小于等于不同字符的个数,这样的子串的个数以1~n个字符作为起点,枚举终点的位置来判断每种......
  • THUCTF MISC题解
    永不停歇的Flag生产机这是一台永不停歇的Flag生产机,它会生产出许许多多的Flag供你挑选和使用,就连这道题的Flag也是由这台生产机制造出来的。哦放心,我知道你想......
  • CF 1779C Least Prefix Sum 题解
    CF链接:LeastPrefixSumLuogu链接:Least PrefixSum${\scr\color{CornflowerBlue}{\text{Solution}}}$先来解释一下题意:给定一个数组,问最少把多少个数变成相反数,......
  • 洛谷P1496 火烧赤壁【题解】
    事先声明本题解文字比较多,较为详细,算法为离散化和差分,如会的大佬可以移步去别处看这道题的思路(因为作者比较懒,不想新开两个专题)。题目简要给定每个起火部分的起点和终点......
  • 【问题解决】Tomcat启动服务时提示Filter初始化或销毁出现java.lang.AbstractMethodEr
    问题背景最近在开发项目接口,基于SpringBoot2.6.8,最终部署到外置Tomcat8.5.85下,开发过程中写了一个CookieFilter,实现javax.servlet.Filter接口,代码编译期正常。部署到外......
  • Codeforces Round #844 (Div.1 + Div.2) CF 1782 A~F 题解
    点我看题A.ParallelProjection我们其实是要在这个矩形的边界上找一个点(x,y),使得(a,b)到(x,y)的曼哈顿距离和(f,g)到(x,y)的曼哈顿距离之和最小,求出最小值之后加h就是......
  • Codeforces Round #844 (Div.1 + Div.2) CF 1782 A~F 题解
    点我看题A.ParallelProjection我们其实是要在这个矩形的边界上找一个点(x,y),使得(a,b)到(x,y)的曼哈顿距离和(f,g)到(x,y)的曼哈顿距离之和最小,求出最小值之后加h就是......
  • Codeforces Round #844 (Div.1 + Div.2) CF 1782 A~F 题解
    点我看题A.ParallelProjection我们其实是要在这个矩形的边界上找一个点(x,y),使得(a,b)到(x,y)的曼哈顿距离和(f,g)到(x,y)的曼哈顿距离之和最小,求出最小值之后加h就是......
  • 电脑维修截图模糊问题解决方案
    微信截图时发现模糊问题可以在两个地方查看设置一、微信应用属性/兼容性中的DPI设置:点击改变高DPI设置,将2、3两处的框选选中,点击ok退出  二、微信中的通用设置:将......
  • 1.16模拟赛题解
    T1对于区间\([1,i]\)的划分方案,划分长度一定是\(i\)的因数,因此考虑暴力枚举区间长度。问题转化为快速check一段区间是不是美丽的。首先,区间内的\(-1\)一定要么......