将军的题解(2025菜鸟杯

发表于 更新于 分类于
本文字数： 2.4k 阅读时长 ≈ 9 分钟

将军 の 题解

赛时只用了 C 和 Python3 提交代码。这里提供一份纯 C 题解，便于语法没学多少 / 只会 C 语言的同学学习理解。题目整体是比较好的（重在考思路）。没写的题目就是我赛时没写。

A 题

1
2
3
4
5
6
#include <stdio.h>

int main() {
    puts("HELL0 WUSTACM!\nmaintain integrity,think diligently, and challenge yourself");
    return 0;
}
1
print("HELL0 WUSTACM!", "maintain integrity,think diligently, and challenge yourself", sep="\n")

B 题

参考官方题解，可以证明与 n 的奇数质因子有关

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

typedef long long ll;

int main() {
    ll n;
    scanf("%lld", &n);
    while (n % 2 == 0) n /= 2;
    ll ans = 0;
    for (ll i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            ans++;
            if (i * i != n) ans++;
        }
    }
    printf("%lld\n", ans);
    return 0;
}
1
2
3
4
5
6
7
n = int(input())
while n % 2 == 0:
    n //= 2
ans = sum(1 for i in range(1, int(n**0.5) + 1) if n % i == 0) * 2
if int(n**0.5)**2 == n:
    ans -= 1
print(ans)

C 题

分类讨论

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

