2025菜鸟杯题解

发表于 分类于
本文字数： 5.7k 阅读时长 ≈ 21 分钟

官方题解

B 题题解

本题是一个纯数学思维题，难度中等，侧重考察数学思维能力

题目大意

给定一个 n，求有多少种方式能将连续的正整数相加等于 n

题目思路

从题目给定的 n 的取值范围不难发现，10 的 12 次方是一个非常大的数据，所以这题首先不考虑暴力和模拟，所以一定是有某个特定的公式能直接涵盖所有情况，就需要我们来用最原始的方法进行纯数学推导。我们设有连续 k 个正整数和为 n，首项为 a，则：
a+(a+1)+(a+2)+…+(a+k-1)=n
化简得：ka+k(k-1)/2=n,即 2n=k(2a+k-1)。
所以可以得到一系列关键条件：
一.a 为正整数，所以 2a+k-1=2n/k，所以 k 为 2n 的正因数，2n%k=0
二.要保证 a>0 所以 2n/k-k+1>0
三.要保证 a 为整数，所以 2n/k-k+1 为偶数
有了这些条件之后，我们就可以开始遍历了，因为 k<2n/k+1,所以 k^2<2n 遍历范围为：k<sqrt(2*n),遍历效率极高（记得要开 long long 哦）。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <math.h>

long long n,cnt=0;
int main(){
	scanf("%lld",&n);
	long long max_k=sqrt(2*n);
	for(int k=1;k<=max_k;k++){
		if((2*n)%k==0){
			long long tmp=(2*n/k)-k+1;
			if(tmp>0&&tmp%2==0){
				cnt++;
			}
		}
	}
	printf("%lld",cnt);
	return 0;
}

C 题

题意梳理

输入两行：

  • 第 1 行：电梯内人数 n (n>0)
  • 第 2 行：季节 s，0 表示夏天，1 表示冬天

规则：

  1. 超载判定：若 n > 15，电梯超载，输出 error（优先级最高，直接结束）。
  2. 不超载时的体感（以 10 人为分界）
    • 夏天（s=0）
      • n >= 10：人多 → 热，输出 hot
      • n < 10：人少 → 凉爽，输出 cool
    • 冬天（s=1）
      • n >= 10：人多 → 暖，输出 warm
      • n < 10：人少 → 冷，输出 cold

解题思路

这是一个典型的分支判断题，按“超载 → 季节 → 人数阈值”顺序依次判断即可。

判定流程（伪代码）

1
2
3
4
5
6
7
读入 n, s
如果 n > 15：输出 error
否则：
  如果 s == 0（夏天）：
     如果 n >= 10 输出 hot 否则输出 cool
  否则（冬天）：
     如果 n >= 10 输出 warm 否则输出 cold

复杂度

  • 时间复杂度：O(1)
  • 空间复杂度：O(1)

参考代码（C++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;

int main() {
    int n, s;
    cin >> n >> s;

    if (n > 15) {
        cout << "error";
        return 0;
    }

    if (s == 0) { // summer
        if (n >= 10) cout << "hot";
        else cout << "cool";
    } else { // winter
        if (n >= 10) cout << "warm";
        else cout << "cold";
    }

    return 0;
}

D 题

基本贪心策略:每轮选择最大的 K 个数减一即可(只是复杂度太高会超时)

这里证明最优次数为 T=max(M,(sum+k-1)/k),M=max(a[i]),sum=a[1]+a[2]+…+a[n]

一、必要性（任何方案都不能少于这个次数）

来自单点的下界

一次操作中，每个位置最多减 1。
因此第 i 个数要从 a[i]减到 0，至少需要 a[i]次操作。

T>=max(a[i])

来自总和的下界

一次操作中，最多对 k 个数减 1，
即数组总和一次最多减少 k。

T>=(sum+k-1)/k

结论（下界）

令 max(a[i])=M

T>=max(M,(sum+k-1)/k)

以下部分需仔细推理

二、充分性（真的能在这么多次内完成）

令总次数为 T=max(M,(S+k-1)/k)

假设前 t 次我们每轮都选择了最大的 k 个数，并且刚好在第 t+1 轮的非 0 数小于 k

由于 T>=(sum+k-1)/k

若第 t+1 轮没有非 0 数就直接结束了

答案就是 sum/k

再考虑第 t+1 轮有数的情况

