小花生

study & life record.

2024 Hubei ICPC

发表于 分类于 ，

2024 Hubei ICPC VP。

题目按难度（个人感觉的难度）由易到难。

GYM地址：The 2024 International Collegiate Programming Contest in Hubei Province, China。

题解

E. Spicy or Grilled?

签到题。

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

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

void solve(){
    int n = read(), x = read(), a = read(), b = read();
    cout << (n - x) * a + x * b << '\n';
}

signed main(){
    int t = read();
    while(t--) solve();
    return 0;
}

A. Long Live

分析：求出 x = lcm(a, b) / gcd(a, b) ，x = a * a * b
要求 a * b 最小值，即让 a 最小，a = 1 显然满足，此时 b = x 即可。

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

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

void solve(){
    int x = read(), y = read();
    int gcd = __gcd(x, y);
    cout << 1 << ' ' << x * y / gcd / gcd << '\n';
}

signed main(){
    int t = read();
    while(t--) solve();
    return 0;
}

B. Nana Likes Polygons

分析：最小面积只能是三角形，遍历每个三个点，求最小面积即可。

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;
typedef pair<int, int> PII;

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

void solve(){
    int n = read();
    vector<PII> v(n);
    for(int i = 0; i < n; i++){
        int x = read(), y = read();
        v[i] = {x, y};
    }
    
    double res = 10000000;
    bool flag = 0;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            for(int k = j + 1; k < n; k++){
                int a1 = v[j].first - v[i].first;
                int b1 = v[j].second - v[i].second;
                int a2 = v[k].first - v[i].first;
                int b2 = v[k].second - v[i].second;
                if(a1 * b2 == a2 * b1) continue;
                flag = 1;
                res = min(res, abs(1.0 * (a1 * b2 - a2 * b1) / 2));
            }
        }
    }
    if(!flag) cout << -1 << '\n';
    else cout << res << '\n';
}

int main(){
    int t = read();
    while(t--) solve();
    return 0;
}

J. Points on the Number Axis A

分析：直观感觉数学期望为平均值即可。（证明见tutorial）

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

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

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

const int mod = 998244353;

void solve(){
    int n = read();
    int s = 0;
    for(int i = 1; i <= n; i++){
        s += read();
    }
    s %= mod;
    cout << s * qmi(n, mod - 2, mod) % mod;
}

signed main(){
    int t = 1;
    while(t--) solve();
    return 0;

补充知识点：逆元

定义：如果一个线性同余方程 $ax\equiv 1 (\mathrm{mod}\ b)$ ，则 $x$ 称为 $a\ \textrm{mod}\ b$ 的逆元，记作 $a^{-1}$ 。
求法：当 $b$ 为质数时，通过费马小定理不难发现 $x\equiv a^{b - 2}(\mathrm{mod}\ b)$，用快速幂求即可。

L. LCMs

分析：如果转移，最优情况下只经过 a，b 的质因数和 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
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>
#define int long long
using namespace std;
typedef pair<int, int> PII;

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

const int N = 500;

void get_prime(int n, vector<int> &v){
    int x = n;
    for(int i = 2; i <= n / i; i++){
        int cnt = 0;
        while(x % i == 0){
            cnt++;
            x /= i;
        }
        if(cnt)
            v.emplace_back(i);
    }
    if(x > 1) v.emplace_back(x);	
}

int dijkstra(vector<int> v, int st, int ed){
    vector<int>dist(N, 0x3f3f3f3f), vis(N, 0);
    priority_queue<PII, vector<PII>, greater<PII>> q;
    
    dist[st] = 0;
    q.emplace(0, st);
    while(!q.empty()){
        int u = q.top().second;
        q.pop();
        
        if(u == ed){
            return dist[u];
        }
        
        if(vis[u]) continue;
        vis[u] = 1;
        
        for(int j = 0; j < v.size(); j++){
            if(j == u) continue;
            int l = lcm(v[u], v[j]);
            if(dist[j] > dist[u] + l){
                dist[j] = dist[u] + l;
                q.emplace(dist[j], j);
            }
        }
    }
    return -1;
}

void solve(){
    int a = read(), b = read();
    if(a == b) {
        cout << 0 << '\n';
        return;
    }
    
    vector<int> v;
    get_prime(a, v), get_prime(b, v);
    v.emplace_back(a), v.emplace_back(b), v.emplace_back(2);

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    
    int st, ed;
    for(int i = 0; i < v.size(); i++){
        if(v[i] == a) st = i;
        else if(v[i] == b) ed = i; 
    }

    cout << dijkstra(v, st, ed) << '\n';
}

signed main(){
    int t = read();
    while(t--) solve();
    return 0;
}