B. Diverse Substrings
思路：直接枚举超时，数的种类为0-9，所以对于每个位置只需往后延伸100位即可，超过100位必重复
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(fast)
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<math.h>
#include<map>#include<vector>
#define ms(x,y) memset(x,y,sizeof x)
#define fu(i,a,b) for(int i=a;i<=b;i ++ )
#define fd(i,a,b) for(int i=a;i>=b;i -- )
#define int long long
const int maxn=2e5+10,INF = 0x3f3f3f3f ;
using namespace std;
int a[maxn];int i,j,k;void solve() {int n; string s;cin >> n >> s;int ans = 0;for (int i = 0; i < n; i++) {vector<int> cnt(10);int Max = 0, sum = 0;for (int j = i; j < min(n, i + 100); j++) {if (++cnt[s[j] - '0'] == 1)sum++;Max = max(Max, cnt[s[j] - '0']);if (sum >= Max) ans++;}}cout << ans << endl;}
signed main()
{ios::sync_with_stdio(false);int t;cin >> t;while (t--) {solve();}}
B - Tying Rope
思路：vector二维数组存图，对于相连的全部度数为2则形成循环，否则不
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<math.h>
#include<map>
#include<vector>
#define int long long
const int maxn = 2e5 + 10;
using namespace std;
bool vis[maxn];
int d[maxn];
void solve() {int n, m;cin >> n >> m;vector<vector<int>>a(n + 1, vector<int>());for (int i = 1; i <= m; i++) {int u, v;char c1, c2;cin >> u >> c1 >> v >> c2;a[u].push_back(v);a[v].push_back(u);d[u]++, d[v]++;}memset(vis, 0, sizeof vis);int x = 0, y = 0;for (int i = 1; i <= n; i++) {if (!vis[i]) {queue<int> q;q.push(i);bool flag = 0;vis[i] = true;while (!q.empty()) {int qu = q.front();q.pop();if (d[qu] != 2)flag = 1;for (auto z : a[qu]) {if (!vis[z]) {q.push(z);vis[z] = true;}}}if (!flag)x++;elsey++;}}cout << x << ' ' << y << '\n';
}
signed main()
{ios::sync_with_stdio(false);solve();
}B. Restore the Weather
思路1：最优策略（与k无关）为：排序为a,b均从小到大排序，根据a位置输出b位置，采用结构体排序
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(fast)
#include<iostream>#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<math.h>
#include<map>
#define int long long
const int maxn=2e5+10;
using namespace std;
int b[maxn];
struct node {int x;int y;
}a[maxn];
bool cmp(node A,node B) {return A.y < B.y;
}
bool cmp1(node A, node B) {return A.x < B.x;
}void solve(){int n, k;cin >> n >> k;for (int i = 1; i <= n; i++) {a[i].x = i;cin >> a[i].y;}for (int j = 1; j <= n; j++) {cin >> b[j];}sort(b + 1, b + 1 + n);sort(a + 1, a + 1 + n, cmp);for (int i = 1; i <= n; i++) {a[i].y = b[i];}sort(a + 1, a + 1 + n, cmp1);for (int i = 1; i <= n; i++) {cout << a[i].y << ' ';}cout << '\n';}
signed main()
{ios::sync_with_stdio(false);int t;cin >> t;while (t--) {solve();}
}G. Hits Different
采用dp,dp公式 dp[i][j]=k*k+dp[i-1][j]+dp[i-1][j-1]-(重复部分)dp[i-2][j-1]
#include<iostream>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
const int maxn = 1e6 + 10;
int dp[3000][3000];
int a[maxn];
void solve() {int n;cin >> n;cout << a[n] << '\n';}
void init() {dp[1][1] = 1;a[1] = 1;int k = 2;for (int i = 2; i <= 3000; i++) {for (int j = 1; j <= i && k <= 1000000; j++, k++) {dp[i][j] = k * k + dp[i - 1][j] + dp[i - 1][j - 1] - dp[i - 2][j - 1];a[k] = dp[i][j];}}
}
signed main()
{ios::sync_with_stdio(false);init();int t;cin >> t;while (t--) {solve();}
}C.Zero - Sum Prefixes
思路：无论前面怎么操作，前缀和在这个位置保持一致
最优操作把出现0位置后前缀和值出现最多的次数变成0,统计相加，最后加上第一个0前面前缀和为0个数
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(fast)
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<math.h>
#include<map>
#include<vector>
#define ms(x,y) memset(x,y,sizeof x)
#define int long long
const int maxn = 2e5 + 10, INF = 0x3f3f3f3f;
using namespace std;
int a[maxn], b[maxn];
int i;
void solve() {int n;cin >> n;int ans = 0;vector<int>v;for (int i = 1; i <= n; i++) {cin >> a[i];b[i] = a[i] + b[i - 1];if (a[i] == 0) {v.push_back(i);}}v.push_back(n + 1);map<int, int>cnt;for (int i = 1; i < v.size(); i++) {int Max = 0;cnt.clear();for (int j = v[i-1]; j < v[i]; j++) {cnt[b[j]]++;Max = max(Max, cnt[b[j]]);}ans += Max;}for (int i = 1; i < v[0]; i++) {if (b[i] == 0) {ans++;}}cout << ans << '\n';
}
signed main()
{ios::sync_with_stdio(false);int t;cin >> t;while (t--) {solve();}
}
lower_bound() 函数用于在指定区域内查找不小于目标值的第一个元素。
c++语言中，multiset是<set>库中一个非常有用的类型，它可以看成一个序列，插入一个数，删除一个数都能够在O(logn)的时间内完成，
而且他能时刻保证序列中的数是有序的，而且序列中可以存在重复的数。(可搭配erase,lower_bount使用)
自定义排序bool cmp(类型 A,类型 B){};
