2024 National Invitational of CCPC (Zhengzhou), 2024 CCPC Henan Provincial Collegiate Programming Contest
2024 年中国大学生程序设计竞赛全国邀请赛（郑州）暨第六届 CCPC 河南省大学生程序设计竞赛
比赛链接
这场的题说实话难度其实都不大（除了
E
E
E 和
I
I
I），但是做法很固定，考思维，想到了一拍脑袋就出，想不到就寄，因此很多强队都翻车了。这场
13
13
13 题其中的
11
11
11 题我觉得都可以赛时出。
是时候祭出这张图了：
Problem A. Once In My Life
题意：
对于小
A
A
A 而言，数位包含
1
∼
9
1 ∼ 9
1∼9，并且至少两个数位是
d
（
1
≤
d
≤
9
）
d（1 ≤ d ≤ 9）
d（1≤d≤9）的**十进制正整数**都是幸运数。
当
d
=
3
d = 3
d=3 时，显然
1234567890123
1234567890123
1234567890123 是小
A
A
A 的幸运数，但
987654321
987654321
987654321 因为数位
3
3
3 仅出现了一次而不是幸运数，
998244353
998244353
998244353 因为缺少数位
1
,
6
,
7
1, 6, 7
1,6,7 而不是幸运数。
现在小
A
A
A 有一个正整数
n
n
n，并给出正整数
d
d
d。他想找到正整数
k
k
k 使得二者的乘积
n
⋅
k
n · k
n⋅k 是幸运数。
你能用计算机辅助他的计算吗？
输出保证
k
≤
2
∗
1
0
10
k\le 2*10^{10}
k≤2∗1010
思路：
本质是个构造题，需要一点点数论知识。
我们想要
n
k
nk
nk 得到的数里有
123456789
123456789
123456789 和额外的一个
d
d
d，那么我们就构造出来，假设结果是
123456789
d
123456789d
123456789d，构造得到的数不一定是
n
n
n 的倍数，但是我们可以加一些数让它成为倍数，不过这就破坏了这十个位置上的数字。
考虑到当
k
k
k 乘以
10
10
10 的时候，
123456789
d
123456789d
123456789d 也会乘以
10
10
10，相当于整体向左移动一位，低位就空出来了，这时我们给低位增加一些数字的时候，就不会影响到高处的十个位置了。最简单的想法就是反正
n
≤
1
0
8
n\le10^8
n≤108，所以我们只要低八位空出来就行了，这时就会得到
123456789
d
00000000
m
o
d
n
=
x
123456789d00000000\bmod n=x
123456789d00000000modn=x，我们再加上
(
n
−
x
)
m
o
d
n
(n-x)\bmod n
(n−x)modn 就是乘积，除以
n
n
n 就是
k
k
k 了。
不过题目要求
k
≤
2
∗
1
0
10
k\le 2*10^{10}
k≤2∗1010，当
n
≤
1
0
7
n\le 10^7
n≤107 时，上面构造出来的数铁定
>
2
∗
1
0
10
\gt 2*10^{10}
>2∗1010。考虑到我们没必要低位留
8
8
8 位，比如
n
n
n 只有一位数的时候，我们低位就只留一位就行了，如果
n
n
n 是
t
t
t 位数，那么我们低位就只留
t
t
t 位就可以了，这样构造出来的数
k
k
k 就是一个小于
2
∗
1
0
10
+
t
−
1
2*10^{10+t-1}
2∗1010+t−1 的数，除以一个大于
1
0
t
−
1
10^{t-1}
10t−1 的数，得到的数肯定小于
2
∗
1
0
10
2*10^{10}
2∗1010。
code：
#include<iostream>#include<cstdio>usingnamespace std;typedeflonglong ll;int T;
ll n,d;
ll pw[20];intmain(){
cin.tie(0)->sync_with_stdio(false);
pw[0]=1;for(int i=1;i<=18;i++)pw[i]=pw[i-1]*10;
cin>>T;while(T--){
cin>>n>>d;int i=0;while(pw[i]<n)i++;
ll ans=123456789ll*pw[i+1]+d*pw[i];
ll x=(pw[i]-ans%n)%pw[i];
cout<<(ans+x)/n<<'\n';}return0;}
Problem B. 扫雷 1
题意：
T0xel 喜欢玩扫雷，但是他玩的扫雷游戏有名为 “地雷探测器” 的特殊道具。
具体来说，T0xel 会进行
n
n
n 轮扫雷。每轮扫雷开始之前，T0xel 会获得
1
1
1 枚扫雷币。扫雷币在每轮扫雷结束后不会回收，可以保留至下一轮扫雷。T0xel 知道，在第
i
i
i 轮
（
1
≤
i
≤
n
）
（1 ≤ i ≤ n）
（1≤i≤n）扫雷中，花费
c
i
c_i
ci 枚扫雷币可以购买一个地雷探测器，清除地图中的一个雷。地雷探测器在一轮扫雷中可以购买任意次。
现在 T0xel 想知道，在这
n
n
n 轮扫雷中最多能购买多少个地雷探测器呢？
思路：
签到，是个贪心。因为我们在一轮中某个探测器可以买任意次，所以如果后面的轮中如果有一个很便宜的探测器，那么我们直接留着钱只买这个就行了，能买多少就买多少。如果后面有一个稍贵的探测器，因为我们不能买前面轮次的探测器，所以我们也有可能买这个探测器。
这种如果有一个
o
i
oi
oi 比你强还比你年轻（这个题里就是探测器既便宜又靠后），那么你就没用了的思想，就很单调栈。所以用一个单调栈模拟一下，然后从前到后贪心买探测器即可。
或者可以按探测器价格排序，然后按顺序枚举，升序地选择购买探测器
如果把
(
i
,
c
i
)
(i,c_i)
(i,ci) 看成一个点，其实相当于一个下凸壳，所以求下凸壳的思想也可以做。
code1：
单调栈
#include<iostream>#include<cstdio>#include<vector>#definepiipair<int,int>usingnamespace std;int n;
vector<pii> sta;intmain(){
cin>>n;for(int i=1,c;i<=n;i++){
cin>>c;while(!sta.empty()&& sta.back().first>=c)sta.pop_back();
sta.push_back({c,i});}int p=0,rm=0,ans=0;for(auto[c,i]:sta){
rm+=i-p;
p=i;
ans+=rm/c;
rm-=rm/c*c;}
cout<<ans<<endl;return0;}
code2：
队友赛时代码，排序后升序选点。
#include<bits/stdc++.h>usingnamespace std;int a[200005];typedef pair<int,int> PII;intmain(){int n;
cin>>n;
vector<PII> pos;for(int i =1;i<=n;i++){
cin>>a[i];
pos.push_back({a[i],i});}sort(pos.begin(),pos.end());int p =1;int ans =0;int was =0;for(PII pii : pos){if(pii.second < p)continue;int le = pii.second - was;int t = le/pii.first;
ans += t;
was += t * pii.first;
p = pii.second;}
cout<<ans;return0;}
Problem C. 中二病也要打比赛
题意：
在被中二病彻底占领的世界中，存在着一个被称为 “现实” 的神秘领域。在这个领域中，小鸟游六花，一位坚信自己拥有着非凡力量的中二病少女，发现了一串神秘的数字序列
A
A
A。这个序列包含了
n
n
n 个元素，每个元素
A
i
A_i
Ai 是
1
1
1 到
n
n
n 之间的整数。据说，只有当这个序列满足**单调不降**的性质时，隐藏在其中的超自然力量才会觉醒。
六花相信，通过解开这个序列的秘密，她可以进一步证明自己的 “邪王真眼” 的力量。然而，她很快就意识到，要驯服这个序列，需要一种特殊的魔法——一个能将
A
A
A 转化为另一个序列的函数
f
f
f，其定义域与值域均为
[
1
,
n
]
∩
Z
[1, n] ∩ Z
[1,n]∩Z。使用这个魔法后，
A
A
A 会变成
B
B
B，其中
B
i
=
f
(
A
i
)
B_i = f(A_i)
Bi=f(Ai)。但是，这个魔法的使用是有代价的，其成本由
[
1
,
n
]
∩
Z
[1, n] ∩ Z
[1,n]∩Z 中
f
(
x
)
≠
x
f(x) \not= x
f(x)=x 的
x
x
x 数量决定。在这个充斥着中二病的世界中，六花必须以最小的代价激发序列中隐藏的力量。
现在，作为六花的冒险伙伴，你的任务是帮助她找到那个神奇的函数
f
f
f，将
A
A
A 转化为单调不降序列，并以最小的代价揭示序列中隐藏的超自然力量。
思路：
我们队出的最后一题，赛时我想到了前半缩点部分，猜测后边做法可能是个带懒节点的线段树优化
d
p
dp
dp（不过并不是），因为时间不太够了，简单讲完后我直接上手写了（写了个缩点部分和带懒节点线段树），之后队友讨论出了后半做法是个最长上升子序列，接着我的部分写完，一遍
A
C
AC
AC，这就是我们热血沸腾的组合技啊！
10
1 10 2 6 10 8 9 6 4 5
比如上面的一个样例，我们可以发现被两个
10
10
10 包含起来的这段区间一定只能同时等于一个值，
10
10
10 的区间内部有一个
6
6
6，而外部也有一个
6
6
6，因为内部的
6
6
6 被固定住了，那么外部的
6
6
6 也会随之固定，这两个
6
6
6 之间的部分也被迫同时等于
10
10
10 包含区间的值，同理其他数。
既然它们都等于一个值，那么我们就可以把它们看成一个点或者一个块。一个块内所有数都会转化成一个相同的数。我们上面缩块的过程就保证了一种数字只有可能出现在一个块内，否则的话，两个块肯定在缩块的时候就被缩在一起了。因此对序列
A
A
A 中出现过的某种数字
x
x
x，它**在且仅在**一个块内。
不难发现，如果一个块内出现了
s
z
sz
sz 个不同的数，那么如果这个块等于块内含有的某个值，代价是
s
z
−
1
sz-1
sz−1，否则如果变成块内没有出现过的其他值的话，代价就是
s
z
sz
sz。因为上面推出过每种出现过的数在且仅在一个块内的结论，因此若原本出现过
t
o
t
tot
tot 种数，那么所有块的
s
z
sz
sz 之和就是
t
o
t
tot
tot，也就是
∑
s
z
=
t
o
t
\sum sz=tot
∑sz=tot。假设有
t
t
t 个块选择等于块内含有的某个值，这时候代价就是
t
o
t
−
t
tot-t
tot−t。我们求最小代价，就是求最多能有几个块可以选择等于块内含有的某个值。
这样问题就转化为了：若干个位置上，每个位置上可以取一些值的一个，求最长上升子序列长度。
code：
#include<iostream>#include<cstdio>#include<map>#include<vector>#include<set>usingnamespace std;constint maxn=2e5+5;int n;int a[maxn],tt[maxn],nxt[maxn];int ans =1;int dp[maxn];intmain(){
cin.tie(0)->sync_with_stdio(false);
set<int> aa;
cin>>n;for(int i=1;i<=n;i++)cin>>a[i],tt[a[i]]=i;//ai出现的最后位置for(int i =1;i<=n;i++)aa.insert(a[i]);for(int i=1;i<=n;i++)nxt[i]=tt[a[i]];for(int i =1;i<=n;i++) dp[i]=0x3f3f3f3f;
vector<set<int>> block;
block.push_back(set<int>());for(int l=1,r;l<=n;){//缩块
r=l;
block.push_back(set<int>());while(l<=r){
r=max(r,nxt[l]);
block.back().insert(a[l++]);}}int sz = block.size()-1;
dp[1]=(*block[1].begin());for(int i =2;i<=sz;i++){auto& st=block[i];
vector<pair<int,int>> ope;for(auto p : st){if(p >= dp[ans]) ope.push_back({ans+1,p});else{int t =lower_bound(dp+1,dp+ans+1,p)- dp;
ope.push_back({t,p});}}for(auto pi : ope){
dp[pi.first]=min(dp[pi.first],pi.second);
ans =max(ans,pi.first);}}
cout<<aa.size()- ans<<endl;return0;}
Problem D. 距离之比
题意：
对于
R
2
\mathbb{R}^2
R2 平面上的两个点
P
(
x
P
,
y
P
)
P(x_P, y_P)
P(xP,yP) 与
Q
(
x
Q
,
y
Q
)
Q(x_Q, y_Q)
Q(xQ,yQ)，
P
Q
PQ
PQ 之间的曼哈顿距离定义为
∥
P
Q
∥
1
=
∣
x
P
−
x
Q
∣
+
∣
y
P
−
y
Q
∣
∥P Q∥_1 = |x_P − x_Q| + |y_P − y_Q|
∥PQ∥1=∣xP−xQ∣+∣yP−yQ∣而
P
Q
PQ
PQ 之间的欧几里得距离定义为
∥
P
Q
∥
2
=
(
x
P
−
x
Q
)
2
+
(
y
P
−
y
Q
)
2
∥P Q∥_2 =\sqrt{(x_P − x_Q)^2 + (y_P − y_Q)^2}
∥PQ∥2=(xP−xQ)2+(yP−yQ)2
现在给出平面上互不重合的
n
n
n 个点
P
1
,
P
2
,
.
.
.
,
P
n
P_1, P_2, . . . , P_n
P1,P2,...,Pn，请求出
max
1
≤
i
<
j
≤
n
∥
P
i
P
j
∥
1
∥
P
i
P
j
∥
2
\max\limits_{1≤i<j≤n}\dfrac{∥P_iP_j∥_1}{∥P_iP_j∥_2}
1≤i<j≤nmax∥PiPj∥2∥PiPj∥1
思路：
直觉上感觉只要直线
P
Q
PQ
PQ 越靠近直线
y
=
x
y=x
y=x 或直线
y
=
−
x
y=-x
y=−x ，这个值就越大，证明：
假设斜线是
P
Q
PQ
PQ（不妨假设靠下的就是
P
P
P 点，靠上的就是
Q
Q
Q 点），过点
P
P
P 作一条水平线，过点
Q
Q
Q 作一条竖直线，交于点
M
M
M，如下图。设
∠
P
=
θ
\angle P=\theta
∠P=θ，
∣
P
Q
∣
=
x
|PQ|=x
∣PQ∣=x，则
∣
P
M
∣
=
x
∣
cos
θ
∣
,
∣
Q
M
∣
=
x
∣
sin
θ
∣
|PM|=x|\cos\theta|,|QM|=x|\sin\theta|
∣PM∣=x∣cosθ∣,∣QM∣=x∣sinθ∣。
因此
∥
P
Q
∥
1
∥
P
Q
∥
2
=
x
∣
sin
θ
∣
+
x
∣
cos
θ
∣
x
=
∣
sin
θ
∣
+
∣
cos
θ
∣
\dfrac{∥PQ∥_1}{∥PQ∥_2}=\dfrac{x|\sin\theta|+x|\cos\theta|}{x}=|\sin\theta|+|\cos\theta|
∥PQ∥2∥PQ∥1=xx∣sinθ∣+x∣cosθ∣=∣sinθ∣+∣cosθ∣
当
0
≤
θ
<
π
2
0\le\theta\lt \dfrac{\pi}{2}
0≤θ<2π 时，有
原式
=
sin
θ
+
cos
θ
=
2
(
sin
θ
cos
π
4
+
cos
θ
sin
π
4
)
=
2
sin
(
θ
+
π
4
)
原式=\sin\theta+\cos\theta=\sqrt{2}(\sin\theta\cos\dfrac{\pi}{4}+\cos\theta\sin\dfrac{\pi}{4})=\sqrt{2}\sin(\theta+\dfrac{\pi}{4})
原式=sinθ+cosθ=2(sinθcos4π+cosθsin4π)=2sin(θ+4π)根据三角函数的知识，显然当
θ
=
π
4
\theta=\dfrac{\pi}{4}
θ=4π 时，
原式
=
2
原式=\sqrt{2}
原式=2 取得最大值，
原式
=
1
原式=1
原式=1 取得最小值。当
θ
∈
[
0
,
π
4
)
\theta\in[0,\dfrac{\pi}{4})
θ∈[0,4π) 时，原式随
θ
\theta
θ 增大而增大，当
θ
∈
[
π
4
,
π
2
)
\theta\in[\dfrac{\pi}{4},\dfrac{\pi}{2})
θ∈[4π,2π) 时，原式随
θ
\theta
θ 增大而减小。通俗点讲就是角度越靠近
45
45
45 度角，值就越大。
同理当
π
2
≤
θ
<
π
\dfrac{\pi}{2}\le\theta\lt \pi
2π≤θ<π 时，有
原式
=
sin
θ
−
cos
θ
=
2
(
sin
θ
cos
π
4
−
cos
θ
sin
π
4
)
=
2
sin
(
θ
−
π
4
)
原式=\sin\theta-\cos\theta=\sqrt{2}(\sin\theta\cos\dfrac{\pi}{4}-\cos\theta\sin\dfrac{\pi}{4})=\sqrt{2}\sin(\theta-\dfrac{\pi}{4})
原式=sinθ−cosθ=2(sinθcos4π−cosθsin4π)=2sin(θ−4π)显然当
θ
=
3
π
4
\theta=\dfrac{3\pi}{4}
θ=43π 时，
原式
=
2
原式=\sqrt{2}
原式=2 取得最大值，
原式
=
1
原式=1
原式=1 取得最小值。当
θ
∈
[
π
2
,
3
π
4
)
\theta\in[\dfrac{\pi}{2},\dfrac{3\pi}{4})
θ∈[2π,43π) 时，原式随
θ
\theta
θ 增大而增大，当
θ
∈
[
3
π
4
,
π
)
\theta\in[\dfrac{3\pi}{4},\pi)
θ∈[43π,π) 时，原式随
θ
\theta
θ 增大而减小。通俗点讲就是角度越靠近
135
135
135 度角，值就越大。
之后再旋转直线，就会和前面重复，所以我们就不需要向下讨论了。
先看直线的角度靠近
45
45
45 度角的情况，其实也就是如果直线越贴和直线
y
=
x
y=x
y=x，值就越大。但是斜着看很难受，我们不妨将整个坐标系关于原点逆时针旋转
45
45
45 度，这样只要直线越贴近
y
y
y 轴（也就是角度越靠近
90
90
90 度），值就越大了。
这时会发现一个很强的性质，就是答案只会出现在横坐标相邻的点对上。
证明：假设坐标系上横坐标按顺序有三个点
A
,
B
,
C
A,B,C
A,B,C，如果
B
B
B 点在直线
A
C
AC
AC 上方，显然直线
A
B
AB
AB 更陡，角度更靠近
90
90
90 度，答案更大。如果
B
B
B 点在直线
A
C
AC
AC 下方，显然直线
B
C
BC
BC 更陡，角度更靠近
90
90
90 度，答案更大。发现对任意三个点，最优答案总是出现在横坐标相邻的点上，而不会出现在直线
A
C
AC
AC 这种线上。
因此我们按横坐标排序后
O
(
n
)
O(n)
O(n) 算一遍相邻点的答案，取最大值即可。**不过注意我们排序是按旋转后的横坐标排序，但是计算还是用原坐标来计算。**
一个点关于原点逆时针旋转
θ
\theta
θ 角度，根据计算几何的知识，它的旋转矩阵为
[
cos
θ
−
sin
θ
sin
θ
cos
θ
]
\begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix}
[cosθsinθ−sinθcosθ]
一个点
(
x
,
y
)
(x,y)
(x,y) 旋转
45
45
45 度也就是
π
4
\dfrac{\pi}{4}
4π 后的坐标为：
[
cos
π
4
−
sin
π
4
sin
π
4
cos
π
4
]
⋅
[
x
y
]
=
1
2
[
x
+
y
−
x
+
y
]
\begin{bmatrix} \cos\dfrac{\pi}{4} & -\sin\dfrac{\pi}{4} \\ \sin\dfrac{\pi}{4} & \cos\dfrac{\pi}{4} \end{bmatrix}\cdot\begin{bmatrix} x\\y \end{bmatrix}=\dfrac{1}{\sqrt{2}}\begin{bmatrix} x+y\\-x+y \end{bmatrix}
cos4πsin4π−sin4πcos4π⋅[xy]=21[x+y−x+y]
沿旋转
45
45
45 度后的横坐标排序就是按
x
+
y
x+y
x+y 排序。
同理
[
cos
3
π
4
−
sin
3
π
4
sin
3
π
4
cos
3
π
4
]
⋅
[
x
y
]
=
1
2
[
x
−
y
x
+
y
]
\begin{bmatrix} \cos\dfrac{3\pi}{4} & -\sin\dfrac{3\pi}{4} \\ \sin\dfrac{3\pi}{4} & \cos\dfrac{3\pi}{4} \end{bmatrix}\cdot\begin{bmatrix} x\\y \end{bmatrix}=\dfrac{1}{\sqrt{2}}\begin{bmatrix} x-y\\x+y \end{bmatrix}
cos43πsin43π−sin43πcos43π⋅[xy]=21[x−yx+y]沿旋转
135
135
135 度后的横坐标排序就是按
x
−
y
x-y
x−y 排序。
code：
#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<iomanip>#definepllpair<ll,ll>usingnamespace std;typedeflonglong ll;constint maxn=2e5+5;
ll T,n;
pll a[maxn];doublecalc(pll a,pll b){auto[x1,y1]=a;auto[x2,y2]=b;return(abs(x1-x2)+abs(y1-y2))/sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}intmain(){
cin.tie(0)->sync_with_stdio(false);
cin>>T;while(T--){
cin>>n;for(int i=1;i<=n;i++){auto&[x,y]=a[i];
cin>>x>>y;}sort(a+1,a+n+1,[](pll a,pll b){return a.first+a.second<b.first+b.second;});double maxx=1;for(int i=2;i<=n;i++)
maxx=max(maxx,calc(a[i-1],a[i]));sort(a+1,a+n+1,[](pll a,pll b){return a.first-a.second<b.first-b.second;});for(int i=2;i<=n;i++)
maxx=max(maxx,calc(a[i-1],a[i]));
cout<<setiosflags(ios::fixed)<<setprecision(12)<<maxx<<endl;}return0;}
Problem F. 优秀字符串
题意：
小
A
A
A 认为，一个字符串
S
S
S 是优秀字符串，当且仅当：
S S S 的长度 ∣ S ∣ |S| ∣S∣ 恰好为 5 5 5；S S S 的第三个字符与第五个字符相同；S S S 的前四个字符互不相同。
例如
henan
是优秀字符串，但
query
、
problem
、
queue
不是，因为：
query的第三个字符为 e e e，而第五个字符为 y y y；problem的长度不为 5 5 5；queue的前四个字符中 u u u 出现了两次。
现在，小
A
A
A 有
n
n
n 个仅包含英文字母与数字的字符串
S
1
,
S
2
,
.
.
.
,
S
n
S_1, S_2, . . . , S_n
S1,S2,...,Sn，请你帮小
A
A
A 求出这些字符串中优秀字符串的数量。
思路：
签到
code：
#include<bits/stdc++.h>usingnamespace std;intmain(){int n;
cin >> n;int ans =0;for(int i =0; i < n; i++){
string s;
cin >> s;if(s.size()==5&&(s[2]== s[4])){
set<char> ss;for(int i =0; i < s.size()-1; i++){
ss.insert(s[i]);}
ans +=(ss.size()==4);}}
cout << ans;return0;}
Problem G. 扫雷 2
题意：
T0xel 喜欢玩扫雷，但是他不喜欢数字
2
2
2。
他想构造一个
n
×
n
n × n
n×n 的扫雷的地图，其中有
m
m
m 个雷，并且没有一个空地周围恰有
2
2
2 个雷。
也就是说，他想构造一个
01
01
01 方阵，使得不存在一个
0
0
0 周围
8
8
8 格中恰有
2
2
2 个
1
1
1。特别地，边上的
0
0
0 周围
5
5
5 个格不能恰有
2
2
2 个
1
1
1，角落上的
0
0
0 周围
3
3
3 个格不能恰有
2
2
2 个
1
1
1。
思路：
还好赛时我放弃写这个题了，不然怕是罚时吃饱然后
G
G
GG
GG 了。这个题看着人畜无害，实际上特殊情况超级多，需要善于调试，写代码把所有情况枚举一遍然后找错，再考虑加特判。
大概思路如下，假设左上角格子的坐标为
(
1
,
1
)
(1,1)
(1,1)。左上黄色蛇形部分包含了两个相邻紫色对角线上的所有格子，假设外侧对角线第一行的格子的坐标为
(
1
,
i
)
(1,i)
(1,i)，那么这个蛇形部分就占据了
2
i
−
1
2i-1
2i−1 个格子。右下蓝色填充部分包含了后
x
x
x 行和列的所有格子和额外的两个格子，其中第
i
i
i 行和第
i
i
i 列包含
2
i
−
1
2i-1
2i−1 个格子。绿色格子可填可不填。
如果我们最多可以填完后
x
+
1
x+1
x+1 行和列，第
x
x
x 行和列没有足够的格子填充，那么我们就剩下少于
2
x
−
1
2x-1
2x−1 个格子，我们先给出那两个额外的蓝色格子，因为蛇形只能凑
2
i
−
1
2i-1
2i−1 个格子，所以如果剩余了偶数个格子，我们就再拿出一个填充到绿色位置。
因为剩余的格子少于
2
x
−
1
2x-1
2x−1，我们还拿出了至少
2
2
2 个格子，因此剩余的格子少于
2
x
−
3
2x-3
2x−3，蛇形需要
2
i
−
1
2i-1
2i−1 个格子，就可以保证
i
<
x
−
1
i<x-1
i<x−1，这样黄色和蓝色区域正好不会冲突。
不过剩余的格子如果少于
2
2
2 个，我们甚至根本拿不出两个额外的蓝色格子，因此我们退一行列，剩余的格子个数就增加
2
x
+
1
2x+1
2x+1，再减去两个额外的蓝色格子，剩余的格子
<
2
x
+
1
<2x+1
<2x+1，正好可以保证
i
<
x
+
1
i<x+1
i<x+1（因为蓝色退了一行列，所以额外蓝色格子填在点
(
1
,
x
+
1
)
,
(
x
+
1
,
1
)
(1,x+1),(x+1,1)
(1,x+1),(x+1,1) 上），正好也不冲突。这时形状大概如下：
这时我们大概的逻辑就出来了，然后就是无数的特殊情况：
一：
当黄色蛇形部分和蓝色额外块之间隔一个块的时候，就会出现
b
u
g
bug
bug。
解决方法：删掉两个蓝色额外块，蛇形部分向外移动一格。
二：
当空间逐渐变小，两个蓝色额外块，黄色块，绿色块会靠的越来越近。当
(
2
,
2
)
(2,2)
(2,2) 被黄色覆盖，
(
4
,
4
)
(4,4)
(4,4) 被绿色覆盖，黄色和绿色会靠的足够近，就会出现一个特色
b
u
g
bug
bug。
解决方法：当
(
2
,
2
)
,
(
4
,
4
)
(2,2),(4,4)
(2,2),(4,4) 同时被填充，将
(
4
,
4
)
(4,4)
(4,4) 换到
(
1
,
1
)
(1,1)
(1,1) 去。
三：
当
m
=
n
2
−
7
m=n^2-7
m=n2−7 时，两个蓝色额外块会靠的足够近，导致
b
u
g
bug
bug。
解决方法：从
(
n
,
n
)
(n,n)
(n,n) 移植一个格子到
(
3
,
3
)
(3,3)
(3,3)。
四：
m
≥
n
2
−
4
m\ge n^2-4
m≥n2−4 的时候，特判吧。
五：
n
=
5
,
m
=
10
n=5,m=10
n=5,m=10 的时候。不需要垫脚就会出现类似特判二的情况。
解决方法：反正就这一个，随便构造。
讨论结束后就可以
A
C
AC
AC 力！其实
m
=
0
m=0
m=0 也要特判，不过题目保证
m
>
0
m>0
m>0，所以无所谓了。
code：
#include<iostream>#include<cstdio>usingnamespace std;constint maxn=1005;int T,n,m;bool mp[maxn][maxn];voidprint(){for(int i=1;i<=n;i++,puts(""))for(int j=1;j<=n;j++)
cout<<(mp[i][j]?"1":"0");}intmain(){// cout<<1000<<endl;// for(int i=0;i<=25;i++)cout<<5<<" "<<i<<endl;
cin>>T;while(T--){
cin>>n>>m;puts("Yes");for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
mp[i][j]=false;if(n==5){if(m==10){
cout<<"11110\n11100\n11000\n10000\n00000\n";continue;}}if(m==n*n-7){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
mp[i][j]=true;
mp[n][n]=mp[1][1]=mp[1][2]=mp[2][1]=mp[2][2]=mp[2][3]=mp[3][2]=false;print();continue;}if(m==n*n-4){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
mp[i][j]=true;
mp[1][1]=mp[1][2]=mp[2][1]=mp[n][n]=false;print();continue;}if(m==n*n-3){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
mp[i][j]=true;
mp[1][1]=mp[1][2]=mp[2][1]=false;print();continue;}if(m==n*n-2){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
mp[i][j]=true;
mp[1][1]=mp[n][n]=false;print();continue;}if(m==n*n-1){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
mp[i][j]=true;
mp[1][1]=false;print();continue;}if(m==n*n){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
mp[i][j]=true;print();continue;}int i1=n,i2;while(m>=2*i1-1){
m-=2*i1-1;
i1--;}if(i1<n && m<2){
i1++;
m+=2*i1-1;}for(int i=i1+1;i<=n;i++)for(int j=1;j<=n;j++)
mp[i][j]=mp[j][i]=true;if(m==2){//m>=2
mp[i1][1]=mp[1][i1]=true;print();continue;}if(~m&1){//m>2
mp[i1][i1]=true;
m--;}//m为奇数 if(2*(i1-1)-1==m){
i2=(m+1)/2;for(int i=1;i<=i2;i++)
mp[i][i2-i+1]=true;for(int i=1;i<i2;i++)
mp[i][i2-i]=true;}else{if(i1<n){
mp[i1][1]=mp[1][i1]=true;
m-=2;}
i2=(m+1)/2;for(int i=1;i<=i2;i++)
mp[i][i2-i+1]=true;for(int i=1;i<i2;i++)
mp[i][i2-i]=true;}if(mp[2][2]==true&& mp[4][4]==true){
mp[1][1]=true;
mp[4][4]=false;}print();}return0;}
Problem H. 随机栈
题意：
Toxel 获得了一个随机的 “栈”。这个栈可被视为一个多重集
S
S
S，从一个非空的随机栈
S
S
S 中取出一个元素时，有可能从中取出任何一个元素，其中每个元素被取出的概率是相等的。取出该元素后，该元素会从集合中删除。以
{
1
,
2
,
2
}
\{1, 2, 2\}
{1,2,2} 为例，有
1
3
\frac13
31 的概率取出
1
1
1，使得集合变为
{
2
,
2
}
\{2, 2\}
{2,2}，有
2
3
\frac23
32 的概率取出
2
2
2，使得集合变为
{
1
,
2
}
\{1, 2\}
{1,2}。每次取出元素的事件相互独立。
Toxel 正在对这个集合做一些操作。集合初始时为空，它总共进行了
2
n
2n
2n 次操作，其中
n
n
n 次操作为插入，
n
n
n 次操作为取出。现在，Toxel 告诉了你它操作的顺序以及每次插入的数，且保证每次取出时，集合非空。Toxel 想知道，如果把每次取出的数排成一个序列，那么这个序列递增的概率是多少？这里，递增的严格定义是：取出数列的每一项（除最后一项）**小于等于**它的后一项。
由于答案可能不是整数，为了方便计算，你只需要求出这个值对
998
244
353
998\ 244\ 353
998 244 353 取模的结果。
思路：
这个题虽然看起来像概率论，但是实际上就是个算数，很签到。
因为我们得到的序列是单调不降的，所以我们每次从多重集中选出来的数一定是最小的数。我们模拟一下这个多重集加数和取数的过程，每次取数的时候累乘一下 最小数的个数和多重集的个数的比值，最后得到的就是答案。
不过我们有可能加数取数的过程本身就会造成无解的情况，也就是在给定的操作序列里，我们一定会取出一个较大数，然后才加入一个较小数，这样是一定无解的。所以我们记录一下前面取出的最小数，如果一次加数比前面最小数还小，就无解。
code：
#include<bits/stdc++.h>usingnamespace std;#defineintlonglongconstint mod =998244353;intqpow(int x,int n){int ans =1;while(n){if(n &1) ans = ans * x % mod;
x = x * x % mod ;
n >>=1;}return ans;}intinv(int x){returnqpow(x,mod -2);}int ope[400005];signedmain(){int n;
cin>>n;int sz =0;
map<int,int> mp;int mx =-1;int ans =1;for(int i =1;i<=2*n;i++)cin>>ope[i];for(int i =1;i<=2*n;i++){int num = ope[i];if(num !=-1){if(mx > num){
cout<<0<<'\n';return0;}
mp[num]++;sz ++;}else{
ans = ans *(*mp.begin()).second %mod;
ans = ans *inv(sz)% mod;
sz --;
mx =max(mx,(*mp.begin()).first);(*mp.begin()).second--;if((*mp.begin()).second ==0) mp.erase(mp.begin());}}
cout<<ans<<'\n';return0;}
Problem J. 排列与合数
题意：
小
A
A
A 在
2023
2023
2023 年河南省
C
C
P
C
CCPC
CCPC 大学生程序设计竞赛的赛场上遇到了一道名为 “排列与质数” 的题目。与大多数选手一样，小
A
A
A 并没能在赛场上解决这个棘手的题目。比赛结束后，小
A
A
A 想到了一个与之相关的题目：排列与合数，可是小
A
A
A 仍然没有能力解决。这个名为 “排列与合数” 的题目是这样的：
给定一个有且仅有
5
5
5 位，且各个数位互不相同的十进制正整数
n
n
n。你可以重新排列
n
n
n 的各个数位，但需要保证重新排列得到的整数
n
′
n'
n′ 没有前导零。请问重新排列数位得到的
n
′
n'
n′ 能否为合数？若能为合数，请求出一个满足条件的
n
′
n'
n′。
例如，当
n
=
12345
n = 12345
n=12345 时，任意排列得到的
n
′
n'
n′ 均是合数，因此可以任意取
n
′
n'
n′。当
n
=
13579
n = 13579
n=13579 时，可以重新排列数位得到合数
n
′
=
97531
=
7
×
13933
n' = 97531 = 7 × 13933
n′=97531=7×13933。
一个正整数是合数，当且仅当它可以分解为两个不小于
2
2
2 的整数的乘积。
现在，小
A
A
A 带着他的题目来到赛场上求助。你能帮助小
A
A
A 解决这个题目吗？
思路：
签到，如果五个数位上有一个偶数，那么把它放在最低位上，这样就是一个非
2
2
2 偶数，一定是合数。如果全是奇数，因为各个数位的数各不相同，因此这五个奇数一定是
1
,
3
,
5
,
7
,
9
1,3,5,7,9
1,3,5,7,9，直接输出
97531
97531
97531 即可。
注意如果有零的情况，不能出现前导零。
code：
#include<bits/stdc++.h>usingnamespace std;intmain(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;
cin>>n;for(int i =0; i < n; i++){
string s;
cin >> s;int p =-1;for(int j =0; j <5; j++){if((s[j]-'0')%2==0){
p = j;}}if(p ==-1){
cout <<"97531\n";continue;}else{for(int j =0; j <5; j++){if(p == j)continue;
cout << s[j];}
cout << s[p];}
cout <<"\n";}return0;}
Problem K. 树上问题
题意：
378QAQ 有一棵由
n
n
n 个节点组成的无根树，节点编号从
1
1
1 到
n
n
n，每个节点有一个正整数点权。
378QAQ 认为一个节点是美丽节点，当且仅当该节点作为根时，对于除根节点以外的所有节点，其
点权都不小于其父亲节点的点权的
1
2
\frac12
21。
请你计算出有多少个节点是美丽节点。
思路1（换根DP）：
相当于 儿子节点值的二倍大于等于父节点的值。当我们认定了一个根节点后，其下的所有边都会满足这样一种情况。
一个边的这个满足关系只和它两端的点有关系，而且是有向的（即远离根的一端的点的值的二倍大于等于靠近根的一端的点的值）。所以当我们的根向旁边一个点移动的时候，除了这两个点之间的边有可能会发生转变（也就是原先有贡献，结果变成没有贡献，或者反过来），其他的边则不会受到影响。
因此考虑换根DP。不妨设
1
1
1 号点是根节点，设
c
n
t
[
i
]
cnt[i]
cnt[i] 为以点
i
i
i 为根节点的子树的不合法边的个数，我们去计算以每个点为整个树的根节点时不合法边的个数，统计一下有几个点的答案为
0
0
0 即可。显然
1
1
1 号点我们已经计算好了，我们计算好点
u
u
u 的答案，需要去计算儿子节点
v
v
v 的答案。
可以发现分别以
u
,
v
u,v
u,v 为根时，红色区域和蓝色区域的边的方向都没变，所以它们对答案的贡献是相同的，只有
u
,
v
u,v
u,v 这条边发生了改变，因此我们给
a
n
s
u
ans_u
ansu 减去
v
→
u
v\rightarrow u
v→u 的贡献，再加上
u
→
v
u\rightarrow v
u→v 的贡献就得到了
a
n
s
v
ans_v
ansv。
code：
#include<iostream>#include<cstdio>usingnamespace std;constint maxn=1e5+5;int T,n,a[maxn];int head[maxn],ent;structedge{int v,nxt;}e[maxn<<1];voidadd(int u,int v){
e[++ent]={v,head[u]};
head[u]=ent;}int cnt[maxn];//以u为根的子树不合法边的个数 voiddfs1(int u,int fa){// cout<<"^^^"<<u<<" "<<fa<<endl;int ans=0;for(int i=head[u],v;i;i=e[i].nxt){
v=e[i].v;if(v==fa)continue;dfs1(v,u);
ans+=cnt[v]+(a[v]*2<a[u]);}
cnt[u]=ans;return;}int ans[maxn];voiddfs2(int u,int fa){// cout<<u<<" "<<val<<endl;for(int i=head[u],v;i;i=e[i].nxt){
v=e[i].v;if(v==fa)continue;
ans[v]=ans[u]-(a[v]*2<a[u])+(a[u]*2<a[v]);dfs2(v,u);}return;}intmain(){
cin>>T;while(T--){
cin>>n;
ent=0;for(int i=1;i<=n;i++)head[i]=0;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1,u,v;i<n;i++){
cin>>u>>v;add(u,v);add(v,u);}dfs1(1,-1);// for(int i=1;i<=n;i++)cout<<cnt[i]<<" \n"[i==n];
ans[1]=cnt[1];dfs2(1,-1);int t=0;for(int i=1;i<=n;i++)t+=(ans[i]==0);
cout<<t<<endl;}return0;}
思路2（并查集缩点）：
我们队赛时的想法。
可以发现这个 儿子节点值的二倍大于等于父节点的值 的关系是“有向”的，如果一条边的两个端点分别是
u
,
v
u,v
u,v，由于这个图是个树，因此整个图会被这条边分成两个连通块（点
u
u
u 一侧和点
v
v
v 一侧）。
如果存在
2
a
u
≥
a
v
,
2
a
v
<
a
u
2a_u\ge a_v,2a_v\lt a_u
2au≥av,2av<au 的关系的话，那么当点选在点
v
v
v 一侧的时候，是永远不可能成立的，我们不妨把这条边改成
u
→
v
u\rightarrow v
u→v 的一条有向边，来表示这种有向关系。当然，当
2
a
u
≥
a
v
,
2
a
v
≥
a
u
2a_u\ge a_v,2a_v\ge a_u
2au≥av,2av≥au 同时满足的话，则没有限制，连成普通的双向边即可。这时，当我们从新图的一个点出发，如果可以到达其他所有点的时候，就说明这个点是可行的一个根节点。
因为一部分树边被改成了有向边，因此修改后的图就含有若干个强连通块，强连通块内的所有点可以互相到达，因此我们把图中所有极大强连通块缩成一个点，这样整个图就变成了一个有向无环图。我们在这个图上找有没有一个点可以到达其他所有点。
因为原图就是一个树，因此缩点后的图仍然是一个树，因此满足条件的点就是树根，它有且只有一个，并且只有它入度为
0
0
0。
我们可以用并查集将一个强连通块缩成一个点，还能同时记录一下块内有几个点，然后我们再通过有向边记录一下每个块的入度，最后检查一下是否存在只有一个块入度为
0
0
0 即可。
code2：
队友赛时代码，当时是
A
C
AC
AC 了，但是在
C
F
CF
CF 上重交就过不了了。局部变量开太多导致
M
L
E
MLE
MLE，视评测机优化还会变
R
E
RE
RE 或者
W
A
WA
WA。把一些局部变量改成全局变量就行了。
#include<bits/stdc++.h>usingnamespace std;constint maxn=1e5+5;intfind(int x,vector<int>& fa){if(fa[x]== x)return x;int fx =find(fa[x],fa);
fa[x]= fx;return fx;}voidmerge(int x,int y,vector<int>& fa,vector<int>& cnt){int fx =find(x,fa);int fy =find(y,fa);if(fx == fy)return;
fa[fx]= fy;
cnt[fy]+= cnt[fx];return;}voidsolve(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);int n;cin>>n;
vector<int>a(n+5);
vector<int>fa(n+5);
vector<int>cnt(n+5);for(int i =1;i<=n;i++){
cin>>a[i];
fa[i]= i; cnt[i]=1;}
vector<int> edge[n+5];for(int i =1;i<n;i++){int u,v;cin>>u>>v;if(a[u]*2>=a[v]&& a[v]*2>= a[u]){merge(u,v,fa,cnt);}elseif(a[u]*2>=a[v]){
edge[v].push_back(u);}elseif(a[v]*2>=a[u]){
edge[u].push_back(v);}}
set<pair<int,int>> st;for(int i=1;i<=n;i++){for(auto j : edge[i]){int u = i,v = j;int fu =find(u,fa);int fv =find(v,fa);if(fu == fv)continue;// if(fu > fv) swap(fu, fv);
st.insert({fu,fv});}}
vector<int>chu(n+5),ru(n+5);for(auto pii : st){
chu[pii.first]++;ru[pii.second]++;}int sz =0;int ans =0;for(int i =1;i<=n;i++){int fi =find(i,fa);if(i != fi)continue;if(ru[i]==0){
sz ++;
ans = cnt[i];}}if(sz >1)
cout<<0<<'\n';else cout<<ans<<'\n';}intmain(){int T;
cin>>T;while(T--){solve();}return0;}
Problem L. Toxel 与 PCPC II
题意：
Toxel 正在参加 PCPC（Pokémon Center Programming Contest）比赛。它写的一段代码中有不少
b
u
g
bug
bug，正在调试。这份代码总共有
n
n
n 行，而且经验丰富的 Toxel 已经知道了其中
m
m
m 行代码有
b
u
g
bug
bug，并锁定了这
m
m
m 行的具体位置。但是 Toxel 还需要进行一些调试以了解错误的具体细节并修复它们。
Toxel 会进行多次调试。每次调试时，Toxel 可以任选一个
i
i
i，使得程序从第
1
1
1 行开始，顺序运行完第
i
i
i 行后退出。Toxel 可以通过这
i
i
i 行代码运行的一些输出结果来进行
d
e
b
u
g
debug
debug。运行这
i
i
i 行代码总共需要
i
i
i 秒。接下来，Toxel 会一次性地
d
e
b
u
g
debug
debug 这
i
i
i 行代码，并修复所有这
i
i
i 行中的所有
b
u
g
bug
bug。
b
u
g
bug
bug 数量越多，修复所需的时间也越多。设这
i
i
i 行代码中现存的
b
u
g
bug
bug 数量为
x
x
x，那么 Toxel 需要
x
4
x^4
x4 秒来
d
e
b
u
g
debug
debug 并完成修复。修复后，这
i
i
i 行代码中将不再存在任何
b
u
g
bug
bug。
PCPC 的赛场争分夺秒。请你帮 Toxel 计算一下，它最短需要多少秒才能完成
d
e
b
u
g
debug
debug，修复整个代码中的所有漏洞？
思路：
很明显的
d
p
dp
dp，朴素想法是设
d
p
[
i
]
dp[i]
dp[i] 表示
d
e
b
u
g
debug
debug 前
i
i
i 行代码所需的最少时间，设
s
j
∼
i
s_{j\sim i}
sj∼i 表示第
j
j
j 行到第
i
i
i 行的
b
u
g
bug
bug 数量，
d
p
[
0
]
=
0
dp[0]=0
dp[0]=0，那么状态转移方程为
d
p
[
i
]
=
min
{
d
p
[
j
]
+
i
+
s
j
+
1
∼
i
4
}
(
0
≤
j
<
i
)
dp[i]=\min\{dp[j]+i+s_{j+1\sim i}^4\} \quad(0\le j\lt i)
dp[i]=min{dp[j]+i+sj+1∼i4}(0≤j<i)
不过这是个
n
2
n^2
n2 递推，会
T
T
T。
优化1：
因为运行一行代码也需要时间，我们要尽可能少地选取代码，因此我们每次选择的时候，选择的这一行一定有
b
u
g
bug
bug。不然如果这一行没
b
u
g
bug
bug 的话，我们不如选上一行，同理向上走，直到我们选中有
b
u
g
bug
bug 的一行。
因此我们枚举的时候只对
b
u
g
bug
bug 行枚举，时间优化为
O
(
m
2
)
O(m^2)
O(m2)。
优化2：
因为
d
e
b
u
g
debug
debug 所需时间是
b
u
g
bug
bug 数量的四次方，非常夸张的增长速度，因此我们猜测其实每次
d
e
b
u
g
debug
debug 只会选取少量
b
u
g
bug
bug。
考虑到我们多运行一次代码，花费也不会超过
2
∗
1
0
5
2*10^5
2∗105。而
3
8
4
−
3
7
4
=
210975
38^4-37^4=210975
384−374=210975，已经超过
2
∗
1
0
5
2*10^5
2∗105 了，这意味着如果我们一次性选取了
38
38
38 个
b
u
g
bug
bug，那么我们不如先选一个
b
u
g
bug
bug，然后再选后面的
37
37
37 个
b
u
g
bug
bug，就算多运行一次也肯定划得来。
因此我们枚举
j
j
j 的时候，不必枚举所有的
b
u
g
bug
bug 行，我们只需要向上枚举四五十行就行了。如果枚举
50
50
50 行，时间复杂度就会优化为
O
(
50
m
)
O(50m)
O(50m)。
code：
#include<iostream>#include<cstdio>usingnamespace std;constint maxn=2e5+5;typedeflonglong ll;int n,m;
ll a[maxn],dp[maxn];intmain(){
cin.tie(0)->sync_with_stdio(false);
cin>>n>>m;for(int i=1;i<=m;i++)cin>>a[i];for(int i=1;i<=m;i++)dp[i]=1e18;for(int i=1;i<=m;i++){for(int j=i-1;j>=max(0,i-50);j--){
dp[i]=min(dp[i],dp[j]+a[i]+1ll*(i-j)*(i-j)*(i-j)*(i-j));}}
cout<<dp[m];return0;}
Problem M. 有效算法
题意：
给出长度为
n
n
n 的正整数序列
{
a
n
}
\{a_n\}
{an} 和
{
b
n
}
\{b_n\}
{bn}。对于每个
a
i
（
1
≤
i
≤
n
）
a_i（1 ≤ i ≤ n）
ai（1≤i≤n），进行恰好一次以下操作：
- 将 a i a_i ai 变成满足 ∣ a i − x ∣ ≤ k × b i |a_i − x| ≤ k × b_i ∣ai−x∣≤k×bi 的任意整数 x x x。
请你求出最小的非负整数
k
k
k，使得存在至少一种方法使得操作后序列
{
a
n
}
\{a_n\}
{an} 所有数都相等。
思路：
满足
∣
a
i
−
x
∣
≤
k
×
b
i
|a_i − x| ≤ k × b_i
∣ai−x∣≤k×bi，则
x
∈
[
k
b
i
−
a
i
,
k
b
i
+
a
i
]
x\in [kb_i-a_i,kb_i+a_i]
x∈[kbi−ai,kbi+ai]。当
k
k
k 增大的时候，这个区间会变得越来越大，就越有可能出现合法的
x
x
x。也就是说答案具有单调性。
因此考虑二分答案，对一个答案进行
O
(
n
)
O(n)
O(n) 验证。验证可以求出
n
n
n 个取值区间，我们只要保证它们的交集不为空即可（我们可以取所有区间左端点的最大值和右端点的最小值，如果最大值小于最小值就说明交集不为空）。
code：
#include<iostream>#include<cstdio>usingnamespace std;constint maxn=3e5+5;typedeflonglong ll;int T,n;
ll a[maxn],b[maxn];boolcheck(ll k){
ll lmx=-1e18,rmi=1e18;for(int i=1;i<=n;i++){
lmx=max(lmx,a[i]-k*b[i]);
rmi=min(rmi,a[i]+k*b[i]);}return lmx<=rmi;}intmain(){
cin.tie(0)->sync_with_stdio(false);
cin>>T;while(T--){
cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)cin>>b[i];
ll l=0,r=1e9,mid;while(l<r){
mid=(l+r)>>1;if(check(mid))r=mid;else l=mid+1;}
cout<<l<<"\n";}return0;}
END
本人的碎碎念，顺便记录一下2024年5月的这场ccpc。
作为本地土著还是庆幸是我轻来办比赛，而不是郑大，郑大不重视计院，尤其不重视acm。郑大去年校赛浪潮杯不仅没给奖品，连出题人的出题费也没给。比赛费用也不报销，与之相对的其他比赛都报销ppt大赛有啥含金量啊 ，来郑大打acm就好比去西伯利亚挖土豆。
郑轻办的这场感觉经验不足，正式赛当天日程就出了点问题，本来是八点四十开幕式，九点半比赛，结果晚点不仅禁止入会场，领导们叨叨到九点十分多还没结束。因为体育馆（音乐厅）位置不够所以有的队要去机房考（不过有补偿），过去要走一两里地，时间来不及，所以我们队直接半途直接润去机房了，之后也是临时调整时间。比赛结束后滚榜也不会滚，人都上去领奖了还在滚榜，领奖的人拿完牌子赶紧退场，之后发河南省奖的时候连榜也不滚了，直接念名字上去领奖。估计应该会被挂贴吧（好像并没）。
第二天郑轻老师居然亲自致歉
不过也能看出来我轻是努力想办好的。虽然出了一些岔子，但是并没有引起什么舆论风波，也侧面说明了大部分人对这场的体验还是不错的。参赛服发的是一件速干T恤，腋下到侧腹有散热设计，纯白，少乱七八糟的
l
o
g
o
logo
logo，质感摸起来非常棒。设计用心了，是一件非常适合日常穿的衣服。训练赛当天发了午餐券和晚餐券，一张在食堂可以抵扣十五元，非常推荐卤肉饭金灿灿的麻布洗（就算不抵扣，直接买也很便宜，一碗卤肉饭半碗全是肉，才十二块，这才应该是大学的食堂） 。赛时午饭给的一整包火腿，酸奶和一个大奶油面包，是马斯卡彭，说是面包，其实是蛋糕胚+奶油，爽吃。在糖的加持下，我们队封榜时直接连出两题，这两天我吃的很开心，下次还想来。
我们河南
A
C
M
e
r
ACMer
ACMer 腰杆子直起来了！
本文转载自: https://blog.csdn.net/qq_45809243/article/details/138890493
版权归原作者 邪神与厨二病 所有， 如有侵权，请联系我们删除。
版权归原作者 邪神与厨二病 所有， 如有侵权，请联系我们删除。