Codeforces Round 1075 (Div. 2)

RookieSama_

公告

欢迎来到小破站ようこそ私のブログへ！

Learn Morea

标签

3140 字

16 分钟

Codeforces Round 1075 (Div. 2)

2026-01-24

题解

codeforce

A - Table with Numbers #

题目大意：#

可以理解为给你 n 个值作为x 或者 y，并放入为 h * l 的棋盘中，问你如何分配x 和 y 使得放入棋盘中的数量最多。
输入:

1
7
2
2 1 1
3
1 1
4
5 2 2
5
1 2 2 3 2
6
8 4 2
7
7 2 2 2 3 4 4 2
8
7 3 6
9
10 4 1 3 5 4 6
10
2 4 4
11
5 5
12
7 6 3
13
10 4 1 3 5 4 6
14
4 1 1
15
1 1 1 1

输出:

理解和思路：#

从题意不难看出，本质上就是找一个最优的方式去落子。不妨设棋盘的大小为 n * m 且 n < m 。
想要落子，必须确保x < n && y < m如果存在 m < y 的情况一定不成立，所以直接删了即可, 剩余的子至少一定能落在 m轴上(但还不一定能分配在 n轴上)
再去判断能放在 n 轴的数量 即 x < n 的数量
答案就是 min(c1 / 2, c2); 其中 c1表示能落在m轴的数量,c2表示能落在n轴数量

代码:#

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

4
const int N = 1e2 + 10;
5

6
int n,m ,k;
7
int a[N], st[N];
8

9
/**
10
 * @brief 解决当前测试数据的核心函数
11
 *
12
 * @details 算法逻辑：
13
 * 1. 读取三个参数：k(数组长度), n(较小阈值), m(较大阈值)
14
 * 2. 确保 n <= m，通过交换实现
15
 * 3. 读取数组元素，过滤掉大于m的元素
16
 * 4. 排序数组并统计小于等于n的元素个数
17
 * 5. 最终结果取：满足条件的元素个数 和 数组长度一半 的最小值
18
 *
19
 * @note 这道题的关键是找到最优分配策略，使得两组都能满足条件
20
 */
21
void solve(){
22
    // 读取输入参数：k-数组长度，n-第一组阈值，m-第二组阈值
23
    cin >> k >> n >> m;
24

25
    // 确保n是较小的阈值，通过交换实现
26
    // 这样后续逻辑只需要判断a[i] <= n即可
27
    if(n > m) swap(n, m);
28

29
    // 读取数组元素，同时进行数据清洗
30
    // 过滤掉大于m的元素（这些元素两组都无法容纳）
31
    for(int i = 1; i <= k; i++) {
32
        cin >> a[i];
33
        // 如果当前元素大于m，则回退索引并减少总长度
34
        // 相当于删除这个无效元素
35
        if(a[i] > m) i--, k--;
36
    }
37

38
    // 对有效元素进行排序，便于后续统计
39
    sort(a + 1, a + k + 1);
40

41
    // 统计满足第一组条件（a[i] <= n）的元素个数
42
    int cnt = 0;
43
    for(int i = 1; i <= k; i++){
44
        if(a[i] <= n) cnt++;
45
    }
46

47
    // 最终结果取最小值：
48
    // - cnt：满足第一组条件的元素个数
49
    // - k/2：理论上的最优分配（两组平分）
50
    // 这样可以确保两组都能获得足够的元素
51
    cout << min(cnt, k / 2) << endl;
52
}
53

54
int main(){
55
    int _ = 1;
56
    cin >> _;
57
    while(_--){
58
        solve();
59
    }
60
}

B - The Curse of the Frog #

题目大意:#

这是一个青蛙跳格子的游戏,就说说关键点:
1.青蛙有 n 种跳法, 其中
- a[i] 表示第i种跳法的格数
- b[i] - 1 表示第a[i]种跳法最多能免费跳的次数
- c[i] 表示每跳b[i] - 1次就会往回跳 c[i]格(先回跳再往前)
2.问青蛙到达 x 点最少需要多少次回跳
输入:

1
6
2
1 1
3
3 3 3
4
1 7
5
4 2 5
6
2 4
7
1 2 3
8
2 2 4
9
5 8
10
12 1 11
11
10 1 4
12
1 1 3
13
1 2 5
14
2 1 7
15
1 1000000000000000000
16
1000000 4 654321
17
1 10
18
2 2 1

输出:

