题解2023.5.21

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++;
            else
                y++;
        }
    }
    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){};