Martian148's blog
martian148
2024-09-01
目录

ICPC2024 江西省赛 题解

# ICPC2024 江西省赛

2024 (ICPC) Jiangxi Provincial Contest (opens new window)

第一次在 vp 的时候夺冠，记录一下

# A - Maliang Learning Painting

# Solution

A+B+CA+B+C

# Code

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a, b, c;
    cin >> a >> b >> c;
    cout << a + b + c << endl;
    return 0;
}
1
2
3
4
5
6
7
8

# B - Magic Leeks

# Question

星光闪闪正在指挥小马们割魔法大蒜，每匹小马被分配到大蒜田的特定行。

对于给定的小马，在时间 00，该行大蒜的高度为 v1,v2,…,vnv_1,v_2,\dots,v_n，小马位于位置 pp。

在时间 tt 的开始（t≥1t\ge 1），每株大蒜因魔法而增长 kk 个单位，然后小马立即割下它所在位置的大蒜，最后小马可以选择移动到相邻的位置或不移动。

现在有些小马想知道在时间 t0t_0 内他们可以割下多少单位的大蒜。

形式上，对于每组数据：

在时间 00，有一个初始数组 v1,v2,…,vnv_1,v_2,\dots,v_n，带有一个指向位置 pp 的指针和初始值为 00 的 sumsum。

在时间 tt 的开始（t≥1t\ge 1），按顺序执行以下操作：

  1. 对于每个 ii，执行 vi←vi+kv_i\leftarrow v_i + k。
  2. sum←sum+vpsum\leftarrow sum + v_p。
  3. vp←0v_p\leftarrow 0。
  4. p←p′∈{p,max⁡(p−1,1),min⁡(p+1,n)}p\leftarrow p'\in \{p,\max(p-1,1),\min(p+1,n)\}。

找到时间 t0t_0 结束时 sumsum 的最大值。

# Solution

非常好的一个题

考虑到，只关注一株大蒜，最后得到多少单位的大蒜是原来有的大蒜 + 生长出来的大蒜

生长出来的高度取决于最后一次割的时间

所以，我们要尽量晚的去割每一株大蒜

假设割的区间为 [L,R][L,R] 那么我们假设从 p→L→Rp\rightarrow L\rightarrow R，那么在 LL 处就是在 t0−(R−L)t_0-(R-L) 的时间割的

那么生长的单位就是一个等差数列可以求出

我们枚举左端点 LL，然后可以 O(1)O(1) 计算出右端点 RR，用一个前缀和记录原来有的大蒜，相加就能知道这次割的总的大蒜了

# Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
signed main() {
    // freopen ("B.in", "r", stdin);
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) {
        int n, p; cin >> n >> p;
        vector<int> a(n + 2);
        for (int i = 1; i <= n; i++) cin >> a[i];
        int k, t0; cin >> k >> t0; t0 -= 1;
        int ans = 0;
        
        auto calc = [&] () {
            vector<int> s(n + 2, 0);
            for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
            for (int j = 0; j <= min(t0 / 2, p - 1); j++) {
                int L = p - j, R = min(n, L + t0 - j);
                int len = R - L + 1;
                int v0 = 1ll * (t0 + 1 + t0 + 1 - len + 1) * (len) / 2 * k;
                int now = v0 + s[R] - s[L - 1];
                ans = max(ans, now);
            }
        };

        calc();
        reverse(a.begin(), a.end()); p = n - p + 1;
        calc();

        cout << ans << '\n';
    }
    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

# C - Liar

# Question

在一个游戏中有nn个玩家。每个玩家被分配一个整数数字，这些数字可能在不同玩家之间不同，而这些数字的总和为ss。

第ii个玩家声称分配给他的数字是aia_i，尽管这种声称可能是错误的。最多有多少个玩家可能在说真话呢？

# Solution

当 ∑ai=s\sum{a_i}=s 时全为真话，否则，只需要让一个人说假话即可

# Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 2e5 + 5;
ll n, s, a[MAXN], sum;
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> s;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        sum += a[i];
    }
    if(sum == s) cout << n << endl;
    else cout << n - 1 << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# D - Magic LCM

# Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 1e6 + 5;
const ll MOD = 998244353;
ll Tex, n, x;
bool p[MAXN + 5];
vector<ll> zs;
vector<ll> pd[MAXN];
void AC(){
    cin >> n;
    unordered_map<ll, ll> mp;
    ll cnt = 0;
    for(int i = 1; i <= n; i ++){
        cin >> x;
        for(int j = 0; ; j ++){
            if(zs[j] > sqrt(x)) break;
            ll sum = 1;
            while(x % zs[j] == 0){
                sum *= zs[j];
                x /= zs[j];
            }
            if(sum > 1){
                if(!mp[zs[j]]) mp[zs[j]] = ++ cnt;
                pd[mp[zs[j]]].push_back(sum);
            }
        }
        if(x > 1){
            if(!mp[x]) mp[x] = ++ cnt;
            pd[mp[x]].push_back(x);
        }
    }
    for(int i = 1; i <= cnt; i ++){
        sort(pd[i].begin(), pd[i].end());
    }
    ll ans = 0, p = 0;
    queue<ll> op;
    for(int i = 1; i <= n; i ++){
        ll ret = 1;
        if(!p){
            for(int j = 1; j <= cnt; j ++){
                if(pd[j].size() == 0) continue;
                ret = ret * pd[j].back() % MOD;
                pd[j].pop_back();
                if(pd[j].size()) op.push(j);
            }
            p = 1;
        }
        else{
            ll PP = op.size(), ct = 0;
            // cout << PP << endl;
            while(PP){
                if(ct == PP) break;
                ll j = op.front();
                op.pop();
                ret = ret * pd[j].back() % MOD;
                ct ++;
                pd[j].pop_back();
                if(pd[j].size()) op.push(j);
            }
        }
        ans = (ans + ret) % MOD;
    }
    cout << ans << "\n";
}
void init(){
    for(int i = 2; i <= MAXN; i ++){
        if(!p[i]){
            zs.push_back(i);
            for(int j = i; j <= MAXN; j += i){
                p[j] = 1;
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    init();
    cin >> Tex;
    while(Tex --) AC();
    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
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

# G - Multiples of 5

# Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 2e5 + 5;
ll Tex, n, sum = 0;
void AC(){
    sum = 0;
    cin >> n;
    for(int i = 1; i <= n; i ++){
        ll a;
        char b;
        cin >> a >> b;
        if(b == 'A') b -= 'A';
        else b -= '0';
        sum += a * b;
    }
    if(sum % 5 == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> Tex;
    while(Tex --) AC();
    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

# H - Convolution

# Solution

考虑卷积核 KK 中的每个元素产生的贡献，KK 中的每个元素都对应矩阵 II 中的一个子矩阵

如果只需要用前缀和找出子矩阵的正负即可

# Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 2e3 + 5;
ll n, m, k, l, a[MAXN][MAXN], s[MAXN][MAXN], sum;
int main(){
    // freopen("in.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin >> n >> m >> k >> l;
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            cin >> a[i][j];
            s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    k = n - k + 1;
    l = m - l + 1;
    for(int i = k; i <= n; i ++){
        for(int j = l; j <= m; j ++){
            sum += abs(s[i][j] - s[i - k][j] - s[i][j - l] + s[i - k][j - l]);
        }
    }
    cout << sum << endl;
    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

# I - Neuvillette Circling

# Question

给定 nn 个点，对于 k=2,⋯,nk=2,\cdots,n 分别回答所有的 kk 点覆盖圆中最小的半径

# Solution

由于 n=100n=100 很小

直接分别用两点作为直接确定一个圆，和圆上三点确定一个圆，然后再 O(n)O(n) 看这个圆覆盖了几个圆

# Code

#include <bits/stdc++.h>
using namespace std;

const double eps = 1e-10;

struct Point {
    double x, y;
    Point() {}
    Point(double x, double y) : x(x), y(y) {}
};

typedef Point Vector;

Vector operator + (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); }
Vector operator - (Point A, Point B) { return Vector(A.x - B.x, A.y - B.y); }
Vector operator * (Vector A, double p) { return Vector(A.x * p, A.y * p); }
Vector operator / (Vector A, double p) { return Vector(A.x / p, A.y / p); }

int dcmp(double x, double y = 0.0) { // 比较两个浮点数的大小
    if (fabs(x - y) < eps) return 0;
    return x < y ? -1 : 1;
}

bool operator == (const Point &a, const Point &b) {
    return dcmp(a.x, b.x) == 0 && dcmp(a.y, b.y) == 0;
}

double dis(Point A, Point B) {
    return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

Point middle(Point A, Point B) {
    return Point((A.x + B.x) / 2, (A.y + B.y) / 2);
}

double dot(Vector A, Vector B) { return A.x * B.x + A.y * B.y; }

double length(Vector A) { return sqrt(dot(A, A)); }

Vector normal (Vector A) { // 左转 90 度， 单位法向量
    double L = length(A);
    return Vector(-A.y / L, A.x / L);
}

double cross(Vector A, Vector B) { return A.x * B.y - A.y * B.x; }

struct Line {
    Point P;
    Vector v;
    Line() {}
    Line(Point P, Vector v) : P(P), v(v) {}
    Point point(double t) { return P + v * t; }
};

bool is_point_on_segment(Point P, Point A, Point B) {
    return dcmp(cross(A - P, B - P)) == 0;
}

Point line_intersection(Line a, Line b) {
    Vector u = a.P - b.P;
    double t = cross(b.v, u) / cross(a.v, b.v);
    return a.point(t);
}

int main() {
    // freopen ("I.in", "r", stdin);
    int n; cin >> n;
    vector<Point> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i].x >> p[i].y;
    }
    vector<double> res(n + 1, 1e9);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            int cnt = 2;
            Point mid = middle(p[i], p[j]);
            double r = dis(p[i], p[j]) / 2;
            for (int k = 0; k < n; k++) {
                if (k == i || k == j) continue;
                if (dcmp(r, dis(mid, p[k])) == -1) continue;
                cnt += 1;
            }
            res[cnt] = min(res[cnt], r);
        }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                if (i == k || j == k) continue;
                if (is_point_on_segment(p[k], p[i], p[j])) continue;
                Line LA = Line(middle(p[i], p[j]), normal(p[i] - p[j]));
                Line LB = Line(middle(p[i], p[k]), normal(p[i] - p[k]));
                Point mid = line_intersection(LA, LB);
                int cnt = 3;
                double r = dis(mid, p[i]);
                for (int q = 0; q < n; q++) {
                    if (i == q || j == q || k == q) continue;
                    if (dcmp(r, dis(p[q], mid)) == -1) continue;
                    cnt += 1;
                }
                res[cnt] = min(res[cnt], r);
            }
        }
    for (int i = 2, j = 1; i <= n; i++) {
        int tp = i * (i - 1) / 2;
        while (j <= tp) {
            printf ("%.10lf\n", res[i]);
            j += 1;
        }
    }
    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
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

# J - Magic Mahjong

麻将题

# Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll Tex;
string s;
bool check1(map<string, int> &mp){
    bool p = 0;
    if(mp["1s"] == 2 || mp["9s"] == 2 || mp["1p"] == 2 || mp["9p"] == 2 || mp["1m"] == 2 || mp["9m"] == 2) p = 1;
    if(mp["1s"] && mp["9s"] && mp["1p"] && mp["9p"] && mp["1m"] && mp["9m"]);
    else return 0;
    for(char i = '1'; i <= '7'; i ++){
        string pp;
        pp.push_back(i);
        pp.push_back('z');
        if(mp[pp] == 2) p = 1;
        if(mp[pp]);
        else return 0;
    }
    return 1;
}
bool check2(map<string, int> &mp){
    for(auto it : mp){
        if(it.second != 2) return 0;
    }
    return 1;
}
void AC(){
    cin >> s;
    map<string, int> mp;
    for(int i = 0; i < s.size(); i += 2){
        string p;
        p.push_back(s[i]);
        p.push_back(s[i + 1]);
        mp[p] ++;
    }
    if(check2(mp)) cout << "7 Pairs" << endl;
    else if(check1(mp)) cout << "Thirteen Orphans" << endl;
    else cout << "Otherwise" << endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> Tex;
    while(Tex --) AC();
    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

# K - Magic Tree

# Question

2×n2\times n 格子从 (1,1)(1,1) 走四联通进行 dfs，问有多少种不同的 dfs 树

# Solution

诈骗题

如果一个 dfs 换行后，下次操作其实只有一种情况（因为另外一侧是死路），如果当前没有换行，下次可以选择换行或者不换行

所以答案是 2n−12^{n-1}

# Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 2e5 + 5;
const ll MOD = 998244353;
ll n;
ll fastPow(ll a, ll b){
    ll ret = 1;
    while(b){
        if(b & 1) ret = ret * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    cout << fastPow(2, n - 1) << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# K. Magic Tree

# Question

一个 nn 点 mm 边的无向图，每个点上有 aia_i 个人，nn 个节点中有 kk 个节点为出口，每个出口有一个开放时间 [li,ri][l_i,r_i]。求 1∼T1\sim T 时刻所有人到最近开放出口的路径长度之和

# Solution

先考虑如果每个出口开放的时间无限，这个就是一个多源最短路问题

然后考虑原问题，可以把开放时间抽象成线段，发现其实 kk 个出口，每个出口开关一次，只有最多 2×k2\times k 种开关情况，可以预处理出这些开关情况，然后进行 2k2k 次多源最短路

# Code

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
typedef long long ll;

struct Gate{
    int p, l, r;
    bool operator < (const Gate &b) {
        return l < b.l || (l == b.l && r < b.r);
    }
};

int main() {
    ios::sync_with_stdio(false);
    int n, m, k, T; cin >> n >> m >> k >> T;
    vector<vector<pair<int, int>>> g(n + 1);
    vector<int> cnt(n + 1);
    vector<Gate> gate(k);
    for (int i = 1; i <= n; i++) cin >> cnt[i];
    for (int i = 0; i < k; i++) {
        cin >> gate[i].p >> gate[i].l >> gate[i].r;
    }

    for (int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back({v, w}); g[v].push_back({u, w});
    }

    priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    sort(gate.begin(), gate.end());
    map<int, ll> mp;
    vector<int> tim;
    for (int i = 0; i < k; i++) {
        tim.push_back(gate[i].l);tim.push_back(gate[i].l - 1);
        tim.push_back(gate[i].r);tim.push_back(gate[i].r + 1);
    }
    tim.push_back(0); tim.push_back(T);
    sort(tim.begin(), tim.end());
    tim.erase(unique(tim.begin(), tim.end()), tim.end());
    int pos = 0, S = 0;
    for (int now_tim : tim) {
        while (pos < k && gate[pos].l <= now_tim) {
            S |= (1 << pos);
            pq.push({gate[pos].r, pos});
            pos += 1;
        }
        while (!pq.empty() && pq.top().first < now_tim) {
            int id = pq.top().second; pq.pop();
            S ^= (1 << id);
        }
        
        if (mp.find(S) == mp.end())
            mp[S] = -1;
    }
    
    auto dij = [&](int S) {
        vector<int> dis(n + 1, INF);
        vector<int> vis(n + 1, 0);
        if (S == 0) return -1ll;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        for (int i = 0; i < k; i++){
            if (S >> i & 1) {
                dis[gate[i].p] = 0; pq.push({0, gate[i].p});
            }
        }
        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            for (auto [v, w] : g[u]) {
                if (dis[u] + w < dis[v]) {
                    dis[v] = dis[u] + w;
                    pq.push({dis[v], v});
                }
            }
        }
        ll ret = 0;
        for (int i = 1; i <= n; i++)
            ret += 1ll * cnt[i] * dis[i];
        return ret;
    };

    for (auto &[S, val] : mp) {
        val = dij(S);
    }
    
    while (!pq.empty()) pq.pop();
    pos = 0; S = 0;
    for (int now_tim = 1; now_tim <= T; now_tim++) {
        while (pos < k && gate[pos].l <= now_tim) {
            S |= (1 << pos);
            pq.push({gate[pos].r, pos});
            pos += 1;
        }
        while (!pq.empty() && pq.top().first < now_tim) {
            int id = pq.top().second; pq.pop();
            S ^= (1 << id);
        }
        if (mp.find(S) == mp.end())
            mp[S] = -1;
        cout << mp[S] << '\n';
    }
    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
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
上次更新: 2025/04/08, 18:03:31
ICPC2024 武汉邀请赛 题解
ICPC2024 网络赛 第一场 题解

← ICPC2024 网络赛 第一场 题解→

最近更新
01
Java基础语法
05-26
02
开发环境配置
05-26
03
pink 老师 JavaScript 学习笔记
05-26
更多文章>
Theme by Vdoing | Copyright © 2024-2025 Martian148 | MIT License