小花生

study & life record.

2025 CCNU 新生赛

发表于 分类于 ，

整理，复盘。

这场比赛几乎完全没有跟榜走，好处是拿了 3 个首 A，坏处是被 H 题卡死了，导致本应该出的很快的 AB 很晚才做（rk++）。

A. 期末复习

对 min(n, m) 为 1，2 的情况特判，除此之外，不断填最大的 L ，总能填到 60%。（二分查找最小的 L）

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

void solve(){
    int n, m, k; cin >> n >> m >> k;
    if(n > m) swap(n, m);
    
    if(n == 1){
        cout << -1 << '\n';
        return;
    }
    if(n == 2){
        if(m <= 5){
            cout << k << '\n';
        }
        else{
            cout << k + k << '\n';
        }
        return;
    }
 
    int need = ceil(n * m * 0.6);
    
    int l = 0, r = min(n, m) - 1;
    while(l + 1 != r){
        int mid = l + r >> 1;
        if(m * n - (m - mid) * (n - mid) >= need) r = mid;
        else l = mid; 
    }
    
    cout << r * k << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

B. 洛杉矶的火

分情况讨论：先往左再往右，或先往右再往左。
枚举最后停止的点的位置，计算最小体力即可。

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;

void solve(){
    int n, h, x0, y0; cin >> n >> h >> x0 >> y0;
    vector<PII>l, r;
    
    
    int left = 1e9, right = -1e9;
    int sumy = 0;
    for(int i = 0; i < n; i++){
        int x, y; cin >> x >> y;
        y = abs(y - h);
        sumy += y;
        if(x < x0){
            left = min(left, x);
            l.emplace_back(x, y);
        }
        else{
            right = max(right, x);
            r.emplace_back(x, y);
        }
    }
    
    int ansl = abs(y0 - h) + sumy * 2;
    if(l.size()) {
        ansl += 2 * (x0 - left);	
    }
    if(r.size()){
        int minn = 1e9;
        ansl += right - x0; 
        for(auto &[x, y] : r){
            minn = min(minn, right - x - y);
        }
        ansl += minn;
    }
    
    int ansr = abs(y0 - h) + 2 * sumy;
    if(r.size()){
        ansr += 2 * (right - x0);
    }
    if(l.size()){
        int minn = 1e9;
        ansr += x0 - left;
        for(auto &[x, y] : l){
            minn = min(minn, x - left - y);
        }
        ansr += minn;
    }
    
    cout << min(ansl, ansr) << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

C. 好数

打表发现神奇结论：只有 2 的幂次凑不出来。
（赛时手推结论失败，卡了好久，最后无奈打表）

证明：$2^n$ 无法被连续自然数的和表示。

设 $2^n=k+(k+1)+\cdots+(k+r-1)=\dfrac{(2k+r-1)r}{2}$

则 $(2k+r-1)r=2^{n+1}$，设 $2k+r-1=2^s$, $r=2^t$，则 $2k-1=2^t(2^{s-t}-1)$.

$2k-1$ 为奇数，于是 $t=0$, 那么得到 $r=1$，因此无法被连续自然数的和表示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;

vector<int>u;

void solve(){
    int l, r; cin >> l >> r;
    int down = lower_bound(u.begin(), u.end(), l) - u.begin();
    int up = upper_bound(u.begin(), u.end(), r) - u.begin();
    cout << r - l + 1 - (up - down) << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    for(int i = 1; i <= 1e18; i <<= 1){
        u.emplace_back(i);
    }
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

E. 交换offer

概率为 $\dfrac{D_n}{(n - 1)^n}$，其中 $D_n$ 为全错位排列数，推导可以看之前写的这篇 全错位排列 | 小花生。

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>
#define int long long
using namespace std;

constexpr int mod = 998244353;

vector<int>D(2e6 + 1);

int qmi(int a, int k, int p){
    int res = 1;
    while(k){
        if(k & 1) res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}

int inv(int a, int p){
    return qmi(a, p - 2, p);
}

void init(){
    D[1] = 0;
    D[2] = 1;
    for(int i = 3; i <= 2e6; i++){
        D[i] = (i - 1) * (D[i - 1] + D[i - 2]) % mod;
    }
}

void solve(){
    int n; cin >> n;
    cout << D[n] * inv(qmi(n - 1, n, mod), mod) % mod << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    init();
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

F. 植树节

小博弈，首先如果 x 为叶子节点，那么 xiaonian wins。
当 x 不为叶子节点时，结束情况一定是仅剩 x 与另外一个节点（因为都不愿意提前让 x 成为叶子节点，这样会让对方直接胜利）。可见，n 为偶数时，xiaonian wins，否则，coldtree wins。

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;


void solve(){
    int n; cin >> n;
    vector<PII>e(n - 1);
    for(int i = 0; i < n - 1; i++){
        cin >> e[i].first >> e[i].second;
    }
    
    int x; cin >> x;
    int ind = 0;
    for(auto &[u, v] : e){
        if(u == x || v == x) ind++;
    } 

    if(ind < 2){
        cout << "xiaonian wins!" << '\n';
        return;
    }
    
    if(n % 2 == 0){
        cout << "xiaonian wins!" << '\n';
    }
    else{
        cout << "coldtree wins!" << '\n';
    }

}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

G. 逻辑门

模拟给出的数字逻辑即可。（感觉被恶趣味了）

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

void solve(){
    int n; cin >> n;
    string s; cin >> s;
    
    string res;
    bool andor = 0;
    for(int i = 0; i < n; i += 2){
        bool cur_xor = (s[i] - '0') ^ (s[i + 1] - '0');
        res += (andor ^ cur_xor) + '0';
        andor = andor & cur_xor;
        andor = andor | ((s[i] - '0') & (s[i + 1] - '0'));
    }
    
    cout << (char)(andor + '0');
    reverse(res.begin(), res.end());
    cout << res << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

I. 找出躺赢狗

按题意排序并输出即可。

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, string> PIS; 

void solve(){
    int n; cin >> n;
    
    vector<PIS>res;
    for(int i = 0; i < n; i++){
        string s; cin >> s; 
        double x; cin >> x;
        int a = x * 10;
        if(a <= 30){
            res.emplace_back(a, s);
        }
    }
    sort(res.begin(), res.end());
    cout << res.size() << '\n';
    for(auto &[a, s] : res){
        cout << s << '\n';
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

J. 音名

模拟音名高低比较即可。

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

map<char, int>mp;

void solve(){
    char a, b; cin >> a >> b;
    if(mp[a] < mp[b]) swap(a, b);
    cout << a << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    mp['C'] = 0;
    mp['D'] = 1;
    mp['E'] = 2;	
    mp['F'] = 3;
    mp['G'] = 4;
    mp['A'] = 5;
    mp['B'] = 6;
    
    int t; cin >> t;
    while(t--) solve();
    return 0;
}