2023年上海市大学生程序设计竞赛-四月赛

发表于 更新于 阅读次数： 本文字数： 9.1k 阅读时长 ≈ 16 分钟

2023年上海市大学生程序设计竞赛-四月赛

A. 宝石划分

题目大意

海盗们获得了$n$颗相同的宝石(宝石无法切割)
船上共$m$个海盗，他们希望能够完美地瓜分这些宝石，即每个人获得的宝石数量相同，但是目前可能无法完美地瓜分
他们商量：如果在座的各位无法完美地瓜分这些宝石，就随机把一个人扔下船，直到可以让每个海盗分到的宝石一样多为止
求最终每个海盗获得的宝石数量

解题思路

如果$n\leq m$，肯定是扔到人和宝石一样多，答案为$1$
否则，要扔到$n$的所有约数中最靠近$m$且小于等于$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
#include <bits/stdc++.h>
using ll = long long;
const ll MOD = 998244353;
std::vector<ll> res;
void get_divisors(ll n)
{
    for (ll i = 1; i <= n / i; ++i)
    {
        if (n % i == 0)
        {
            res.push_back(i);
            if (i != n / i)
                res.push_back(n / i);
        }
    }
    std::sort(res.begin(), res.end());
}
void solve()
{
    ll n, m;
    std::cin >> n >> m;
    if (n <= m)
    {
        std::cout << 1 << '\n';
        return;
    }
    else
    {
        get_divisors(n);
        int l = 0, r = res.size() - 1;
        while (l < r)
        {
            int mid = (l + r + 1) >> 1;
            if (res[mid] <= m)
                l = mid;
            else
                r = mid - 1;
        }
        std::cout << n / res[l] << '\n';
    }
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    // std::cin >> T;
    while (T--)
        solve();
    return 0;
}

B. CHAO！OP！

题目大意

济云星这个星球上的语言是摩斯电码，对应$26$个大写字母
现在有一篇文章
已知文章是人写的，也是给人看的，那么它就不应该出现$OP$
现在将这篇文章的摩斯电码给你，请你算一算，这段电码有多少种划分方案，使得最后的文章不存在子串$OP$
请输出划分的方案数，对$10^9+7$取模
字符串中$1$代表$-$,$0$代表$\cdot$

解题思路

计数$dp$
考虑对状态进行划分，最后一个划分出的字符是否是$O$
$dp[n][0/1]$表示对于前$n$位，最后一个字符不是$/$是$O$的合法方案有多少种
转移式子很简单

具体代码

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
#include <bits/stdc++.h>
using ll = long long;
const ll MOD = 1e9 + 7;
const int N = 1e6 + 10;
const int M = 2;
std::map<std::string, char> mp;
ll dp[N][M];
ll add(ll a, ll b)
{
    ll res = a + b;
    if (res > MOD)
        res -= MOD;
    return res;
}
void solve()
{
    mp["01"] = 'A';
    mp["1000"] = 'B';
    mp["1010"] = 'C';
    mp["100"] = 'D';
    mp["0"] = 'E';
    mp["0010"] = 'F';
    mp["110"] = 'G';
    mp["0000"] = 'H';
    mp["00"] = 'I';
    mp["0111"] = 'J';
    mp["101"] = 'K';
    mp["0100"] = 'L';
    mp["11"] = 'M';
    mp["10"] = 'N';
    mp["111"] = 'O';
    mp["0110"] = 'P';
    mp["1101"] = 'Q';
    mp["010"] = 'R';
    mp["000"] = 'S';
    mp["1"] = 'T';
    mp["001"] = 'U';
    mp["0001"] = 'V';
    mp["011"] = 'W';
    mp["1001"] = 'X';
    mp["1011"] = 'Y';
    mp["1100"] = 'Z';
    std::string str;
    std::cin >> str;
    int n = str.length();
    str = "?" + str;
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int len = 1; len <= std::min(i, 4); ++len)
        {
            std::string tmp = std::string(str.begin() + 1 + i - len, str.begin() + 1 + i);
            if (mp.count(tmp))
            {
                char c = mp[tmp];
                if (c == 'O')
                    dp[i][1] = add(dp[i][1], add(dp[i - len][0], dp[i - len][1]));
                else if (c == 'P')
                    dp[i][0] = add(dp[i][0], dp[i - len][0]);
                else
                    dp[i][0] = add(dp[i][0], add(dp[i - len][0], dp[i - len][1]));
            }
        }
    std::cout << add(dp[n][0], dp[n][1]) << '\n';
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    // std::cin >> T;
    while (T--)
        solve();
    return 0;
}