1
0
2
1
3
-1
4
2
5
298892990032
6
3

理解和思路：#

这也是一题明显的贪心问题，我们要找到一个最优的跳格子方法，使得到大 x 格，往回跳的次数少。
很明显每一种魔法，都有b[i] - 1 次免费的跳格子机会，可以先减去。即 $x=x-\sum_{i=1}^{n} (a_i \cdot (b_i-1))$
1. 如果 $x<0$ 则说明一定可以在0步回退前到达x格子
1. x > 0：则持续的进行一个跳格魔法，直到到达x格
- 能成立的前提是：至少有一个 $0 < a_i \cdot b_i - c_i$ 否则无法到达 x 格
- 若有，则挑选 $max(a_i \cdot b_i - c_i)$ 表示会跳一次往前最多的值
- 计算回跳次数 $\lceil \frac{x}{max(a_i \cdot b_i - c_i)} \rceil$ 就是答案

代码:#

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

4
#define int long long
5
const int N = 1e5 + 10, INF = 1e18;
6
using PII = pair<int, pair<int,int>>;
7

8
int n, m, x;
9
int a[N], b[N], c[N];
10

11
/**
12
 * @brief 解决魔法使用策略的核心函数
13
 *
14
 * @details 算法思路：
15
 * 1. 数据预处理：过滤掉无需使用魔法的物品（b[i]=1且a[i]<=c[i]）
16
 * 2. 贪心策略：优先使用"性价比"最高的魔法
17
 * 3. 资源分配：先用免费机会，再用付费机会
18
 *
19
 * @note 关键在于如何高效利用有限的魔法资源x
20
 */
21
void solve()
22
{
23
    // 读取输入：n-物品数量，x-可用魔法资源
24
    cin >> n >> x;
25

26
    // 第一步：数据预处理，过滤无效物品
27
    for (int i = 1; i <= n; i++)
28
    {
29
        cin >> a[i] >> b[i] >> c[i];
30
        // 对于b[i]=1的物品，如果a[i]<=c[i]，则无需使用魔法
31
        // 直接过滤掉这些物品，减少后续处理复杂度
32
        if (b[i] == 1)
33
        {
34
            if (a[i] <= c[i])
35
                n--, i--;
36
        }
37
    }
38

39
    // 第二步：构建需要付费魔法的物品列表
40
    vector<PII> q;
41
    for (int i = 1; i <= n; i++)
42
    {
43
        // 跳过那些即使使用魔法也无法满足的物品
44
        if (a[i] * b[i] <= c[i])
45
            continue;
46

47
        // 存储魔法信息：
48
        // first: 魔法消耗 = a[i]*b[i] - c[i]（付费部分）
49
        // second.first: 总价值 = b[i]*a[i]
50
        // second.second: 魔法类型 = b[i]
51
        q.push_back({a[i] * b[i] - c[i], {b[i] * a[i], b[i]}});
52
    }
53

54
    // 第三步：使用免费魔法机会（b[i]-1次免费使用）
55
    for (int i = 1; i <= n; i++)
56
    {
57
        // b[i]=1的物品已经处理过了，跳过
58
        if(b[i] == 1 ) continue;
59

60
        // 如果有足够的资源使用免费魔法
61
        if (a[i] * (b[i] - 1) <= x)
62
        {
63
            x -= a[i] * (b[i] - 1);
64
        }
65
        else
66
        {
67
            // 资源不足，清空剩余资源并退出
68
            x = 0;
69
            break;
70
        }
71
    }
72

73
    // 第四步：处理剩余资源和结果计算
74
    if (x == 0)
75
    {
76
        cout << 0 << endl;
77
        return;
78
    }
79

80
    // 如果没有需要付费魔法的物品，返回-1
81
    if(q.empty()){
82
        cout << -1 << endl;
83
        return;
84
    }
85

86
    // 第五步：贪心选择最优魔法
87
    int cnt = 0;
88
    // 按魔法消耗降序排序，优先使用消耗大的魔法
89
    sort(q.begin(), q.end(), [](PII a, PII b){
90
        if(a.first != b.first) return a.first > b.first;
91
        return a.second.first > b.second.first; });
92

93
    // 计算可以使用的魔法次数
94
    if(q[0].second.second == 1){
95
        // 向上取整计算：(x + cost - 1) / cost
96
        cnt = (x + q[0].first - 1) / q[0].first;
97
        cout << cnt << endl;
98
        return;
99
    }
100

101
    // 通用情况：计算剩余资源可以支持的魔法次数
102
    cnt = (x  + q[0].first - 1) / q[0].first;
103
    cout << cnt << endl;
104
}
105

