题目链接

题目大意：

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

解题思路：

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

总结：

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

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

本题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——B题题解

题目链接

题目大意：

解题思路：

总结：

本题AC代码：

最新文章

热门文章