那么 t+1<=T

令第 t+1 轮中，最大的数为 Mx

那么我们只需要证明 Mx<=T-t 即可(即以后的每轮都全选剩下的数)

这里用反正法，若 Mx>=T-t+1

假设 Mx 对应的元素下标为 id，那么在前 t 次操作中它被选择了 c 次，没有选择 q 次，c+q=t

那么它原本的值为 Mx+c

因为 T=max(M,(S+k-1)/k)

又 M 是原数组的最大值

所以 Mx+c<=T

即 Mx+t-q<=T

Mx<=T+q-t

因为 Mx>=T-t+1

所以 T+q-t>=T-t+1

那么 q>=1

这意味着这个元素一定至少有一次没有被选择

  • 我们注意没有选择的那次，代表那次有至少 k 个元素不小于当时的 Mx

  • 而我们每轮的策略方法会使得任意两个数的差只会越来越靠近(这里差为 0 除外，比如 2 2 2 2 每次选三个，差会从 0 变成 1)

  • 而 Mx 又是当前的最大值,既然如此，从每次贪心策略来看，不管后续怎么选择，它与这 k 个元素不可能差 2，最多也是差 1

  • 而最后只剩下小于 k 个元素，意味着这 k 中的某些元素已经变成 0 了,差又不会超过 1，那么一定有 Mx=1

而前面说

Mx>=T-t+1

即 0>=T-t

又因为 T-t>=1

即 0>=1

因此不可能存在 Mx>=T-t+1

那么 T 次以内一定可操作完

证毕

还有一种直观的方法:将每个 a[i]拆成 a[i]个 1 线性排列,设第一个元素为最大值，后面的元素拆成的 1 去对 a[1]*k 的特殊矩形空间补充，若能补满矩形答案为(sum+k-1)/k，若补不满答案即 M (注意矩形构造的限制条件)

参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>

int main() {
    int n, k;

    scanf("%d %d", &n, &k);

    long long int sum = 0, ma = 0;

    for (int i = 1; i <= n; i++) {
        int c;
        scanf("%d", &c);
        sum += c;
        if (ma < c) {
            ma = c;
        }
    }
    if ((sum + k - 1) / k < ma) {
        printf("%lld", ma);
    }
    else {
        printf("%lld", (sum + k - 1) / k);
    }
}

E 题题解

本题难度略微偏高，需要有一定的耐心并且需要考虑到所有的情况

题目大意

给定两个正实数 A 和 B,先比较 A 和 B 的大小，然后把 A，B 分别按照小数点分开，整数部分正常比较，将小数部分看成整数，再进行比较。如果两次比较的结果相同，输出”ni shi dui de”, 否则输出”ni cuo le, ying gai shi >(</=)”。

题目思路

注意到这题的数据范围，数字长度最长可以到达 1000，很明显会超过 long long 和 double 的数据存储范围，所以这题用 C/C++写需要使用字符串模拟高精度。一个小思路，如果这两个数中有一个是整数，那么最后的结果一定是”ni shi dui de”,因为若整数部分相同,如果有一个数有小数部分，那么它在两种比较下都一定大于没有小数部分的另一个数，若整数部分不同，答案都由整数决定，所以两种比较结果相同。 比较小数部分时，正常比较方法应该按位进行比较，同时忽略小数部分的后缀零，因为在正常情况下比较后缀零无意义。而在另一种比较方式下，后缀零不能被直接忽略，例如：$0.10 \ne 0.1$,因为显然$10 \ne 1$。在这种比较下需要忽略小数点后的前导 0。本题需要注意的地方大概就是这些了，接下来就是需要进行一个字符串的大模拟。

补一嘴，这题按题意应该可以有负数的，但是降低了难度，没有给出负数测试点

参考代码

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <stdio.h>
#include <string.h>

int max(int x, int y) {
    return x > y ? x : y;
}