C. dataHacker

题目大意

你是一名黑客，你的目标是破解一个神秘组织的数据库
你不能直接访问他们的数据，因为他们使用了一种特殊的加密算法
你只能询问指定两个位置的校验码，也就是得到两个不同位置的数据块的按位与运算的结果
总共$n$个数据块，每个数据块由$[0,1023]$范围内的整数构成
你需要在有限的$2\times n+220$次询问（包括回答）内，还原出他们的所有数据块
下面是交互流程
首先输入一个整数$n$
你的程序有两种输出询问的方式
第一种：
$0\ p1\ p2$
询问$p1,p2$两个位置的“与”的结果
其中$p1,p2$是编号从$0$开始的两个不同的位置
$p1\neq p2$并且$0\leq p1,p2\leq n-1$
第二种：
$1\ a0\ a1\ a2\cdots$
$1$后面连续$n$个整数，代表数组内容
如果数组内容正确，结果会返回AC
数组保证随机生成

解题思路

每个元素的值是所有和其有关的询问的结果的”或”
因为数据是随机生成，大概率有两个值的”或”结果是全$1$
利用$220$次询问找到这样的两个值
然后用剩下$2n$次询问去确定剩下的值

具体代码

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>
using ll = long long;
const int N = 1010;
int ans[N];
int n;
int ask(int a, int b)
{
    if (a > b)
        std::swap(a, b);
    std::cout << "0 " << a << " " << b << std::endl;
    int res;
    std::cin >> res;
    return res;
}
void solve()
{
    std::mt19937 rng(std::random_device{}());
    std::cin >> n;
    int o = 220;
    while (o)
    {
        --o;
        int a = rng() % n, b = rng() % n;
        if (a == b)
            continue;
        int res = ask(a, b);
        ans[a] |= res;
        ans[b] |= res;
    }
    int a = -1, b = -1;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if ((ans[i] | ans[j]) == 1023)
                a = i, b = j;
    for (int i = 0; i < n; ++i)
    {
        if (i != a && i != b)
        {
            int res = ask(i, a);
            ans[i] |= res;
            ans[a] |= res;
            res = ask(i, b);
            ans[i] |= res;
            ans[b] |= res;
        }
    }
    std::cout << "1";
    for (int i = 0; i < n; ++i)
        std::cout << " " << ans[i];
    std::cout << std::endl;
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    // std::cin >> T;
    while (T--)
        solve();
    return 0;
}

D. 单词游戏

题目大意

给定$n$个字符串
现在要选至少一个字符串(可以重复选择同一个字符串)来拼接形成回文串
选择每个字符串$s_i$都有对应的代价$c_i$
问构造出回文串的最小代价

解题思路

考虑最后构造出的回文串长什么样子
如果由单一串构成，那很简单
如果由多个不同串构成，那么选定第一个串，其实最后一个串的选择并不多
并且选了一个可能的最后一个串后，可以发现问题变成了一个子问题，要么已经回文，要么还是有一个串的部分没有匹配
考虑状态$dis[i][0/1][j]$表示未能完全匹配的串为第$i$个串，$0/1$表示前$/$后缀，长度为$j$，此时最小的$cost$为多少
然后跑最短路
结点数只有$100\times 2\times 60=12000$个
和蓝书上的《装满的油箱》有点像

