A

• 给定一个串，sum初始为1，遇到-，sum-1，遇到*，sum*2，求给定串能否使得sum>=2025

思路

• 直接模拟即可

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    int sum=1;
    for(int i=0;i<s.size();i++){
        if(s[i]=='-'){
            sum-=1;
        }else{
            sum*=2;
        }
        if(sum>=2025){
            printf("YES\n");
            return 0;
        }
    }
    printf("NO\n");
}

B

• 长度n的串，最多删一个，能否使得整个串任意两个相邻位置不同

思路

• 模拟，删了以后可能还是相同，如：aaa,记得判断就行

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    char s[202020];
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%c",&s[i]);
    }
    int cnt,idx;
    for(int i=2;i<=n;i++){
        if(s[i]==s[i-1]){
            cnt++;
            idx=i;
        }
        if(cnt>1){
            printf("NO\n");
            return 0;
        }
    }
    if(cnt==1&&idx!=n){
        if(s[idx+1]==s[idx]){
            printf("NO\n");
            return 0;
        }
    }
    printf("YES\n");
}

C

• 给定若干数组，不改变数组内元素的相对顺序，能否使得所有数组拼接后变为连续数组

思路

• 只要每个数组不含逆序对，且集合的元素个数等于k的和且最大最小值差值等于k的和

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	set<int> a;
	int q;
    long long sum=0;
	int mx=-1,mn=1e9+7;
	scanf("%d",&q);
	for(int i=0;i<q;i++){
		int k;
		scanf("%d",&k);
        sum+=k;
		int now,pre=-1;
		for(int i=0;i<k;i++){
			scanf("%d",&now);
			if(now<=pre){
				printf("NO\n");
				return 0;
			}
			mx=max(mx,now);
			mn=min(mn,now);
			a.insert(now);
			pre=now;
		}
	}
	if(a.size()==mx-mn+1&&a.size()==sum){
		printf("YES\n");
	}else{
		printf("NO\n");
	}
	return 0;
}

D

• 给定一个n个自然数组成的数组，每次给数组每一个元素减去当前的mex(未出现的最小非负数)，问进行几次操作可以将数组中的每一个元素变为相同数，特别的，如果无法使得每个元素相同，输出-1

思路

• 将数组分段{0,1,2,4,5,7,8,9}变为|0,1,2|,|4,5|,|7,8,9|，会发现每一个小段会同时变为0，而在一个段落变为0后，另一个段落段首直到变为1之前，每次mex都是1
• 综上，把每一段变为1需要前一段的段首值-上一段的段尾-1次，所以，对每一个分段求和即可，最后要把最后一段从1变成0，故还要加一

AC代码一

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[202020];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%lld",&a[i]);
    }
    sort(a,a+n);
    long long ans=0;
    if(a[0]==a[n-1]){printf("0\n");return 0;}
    if(a[0]!=0){printf("-1\n"); return 0;}
    for(int i=1;i<n;i++){
        if(a[i]-a[i-1]>1){
            ans+=a[i]-a[i-1]-1;
        }
    }
    printf("%lld\n",ans+1);
    return 0;
}

思路二

• 差分处理原数组，每次将差分数组前面的01串全变为0，然后对于非01元素，会发现每次操作会将该元素-1，综上靠差分也可以呃做出该题

AC代码二

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
i64 n, pd, ans;
i64 a[100005];
void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        if (a[i] != a[1]) pd = 1;
    }
    if (!pd) cout << "0\n", exit(0);
    if (a[1]) cout << "-1\n", exit(0);
    for (int i = 2; i <= n; i++) ans += max(0LL, a[i] - a[i - 1] - 1);
    cout << ans + 1 << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}