比赛链接：Dashboard - Codeforces Round 833 (Div. 2) - Codeforces
B. Diverse Substrings
题意：
思路：
当字符串长度 > 10 时，每个字符出现的次数至少是 2 次 ( 0 ~ 9 个出现一次，剩余字符出现 )
当字符串长度 > 20 时，每个字符出现的次数至少是 3 次
......
当字符串长度 > 100 时，每个字符出现的次数至少是 11 次
但是数字种类就只有 10 个 ( 0 ~ 9 )，所以当字符串长度 > 100时，一定是错误的
所以只用枚举长度在 100 以内的即可
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{int n; cin >> n;string s; cin >> s;int ans = 0;for( int i = 0 ; i < n ; i++){int cnt[10] = { 0 };int mx = 0; int temp = 0;for( int j = i ; j < min( i + 101 , n ) ; j++ ){if( cnt[ s[j] - '0' ] == 0 ) temp++;cnt[ s[j] - '0' ]++;mx = max( mx , cnt[s[j] - '0']);if( temp >= mx )ans++;}}cout << ans << endl;
}
signed main()
{int tt; cin >> tt;while(tt--)solve();return 0;
}C. Zero-Sum Prefixes
题意：
思路：（贪心）
n = 9
a = 1 0 0 1 -1 0 1 0 -1
前缀和 1 1 1 2 1 1 2 2 1
x y z p
要使前缀尽量变为0 ，所以这个数就要尽量变成 [ y , z )中前缀和的众数的相反数，此时贡献最大
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{int n; cin >> n;vector<int> a(n + 1);for( int i = 1; i <= n; i++ ) cin >> a[i];vector<int> pre(n + 1);vector<int> b;for( int i = 1; i <= n; i++){pre[i] = pre[i-1] + a[i];if( !a[i] ) b.push_back(i);}if( b.size() == 0 ) // 没有0的时候单独讨论一下{int ans = 0;for( int i = 1 ; i <= n; i++) {if( pre[i] == 0 ) ans++;}cout << ans << endl;return;}int ans = 0;for( int i = 1 ; i < b[0] ; i++)if( !pre[i] )ans++; // 在第一个0之前的前缀和有多少贡献b.push_back( n + 1 ); // 为了下面与 b[ i + 1 ]那个方便for( int i = 0 ; i < b.size() - 1 ; i++){map<int,int> mp;int mx = 0;for( int j = b[i] ; j < b[i + 1] ; j++){mp[pre[j]]++;mx = max( mx , mp[pre[j]] ); // 找众数}ans += mx;}cout << ans << endl;
}
signed main()
{int tt; cin >> tt;while(tt--)solve();return 0;
}