2023 (ICPC) Jiangxi Provincial Contest -- Official Contest

A

image-20240815174951467

正常判断即可。

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;
const int N = 1e6 + 100;
ll a[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()
{
    ll n, s, v;
    cin >> n >> s >> v;
    if (s * v >= n)
    {
        cout << 1 << "\n";
    }
    else
    {
        cout << 0 << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
        Totoro();
    return 0;
}

B

image-20240815175001381

正难则反。

考虑求大于，将\(a_i\)对m取模，不会影响答案。因为0 ⩽ bi+1 − bi < m

所以：bi mod m > bi+1 mod m ⇐⇒ ⌊bi/m⌋ < ⌊bi+1/m⌋

因此，>的个数应该就是\(b_n\)能够整除多少个m

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;
const int N = 1e6 + 100;
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()
{
    ll n, m, k;
    cin >> k;
    ll sum = 0;
    vector<ll> a(k + 10);
    for (int i = 1; i <= k; i++)
    {
        cin >> a[i];
    }
    ll x;
    cin >> n >> m >> x;
    ll b;
    b = x % m;
    for (int i = 1; i <= k; i++)
    {
        a[i] %= m;
        sum += a[i];
    }
    b += (n / k) * sum;
    ll res = n % k;
    for (int i = 1; i <= res; i++)
    {
        b += a[i];
    }
    cout << n - b / m;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        Totoro();
    return 0;
}

H

image-20240815174756724

我们考虑前缀 max 的位置$ l_1 < l_2 < ... < l_k$，如果在序列 A 选了 \(p_{l_i}\)，那 么序列 B 开头的元素一定比\(p_{l_i}\)大，\([l_i,l_i+1)\) 这一段一定在序列 A 中。 那么问题就转化成了一个多重集合 S，是否存在 S 的子集使得子集和为 n/2 。 有一个很重要的性质，多重集合 S 所有数的和是 n，这意味着 S 中本质 不同的数只有 √ n 个。我们对这 √ 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
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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;
const int N = 1e6 + 100;
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;
    vector<ll> a(n + 1), pre(n + 1), cnt(n + 1), f(n + 1), bkt(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        pre[i] = max(pre[i - 1], a[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        ++cnt[pre[i]];
    }
    f[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        if (cnt[i])
        {
            ++bkt[cnt[i]];
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (bkt[i])
        {
            ll sum = 0;
            for (int j = 0; sum + (1 << j) <= bkt[i]; ++j)
            {
                int v = i * (1 << j);
                sum += 1 << j;
                for (int k = n >> 1; k >= v; k--)
                {
                    f[k] |= f[k - v];
                }
            }
            if (sum != bkt[i])
            {
                int v = i * (bkt[i] - sum);
                for (int k = n >> 1; k >= v; k--)
                {
                    f[k] |= f[k - v];
                }
            }
        }
    }
    if (f[n >> 1])
    {
        cout << "Yes" << '\n';
    }
    else
    {
        cout << "No" << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
        Totoro();
    return 0;
}

I

image-20240815174649142 
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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;
const int N = 1e6 + 100;
ll f[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, k;
    cin >> n >> k;
    for (int i = 0; i < n - 1; ++i)
    {
        int x, y, z;
        cin >> x >> y >> z;
        f[x] ^= z;
        f[y] ^= z;
    }
    while (k--)
    {
        int op;
        cin >> op;
        if (op == 2)
        {
            int x;
            cin >> x;
            cout << f[x] << '\n';
        }
        else
        {
            int x, y, z;
            cin >> x >> y >> z;
            f[x] ^= z, f[y] ^= z;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        Totoro();
    return 0;
}

J

image-20240815174550288

查询 x = a 时函数的最小值，容易发现可能为最小值的函数只可能在左右 根号的范围内。

那么只要在左右根号的范围内枚举所有函数，找出最优的即可。

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;
const int N = 1e6 + 100;
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;
    vector<int> th(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> th[i];
    }
    cin >> m;
    while (m--)
    {
        int a, b, x, op;
        cin >> op;
        if (op == 1)
        {
            cin >> x;
            int ans = th[x];
            double p = sqrt(th[x]);
            int l = max(1, x - (int)ceil(p));
            int r = min(n, x + (int)ceil(p));
            for (int i = l; i <= r; i++)
            {
                ans = min(ans, th[i] + (x - i) * (x - i));
            }
            cout << ans << '\n';
        }
        else
        {
            cin >> a >> b;
            if (th[a] > b)
            {
                th[a] = b;
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        Totoro();
    return 0;
}

K

image-20240815174610385

操作二本质就是取最小的k-1个差分值的和。

操作一不影响操作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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;
const int N = 1e6 + 100;
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;
    vector<ll> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = n - 1; i >= 1; i--)
    {
        b[i] = a[i] - a[i + 1];
    }
    sort(b.begin() + 1, b.begin() + n, greater<ll>());
    vector<ll> sum(n + 1);
    for (int i = 1; i <= n - 1; i++)
    {
        sum[i] = sum[i - 1] + b[i];
    }
    int m;
    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        int type;
        cin >> type;
        int x;
        cin >> x;
        if (type == 0)
        {
            continue;
        }
        cout << sum[n - 1] - sum[x - 1] << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        Totoro();
    return 0;
}

L

签到题

输出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
37
38
39
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;
const int N = 1e6 + 100;
ll a[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;
    cin >> n;
    cout << n - 1 << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        Totoro();
    return 0;
}