题目链接
题目大意:
给一串字符串(只包含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,字符,int,题解,算法,最优,define From: https://www.cnblogs.com/msluli/p/16886953.html