img

2024 (ICPC) Jiangxi Provincial Contest -- Official Contest

（坐牢一下午，坐不下去了）

image-20240813162903057

A

题意：a + b + c

签到题，哎，有点手残。

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

C

题意：n 个 数字总和是 s ，每个人说出自己得到的数字，有人可能撒谎，问最多有多少人说真话

思路：如果总和正确的话就直接就是n,不然的话就是直接n-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
// 2024 (ICPC) Jiangxi Provincial Contest -- Official Contest
// Totoroの旅
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
        int n, x;
        cin >> n >> x;
        ll sum = 0;
        for (int i = 1; i <= n; i++)
        {
                int d;
                cin >> d;
                sum += d;
        }
        if (sum == x)
        {
                cout << n << '\n';
        }
        else
        {
                cout << n - 1 << '\n';
        }
        return 0;
}

D

题意：给定 n 个数，每次可以选定两个数，把其中一个改为 gcd(x, y)，另外一个改为 lcm(x, y)，求最大的数列和

思路：贪心的把最大的幂次交给最大的，依次贪心即可。

最后不要忘记最多项数的质因子会变成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
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
// 2024 (ICPC) Jiangxi Provincial Contest -- Official Contest
// Totoroの旅
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;
const int N = 1e6 + 100;
const ll INF = 1e18;
ll ksm(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
        {
            ans = ans * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return ans % mod;
}
int p[N];
int sum;
int vis[N];
void prime()
{
    for (int i = 2; i <= N; i++)
    {
        if (!vis[i])
        {
            p[++sum] = i;
        }
        for (int j = 1; p[j] * i <= N; j++)
        {
            vis[p[j] * i] = 1;
            if (i % p[j] == 0)
            {
                break;
            }
        }
    }
    vis[1] = 1;
}
void Totoro()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    map<int, vector<int>> mp;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        int x = a[i];
        for (int j = 1; j <= sum; j++)
        {
            if (p[j] * p[j] > x)
            {
                break;
            }
            int cnt = 0;
            while (x % p[j] == 0)
            {
                x /= p[j];
                cnt++;
            }
            if (cnt != 0)
            {
                mp[p[j]].push_back(cnt);
            }
        }
        if (x > 1)
        {
            mp[x].push_back(1);
        }
    }
    int len = 0;
    for (auto &x : mp)
    {
        auto &vec = x.second;
        len = max(len, (int)vec.size());
        sort(vec.begin(), vec.end());
    }
    int k = 1;
    int ans = 0;
    for (int i = 0; i < len; i++)
    {
        int t = 1;
        for (auto it = mp.begin(); it != mp.end();)
        {
            auto &vec = it->second;
            int siz = vec.size();
            if (siz - k >= 0)
            {
                t = (t * ksm(it->first, vec[siz - k])) % mod;
                if (siz - k == 0)
                {
                    mp.erase(it++);
                }
                else
                {
                    ++it;
                }
            }
        }
        k++;
        ans = (ans + t) % mod;
    }
    ans = (ans + (n - len)) % mod;
    cout << ans << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    prime();
    while (t--)
    {
        Totoro();
    }
    return 0;
}

G

题意：给定一个11进制数，求它是不是 5 的倍数

思路：11的每一项幂最后一个数字都是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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 2024 (ICPC) Jiangxi Provincial Contest -- Official Contest
// Totoroの旅
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void Totoro()
{
        ll n;
        cin >> n;
        ll ans = 0;
        for (int i = 1; i <= n; i++)
        {
                ll a1, a2;
                char b;
                cin >> a1 >> b;
                if (b != 'A')
                {
                        a2 = (b - '0');
                }
                else
                {
                        a2 = 10;
                }
                ans = (ans + a1 * a2) % 5;
        }
        if (ans == 5 || ans == 0)

        {
                cout << "Yes\n";
        }
        else
        {
                cout << "No\n";
        }
}
int main()
{
        int t;
        cin >> t;
        while (t--)
        {
                Totoro();
        }
        return 0;
}

H