int main()
{
    char a[1005], b[1005];
    scanf("%s%s", a, b);
    int na = strlen(a);
    int nb = strlen(b);
    int ia, ib;

    //判断a是否为整数，如果不是整数找到小数点后第一个下标
    for(int i = 0; i < na; i++) {
        if(a[i] == '.') {
            ia = i + 1;
            break;
        }
        if(i == na - 1) {
            printf("ni shi dui de\n");
            return 0;
        }
    }
    //判断b是否为整数，如果不是整数找到小数点后第一个下标
    for(int i = 0; i < nb; i++) {
        if(b[i] == '.') {
            ib = i + 1;
            break;
        }
        if(i == nb - 1) {
            printf("ni shi dui de\n");
            return 0;
        }
    }
    //如果有整数存在，输出并结束程序

    for(int i = 0; !(a[i] == b[i] && a[i] == '.'); i++) {
        if(a[i] != b[i]) {
            printf("ni shi dui de\n");
            return 0;
        }
    }
    //如果整数部分不同，输出并结束程序

    int flag1 = 2, flag2 = 2;

    char x[1005] = "", y[1005] = ""; //去除前导0
    char zx[1005] = "", zy[1005] = ""; //保留前导0
    int nx = 0, ny = 0, nzx = 0, nzy = 0;

    //提取小数部分

    // 提取a的小数部分
    int fir = 0;
    for (int i = ia; i < na; i++)
    {
        zx[nzx++] = a[i];
        if(a[i] != '0') fir = 1;
        if(!fir) continue;
        x[nx++] = a[i];
    }

    // 提取b的小数部分
    fir = 0;
    for (int i = ib; i < nb; i++)
    {
        zy[nzy++] = b[i];
        if(b[i] != '0') fir = 1;
        if(!fir) continue;
        y[ny++] = b[i];
    }

    //以数学方法进行比较
    for(int i = 0; i < max(nzx, nzy); i++) {
        if(i >= nzx) zx[i] = '0';
        if(i >= nzy) zy[i] = '0';
        if(zx[i] > zy[i]) {
            flag1 = 1;
            break;
        }else if(zx[i] < zy[i]) {
            flag1 = 3;
            break;
        }
    }

    //以数字王国方法进行比较
    if(nx > ny) {
        flag2 = 1;
    }else if(nx < ny) {
        flag2 = 3;
    }else{
        for(int i = 0; i < nx; i++) {
            if(x[i] > y[i]) {
                flag2 = 1;
                break;
            }else if(x[i] < y[i]) {
                flag2 = 3;
                break;
            }
        }
    }


    //输出
    if(flag1 == flag2) {
        printf("ni shi dui de\n");
    } else{
        if(flag2 == 1) {
            printf("ni cuo le, ying gai shi >\n");
        }else if(flag2 == 2) {
            printf("ni cuo le, ying gai shi =\n");
        }else{
            printf("ni cuo le, ying gai shi <\n");
        }
    }


    return 0;
}

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
using namespace std;

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    string s1_z, s1_x, s2_z, s2_x;
    for(int i = 0; i < s1.size(); i++) {
        if(s1[i] == '.') {
            s1_z = s1.substr(0,i);
            s1_x = s1.substr(i + 1);
            break;
        }
        if(i + 1 == s1.size()) {
            s1_z = s1;
            s1_x = "0";
        }
    }
    for(int i = 0; i < s2.size(); i++) {
        if(s2[i] == '.') {
            s2_z = s2.substr(0,i);
            s2_x = s2.substr(i + 1);
            break;
        }
        if(i + 1 == s2.size()) {
            s2_z = s2;
            s2_x = "0";
        }
    }
    if(s1_z != s2_z || s1_x == "0" || s2_x == "0") {
        cout << "ni shi dui de" << '\n';
        return 0;
    }
    int flag1, flag2;
    string tmps1, tmps2;

    for(int i = 0; i < s1_x.size(); i++) {
        if(s1_x[i] != '0' || i + 1 == s1_x.size()) {
            tmps1 = s1_x.substr(i);
            break;
        }
    }
    for(int i = 0; i < s2_x.size(); i++) {
        if(s2_x[i] != '0' || i + 1 == s2_x.size()) {
            tmps2 = s2_x.substr(i);
            break;
        }
    }

    if(tmps1.size() != tmps2.size()) {
        if(tmps1.size() > tmps2.size()) {
            flag2 = 1;
        }else if(tmps1.size() < tmps2.size()) {
            flag2 = 3;
        }else {
            flag2 = 2;
        }
    }else {
        if(tmps1 > tmps2) flag2 = 1;
        else if(tmps1 == tmps2) flag2 =2;
        else flag2 = 3;
    }

    for(int i = s1.size(); i < 1010; i++) {
        s1_x += '0';
    }
    for(int i = s2.size(); i < 1010; i++) {
        s2_x += '0';
    }

    if(s1_x > s2_x) {
        flag1 = 1;
    }else if(s1_x < s2_x) {
        flag1 = 3;
    }else{
        flag1 = 2;
    }
    if(flag1 == flag2) cout << "ni shi dui de";
    else {
        if(flag2 == 1) cout << "ni cuo le, ying gai shi >";
        else if(flag2 == 2) cout << "ni cuo le, ying gai shi =";
        else cout << "ni cuo le, ying gai shi <";
    }

}