int main() {
    int n;  scanf("%d", &n);
    int season; scanf("%d", &season);
    if(n > 15) {
        puts("error");
    } else {
        if(season == 0)
            puts(n >= 10 ? "hot" : "cool");
        else if(season == 1)
            puts(n >= 10 ? "warm" : "cold");
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n = int(input())
season = int(input())

if n > 15:
    print('error')
elif season == 0:
    if n >= 10:
        print('hot')
    else:
        print('cool')
elif season == 1:
    if n >= 10:
        print('warm')
    else:
        print('cold')

D 题

结论题，答案等于 $\max(\max{a}, \lceil \frac{\sum{a}}{k}\rceil )$ ，推导参考官方题解

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

#define N 100000 + 10
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int a[N];

int main() {
    int n, k;   scanf("%d%d", &n, &k);
    long long sum = 0, max_a = 0;
    for(int i = 0, x; i < n; ++i) {
        scanf("%d", &x);
        if(x > max_a) max_a = x;
        sum += x;
    }
    long long ans = MAX(max_a, (sum + k - 1) / k);
    printf("%lld", ans);
    return 0;
}
1
2
3
4
5
6
7
8
n, k = map(int, input().split())
a = list(map(int, input().split()))

max_a = max(a)
sum_a = sum(a)

ans = max(max_a, (sum_a + k - 1) // k)
print(ans)

E 题

C 语言解法

思路：
一个实数分为整数和小数两部分（没小数部分的视为 “0”）
整数部分： 1. 先去掉前导 0 2. 更长的更大，一样长 strcmp
小数部分： 1. 人类规则：短的一方尾部补 0，和长的一方逐位比较 2. 新王国规则：跟整数部分一样比较就行

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
#include <stdio.h>
#include <string.h>

#define MX_LEN 1010

const char* strip_leading_zeros(const char *s) {
    while (*s == '0') s++;
    return *s ? s : "0";
}

void split(const char *s, char *int_ptr, char *frac_ptr) {
    const char *dot = strchr(s, '.');
    if (!dot) {
        strcpy(int_ptr, s), strcpy(frac_ptr, "0");
    } else {
        int len = dot - s;
        strncpy(int_ptr, s, len);
        int_ptr[len] = '\0';
        strcpy(frac_ptr, dot + 1);
    }
}

char cmp_int(const char *a, const char *b) {
    a = strip_leading_zeros(a), b = strip_leading_zeros(b);
    int la = strlen(a), lb = strlen(b);
    if (la != lb) return la > lb ? '>' : '<';

    int res = strcmp(a, b);
    if (res > 0)    return '>';
    else if(res < 0)    return '<';
    else    return '=';
}

char cmp_frac_trad(const char *a, const char *b) {
    int la = strlen(a), lb = strlen(b), L = la > lb ? la : lb;
    for (int i = 0; i < L; i++) {
        char ca = (i < la) ? a[i] : '0';
        char cb = (i < lb) ? b[i] : '0';
        if (ca != cb) return ca > cb ? '>' : '<';
    }
    return '=';
}

char cmp_frac_new(const char *a, const char *b) {
    return cmp_int(a, b);
}

int main() {
    char sa[MX_LEN], sb[MX_LEN], ai[MX_LEN], af[MX_LEN], bi[MX_LEN], bf[MX_LEN];
    scanf("%s %s", sa, sb);
    split(sa, ai, af);
    split(sb, bi, bf);

    char r1 = cmp_int(ai, bi);
    if (r1 == '=') r1 = cmp_frac_trad(af, bf);

    char r2 = cmp_int(ai, bi);
    if (r2 == '=') r2 = cmp_frac_new(af, bf);

    if (r1 == r2) puts("ni shi dui de");
    else printf("ni cuo le, ying gai shi %c\n", r2);
    return 0;
}

Python 解法

这题很适合用 Python 写。思路：

  • 整数部分，较短一方添加前导 0 对齐长度，然后逐字符比较即可
  • 小数部分
    • 人类比较法：较短一方添加后导 0 对齐长度，然后逐字符比较即可
    • 题目规定的：双方均去除前导 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
def parse_number(s: str):
    if "." not in s:
        s += ".0"
    return s.split(".")


def compare_int(a_int: str, b_int: str) -> str:
    a_int, b_int = int(a_int), int(b_int)
    if a_int > b_int:
        return ">"
    elif a_int < b_int:
        return "<"
    return "="


def trad_comp(a: str, b: str) -> str:
    a_int, a_frac = parse_number(a)
    b_int, b_frac = parse_number(b)

    res = compare_int(a_int, b_int)
    if res != "=":
        return res

    max_len = max(len(a_frac), len(b_frac))
    a_frac += (max_len - len(a_frac)) * "0"
    b_frac += (max_len - len(b_frac)) * "0"
    if a_frac > b_frac:
        return ">"
    elif a_frac < b_frac:
        return "<"
    return "="


def new_comp(a: str, b: str) -> str:
    a_int, a_frac = parse_number(a)
    b_int, b_frac = parse_number(b)

    res = compare_int(a_int, b_int)
    if res != "=":
        return res

    return compare_int(a_frac, b_frac)


x, y = input().split()
trad_res, new_res = trad_comp(x, y), new_comp(x, y)
print("ni shi dui de" if trad_res == new_res else f"ni cuo le, ying gai shi {new_res}")

F 题

题面非常有意思。赛时我以为有诈做了个记忆化

先给出出题人期望的题解

这个函数显然接受 int 作为参数，返回 int 。我们转换成 C 代码就好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define miaomiao if
#define miaomiaomiao else if
#define miaomiaomioa else
#define miaomiaomiaowu return

#include <stdio.h>

int miao_func(int x) {
    miaomiao (x < 1)
        miaomiaomiaowu 0;
    miaomiaomiao (x & 1)
        miaomiaomiaowu x + miao_func(x - 2);
    miaomiaomioa
        miaomiaomiaowu miao_func(x - 2) - x;
}

int main() {
    int n;  scanf("%d", &n);
    printf("%d", miao_func(n));
    return 0;
}

赛时题解

如果你做过斐波那契数列的递归写法，会知道递归时分叉会有大量的重复计算，复杂度会去到 $2^n$ 非常爆炸。但是如果用一个数组存储你已经计算过的结果，那么就可以避免重复计算，复杂度变为 $n$ 。显然 miao_func 在输入为负数时不用考虑，正数部分开一个 1000 + 1 大小的数组记录已经计算过的结果就行

（实则没仔细看，出题人良心，不用这样搞。不知道记忆化的就学个新知识点吧）

Py3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def func(x:int):
    if x < 1:
        return 0
    elif x & 1:
        if(mem[x - 2] != -1):
            mem[x] = x + mem[x - 2]
            return x + mem[x - 2]
        return x + func(x - 2)
    else:
        if(mem[x - 2] != -1):
            mem[x] = mem[x - 2] - x
            return mem[x - 2] - x
        return func(x - 2) - x

mem = [-1] * 1001
x = int(input())
print(func(x))

G 题

用手模拟一下会发现最后整个数列都变得完全相同，但是自始至终两人无法修改最后一个数字，其他所有数字都会被修改为 $a_n$ 答案就是 $n \times a_n$

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);
  	ll an = 0;
  	for(int i = 1, x ; i <= n ; ++i) {
      	scanf("%d", &x);
      	if(i == n)  an = x;
    }
    printf("%lld", n * an);
  	return 0;
}
1
2
3
n = int(input())
a = list(map(int, input().split()))
print(n * a[-1])

H 题

嗯模拟就行了。需要注意这里的溢出可以用取余数的技巧。

acmbot 一句话讲解 12 和 19 行的技巧：
先用 +m 把所有数（无论正负）都搬到正数轴，再用 %m 统一映射到 [0, m-1]，最后 +1 挪到你想要的 [1, 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
25
26
27
28
29
30
31
#include <stdio.h>

#define N 100 + 10
int a[N][N];

int main() {
    int n, m, q;    scanf("%d%d%d", &n, &m, &q);
    while(q--) {
        int x, y, k, s;  scanf("%d%d%d%d", &x, &y, &k, &s);

        for(int j = y - k ; j <= y + k ; j++) {
            int cy = ((j - 1) % m + m) % m + 1;
            a[x][cy] += s;
        }

        for(int i = x - k ; i <= x + k ; i++) {
            if (i == x) continue;		// 不重复操作

            int cx = ((i - 1) % n + n) % n + 1;
            a[cx][y] += s;
        }
    }

    for(int i = 1 ; i <= n ; i++) {
        for(int j = 1 ; j <= m ; j++) {
            printf("%d ", a[i][j]);
        }
        putchar('\n');
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n, m, q = map(int, input().split())
a = [[0] * (m + 1) for _ in range(n + 1)]

for _ in range(q):
    x, y, k, s = map(int, input().split())

    for j in range(y - k, y + k + 1):
        cy = ((j - 1) % m + m) % m + 1
        a[x][cy] += s

    for i in range(x - k, x + k + 1):
        if i == x:
            continue
        cx = ((i - 1) % n + n) % n + 1
        a[cx][y] += s

for i in range(1, n + 1):
    print(" ".join(map(str, a[i][1:])))

K 题

讲下思路：
p 的取值为 1 ~ 9 。那么对于任意 a_i 它对 p 取余数都会落在 0 ~ p - 1 之间。对于和 p 余数相同的数字才能通过若干次 + p 操作使之相等；反之做不到。

那么先统计对 p 取余数的每一组有多少数字，如果均小于 k 则无解，反之有解。

然后对于每一组有解的数字进行一个滑动窗口来统计答案（需要自行学习一下滑动窗口算法）即可

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
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define N 100010

typedef long long ll;

typedef struct {
    ll val;
    ll rem;
} Num;

Num a[N];

int cmp(const void *a, const void *b) {
    Num *x = (Num *)a;
    Num *y = (Num *)b;
    if (x->rem != y->rem) {
        return (x->rem > y->rem) - (x->rem < y->rem);
    }
    return (x->val > y->val) - (x->val < y->val);
}

int main() {
    int n;
    ll k, p;
    scanf("%d %lld %lld", &n, &k, &p);

    for(int i = 0; i < n; ++i) {
        scanf("%lld", &a[i].val);
        a[i].rem = a[i].val % p;
    }

    qsort(a, n, sizeof(Num), cmp);

    ll ans = -1;

    for(int i = 0; i < n; ) {
        int j = i;
        while(j < n && a[j].rem == a[i].rem) {
            j++;
        }

        int cnt = j - i;
        if(cnt >= k) {
            ll current_sum = 0;

            for(int x = 0; x < k; ++x) {
                current_sum += a[i + x].val;
            }

            ll target = a[i + k - 1].val;
            ll cost = (target * k - current_sum) / p;

            if(ans == -1 || cost < ans) ans = cost;

            for(int x = k; x < cnt; ++x) {
                current_sum -= a[i + x - k].val;
                current_sum += a[i + x].val;

                target = a[i + x].val;
                cost = (target * k - current_sum) / p;

                if(ans == -1 || cost < ans) ans = cost;
            }
        }

        i = j;
    }

    if(ans != -1) {
        printf("%lld\n", ans);
    } else {
        puts("wuwuwu");
    }

    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
n, k, p = map(int, input().split())
vals = list(map(int, input().split()))

vals.sort(key=lambda x: (x % p, x))

ans = None
i = 0
while i < n:
    j = i
    while j < n and vals[j] % p == vals[i] % p:
        j += 1
    group = vals[i:j]

    if len(group) >= k:
        current_sum = sum(group[:k])
        target = group[k - 1]
        cost = (target * k - current_sum) // p
        ans = cost if ans is None else min(ans, cost)

        for x in range(k, len(group)):
            current_sum += group[x] - group[x - k]
            target = group[x]
            cost = (target * k - current_sum) // p
            ans = min(ans, cost)

    i = j

print(ans if ans is not None else "wuwuwu")

L 题

仔细一算假设完全不查课好像是 $6 \times 5^6 = 93750$ 种可能性？不清楚反正直接暴力可以做。今年好像也没有人写 $7$ 层 for 循环呀

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
#include <stdio.h>

int a[7 + 1][6 + 1];
int ans = 0;

void dfs(int d, int c) {
    if(d == 7) {
        ans++;
        return;
    }

    for(int i = 1 ; i <= 6 ; ++i) {
        if(a[d + 1][i] == 1 || c == i)  continue;
        dfs(d + 1, i);
    }
}

int main() {
    int n;  scanf("%d", &n);
    for(int i = 0 ; i < n ; ++i) {
        int d, c;   scanf("%d %d", &d, &c);
        a[d][c] = 1;
    }

    dfs(0, 0);
    printf("%d\n", ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
a = [[0] * 7 for _ in range(8)]
ans = 0

def dfs(d, c):
    global ans
    if d == 7:
        ans += 1
        return
    for i in range(1, 7):
        if a[d + 1][i] == 1 or c == i:
            continue
        dfs(d + 1, i)

n = int(input())
for _ in range(n):
    d, c = map(int, input().split())
    a[d][c] = 1

dfs(0, 0)
print(ans)