具体代码

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
#include <bits/stdc++.h>
using ll = long long;
const ll N = 105;
const ll K = 2;
const ll M = 65;
ll n;
std::string s[N];
ll c[N];
bool ed[N][K][M];
ll dis[N][K][M];
bool vis[N][K][M];
bool check(std::string t)
{
    for (ll i = 0; i < t.size(); ++i)
        if (t[i] != t[t.size() - 1 - i])
            return false;
    return true;
}
struct node
{
    ll i, k, j;
    ll cost;
    node (ll a, ll b, ll c, ll d)
    {
        i = a, k = b, j = c, cost = d;
    };
    friend bool operator < (node a, node b)
    {
        return a.cost > b.cost;
    };
};
node calc(node u, ll x)
{
    std::string t;
    if (u.k == 0)
        t = std::string(s[u.i].begin(), s[u.i].begin() + u.j);
    else
        t = std::string(s[u.i].end() - u.j, s[u.i].end());
    if (u.k == 0)
    {
        ll cnt = 0;
        for (ll i = 0, j = t.size() - 1; i < s[x].size() && j >= 0; ++i, --j)
        {
            if (s[x][i] == t[j])
                ++cnt;
            else
                break;
        }
        if (cnt != std::min(t.size(), s[x].size()))
            return node(-1, -1, -1, -1);
        if (cnt == t.size())
            return node(x, 1, s[x].size() - cnt, u.cost + c[x]);
        if (cnt == s[x].size())
            return node(u.i, u.k, u.j - cnt, u.cost + c[x]);
    }
    else
    {
        ll cnt = 0;
        for (ll i = 0, j = s[x].size() - 1; i < t.size() && j >= 0; ++i, --j)
        {
            if (s[x][j] == t[i])
                ++cnt;
            else
                break;
        }
        if (cnt != std::min(t.size(), s[x].size()))
            return node(-1, -1, -1, -1);
        if (cnt == t.size())
            return node(x, 0, s[x].size() - cnt, u.cost + c[x]);
        if (cnt == s[x].size())
            return node(u.i, u.k, u.j - cnt, u.cost + c[x]);
    }
}
ll dijkstra()
{
    memset(dis, 0x3f, sizeof dis);
    std::priority_queue<node> q;
    for (ll i = 1; i <= n; ++i)
    {
        q.push(node(i, 0, s[i].size(), c[i]));
        dis[i][0][s[i].size()] = 0;
    }
    while (q.size())
    {
        auto u = q.top();
        auto [i, k, j, cost] = q.top();
        q.pop();
        if (ed[i][k][j])
            return cost;
        if (vis[i][k][j])
            continue;
        vis[i][k][j] = true;
        for (ll x = 1; x <= n; ++x)
        {
            auto v = calc(u, x);
            if (v.cost != -1 && dis[v.i][v.k][v.j] > v.cost)
            {
                dis[v.i][v.k][v.j] = v.cost;
                q.push(v);
            }
        }
    }
    return -1;
}
void solve()
{
    std::cin >> n;
    for (ll i = 1; i <= n; ++i)
        std::cin >> s[i] >> c[i];
    for (ll i = 1; i <= n; ++i)
        for (ll k = 0; k <= 1; ++k)
            for (ll j = 0; j <= s[i].size(); ++j)
            {
                std::string t;
                if (k == 0)
                    t = std::string(s[i].begin(), s[i].begin() + j);
                else
                    t = std::string(s[i].end() - j, s[i].end());
                ed[i][k][j] = check(t);
            }
    std::cout << dijkstra() << '\n';
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    ll T = 1;
    // std::cin >> T;
    while (T--)
        solve();
    return 0;
}

E. 画画的贝贝

题目大意

给定一面颜色初始为$1$的长度为$n$的墙
进行$m$次操作
每次操作将$[l,r]$区间内的墙涂成颜色$c$(会覆盖原有颜色)
在每次操作后，输出当前整面墙壁上的颜色种类总数

解题思路

珂朵莉树
数据没有保证随机，复杂度有点玄学

具体代码

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
#include <bits/stdc++.h>
using ll = long long;
const int N = 1e6 + 10;
struct Node
{
    ll l, r;
    ll c;
    Node(ll x = 0, ll y = 0, ll z = 0)
    {
        l = x, r = y, c = z;
    }
    friend bool operator<(Node a, Node b)
    {
        return a.l < b.l;
    }
};
std::set<Node> S;
using S_IT = std::set<Node>::iterator;
ll n, m;
ll cnt[N];
ll ans;
S_IT split(int pos)
{
    S_IT it = S.lower_bound(Node(pos, 0, 0));
    if (it != S.end() && it->l == pos)
        return it;
    --it;
    ll l = it->l, r = it->r, c = it->c;
    S.erase(it);
    S.insert(Node(l, pos - 1, c));
    return S.insert((Node(pos, r, c))).first;
}
void assign(int l, int r, int c)
{
    S_IT it2 = split(r + 1), it1 = split(l);
    for (S_IT it = it1; it != it2; ++it)
    {
        cnt[it->c] -= (it->r - it->l + 1);
        if (cnt[it->c] == 0)
            --ans;
    }
    S.erase(it1, it2);
    S.insert(Node(l, r, c));
    if (cnt[c] == 0)
        ++ans;
    cnt[c] += r - l + 1;
}
void solve()
{
    std::cin >> n >> m;
    S.insert(Node(1, n, 1));
    S.insert(Node(n + 1, n + 1, 0));
    cnt[1] = n;
    ans = 1;
    for (int i = 1; i <= m; ++i)
    {
        ll l, r, c;
        std::cin >> l >> r >> c;
        assign(l, r, c);
        std::cout << ans << '\n';
    }
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    // std::cin >> T;
    while (T--)
        solve();
    return 0;
}