Python 版

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
66
67
68
69
70
71
72
73
74
# 如果给定数字不包含小数点，手动添加".0"
# 然后在小数点处切开，返回 整数部分 和 小数部分 两个字符串
def parse_number(s: str):
    if '.' not in s:
        s += '.0'
    return s.split('.')


# 模拟人类的比较方式
# 整数部分：直接比较
# 小数部分：在较短的一方尾部补 0 使双方长度一致
#          然后按照字典序比较，逻辑与 C 的 strcmp 一致
def traditional_compare(a: str, b: str) -> str:
    a_int_str, a_frac_str = parse_number(a)
    b_int_str, b_frac_str = parse_number(b)

    a_int = int(a_int_str)
    b_int = int(b_int_str)

    if a_int > b_int:
        return ">"
    elif a_int < b_int:
        return "<"

    # 按照小数部分较长一方的长度在尾部补 0
    max_len = max(len(a_frac_str), len(b_frac_str))
    a_frac_padded = a_frac_str.ljust(max_len, '0')
    b_frac_padded = b_frac_str.ljust(max_len, '0')

    if a_frac_padded > b_frac_padded:
        return ">"
    elif a_frac_padded < b_frac_padded:
        return "<"

    return "="


# 题目定义的比较方式
# 整数部分：直接比较
# 小数部分：转换成整数部分，然后用整数的比较方式（直接比较）
def new_compare(a: str, b: str) -> str:
    a_int_str, a_frac_str = parse_number(a)
    b_int_str, b_frac_str = parse_number(b)

    a_int = int(a_int_str)
    b_int = int(b_int_str)

    if a_int > b_int:
        return ">"
    elif a_int < b_int:
        return "<"

    a_frac = int(a_frac_str)
    b_frac = int(b_frac_str)

    if a_frac > b_frac:
        return ">"
    elif a_frac < b_frac:
        return "<"
    return "="


def solve():
    x, y = input().split()
    trad_res = traditional_compare(x, y)
    new_res = new_compare(x, y)

    if trad_res == new_res:
        print("ni shi dui de")
    else:
        print(f"ni cuo le, ying gai shi {new_res}")

solve()
# easy and elegant

F 题

题意： 给一个 n,实现给定伪代码

1
2
3
4
5
6
7
8
9
10
11
12
miaomiao -> if
miaomiaomiao -> else if
miaomiaomioa -> else
miaomiaomiaowu -> return

miao_func (x) :
    miaomiao (x < 1)
        miaomiaomiaomiwu 0
    miaomiaomiao (x & 1)
        miaomiaomiaomiwu x + miao_func (x-2)
    miaomiaomioa
        miaomiaomiaomiwu miao_func (x-2) - x

这是签到题，不给过多解释，只需要能够实现这个伪代码就能过，输出的答案
其实是如果 n 为奇数，则为 1 ～ n 的正奇数和，如果 n 为偶数，则 1 ～ n 的负偶数和

std:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>

using ll=long long;
using pii= std:: pair<ll,ll>;

int func(int x){

    if(x<1)
        return 0;
    if(x&1)
        return x + func(x-2);
    else
        return func(x-2) - x;
}

int main(void){
    int x;
    scanf("%d",&x);
    printf("%d",func(x));
    return 0;
}

G 题题解

本题难度并不高，但是带有诈骗性质，如果能仔细看一看的话不难想明白。

题目大意

给定一个长度为 $n$ 的数组 $a$。

两人轮流操作，礼包先手：

  • 选择一个 $i$，满足 $a_i \ne a_{i+1}$
  • 礼包操作：$a_i \leftarrow \max(a_i, a_{i+1})$
  • scandi 操作：$a_i \leftarrow \min(a_i, a_{i+1})$