106
signed main()
107
{
108
    int _ = 1;
109
    cin >> _;
110
    while (_--)
111
    {
112
        solve();
113
    }
114
}

C1 - XOR Convenience (Easy Version)#

题目概述：让你构造出一个排列，满足 $a_i \neq a_j,a_i \in [1,n]$ ，使得存在 $a_j(i<j)=a_i \bigoplus i$ 且 $i \in [2,n-1]$
简单举个例子:
输入：

输出：

1
2 1 3
2
3 6 2 5 1 4

$1 \bigoplus 2 = 3$ （不包含 1 和 3）所以排序 2 1 3 成立

理解和思路：#

本题比较考对异或的认识：
- 1. 首先你必须知道异或是什么 简单说就是同位相同0 不同1
- 1. a ^ b == c a 只有异或 b == c 不存在其他数字，具有唯一性
- 1. a ^ b == c -> a ^ b ^ b == b ^ c -> a == b ^ c
再探究怎么写：
- 首先 $n-1$ 点一定要满足 $a_n-1 \bigoplus (n-1) == a_n$
- 不妨让所有 $a_i \bigoplus i == a_n$ 即是: $a_n \bigoplus i == a_i$
- 因为 $a_i \leq n$ ，即 $a_n \bigoplus i \leq n$ 当 $a_n = 1$ 时 $a_n-1 \bigoplus 1 <= n$ 成立
- 又因为 a ^ b == c 具有唯一性,不会重复，因此我们将得到一个不重复的排序
- 最后一个剩余的数字放个 $a_1$

代码:#

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

4
#define int long long
5
const int N = 2e5 + 10, INF = 1e18;
6
using PII = pair<int, pair<int,int>>;
7

8
int n;
9
int a[N], st[N];
10

11
/**
12
 * @brief 构造满足特定条件的排列
13
 * @details
14
 * 构造一个长度为n的排列a，使得对于每个位置i，a[i] ^ i的值尽可能分散。
15
 * 算法思路：
16
 * 1. 初始化标记数组st，记录哪些数字已被使用
17
 * 2. 特殊处理位置n：设置a[n] = 1
18
 * 3. 对于位置2到n-1：设置a[i] = i ^ 1，这样a[i] ^ i = 1
19
 * 4. 找到未使用的数字，填入位置1
20
 * 5. 输出构造的排列
21
 *
22
 * 关键性质：对于i ∈ [2, n-1]，有a[i] ^ i = 1
23
 * 这样可以让异或结果集中在小数值，便于后续处理
24
 */
25
void solve()
26
{
27
    cin >> n;  // 读取排列长度
28

29
    // 初始化标记数组，st[i] = 1表示数字i已被使用
30
    for(int i = 1; i <= n; i++) st[i] = 0;
31

32
    // 特殊处理：设置a[n] = 1，并标记数字1已被使用
33
    a[n] = 1, st[1] = 1;
34

35
    // 构造核心部分：对于位置2到n-1
36
    // 设置a[i] = i ^ 1，这样a[i] ^ i = 1（异或性质）
37
    for(int i = 2; i < n; i++){
38
        a[i] = i ^ 1;  // 异或操作，a[i] ^ i将得到1
39
        st[a[i]] = 1;  // 标记该数字已被使用
40
    }
41

42
    // 找到未使用的数字，填入位置1
43
    // 这个位置的特殊性在于a[1] ^ 1需要与其他位置不同
44
    for(int i = 1; i <= n; i++){
45
        if(!st[i]) {  // 找到第一个未使用的数字
46
            a[1] = i;
47
            break;
48
        }
49
    }
50

51
    // 输出构造的排列
52
    for(int i = 1; i <= n; i++){
53
        cout << a[i] << " ";
54
    }
55
    cout << endl;
56
}
57

58
signed main()
59
{
60
    int _ = 1;
61
    cin >> _;
62
    while (_--)
63
    {
64
        solve();
65
    }
66
}

C2 - XOR-convenience (Hard Version)#

题目大意：#

和上题大差不差，区别为:
- 从 $i \in [1,n-1]$ 都得满足 $a_i \bigoplus i==a_j$
- 存在输出排序，不存在输出 -1
输入：

输出:

理解和思路：#

