暑期cspj模拟赛8

#T1
过于简单,直接代码

#include<bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    long long ans = 0;
    for (int i = 0; i < n; i += 3) {
        // 每组的最大值是 a[i+2]，最小值是 a[i]
        ans += a[i + 2] - a[i];
    }

    cout << ans << endl;

    return 0;
}

#T2

#include<bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        string s1, s2;
        cin >> s1 >> s2;
        int s = 0;

        string re1;
        string re2;
        for (int i = 0; i < s1.size(); i++) {
            if(s1[i] == 'S') {
                s++;
            }else {
                if (re1.size() && re1.back() == s1[i]) {
                    re1.pop_back();
                }else {
                    re1.push_back(s1[i]);
                }
            }

        }
        for (int i = 0; i < s2.size(); i++) {
            if(s2[i] == 'S') {
                s--;
            }else {
                if (re2.size() && re2.back() == s2[i]) {
                    re2.pop_back();
                }else {
                    re2.push_back(s2[i]);
                }
            }
        }

        if (s %2 == 0 && re1 == re2) {
            cout << "Yes" << endl;
        }else {
            cout << "No" << endl;
        }

    }
    return 0;
}

#T3

#include<bits/stdc++.h>
using namespace std;

int a[1000010];
long long dp[1000010][3];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // freopen("input.txt", "r", stdin);

    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    // 初始化（处理第一个元素）
    dp[1][0] = a[1]; // 未异或，以1结尾的最大子段和
    dp[1][1] = (a[1] ^ k); // 正在异或区间，以1结尾的最大子段和
    dp[1][2] = 0; // 已结束异或区间（不可能，因为只有一个元素），初始设为极小值

    long long ans = max({dp[1][0], dp[1][1], dp[1][2]});
    for (int i = 2; i <= n; ++i) {
        long long curr = a[i];
        long long curr_xor = curr ^ k;
        // 状态转移：计算新的 dp0, dp1, dp2
        dp[i][0] = max({dp[i-1][0] + curr, curr});
        dp[i][1] = max({curr_xor, dp[i - 1][0] + curr_xor, dp[i - 1][1] + curr_xor});
        dp[i][2] = max({dp[i - 1][2] + curr, curr, dp[i - 1][1] + curr});
        // 更新全局最大值
        ans = max({ans, dp[i][0], dp[i][1], dp[i][2]});
    }

    cout << max(ans, 0ll) << endl;

    return 0;
}

#T4

来自TDER

#include<bits/stdc++.h>
using namespace std;
int main()
{

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	long long n,k;
	cin>>n>>k;
	vector<long long> a(n);
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	unordered_map<long long,long long> mapp;
	long long ans=0,last=0;
	for(int i=0;i<n;i++)
	{
		mapp[a[i]]++;
		if(mapp[a[i]]>=k)
		{
			ans+=n-i;
			last=i;
			break;
		}
	}
	for(int i=0;i<n;i++)
	{
		mapp[a[i]]--;
		if(a[i]==a[last])
		{
			while(mapp[a[last]]<k && last<n)
			{
				last++;
				mapp[a[last]]++;
			}
		}
		ans+=n-last;
	}
	cout<<ans;
	return 0;
}

来自LJY

#include<bits/stdc++.h>
using namespace std;
long long n,k,a[100010];
unordered_map<long long,vector<long long>> mp;
unordered_map<long long,long long> cnt;
long long b[100010],ans;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(!mp[a[i]].size()){
			mp[a[i]].push_back(i-1);
		}
		mp[a[i]].push_back(i);
	}
	b[0]=-1e18;
	for(int i=1;i<=n;i++){
		cnt[a[i]]++;
		//cout<<"cnt:"<<cnt[a[i]]<<'\n';//c
		if(cnt[a[i]]<k){
			b[i]=b[i-1];
		}else{
			b[i]=max(b[i-1],mp[a[i]][cnt[a[i]]-k+1]-1);
		}
	}
	for(int i=1;i<=n;i++){
		//cout<<b[i]<<'\n';//c
		if(b[i]==-1e18){
			continue;
		}
		ans+=b[i]+1;
	}
	cout<<ans<<'\n';
	return 0;
}