当不存在任何满足 $a_i \ne a_{i+1}$ 的 $i$ 时，游戏结束。

双方都采取最优策略。问最终数组元素之和。

题目思路

通过分析样例不难发现：

对于 礼包 他只会对 $a_i < a_{i+1}$ 的数对产生影响，让$a_i = a_{i+1}$，使得 “相邻不等” 的位置数量减一；对于 礼包 他只会对 $a_i > a_{i+1}$ 的数对产生影响，让$a_i = a_{i+1}$，使得 “相邻不等” 的位置数量减一。

所以每次操作对数组中 “相邻不等” 的位置数量是不会增加的

由此，最终整个数组一定会相等并等于数组 $a$ 中的某一值，如果设最终的数字为 $X$，那么案就是 $n \times X$

观察操作，对于任意一对 $<a_i,a_{i+1}>$ 只有 $a_i$ 可能产生改变，并且一定会在最终和 $a_{i+1}$ 保持一致。所以存在一个关系链：

$$
a_1 \leftarrow a_2 \leftarrow a_3 \leftarrow \dots \leftarrow a_n
$$

任意位置的数值变化只能在“向右侧元素靠拢”的过程中完成，所以无法产生一个不来自原序列右侧的数值，同时 $a_n$ 永不改变，因此 $X= a_n$ 答案为 $n \times a_n$

​ $\square$

参考代码

C：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<stdio.h>
typedef long long ll;
int main() {

    int n; scanf("%d", &n);
    long long a[1010] = {0};

    for (int i=1 ; i<=n ; ++i)
        scanf("%lld", a+i);

    printf("%lld\n", n * a[n]);

    return 0;
}

CPP：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using ll = long long;
using namespace std;

int main() {
    int n; cin >> n;

    vector<int> a(n);

    for (auto& i : a) cin >> i;

    cout << (ll)a.back() * n << '\n';

    return 0;
}

python：

1
2
n, last_bowl = int(input()), list(map(int, input().split()))[-1]
print(last_bowl * n)

H 题

首先要跟大家道个歉，在题目中的 n, m 的定义，说的是长宽，实际上应该是行跟列，大家嘴下留情（磕头）。

输入样例 1

1
2
3
5 5 2
1 1 1 2
3 3 1 1

输出样例 1

1
2
3
4
5
2 2 0 0 2
2 0 1 0 0
0 1 1 1 0
0 0 1 0 0
2 0 0 0 0

样例解释

（1, 1）点如果向左延伸，会超出范围，但是因为有空间魔法的原因，多出来的会再右边加上，向上的同理。

这题实际上是一道非常简单的题目，我们只需要会用 for 和 if 语句就好了，我们可以看到 $0 \leq k \leq \frac{min(x, y) - 1}{2}$，所以是绝对不会出现一个魔法在同一个地块生成两次，接下来我们可以分别考虑向上下左右延伸，但是我们还要多考虑多出部分，下面给出正确的 AC 代码，简单通俗易懂版本的：

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>

//#define int long long
using namespace std;
using ar2       = array<int, 2>;
using ar3       = array<int, 3>;
const int mod   = 998244353;
const int N     = 5e5 + 10;
const double pi = acos(-1);

void solve() {
    int n, m, q;
    cin >> n >> m >> q; //输入
	vector<vector<int>> num(n + 1, vector<int>(m + 1)); //int num[n + 1][m + 1]

	while(q --) {
		int x, y, k, s;
		cin >> x >> y >> k >> s; //输入

		//向上
		for(int i = max(1, x - k); i <= x; i ++) {
			num[i][y] += s;
		}

		if(x - 1 < k) {
			int p = k - x + 1;
			for(int i = n; i > n - p; i --) {
				num[i][y] += s;
			}
		}

		//向下
		if(x < n) {
			for(int i = x + 1; i <= min(n, x + k); i ++) {
				num[i][y] += s;
			}
		}

		if(k > n - x) {
			int p = k - (n - x);
			for(int i = 1; i <= p; i ++) {
				num[i][y] += s;
			}
		}

		//向左
		for(int j = max(1, y - k); j <= y; j ++) {
			num[x][j] += s;
		}

		if(y - 1 < k) {
			int p = k - y + 1;
			for(int j = m; j > m - p; j --) {
				num[x][j] += s;
			}
		}

		//向右
		if(y < m) {
			for(int j = y + 1; j <= min(m, y + k); j ++) {
				num[x][j] += s;
			}
		}

		if(k > m - y) {
			int p = k - (m - y);
			for(int j = 1; j <= p; j ++) {
				num[x][j] += s;
			}
		}
		num[x][y] -= s;
	}

	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j <= m; j ++) {
			cout << num[i][j] << " "; //输出
		}
		cout << "\n"; //输出
	}
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
//    cin >> t;

    while (t--) {
        solve();
    }
    return 0;
}