基本要点就不重述了
根据我们最开始得到的理论，必须保证:
- $a_i \leq n$ ，即 $a_n \bigoplus i \leq n$ 当 $a_n = 1$ 时 $a_n-1 \bigoplus 1 <= n$ 成立
1. 当 $n=2^k$ 时 n 的二进制表达为 $10000...$ 任意数字异或 n 都是大于n的一定不成立
还有个前置：任意数字异或1 可以分为两类:
- 1. 奇数 $a \bigoplus 1 == a - 1$
- 1. 偶数 $a \bigoplus 1 == a + 1$
- 因此我们可以很明显的发现每一对 {偶数，奇数}可以配对，且相差1
- 因此我们可以设定将 $a_n = 1$
1. 当 $n=2^k + r$ 时
- 1. n为奇数：
  - 除了 $a_n$ 以外的所有数都可以配凑成 ${i+1,i}$ 并且满足 $i \bigoplus 1 == a[i]$
  - $i=1$ 时: $a_1=n-1$ 且 $(n-1) \bigoplus n == 1$ 成立`（因为一定找得到一个aj=n且i < j)
  - $i=n-1$ 时:同理于奇偶数配对成立
  - 所以一定有一个排列成立
- 1. n为偶数
  - 我们还能够凑出奇偶数配对 {偶数，奇数}不同的是，n 数字被留空了，没人接手数字n
  - 比如:1 2 3 4 5 6 接手后应该是 6 3 2 5 4 1 但是很明显 6 ^ 1 = 7不成立
  - 所以得找到能够替换的值
  - 观察式子 $n=2^k + r$ 可以发现 $n \bigoplus r == 2^k$ 且 r 一定是偶数
  - 借此我们可以将 $a_r=n,a_1=r+1$ 就是交换 $a_r a_1$
  - $r+1 \bigoplus 1==r==a_r+1$ 成立
  - $n \bigoplus r==2^k$ 且 $r<2^k$ 故成立

代码：#

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

4
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
5

6
int n;
7

8
void solve() {
9
    cin >> n;
10
    if(n == (1 << __lg(n))){ //判断是否为2的幂次 __lg(n) 表示 n 的二进制表示中 1 的最高位从0开始
11
        cout << -1 << endl;
12
        return;
13
    }
14

15
    if(n % 2 == 0){ //如果是偶数
16
        vector<int> ans = {n};
17
        for(int i = 2; i <= n - 2; i+=2){
18
            ans.push_back(i + 1);
19
            ans.push_back(i);
20
        } // 每一个 a[i] ^ i 都 = 1 即此时 j = n
21
        ans.push_back(1);
22
        // n = 2 ^ k + r , r是除了最高位以外的数字
23
        int r = n - (1 << __lg(n));
24
        // 因为 r是偶数 所以此时ans[0] = r + 1, a[r] = n
25
        // r + 1 ^ 1 = r 能够在 ans[r + 1] 找到
26
        // n ^ r = 2 ^ k > r 能够在 ans[2 ^ k + 1] 找到
27
        // 故所有点 i 都能找到 点j使得 a[i] = a[j] ^ i
28
        swap(ans[0] ,ans[r - 1]);
29
        for(int i = 0; i < n; i++){
30
            cout << ans[i] << " ";
31
        }
32
        cout << endl;
33

34
    }else{
35
        cout << n - 1 << " ";
36
        for(int i = 2; i <= n - 3; i+=2){
37
            cout << i + 1 << " " << i << " ";
38
        }
39
        cout << n << " " << 1 << endl;
40
    }
41
}
42

43
int main() {
44
    IOS;
45
    int t;
46
    cin >> t;
47
    while (t--) {
48
        solve();
49
    }
50
    return 0;
51
}

Codeforces Round 1075 (Div. 2)

https://blog.rookiesama.space/posts/codeforce/codeforces-round-1075-div-2/

作者

Rookiesama

发布于

2026-01-24

许可协议

CC BY

部分信息可能已经过时

AtCoder Beginner Contest 442

并查集

素晴らしき日々

A - Table with Numbers#

题目大意：#

理解和思路：#

代码:#

B - The Curse of the Frog#

题目大意:#

理解和思路：#

代码:#

C1 - XOR Convenience (Easy Version)#

理解和思路：#

代码:#

C2 - XOR-convenience (Hard Version)#

题目大意：#

理解和思路：#

代码：#

A - Table with Numbers #

B - The Curse of the Frog #