2023年上海市大学生程序设计竞赛-四月赛
A. 宝石划分
题目大意
海盗们获得了$n$颗相同的宝石(宝石无法切割)
船上共$m$个海盗,他们希望能够完美地瓜分这些宝石,即每个人获得的宝石数量相同,但是目前可能无法完美地瓜分
他们商量:如果在座的各位无法完美地瓜分这些宝石,就随机把一个人扔下船,直到可以让每个海盗分到的宝石一样多为止
求最终每个海盗获得的宝石数量
解题思路
如果$n\leq m$,肯定是扔到人和宝石一样多,答案为$1$
否则,要扔到$n$的所有约数中最靠近$m$且小于等于$m$的那一个约数
具体代码
#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$的合法方案有多少种
转移式子很简单
具体代码
#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$次询问去确定剩下的值
具体代码
#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$个
和蓝书上的《装满的油箱》有点像
具体代码
#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$(会覆盖原有颜色)
在每次操作后,输出当前整面墙壁上的颜色种类总数
解题思路
珂朵莉树
数据没有保证随机,复杂度有点玄学
具体代码
#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;
}