赛事某同学还写了一个非常优雅的码，给大家分享一下：

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f3f3f3f3f
#define pi acos(-1)
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define si(x) (int)(x.size())
using ll = long long;
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;
const int mod = 998244353;
const double eps = 1e-10;

void solve(){
	int n, m, q;
	cin >> n >> m >> q;
	ll x, y, k, s;
	vector<vector<int>> a(n + 1, vector<int>(m + 1, 0));
	while(q --){
		cin >> x >> y >> k >> s;
		for(int i = 1; i <= k; i ++){
			a[(x - i + n - 1) % n + 1][y] += s;
			a[(x + i + n - 1) % n + 1][y] += s;
		}
		for(int i = 1; i <= k; i ++){
			a[x][(y - i + m - 1) % m + 1] += s;
			a[x][(y + i + m - 1) % m + 1] += s;
		}
		a[x][y] += s;
	}
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= m; j ++){
			if(j != 1){
				cout << ' ';
			}
			cout << a[i][j];
		}
		cout << endl;
	}
}

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

I 题 攻守兼备

题目要求我们在$n$组$h_i,d_i$之间选择两个互不相同的下标$i,j$，使得$max(min(h_i+h_j,d_i+d_j))$最小。

二分答案+最大值预处理

我们不妨先消除一个变量的影响，将原数组按$h_i$从小到大排序，就可以在$h$数组上进行二分了。由于题目的值很大，这里使用二分答案法枚举$mid$。从 1 开始枚举$h_i$，然后在$h$数组中找到一个下标$j(j>i)$，这时我们就可以保证$h_i+h_k \geq mid(k\geq j)$，这部分的查找可以使用二分，因为数据是有序的。接下来，只需要在$j$到$n$的范围上找到一个$k$满足$d_i+d_k\geq mid$，就能保证答案一定大于等于$mid$，否则答案一定小于$mid$。

对于$d_k$的查找，我们只需要贪心的查找在这一段范围内的最大值就行了，这里需要后缀处理最大值数组。

时间复杂度$:O(n\times logn\times logA)$ $A$为数值上界，分析可得$maxA==2\times10^9$

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
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct node{
    ll h,d; // 建议开 long long ，否则可能会在二分时爆int

    bool operator<(const node& a){
        return h<a.h;
    }
};
struct node a[200010]; // 原始数组
ll sufd[200010]; // 预处理后缀最大值数组
int n;

bool check(int x){
    for(int i = 1;i<=n;i++){
        ll l1 = i+1, r1 = n, mid1, j = -1; // j是我们要查询的坐标
        while(l1<=r1){
            mid1 = l1 + r1 >> 1;
            if(a[i].h+a[mid1].h>=x){
                j = mid1;
                r1 = mid1 - 1;
            }
            else{
                l1 = mid1 + 1;
            }
        }
        // 如果存在这个j 并且 ...
        if(j!=-1 && a[i].d+sufd[j]>=x) return true;
    }
    // 否则 ...
    return false;
}

void solve(){
    cin >> n;
    for(int i = 1;i<=n;i++){
        cin >> a[i].h >> a[i].d;
    }

    sort(a+1,a+n+1); // 排序
    for (int i = n; i >= 1;i--){
        sufd[i] = max(a[i].d, sufd[i + 1]); // 预处理后缀最大值
    }

    ll l = 0, r = 2e9, mid, ans = 0; // 二分答案
    while(l<=r){
        mid = l + r >> 1;
        if(check(mid)){
            l = mid + 1;
            ans = mid;
        }
        else{
            r = mid - 1;
        }
    }
    cout << ans << endl;
}

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

    int _ = 1;
    // cin >> _;
    while(_--){
        solve();
    }

    return 0;
}

贪心

