首页 > 其他分享 >833——B题题解

833——B题题解

时间:2022-11-13 21:14:03浏览次数:75  
标签:子串 833 字符 int 题解 算法 最优 define

题目链接

题目大意:

给一串字符串(只包含0~9),定义一个最优子串的定义:如果该子串同字符种类数大于最最多字符出现数,那么这个子串可以被称为最优子串。

解题思路:

大眼一看这个数据范围他用n^2的算法他不就超时了嘛。确实会超时,不过我们向里面去思考一下,字符因为限制为0~9了,所以子串超过100的时候他一定不是最优子串,所以我们枚举的n^2就变成了100*n了,这样我们呢就可以用朴素算法过了这道题目了。

总结:

遇到问题不要慌,当他数据量很大的时候他就会有两道路去优化

  1. 去寻找更高效的算法,如:n^2 -> nlog(n)
  2. 去进行剪枝优化。

本题AC代码:

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i <= (k); --i)
#define ll long long
#define sz(a) ((int) (a).size())
#define vi vector< int >
#define me(a, x) memset(a, x, sizeof(a))
#define ull unsigned long long

using namespace std;

const int N = 1e5 + 7;
int n, m, t;
int a[N];
char s[N];
int st[20];

void Main()
{
	cin >> n;
	cin >> (s + 1);
	L(i, 1, n)
		{
			a[i] = s[i] -'0';
		}
	int res = 0;
	
	L(i, 1, n)
		{
			me(st, 0);
			int cnt = 0, mx = 0;
			for(int j = i; j <= min(n, i + 99); j ++ )
			{
				if(!st[a[j]])
				{
					st[a[j]] = 1;
					cnt ++;
					mx = max(mx, st[a[j]]);
				}
				else
				{
					st[a[j]] ++;
					mx = max(mx, st[a[j]]);
				}
				if(cnt >= mx) res ++ ;
			}
		} 
		
	cout << res << '\n';

}


int main(){
	ios :: sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> t;
	while(t--) Main();
	return 0;
}

/* stuff you should look for 你应该寻找的东西
 * int overflow, array bounds (int)溢出,数组边界
 * special cases (n=1?) 特殊情况(n=1?)
 * do smth instead of nothing and stay organized 做一些事情而不是什么也不做,保证效率
 * WRITE STUFF DOWN 将东西写下
 * DON'T GET STUCK ON ONE APPROACH 不要在一个地方死磕
 */

 

标签:子串,833,字符,int,题解,算法,最优,define
From: https://www.cnblogs.com/msluli/p/16886953.html

相关文章

  • [ARC086F] Shift and Decrement 题解
    linkSolution一个简易的贪心想法是我们肯定是对于一个相同的序列求出操作到它的最小操作次数,看能否\(\leK\)。注意到我们在第\(x\)次A操作后进行\(-1\)操作相当于......
  • 833(DIV2)——C题题解
    题目链接题目大意:给定n个数,你可以对数值为0的数改变其为任意值,问最后前缀和为0的个数的最大值。思路:这题比较可惜,自己的思路没有问题,但是他少了一些东西。对数组进行前......
  • LG_P4588 [TJOI2018] 数学计算 题解
    LuoguP4588题解这个玩意还是挺好想到的,也不难看出他是一个线段树。没想到可以评上蓝。考虑每次操作对于答案的贡献。由于\(x=1\),所以我们相当于是在维护一堆数的积,初始......
  • DTOJ 3498 无限剑制 题解
    题面题目链接题解想了好久,其实很水tt想写题解主要是因为这题题面是Fate很有意思我们注意到“所有\(v_i\)值域在\([1,5]\)”这个部分分,这种情况下,初始的不同情......
  • DTOJ 5932 Counting 题解
    题目链接portal题解认识到了生成函数很好用,于是摆了一篇题解10分直接dp,\(f_{i,j}\)表示走了\(i\)步之后,当前位置在\(j\)的方案数然后就有状态转移方程\(f_{i,......
  • DTOJ 5769 下棋 题解
    题目链接portal题解首先比较容易想到\(dp\),因为任意一段绝对值不超过\(k\),所以白棋个数减黑棋个数要在\([-k,k]\)区间里,我们于是考虑把状态设为白棋减黑棋个数......
  • DTOJ 5093 淘淘种地 题解
    题面题目链接题解这个是CSP前最后一场测试的T2,打的不是很好,没有想到这题正解,但是这题暴力分很多ww二进制拆位的思想要有((30分暴力模拟\(O(nmT)\)70分满足\(1\le......
  • DTOJ 6316 沙丘 题解
    DTOJ6316沙丘题解题面:http://59.61.75.5:8018/p/P6316在满天的星光下,灰大狼一人孤独地堆起了小沙丘。有\(n\)堆沙丘,每堆沙丘有相对高度\(h_i\),每次灰大狼可以选择......
  • CF1748E Yet Another Array Counting Problem 题解
    可能更好的阅读体验题目传送门题目大意给定一个长度为\(n\)的序列\(a\)和\(m\),定义\([l,r]\)的最左边的最大值为最小的\(l\lei\ler\)满足\(x_i=\max\{a_......
  • CF1748D ConstructOR 题解
    可能更好的阅读体验题目传送门题目大意给定\(a,b,d\),要求找到一个\(0\lex\le2^{60}\),满足\(a|x,b|x\)都是\(d\)的倍数(\(|\)代表按位或)。\(T\le10^4\),\(0\le......