首页 程序设计 杂题集

写在前面
没抢到名额写个🥚

[补题链接][https://codeforces.com/gym/105901]

# A

# 题目大意

现在有 nn 个问题，每个问题的难度是 aia_i
然后有 qq 个调整，每个调整会给你一个需求 [qi,li,ri][q_i, l_i,r_i]，要求把 qiq_i 问题的难度调整到 [li,ri][l_i, r_i] 区间，如果不能满足所有需求，则输出 -1 ，能满足则输出最小难度变化代价

# 数据范围

  • 1≤T≤1001 \le T \le 100
  • 1≤n,q≤1001 \le n,q \le 100
  • 1≤ai,l,r≤1091 \le a_i, l, r \le 10^9

# 题解

输入完所有数据之后，再开始计算每个问题的最终区间，然后扫一遍算结果即可

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int n, q;
vector<int> a, p, l, r, rl, rr;

void solve () {
    cin >> n >> q;

    a = vector<int>(n + 1);
    p = vector<int>(q + 1), l = vector<int>(q + 1), r = vector<int>(q + 1);
    rl = vector<int>(n + 1, 0), rr = vector<int>(n + 1, 1e10);

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= q; i++)
        cin >> p[i] >> l[i] >> r[i];

    for (int i = 1; i <= q; i++) {
        if (l[i] > rr[p[i]] || r[i] < rl[p[i]]) {
            cout << -1 << '\n';
            return;
        }

        rl[p[i]] = max(rl[p[i]], l[i]), rr[p[i]] = min(rr[p[i]], r[i]);
    }

    int res = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] >= rl[i] && a[i] <= rr[i])
            continue;
        
        if (a[i] > rr[i])
            res += (a[i] - rr[i]);
        else if (a[i] < rl[i])
            res += (rl[i] - a[i]);
    }

    cout << res << '\n';
}

# I

# 题目大意

你需要构造一个 n×nn \times n 的网格，每个网格里有一个数，从 1→n21 \to n^2 的数都会出现一次，如果一个整数 xx 满足以下两个中的一个条件，我们则称它为宾果整数

  • 至少有一行，该行所有元素都 ≤x\le x
  • 至少有一列，该列所有元素都 ≤x\le x

现在给定 nn 和 kk，请你构造出 n×nn \times n 的网格，使得最小的宾果整数恰好是 kk

# 数据范围

  • 1≤T≤501 \le T \le 50
  • 1≤n≤501 \le n \le 50
  • 1≤k≤n21 \le k \le n^2

# 题解

构造的结果应该是

SHOW
1
2
3
4
5
6
n*n
    ...
        ...
            ...
                n*n-n+2
1   ... ... ... ...     k

所以 kk 只需要满足 k>nk > n 和 k≤n∗n−n+1k \le n * n - n+1 即可

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void solve () {
    cin >> n >> k;

    if (k < n || k > n * n - n + 1) {
        cout << "No\n";
        return;
    }

    cout << "Yes\n";

    flag = vector<bool>(n * n + 1);
    a = vector<vector<int>>(n + 1, vector<int>(n + 1, 0));

    for (int i = 1, t = n * n; i <= n - 1; i++, t--)
        a[i][i] = t, flag[t] = 1;

    for (int j = 1; j <= n - 1; j++)
        a[n][j] = j, flag[j] = 1;

    a[n][n] = k, flag[k] = 1;

    int t = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (!a[i][j]) {
                while (flag[t])
                    t++;
                a[i][j] = t, flag[t] = 1;
            }
        }
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cout << a[i][j] << (j == n ? '\n' : ' ');
}

# L

# 题目大意

如果长度为 kk 的，整数序列 C=c1,....,ckC = c_1, ...., c_k 的 最大元素和最小元素的均值等于中值

换句话说，如果排序后的 CC 序列（记为 dd 序列），满足

d1+dk=d⌈k/2⌉d_1+d_k=d_{\lceil{k/2}\rceil}

那么则称这个序列为好序列

现在，给定整数序列 A=a1,a2,...,anA=a_1,a_2,...,a_n，计算其最长好序列的长度（这里指的是，任意从 AA 中选数）

# 数据范围

  • 1≤n≤3×1031 \le n \le 3 \times 10^3
  • 1≤ai≤1091 \le a_i \le 10^9

# 题解

观察到，数据范围只有 3×1033 \times 10^3，所以 O(n2)O(n^2) 的复杂度也是可以接受的，我们不妨先 sortsort 一遍原数组，然后从 a1→ana_1 \to a_n 枚举中位数 xx，然后用 l,rl,r 分别往 aia_i 挪动，不断确定最长好序列区间

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];

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

    int res = 0;

    for (int i = 1; i <= n; i++) {
        int l = 1, r = n;

        while (l <= i && i <= r) {
            int x = a[l] + a[r];

            if ((x & 1) == 0 && (x >> 1) == a[i])
	            // 在两侧取更短的那段
                res = max(res, (i - l <= r - i - 1) ? (i - l + 1) * 2 : (r - i) * 2 + 1);
            
            if (x / 2 >= a[i])
                r--;
            else
                l++;
        }
    }

    cout << res << '\n';
}

# F

# 题目大意

有 nn 个物品组，其中第 ii 个物品组包含 aia_i 个物品，每个物品的重量为 2bi2^{b_i}
还有 mm 个背包，每个背包的容量为 kk，请你计算最小的 kk，使得

  • 所有物品都能装入背包
  • 每个背包的物品总重量不超过 kk

# 数据范围

  • 1≤T≤1041 \le T \le 10^4
  • 1≤n≤2×1051 \le n \le 2 \times 10^5
  • 1≤m≤1091 \le m \le 10^9
  • 0≤bi≤1090 \le b_i \le 10^9

# 题解

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
int qmi(int a, int b, int p) {
    int res = 1;
    while (b) {
        if (b & 1)
            res = res * a % p;
        a = a * a % p, b >>= 1;
    }

    return res;
}

int n, m;

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

    for (int i = 1, a, b; i <= n; i++)
        cin >> a >> b, d[b] += a;

    vector<int> a;
    for (auto [key, val] : d)
        a.push_back(key);

    sort(a.begin(), a.end(), [](int x, int y) {
        return x > y;
    });

    int total = 0, pre = a[0], res = 0;

    for (int k : a) {
        // 1) 先判断是否可以提前退出
        if (total) {
            int cnt = 0, tmp = total;

            while (tmp)
                tmp >>= 1, cnt++;

            if (cnt + (pre - k) >= 50)
                break;
        }

        // 2) 做“扩容”：把之前的 total 扩展到当前位
        if (pre != k) {
            if (total > 0)
                total = total * qmi(2, pre - k, 1e18);

            pre = k;
        }
        
        // 3) 用现有空槽放 d[k] 件
        if (total >= d[k]) {
            total -= d[k];
            continue;
        }

        // 4) 不足，再开新槽
        d[k] -= total;
        long long x = (d[k] + m - 1) / m;
        res = (res + (x % MOD) * qmi(2, k, MOD) % MOD) % MOD;
        total = x * m - d[k];
    }

    cout << res << '\n';
}