不妨先假设$h_j\leq d_j,i<j$。如果$d_i+d_j\leq h_i+h_j$，则$h_i-d_i\geq d_j-h_j$。也就是说只需要保证$h_i-d_i\leq d_j-h_j$，就能保证最小值为$h_i+h_j$ ；同理，若$h_j \geq d_j,i<j$，只需要保证$d_i-h_i \leq h_j-d_j$，就能保证最小值为$d_i+d_j$。整理一下即可得到排序的要求：对于$i<j,abs(h_i-d_i)<abs(h_j-d_j)$，即按照绝对值大小排序。

为保证答案最大，使用两个变量$maxh,maxd$记录下标$i$之前最大的$h$，$d$。遍历过程中，如果$h>d$，则选取$d+maxd$与最终答案比较，否则选取$h+maxh$与最终答案比较。

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct node{
	int h,d;

    bool operator <(const node& a){
        return abs(h-d)<abs(a.h-a.d);
    }
};
struct node a[200010];
int maxh = 0,maxd = 0,ans = 0;
int n;

void solve(){
    cin >> n;
    for(int i = 1;i<=n;i++){
        cin >> a[i].h >> a[i].d;
    }
    sort(a+1,a+n+1);
    for(int i = 1;i<=n;i++){
        if(a[i].h>a[i].d) ans = max(ans , a[i].d+maxd);
        else ans = max(ans , a[i].h+maxh);
        maxh = max(maxh , a[i].h);
        maxd = max(maxd , a[i].d);
    }
    cout << ans << endl;
}

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

    int _ = 1;
    //cin >> _;
    while(_--){
        solve();
    }

    return 0;
}

比较遗憾的是，这道题本来是想考贪心的，结果都写二分去了$(TOT)$

L 题 逃课计划

从每一列数据中可选择的数据中选择一个，并且不可选择与上一列选择数据在同一行，求方案数。

根据题意，我们可以先生成一个二维数组，用于表示是否可选，如果值为 1，就是可选，否则不可选。

DFS（深度优先搜索）

我们可以将题目看作找到从 day1 到 day7 的路径数的个数，用 dfs 记录路径，每有一个路径，答案+1。

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n;
int vis[8][7];

int dfs(int col,int pre){// col->当前列 , pre->上一列选择的行
    if(col==7) return 1; // 到达可以选择的第7列,即为一个方案
    int res = 0;
    for(int i = 1;i<=6;i++){
        if(!vis[col][i] && i!=pre){
            res += dfs(col+1,i); // 加上后方可选则方案数
        }
    }
    return res;
}

void solve(){
    scanf("%d",&n);
    while(n--){
        int a,b;
        scanf("%d%d",&a,&b);
        vis[a][b] = 1;
    }
    printf("%d",dfs(0,0));
    /*
    调用dfs(0,0)的原因:
    	保证能选中day1所有可选的选项，做到不漏答案
    */
}

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

    int _ = 1;
    //cin >> _;
    while(_--){
        solve();
    }

    return 0;
}

for 循环暴力写法

和 dfs 同理。

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int vis[7][8] ;

void solve(){
    int n; scanf("%d",&n);

    while(n--){
        int a,b; scanf("%d%d" , &a,&b);
        vis[a][b] = 1;
    }

    int ans = 0;
    for(int i1 = 1;i1<=6;i1++){
        if(vis[1][i1]) continue;
        for(int i2 = 1;i2<=6;i2++){
            if(vis[2][i2] || i2==i1) continue;
            for(int i3 = 1;i3<=6;i3++){
                if(vis[3][i3] || i3==i2) continue;
                for(int i4 = 1;i4<=6;i4++){
                    if(vis[4][i4] || i4==i3) continue;
                    for(int i5 = 1;i5<=6;i5++){
                        if(vis[5][i5] || i5==i4) continue;
                        for(int i6 = 1;i6<=6;i6++){
                            if(vis[6][i6] || i6==i5) continue;
                            for(int i7 = 1;i7<=6;i7++){
                                if(vis[7][i7] || i7==i6) continue;
                                ans ++;
                            }
                        }
                    }
                }
            }
        }
    }
    printf("%d" , ans);
}

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

    int _ = 1;
//     cin >> _;
    while(_--){
        solve();
    }

    return 0;
}

时间复杂度$:O(6^7)$

感兴趣的同学可以尝试一下 dp(动态规划)写法