T1

模拟，排序

• 注意成绩相同按编号从小到大排序，以及保留两位小数

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

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    vector<int> a(n), sc(n, 10);
    vector b(n, vector<int>(m));
    for (auto &x : a) scanf("%d", &x);
    for (auto &v : b) for (auto &x : v) scanf("%d", &x);
    for (int k, x, i = 0; i < m; ++i) {
        scanf("%d", &k);
        while (k--) scanf("%d", &x), --x, !b[x][i] ? --sc[x] : 0;
    }
    vector<pair<int, int>> ans(n);
    for (int i = 0; i < n; ++i) ans[i] = {40 * max(0, sc[i]) + 6 * a[i], -i};
    sort(ans.begin(), ans.end(), greater<>());
    for (auto [x, y] : ans)
        printf("%d %.2lf\n", -y + 1, x * 0.1);
    return 0;
}

T2

给 个字符串，任意删除一个非空区间的字符串，最大化完全相同字符串的区间长度。

• 字符串哈希转换为数字序列
• 预处理 表示上一个/下一个哈希值不等于 的位置
• 对于一个分段点 ，答案为
• 开 个 set 维护相同 的连续段长度
• 从后往前枚举分段点 ，将 从 中删除，统计答案
• 注意边界条件，

#include <bits/stdc++.h>
using namespace std;
const int B = 97, P = 1e9 + 7;
const int N = 1e6 + 5;
int pw[N]; char str[N];
int main() {
   pw[0] = 1;
   for (int i = 1; i < N; ++i) pw[i] = 1ll * pw[i - 1] * B % P;
   int n, m = 0, ans = 1;
   scanf("%d", &n);
   vector<int> a(n);
   unordered_map<int, int> mp;
   for (int i = 0; i < n; ++i) {
       scanf("%s", str);
       int L = strlen(str), &k = a[i];
       for (int j = 0; j < L; ++j)
           k = (1ll * k * B + str[j] - 'a') % P;
       if (!mp.count(k)) mp[k] = m++;
       k = mp[k];
   }
   vector<int> pre(n), nxt(n);
   pre[0] = -1, nxt[n - 1] = n;
   for (int i = 1; i < n; ++i)
       if (a[i] == a[i - 1]) pre[i] = pre[i - 1];
       else pre[i] = i - 1;
   for (int i = n - 2; i >= 0; --i)
       if (a[i] == a[i + 1]) nxt[i] = nxt[i + 1];
       else nxt[i] = i + 1;
   map<int, set<pair<int, int>>> f;
   for (int i = 0; i < n; ++i)
       f[a[i]].insert({i - pre[i], i});
   for (int i = n - 1; i >= 0; --i) {
       f[a[i]].erase({i - pre[i], i});
       int res = i < n - 1 ? nxt[i + 1] - (i + 1): 0;
       if (0 < i && i + 1 < n && !f[a[i + 1]].empty())
           res += f[a[i + 1]].rbegin()->first;
       ans = max(ans, res);
   }
   printf("%d\n", ans);
   return 0;
}

T3

个人依次采矿，第 个人会采集所有深度不超过 的矿物； 个矿脉，第 个矿脉在深度 都有 1 单位矿物。问每个人分别能采集多少单位矿物？

• 对 排序，如果 ，则有：

• 

• 每次更新 ，双指针维护 upper_bound 即可。

#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
int main() {
   int n, m;
   scanf("%d%d", &n, &m);
   vector<int> a(n), b(m);
   vector<ll> ans(n);
   for (auto &x : a) scanf("%d", &x);
   for (auto &x : b) scanf("%d", &x);
   sort(b.begin(), b.end());
   for (int i = 0, j = 0, h = 0; i < n && j < m; ++i) {
       if (a[i] <= h) continue;
       ll &sum = ans[i];
       while (j < m && a[i] >= b[j]) sum += b[j++] - h;
       sum += 1ll * (m - j) * (a[i] - h), h = a[i];
   }
   for (auto x : ans) printf("%lld ", x);
   return 0;
}