补题链接
QOJ
Universal Cup

A. 出题

对每个元素的上下界取交集

import sys
from math import inf
input = lambda: sys.stdin.readline().rstrip()

def solve():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    min_val = [-inf] * n
    max_val = [inf] * n
    
    for _ in range(q):
        p, l, r = map(int, input().split())
        min_val[p - 1] = max(min_val[p - 1], l)
        max_val[p - 1] = min(max_val[p - 1], r)
        
    ans = 0
    for i, x in enumerate(a):
        l, r = min_val[i], max_val[i]
        if l == -inf or r == inf:
            continue
        
        if l > r:
            print('-1')
            return
        
        ans += max(0, l - x, x - r)
    
    print(ans)
    
    
for i in range(int(input())):
    solve()

I. Bingo 3

要让其余每行每列不出现小于 k 的bingo数，可以构造对角线 k, k + 1, …。

k
	k + 1
		k + 2
			k + 3

这样每行每列所出现的 bingo数一定大于等于 k。
然后排除特殊情况 k < n（一行 bingo数 为 k 都凑不出来），n * n - n + 1 < k（对角线没有 k + i 的数字可以构造）。

import sys
input = lambda: sys.stdin.readline().rstrip()

def solve():
    n, k = map(int, input().split())
    
    if k < n or n * n - n + 1 < k:
        print('No')
        return
    
    g = [[0] * n for _ in range(n)]
    cur = k
    
    for i in range(n):
        g[i][i] = cur
        cur += 1
    
    print('Yes')
    
    cur = 1
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            
            if cur == k:
                cur += n
            
            g[i][j] = cur
            cur += 1
            
        print(*g[i])    

for i in range(int(input())):
    solve()

L. 子序列

排序 + 二分 + 区间讨论

枚举子序列的最小值和最大值，如果两值之和为奇数一定没有整型平均值，可以排除。
主要麻烦点在于枚举 < 平均值 的个数， > 平均值 的个数 和 == 平均值 的个数。

用 左边指代 < 平均值 的个数
用 右边指代 > 平均值 的个数
用 中间指代 == 平均值 的个数

左边 > 右边 就需要用中间个数凑出形如 新的左边 == 新的右边 + 1 这样
左边 < 右边 就需要用中间个数凑出形如 新的左边 == 新的右边 这样
最后当前枚举的子序列的最大长度就是 新的左边 + 新的右边 + 新的中间

QOJ 没有 pypy3，直接用 python3 会 TLE，所以用 C++ 写一手。

import sys
from bisect import bisect_left
input = lambda: sys.stdin.readline().rstrip()

def solve():
    n = int(input())
    a = sorted(list(map(int, input().split())))
    
    ans = 1
    for i in range(n):
        for j in range(i + 1, n):
            val = a[i] + a[j]
            if val & 1:
                continue
            
            val >>= 1
            l_idx = bisect_left(a, val)
            if a[l_idx] != val:
                continue
            
            r_idx = bisect_left(a, val + 1) - 1
            
            l, r = l_idx - i, j - r_idx
            cnt = r_idx - l_idx + 1
            
            if l < r:
                diff = min(r - l, cnt)
                l += diff
                cnt -= diff
                r = l
                
            if l > r:
                diff = min(l - r + 1, cnt)
                r += diff
                cnt -= diff
                l = r - 1
                
            ans = max(ans, l + r + cnt)
    
    print(ans)
    
for i in range(int(input())):
    solve()

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    sort(a.begin(), a.end());
    
    int ans = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int val = a[i] + a[j];
            if (val & 1)
                continue;
            
            val >>= 1;
            int l_idx = lower_bound(a.begin(), a.end(), val) - a.begin();
            if (l_idx == n || a[l_idx] != val)
                continue;
            
            int r_idx = lower_bound(a.begin(), a.end(), val + 1) - a.begin() - 1;
            
            int l = l_idx - i;
            int r = j - r_idx;
            int cnt = r_idx - l_idx + 1;
            
            if (l < r) {
                int diff = min(r - l, cnt);
                l += diff;
                cnt -= diff;
                r = l;
            }
            
            if (l > r) {
                int diff = min(l - r + 1, cnt);
                r += diff;
                cnt -= diff;
                l = r - 1;
            }
            
            ans = max(ans, l + r + cnt);
        }
    }
    
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    
    return 0;
}

F. 背包

贪心 + 排序 + 剪枝

贪心优先放入大的物品，再考虑放小的。
对于第一个物品考虑开 $\lceil \frac{a_i}{m}\rceil$ 倍的背包空间，多开的空间记录下来，看看是否能直接放入后面较小的物品，放不下也可以将当前枚举到的物品重量减去先前较大物品所预留的空间（二进制 每回扩大一倍）。

由于 $0\le b_i\le 10^9$ 直接从大物品枚举到小物品，$pow(2,10^9)\ast 之前剩余的空间$，这样肯定会炸，所以需要手动判断类似剪枝，如果当前空间足够包含后面的物品，直接退出遍历，处理给出答案。

由于 $0\le n\le 2\ast 10^5$ $0\le a_i\le 10^9$，可能出现 $2\ast 10^{14}$，因此采用 $math.log2(total)+前一次的b-当前的b\ge 50$ 来判断当前剩余容量是否够包括后续所有的小物品容量的可能最大值，即满足 $2^{50}\ge 1\ast 10^{15}$。

Python 代码

import sys
from math import log2

input = lambda: sys.stdin.readline().rstrip()

MOD = 998244353


def solve():
    n, m = map(int, input().split())
    d = {}

    for _ in range(n):
        a, b = map(int, input().split())
        d[b] = d.get(b, 0) + a

    arr = sorted(d.keys(), reverse=True)
    ans = 0

    total = 0
    pre = arr[0]

    for key in arr:
        if total:
            if log2(total) + pre - key >= 50:
                break
            total *= pow(2, pre - key)

        pre = key

        if total >= d[key]:
            total -= d[key]
            continue

        d[key] -= total
        x = (d[key] + m - 1) // m
        ans = (ans + x % MOD * pow(2, key, MOD) % MOD) % MOD
        total = (d[key] + m - 1) // m * m - d[key]

    print(ans)

for i in range(int(input())):
    solve()

C++ 代码

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

const int MOD = 998244353;

ll qpow(ll a, ll b, ll p) {
    ll res = 1;
    while (b) {
        if (b & 1)
            res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

void solve() {
    int n, m;
    cin >> n >> m;
    unordered_map<ll, ll> d;

    for (int i = 0; i < n; ++i) {
        ll a, b;
        cin >> a >> b;
        d[b] += a;
    }

    vector<ll> arr;
    for (auto [key, value] : d)
        arr.push_back(key);
    sort(arr.rbegin(), arr.rend());

    ll total = 0, pre = arr[0], res = 0;

    for (ll key : arr) {
        if (total) {
            ll cnt = 0, tmp = total;
            while (tmp) {
                tmp >>= 1;
                cnt++;
            }
            if (cnt + pre - key >= 50)
                break;

            total *= qpow(2, pre - key, LLONG_MAX);
        }

        pre = key;

        if (total >= d[key]) {
            total -= d[key];
            continue;
        }

        d[key] -= total;
        ll x = (d[key] + m - 1) / m;
        res = (res + x % MOD * qpow(2, key, MOD) % MOD) % MOD;
        total = x * m - d[key];
    }

    cout << res << endl;
}

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

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}