2024
c
c
p
c
中国大学生程序设计竞赛（郑州全国邀请赛）
\Huge{2024ccpc中国大学生程序设计竞赛（郑州全国邀请赛）}2024ccpc中国大学生程序设计竞赛（郑州全国邀请赛） P
r
o
b
l
e
m
s
A
、
B
、
F
、
H
、
J
、
K
、
L
、
M
\huge{Problems~A、B、F、H、J、K、L、M}ProblemsA、B、F、H、J、K、L、M 文章目录 Problem A. Once In My Life 题意 思路 标程 Problem B. 扫雷 1 题意 思路 标程 Problem F. 优秀字符串 题意 思路 标程 Problem H. 随机栈 题意 思路 标程 Problem J. 排列与合数 题意 思路 标程 Problem K. 树上问题 题意 思路 标程 Problem L. Toxel与PCPC II 题意 思路 标程 Problem M. 有效算法 题意 思路 标程 模板 题目链接：Dashboard - 2024 National Invitational of CCPC (Zhengzhou), 2024 CCPC Henan Provincial Collegiate Programming Contest - Codeforces 写在前面… 破铜烂铁选手，这次拿到了邀请赛的铜牌🥉。
再接再励！
补题环节… 题解中的标程只放了伪代码，完整模板我放在了最后。
Problem A. Once In My Life 题意 给定两个整数 n
,
d
n,dn,d ，然后要求构造一个数字 k
kk ，要求 n
×
k
n\times kn×k 的值的数位中包含 0...9
0...90...9 至少一次，并且 d
(
1
≤
d
≤
9
)
d(1\le d\le 9)d(1≤d≤9) 至少两次。
思路 赛时的一道签到题，可是过题数好少。
我们按照顺序来构造即可： 我们考虑先构造出 N
=
n
×
k
N=n \times kN=n×k ，那么 1234567890
+
d
1234567890+d1234567890+d 即符合题意。
然后我们考虑在 N
NN 后面加上若干位数字使得在不改变 N
NN 的前面 10
1010 位的情况下能够被 n
nn 整除。
上一步的具体方法为： 让 N
NN 左移 n
nn 的位数位，然后加上 n
nn （把 n
nn 放在 N
NN 后边），然后减去 N
%
n
N\%nN%n ，就可以被 n
nn 整除了。
标程
#define int long long
void Solved() {
int n, d; cin >> n >> d;
int len = to_string(n).size();
int luck = (1234567890 + d) * pow(10, len);
luck += n;
luck -= luck % n;
cout << luck / n << endl;
}
Problem B. 扫雷 1 题意 进行 n
nn 轮游戏，每轮会获得一个扫雷币，每轮可以买地雷探测器，给出每轮的地雷探测器的价格，求最多能买多少个地雷探测器？
思路 可以维护一个单调队列，每次存这位置地雷探测器的价格和下标。
在单调队列里第 i
ii 个位置下标前攒的扫雷币都可以用这个价格来买。
标程
#define int long long
#define fi first
#define se second
void Solved() {
int n; cin >> n;
vector a;
for(int i = 1; i <= n; i ++ ) {
int x; cin >> x;
while(!a.empty() && a.back().fi >= x) a.pop_back();
a.push_back({x, i});
}
int res = a[0].se / a[0].fi;
int t = a[0].se % a[0].fi, len = a.size();
for(int i = 1; i < len; i ++ ) {
res += (a[i].se - a[i - 1].se + t) / a[i].fi;
t = (a[i].se - a[i - 1].se + t) % a[i].fi;
}
cout << res << endl;
}
Problem F. 优秀字符串 题意 给出优秀字符串的定义： 长度为5。
第三个字符和第五个字符相同。
前四个字符互不相同。
求优秀字符串个数。
思路 签到题，模拟即可。
标程
void Solved() {
int n; cin >> n;
int res = 0;
for(int i = 1; i <= n; i ++ ) {
string s; cin >> s;
if(s.size() != 5) continue;
if(s[2] != s[4]) continue;
bool f = 1;
for(int i = 0; i < 4; i ++ )
for(int j = i + 1; j < 4; j ++ )
if(s[i] == s[j]) f = 0;
res += f;
}
cout << res << endl;
}
Problem H. 随机栈 题意 题目给出 2
n
2n2n 次操作，每次操作有两种情况： −
1
-1−1 ：从当前集合中取出一个数。
非 −
1
-1−1 ：将当前数字放入集合中。
两种情况各 n
nn 次，求最后取出的数字数组为递增（ 小于等于后一项 ）的概率，概率 p
q
\frac{p}{q}qp 表示为： p
×
q
−
1
m
o
d
998244353
p\times q^{-1} mod~~998244353p×q−1mod998244353 。
思路 题目要求输出的数字数组为递增，我们可以通过贪心策略每次只取当前集合中最小的数字；如果当前的最小数字小于前面已选择的数字，那么将不可能构造出升序序列，概率为 0
00 。
题中对应的两种操作我们可以通过大根堆和 m
a
p
mapmap 实现。
但是这道题的一个难点是在求概率上： 容易想到，概率中的分子 p
pp 即为当前集合中最小数的个数；分母 q
qq 即为当前集合中的数字个数。
由于概率需要取模，所以需要用到乘法逆元。
在循环模拟的过程中，分子 p
pp 和分母 q
qq 会非常大，但是我们如果在循环中直接求逆元，会超时。
可以在循环过程中将分子分母分别保存，然后在循环外求逆元即可。
标程
const int mod = 998244353;
int quick_mi(int a,int b) {
int ans = 1;
while(b) {
while(b % 2 == 0)
a = a * a % mod, b = b / 2;
ans = ans * a % mod; b = b - 1;
}
return ans ;
}
void solve() {
int n; cin >> n;
for(int i = 1; i<= 2 * n; i++){
cin >> arr[i];
}
priority_queue,greater> que;
int maxx = 0;
vector z, m;
for(int i = 1; i <= 2 * n; i++){
if(arr[i] > -1){
que.push(arr[i]); mp[arr[i]] ++;
} else {
int temp = que.top();
if(temp < maxx){
cout << "0" << endl; return;
}
maxx = max(maxx,temp);
z.push_back(mp[temp]); m.push_back(que.size());
que.pop(); mp[temp]--;
}
}
int ans = 1;
for(int i : z){
ans *= i; ans %= mod;
}
for(int i : m){
ans = ans * quick_mi(i, mod - 2); ans = ans % mod;
}
cout << ans <
Problem J. 排列与合数 题意 给出一个五位整数，然后将其每位重新排列，组成一个合数并输出；如果无法构造，则输出-1。
思路 签到题 构造合数只需将其中的合数位放在最后即可（注意前导零的情况）。
但是如果没有合数的情况呢？
题目样例中已经给出，五位都是奇数的情况直接输出 97531 即可。
所以说没有 −
1
-1−1 的情况，不用考虑。
标程
void Solved() {
string s; cin >> s;
deque dq;
int sum = 0;
for(int i = 0; i < 5; i ++ ) {
int x = s[i] - '0';
if(x & 1) dq.push_front(x), sum ++;
else dq.push_back(x);
}
if(sum == 5) {
cout << "97531\n";
} else {
for(int i : dq) cout << i; cout << endl;
}
}
Problem K. 树上问题 题意 给出一个由 n
nn 各节点组成的无根树，编号为 1...
n
1...n1...n ，每个节点有一个正整数点权a[i]。
现在定义 美丽节点 ：如果一个节点作为根节点，当其他所有节点的点权都不小于其父节点点权的 1
2
\frac{1}{2}21 时， 当前根节点为美丽节点 。
思路 考虑从边入手： 若x与y之间有边，那么共有两种情况： a
[
x
]
×
2
<a
[
y
]
a[x] \times 2 < a[y]a[x]×2
xx
看作子节点，那么y及其所有祖宗节点都不为美丽节点。
a
[
x
]
×
2
>
a
[
y
]
a[x] \times 2 > a[y]a[x]×2>a[y]
，将
y
yy
看作子节点，那么x及其所有祖宗节点都不为美丽节点。
所以我们只需遍历所有边，并且将上述所有情况的祖宗节点标记即可，最后没有被标记的即为
美丽节点
。
直接遍历会导致超时，通过观察会发现，被标记过的点的祖宗节点必定被标记，不需要再次进行标记，在循环的时候可以提前返回。
但是剪枝后会出现如下情况：
1
3
3 1 1
1 2
1 3
这种情况是因为可行解有超过一个父节点，不符合树的定义。 这种情况需要记录每个节点的父节点，然后进行判断。
标程
vector
void init() {
f.clear(); f.resize(n + 1);
fa.clear(); fa.resize(n + 1);
edge.clear(); flag = 1;
for(int i = 1; i <= n; i ++ ) b[i].clear(), fa[i] = -1;
}
void biaoji(int x) {
if(f[x] || fa[x] == -1) return;
f[x] = 1;
for(auto i : b[x]) {
if(i == fa[x]) continue;
if(fa[i] != -1 && fa[i] != x) {flag = 0; return;}
fa[i] = x;
biaoji(i);
}
}
void Solved() {
cin >> n;
init();
for(int i = 1; i <= n; i ++ ) cin >> a[i];
for(int i = 1; i < n; i ++ ) {
int x, y; cin >> x >> y;
b[x].push_back(y); b[y].push_back(x);
if(a[x] * 2 < a[y]) { //把x当作子节点，y当作父节点
if(fa[y] != -1) flag = 0;
fa[y] = x;
}
if(a[y] * 2 < a[x]){ //把y当作子节点，x当作父节点
if(fa[x] != -1) flag = 0;
fa[x] = y;
}
}
for(int i = 1; i <= n; i ++ ) {
biaoji(i);
}
int sum = 0;
for(int i = 1; i <= n; i ++ ) {
if(!f[i]) sum ++; //未被标记的即为美丽节点
}
if(flag == 0) cout << "0\n";
else cout << sum << endl;
}
Problem L. Toxel与PCPC II
题意
有一份长度为
n
nn
的代码，一共有
m
mm
行有错，并且给出有bug的行标，修复bug的规则为：
每次能选择一个数字
i
ii
，然后修复前
i
ii
行的所有bug，设前
i
ii
行的bug数为
x
xx
，则本次需要花费的时间为：
t
i
=
i
+
x
4
t_i=i+x^4ti=i+x4
。
求最少的修复所有bug时间。
思路
这道题我们赛时通过数据范围pass了dp的思路，然后考虑贪心，后来发现不太对。
考虑用dp思路：
我们可以用
f
[
i
]
f[i]f[i]
表示修复前i个bug需要的最短时间，那么状态转移方程为：
f
[
i
]
=
min
1
≤
j
≤
i
(
f
[
j
]
+
a
[
i
]
+
(
i
−
j
)
4
)
f[i]=\min_{1\le j\le i}(f[j]+a[i]+(i-j)^4)f[i]=1≤j≤imin(f[j]+a[i]+(i−j)4)
但是
O
(
n
2
)
O(n^2)O(n2)
的时间复杂度是无法通过的，我们考虑优化：
2
1
4
=
194481
,
2
2
4
=
234256
21^4=194481,22^4=234256214=194481,224=234256
2
1
4
2
e
5
21^4<2e5214<2e5
，是可能会被优化的，但是
2
2
4
>
2
e
5
22^4>2e5224>2e5
不会被优化。 所以说是不会出现同时修复超过22处bug的情况。
所以我们可以将第二维枚举的范围改为22就行，那么时间复杂度将优化为
O
(
n
n
4
)
O(n\sqrt[4]{n})O(n4n)
。
标程
vector
for(int i = 1; i <= n; i ++ ) {
cin >> a[i];
}
f[0] = 0;
f[1] = a[1] + 1ll;//init
auto pow4 = [](int x)->int {return x * x * x * x;};
for(int i = 2; i <= n; i ++ ) {
int j = 1;
if(i - j + 1 >= 22) j = i - 21;//注意边界
for(; j <= i; j ++ )
f[i] = min(f[i], f[j - 1] + a[i] + pow4(i - j + 1));
}
cout << f[n] << endl;
}
Problem M. 有效算法
题意
给出两个长度为
n
nn
的数组
a
,
b
a,ba,b
，要求对每个
a
i
a_iai
进行以下操作正好一次：
将
a
i
a_iai
变成满足
∣
a
i
−
x
∣
≤
k
×
b
i
|a_i−x|\le k\times b_i∣ai−x∣≤k×bi
的任意整数
x
xx
。
求出最小的非负整数
k
kk
，使得存在一个
x
xx
能够将操作后的
a
aa
数组按位等于
b
bb
数组。
思路
题目的数据范围比较大
(
2
≤
n
≤
3
×
1
0
5
)
(2\le n \le 3 \times 10^5)(2≤n≤3×105)
。
根据数据范围猜测，这道题只能在
O
(
n
l
o
g
n
)
O(nlog_n)O(nlogn)
的时间复杂度以内过掉。
然后看题，题目要求找出最小的
k
kk
，
k
kk
能够确定出
a
i
a_iai
变化的范围；那么
k
kk
必定是有序的，即若
k
kk
可行，那么
k
+
1...
k+1...k+1...
也必定可行。
根据题目中的操作，我们可以将其分解为：
a
i
≥
x
a_i \ge xai≥x
：原不等式可化为：
a
i
−
k
×
b
i
≤
x
a_i-k\times b_i \le xai−k×bi≤x
。
a
i
≤
x
a_i \le xai≤x
：原不等式可化为：
k
×
b
i
+
a
i
≥
x
k \times b_i+a_i \ge xk×bi+ai≥x
。
因此可以求出
x
xx
的区间，若区间合法，则
k
kk
满足要求，否则不满足要求。
标程
vector
bool check(int k) {
int mi = 0, mx = LONG_MAX;
for(int i = 1; i <= n; i ++ ) {
mi = max(mi, a[i] - k * b[i]);
mx = min(mx, k * b[i] + a[i]);
if(mi > mx) return false;
}
return true;
}
void Solved() {
cin >> n;
a.resize(n + 1); b.resize(n + 1);
for(int i = 1; i <= n; i ++ ) cin >> a[i];
for(int i = 1; i <= n; i ++ ) cin >> b[i];
int l = 0, r = 1e9, mid;
while(l < r) {
mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout << l << endl;
}
模板
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
#define LL long long
#define ULL unsigned long long
#define PII pair
const int INF = 0x7fffffff;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
void Solved() {
}
signed main(void) {
IOS
int ALL = 1;
// cin >> ALL;
while(ALL -- ) Solved();
// cout << fixed;//强制以小数形式显示
// cout << setprecision(n); //保留n位小数
return 0;
}
vector
#define int long long
#define int long long
#include