板子

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

const int inf = 0x3f3f3f3f;
using ll = long long;
using ld = long double;

#define MOD 1000000007
#define mod 998244353
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define longer __int128_t
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<vector<int> >;
using vll = vector<vector<ll> >;

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	return 0;
}

A题：

知识点：贪心，数学，前缀和

难度：1300 思路：题目要求求出 [l,r] 中所有数对于 m 取模后相加的数值，然后对于每个测试样例求出后的数值进行异或和，我们下面介绍处理一组测试样例我们可以发现， [l,r] 中的每一个数对于 m 取模后的数值是有规律的，比如 [2,10] 对于 3 取模：2,0,1,2,0,1,2,0,1 可以明显的发现出现了段数的规律，知道了这一点，我们可以将问题进行简化，[l, r] 相当于进行求 [1, r] 减去 [1, l-1]。因为这样化简后我们不需要处理前面不正常的段数，只需要进行处理后面不正常的段数即可。

ll l, r, m;
ll sol(ll num) {
    return num*(num+1)/2; // 段数的总和
}

ll g(ll len) {
    return len/m * sol(m-1) + sol(len%m); // 成段的数加上后面没成段的数
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T; cin >> T;
    vl ac;
    while (T--) {
        cin >> l >> r >> m;
        ll ans = g(r) - g(l - 1); // 化简
        ac.pb(ans);
    }

    for (int i = 1; i < (int)ac.size(); i++) {
        ac[0] ^= ac[i]; // 进行取异或和
    }
    cout << ac[0] << endl;
    return 0;
}

H题：

知识点：贪心，模拟

难度：1100

思路：题目要求求出将数组中任意一个位置修改成（也可以不修改）任意的一个数后满足题意条件的最大值

我们可以发现，题中数据范围很小，可以进行双层 for 循环，因此我们可以进行修改一个位置为很大或者很小的数值让它直接爆发，然后我们进行模拟即可

int n, l, r;

int sol(int xou, vi a) {
    int p = 1; // 由于直接爆发，我们这里就直接计为 1 了
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        if (i == xou) {
            sum = 0;
            // 这里没有进行 p++ 是因为上面进行了 p 的初始化
            continue;
        }
        sum += a[i];
        if (sum < l || sum > r) {
            sum = 0;
            p++;
        }
    }
    return p;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> l >> r;
    vi a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    int sum = 0;
    int ans = 0;
    // 模拟初始答案
    for (int i = 1; i <= n; i++) {
        sum += a[i];
        if (sum < l || sum > r) {
            ans++;
            sum = 0;
        }
    }

    // 模拟直接爆发的点
    for (int i = 1; i <= n; i++) {
        ans = max(ans, sol(i, a));
    }

    cout << ans << endl;

}

I 题：

知识点：贪心，优先队列，数据结构

难度：1633

思路：如果加入一张牌后如果不超过 4 张直接加入即可，如果超过了 4 张需要弃掉未来第一次出现最晚才会用到牌是最优策略，因为它对未来的影响最小。未现第一次出现最晚的牌如何判断呢？我们这里选优先队列进行即可

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    ll n; cin >> n;
    vl a(n);                // 出牌顺序（每次需要的牌）
    vl lpos(n, inf);        // lpos[i] 表示第 i 张牌未来第一次出现的位置
    map<int, int> last;     // 记录每张牌最后出现的位置

    for (int i = 0; i < n; i++) cin >> a[i];
    // 处理未来第一次出现的位置（倒着遍历）
    for (int i = n - 1; i >= 0; i--) {
        if (last.count(a[i])) {
            lpos[i] = last[a[i]];   // 如果未来还会出现，记录下次出现位置
        }
        last[a[i]] = i;             // 更新最后出现位置
    }

    ll ac = 0;              // 失误次数（摸牌次数）
    set<int> ans;           // 当前手牌集合
    priority_queue<PLL> q;  // 优先队列，存储 {未来出现位置, 牌}，用于决定弃牌

    for (int i = 0; i < n; i++) {
        if (ans.count(a[i])) {
            // 如果当前需要的牌已经在手牌中，直接使用，不算失误
            q.push({lpos[i], a[i]});
        } else {
            // 否则必须摸牌，失误 +1
            ac++;
            if (ans.size() < 4) {
                // 如果手牌未满，直接加入
                q.push({lpos[i], a[i]});
                ans.insert(a[i]);
            } else {
                // 如果手牌已满，必须弃掉一张牌再加入新牌
                // 弃掉未来第一次出现最晚才会用到的牌
                auto [u, v] = q.top(); q.pop();
                ans.erase(v);
                q.push({lpos[i], a[i]});
                ans.insert(a[i]);
            }
        }
    }

    cout << ac << endl;
    return 0;
}