华中师范大学2023级程序设计新生赛

发表于 更新于 分类于 阅读次数： 本文字数： 1.2k 阅读时长 ≈ 5 分钟
It's Okay to not be Okay.

难度梯度：

根据官方数据：

  • 签到：A, J
  • Easy：B, C, L, M
  • Mid：D, G, H
  • Hard：E, F, I, K

A. 2024

思路：

  • 可以直接看右下角日历

时间复杂度：

1
2
3
4
5
n = int(input())
if n == 9 or n == 12:
    print(6)
else:
    print(5)

J. 简化双星问题

思路：

  • 首先，看到这个题目的万有引力公式，可以发现可以约掉 和 然后公式可以转换为

  • 然后我们运用初中学习的一元二次方程的求根公式可得：
  • 还要特判当 和 相等时，输出

附：

时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(3);

    long double M1, M2, L, m;
    std::cin >> M1 >> M2 >> L >> m;

    if (M1 == M2) {
        std::cout << L / 2 << "\n";
        return 0;
    }

    long double delta = pow((2 * L * M1), 2) - 4 * (M1 - M2) * M1 * L * L;
    long double x = (2 * L * M1 - sqrt(delta)) / (2 * (M1 - M2));

    std::cout << x << "\n";

    return 0;
}

B. 硬币

思路：

  • 当总数为奇数，并且取的个数为偶数时，一定无解，最后会发现无论怎么取，都会剩下最少一个无法被翻动

时间复杂度：

1
2
3
4
5
6
7
8
9
10
void solve() {
    int n, m;
    std::cin >> n >> m;

    if (n & 1 && m % 2 == 0) {
        std::cout << "NO\n";
        return ;
    }
    std::cout << "YES\n";
}

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
void solve() {
    int x, y;
    std::cin >> x >> y;

    if (y == 1) {
        std::cout << x + 1 << "\n";
        return ;
    } else if ((y - 1) * 9 == x) { // 形如n = 1000的数
        std::cout << 1;
        for (int i = 1; i < y; i++) {
            std::cout << 0;
        }
        std::cout << "\n";
        return ;
    }

    std::function<bool(int, int, i64)> dfs = [&](int num, int rex, i64 val) {
        if ((y - num) * 9 < rex) return false; // 如果剩下的数位全部填9都无法满足

        if (num >= y) { // 找到这个数字了就直接输出，其实应该写 == ，但只要到达y就行
            std::cout << val + 1 << "\n";
            return true;
        }

        for (int i = num ? 0 : 1; i <= 9; i++) { // 枚举每一位应该填啥
            if (dfs(num + 1, rex - i, val * 10 + i)) return true;
        }
        return false;
    };

    dfs(0, x, 0);
}

L. 按位与

思路:

  • 贪心，每次贪心一个数的两个位都为1的数字集合，然后最后将最终结果的首个数字输出即可，那么最后一个序列的首位一定是相同位数为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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    
    std::vector<int> p(n);
    std::iota(p.begin(), p.end(), 0);

    for (int i = 29; i >= 0; i--) { // 从最高位开始枚举每一位
        std::vector<int> b; // 存当前这一位相同数的下标
        for (int j = 0; j < p.size(); j++) {  // 枚举下标 0 - n
            if (a[p[j]] >> i & 1) { // 如果 j 这个下标的那一位是 1, 就把它存进 b 中
                b.push_back(p[j]);
            }
        }
        if (b.size() > 1) p = b; // 如果出现了两个以上同一位都是 1 的数，就说明他们这一位按位 & 不会发生变化，然后将这一位不会发生变化的下标更新一下，找下一个相同的位
    }
    std::cout << p[0] + 1 << " " << p[1] + 1 << "\n";

    return 0;
}

M. 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
constexpr i64 inf = LLONG_MAX;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, k;
    std::cin >> n >> k;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    std::sort(a.begin(), a.end());

    std::vector<i64> s(n + 1);
    for (int i = 0; i < n; i++) {
        s[i + 1] = s[i] + a[i];
    }

    i64 ans = inf;
    for (int i = k - 1; i < n; i++) {
        i64 sum = 1ll * (k - 1) * a[i];
        sum -= s[i] - s[i - k + 1];
        ans = std::min(ans, sum);
    }
    std::cout << ans << "\n";

    return 0;
}

H. 龙

思路：

  • 有 个宝石孔，那么每个宝石进入孔的概率为 ，所以其留下的概率为 ，所以最大总收益为 ​
题解-H 
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
constexpr int P = 998244353;
template <typename T>
T power(T a, T b) {
    T res = 1;
    for (; b; b >>= 1) {
        if (b & 1) {
            res = 1LL * res * a % P;
        }
        a = 1LL * a * a % P;
    }
    return res % P;
}

template <typename T>
T inv(T a) {
    return power(a, P - 2);
}

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

    int N, M;
    std::cin >> N >> M;

    std::vector<int> a(N);
    for (int i = 0; i < N; i++) {
        std::cin >> a[i];
    }

    std::sort(a.rbegin(), a.rend());

    i64 p = 1LL * (M - 1) * inv(M) % P;
    i64 base = 1, ans = 0;
    for (int i = 0; i < N; i++) {
        ans += a[i] * base % P;
        ans %= P;
        base = base * p % P;
    }
    std::cout << ans % P << "\n";

    return 0;
}