题意：给定一个n * m的矩阵 a ，求一个k * l的矩阵 b 和 a 的乘积的最小值，b 只包含(-1, 0, 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
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
// 2024 (ICPC) Jiangxi Provincial Contest -- Official Contest
// Totoroの旅
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;
const int N=1e3+100;
int a[N][N];
ll ksm(ll a, ll b)
{
        ll ans = 1;
        while (b)
        {
                if (b & 1)
                {
                        ans = ans * a % mod;
                }
                a = a * a % mod;
                b >>= 1;
        }
        return ans % mod;
}
void Totoro()
{
        int n, m;
        cin >> n >> m;
        int p, q;
        cin >> p >> q;
        for (int i = 1; i <= n; i++)
        {
                for (int j = 1; j <= m; j++)
                {
                        cin >> a[i][j];
                }
        }
        for (int i = 1; i <= n; i++)
        {
                for (int j = 1; j <= m; j++)
                {
                        a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
                }
        }
        ll ans = 0;
        for (int i = 1; i <= p; i++)
        {
                for (int j = 1; j <= q; j++)
                {
                        int x = n - p + i;
                        int y = m - q + j;
                        ans += abs(a[x][y] - a[i - 1][y] - a[x][j - 1] + a[i - 1][j - 1]);
                }
        }
        cout << ans << '\n';
}
int main()
{
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int t = 1;
        // cin >> t;
        while (t--)
        {
                Totoro();
        }
        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
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
#include <bits/stdc++.h>
using namespace std;

// 定义所有的牌的编号
unordered_set<string> terminals = {"1p", "9p", "1s", "9s", "1m", "9m"};
unordered_set<string> honors = {"1z", "2z", "3z", "4z", "5z", "6z", "7z"};
unordered_set<string> thirteenOrphansSet = {"1p", "9p", "1s", "9s", "1m", "9m", "1z", "2z", "3z", "4z", "5z", "6z", "7z"};

// 判断是否是“十三幺”
bool isThirteenOrphans(vector<string>& hand) {
    unordered_map<string, int> counts;
    for (auto& tile : hand) {
        counts[tile]++;
    }
    // 检查是否包含所有老头牌和字牌，并且其中一张牌出现两次
    bool hasPair = false;
    for (auto& tile : thirteenOrphansSet) {
        if (counts[tile] == 0) return false;
        if (counts[tile] == 2) hasPair = true;
    }
    return hasPair;
}

// 判断是否是“七对”
bool isSevenPairs(vector<string>& hand) {
    unordered_map<string, int> counts;
    for (auto& tile : hand) {
        counts[tile]++;
    }
    // 检查是否有7对不同的牌
    if (counts.size() != 7) return false;
    for (auto& pair : counts) {
        if (pair.second != 2) return false;
    }
    return true;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        vector<string> hand;
        for (int i = 0; i < 28; i += 2) {
            hand.push_back(s.substr(i, 2));
        }

        if (isThirteenOrphans(hand)) {
            cout << "Thirteen Orphans" << endl;
        } else if (isSevenPairs(hand)) {
            cout << "7 Pairs" << endl;
        } else {
            cout << "Otherwise" << endl;
        }
    }
    return 0;
}

K

题意：2 * n的路有几条不同的填充方式

思路：手画一下发现$ 2^{（n - 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
29
30
31
32
33
34
35
36
// 2024 (ICPC) Jiangxi Provincial Contest -- Official Contest
// Totoroの旅
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;
ll ksm(ll a, ll b)
{
        ll ans = 1;
        while (b)
        {
                if (b & 1)
                {
                        ans = ans * a % mod;
                }
                a = a * a % mod;
                b >>= 1;
        }
        return ans % mod;
}
void Totoro()
{
        int n;
        cin >> n;
        cout << ksm(2, n - 1) << '\n';
}
int main()
{
        int t = 1;
        // cin >> t;
        while (t--)
        {
                Totoro();
        }
        return 0;
}

L

题意：一个 n 个点 m 条边的无向图，每个节点上有 \(a_i\) 个人。n 个节点中有 k 个 节点为出口，每个出口有一个开放时间 [\(l_i\) ,$ r_i$ ]。求第 1 ∼ T 时刻所有人到 最近的开放出口的路径长度之和。

我嘞个调了一小时啊。

具体就是预处理出每一种出口对每个人的最短路，然后取min即可。

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
// 2024 (ICPC) Jiangxi Provincial Contest -- Official Contest
// Totoroの旅
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;
const int N = 1e6 + 100;
const ll INF = 1e18;
ll a[N];
int n, m, k, t;
struct Node
{
    ll l, r, id;
    bool operator<(Node &a_)
    {
        return l < a_.l;
    }
} b[N];
struct Edge
{
    ll to, w;
};
vector<Edge> edge[N];
void _dijksra(ll s, vector<ll> &p)
{
    vector<ll> dist(n + 1, 1e9);
    vector<bool> vis(n + 1, false);
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q;
    dist[s] = 0;
    for (ll i = 1; i <= n; i++)
    {
        q.push({dist[i], i});
    }
    while (!q.empty())
    {
        ll x = q.top().second;
        q.pop();
        if (vis[x])
        {
            continue;
        }
        vis[x] = 1;
        for (auto y : edge[x])
        {
            if (dist[x] + y.w < dist[y.to])
            {
                dist[y.to] = dist[x] + y.w;
                q.push({dist[y.to], y.to});
            }
        }
    }
    // for(int i=1;i<=n;i++)
    // {
    //         cout<<dist[i]<<'\n';
    // }
    p = dist;
}
ll ksm(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
        {
            ans = ans * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return ans % mod;
}
ll ans[N];
void Totoro()
{
    cin >> n >> m >> k >> t;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= k; i++)
    {
        cin >> b[i].id >> b[i].l >> b[i].r;
    }
    for (int i = 1; i <= m; i++)
    {
        ll u, v, w;
        cin >> u >> v >> w;
        edge[u].push_back({v, w});
        edge[v].push_back({u, w});
    }
    vector<vector<ll>> d(k + 1, vector<ll>(n + 1));

    for (int i = 1; i <= k; i++)
    {
        _dijksra(b[i].id, d[i]);
    }

    map<string, vector<ll>> mp;
    string s1;
    for (int i = 1; i <= k; i++)
    {
        s1 += '0';
    }
    for (int i = 1; i <= t; i++)
    {
        string s = s1;
        for (int j = 1; j <= k; j++)
        {
            if (b[j].l <= i && i <= b[j].r)
            {
                s[j - 1] = '1';
            }
        }
        mp[s].push_back(i);
    }
    for (auto &[x, y] : mp)
    {
        vector<ll> q(n + 1, INF);
        bool ok = 0;
        for (int i = 1; i <= k; i++)
        {
            if (x[i - 1] == '1')
            {
                ok = 1;
                for (int j = 1; j <= n; j++)
                {
                    q[j] = min(q[j], d[i][j]);
                }
            }
        }
        ll res = 0;
        if (!ok)
        {
            res = -1;
        }
        else
        {
            for (int i = 1; i <= n; i++)
            {
                res += a[i] * q[i];
            }
        }
        for (auto v : y)
        {
            ans[v] = res;
        }
    }

    for (int i = 1; i <= t; i++)
    {
        cout << ans[i] << '\n';
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        Totoro();
    }
    return 0;
}