比赛链接：2024牛客暑期多校训练营3
A.Bridging the Gap 2
题目大意
n
n
n个人过河，第
i
i
i 个人初始有
h
i
h_i
hi 点体力。
由于船的限制，每次过河（或返回）至少需要乘坐
l
l
l 人（来划船），至多可以乘坐
r
r
r 人，每个乘船的人都会消耗
1
1
1 点体力。体力为
0
0
0 的人无法乘船。
求对于给定的条件，是否能够使所有人过河。
解题思路
假设初始所有人在左岸，考虑一种贪心模拟的做法：
- 从在左岸的所有人中选取 l l l 个体力最大的人划船，带 r − l r-l r−l 个体力最小的人去右岸。
- 从在右岸的所有人中选取 l l l 个体力最大的人划船返回左岸。
- 重复以上步骤，直到所有人都到达右岸，或者无法继续。
这个过程中，除去最后一次划到右岸的
r
r
r 个人，每次能运输的人数为
r
−
l
r-l
r−l 。
最低往返的次数为
t
u
r
n
=
⌈
n
−
r
r
−
l
⌉
turn = \lceil \dfrac{n-r}{r-l}\rceil
turn=⌈r−ln−r⌉ ，且最优，因为往返越少对体力的要求越低。
对于个人，除自己前往右岸的1点体力，多余的体力可以用于划船带人，往返一次需要2点体力。
因此第
i
i
i 个人能够参与的往返次数为
⌊
h
i
−
1
2
⌋
\lfloor \dfrac{h_i-1}{2}\rfloor
⌊2hi−1⌋ 。
由于只存在
t
u
r
n
turn
turn 次往返，因此第
i
i
i 个人能够参与的往返次数为
min
(
⌊
h
i
−
1
2
⌋
,
t
u
r
n
)
\min(\lfloor \dfrac{h_i-1}{2}\rfloor,turn)
min(⌊2hi−1⌋,turn) 。
计算所有人能够参与的往返次数之和，如果大于等于 t u r n ∗ l turn*l turn∗l ，则按照上述贪心模拟的方法，可以使所有人过河。
参考程序
程序是副机长根据解题思路写的，居然A了()
void solve()
{
ll n,l,r; cin >> n >> l >> r;
vector<ll> v(n);
for(auto&x:v) cin >> x;
ll turn = (n-r)/(r-l) + ((n-r)%(r-l)!=0);
ll sum = 0;
for(auto x:v) sum += min((x-1)/2,turn);
cout << (sum>=turn*l?"Yes":"No") << endl;
}
B.Crash Test
题目大意
初始距离墙壁的距离为
d
d
d 。
每次前进有
n
n
n 种长度可以选择：
h
1
,
h
2
,
⋯
,
h
n
h_1,h_2,\cdots,h_n
h1,h2,⋯,hn。每次前进的长度可以是任意一种长度。
如果选择的长度
h
i
h_i
hi 大于当前与墙壁的距离
d
′
d'
d′ ，将会退后多余的距离，即新的距离为
h
i
−
d
′
h_i - d'
hi−d′ 。
求在任意次（包括0次）前进后，与墙壁的最小距离。
解题思路
裴蜀定理：对于非0整数 a , b a,b a,b ，对任意整数 x , y x,y x,y 有 g c d ( a , b ) ∣ a x + b y gcd(a,b)|ax+by gcd(a,b)∣ax+by 成立，即 g c d ( a , b ) gcd(a,b) gcd(a,b) 是所有 a , b a,b a,b 的线性组合中，绝对值最小的非0整数。
裴蜀定理扩展到多整数的情况仍然成立。
因此计算出 g = gcd i = 1 n ( h i ) g=\gcd\limits_{i=1}^n(h_i) g=i=1gcdn(hi) ， g g g 的意义是通过对 h i h_i hi 的某种线性组合，能够得到的最小前进距离。
然后每一步视为走 g g g ，以此求得不撞墙答案 d % g d\%g d%g 与撞墙答案 g − d % g g-d\%g g−d%g ，取较小值即可。
参考程序
void solve()
{
ll n,d; cin >> n >> d;
create_vec(v,n);
ll g = v[0];
for(auto x:v) g = __gcd(g,x);
cout << min(d%g,g-d%g) << endl;
}
D.Dominoes!
//TODO
J.Rigged Games
//TODO
L.Sudoku and Minesweeper
题目大意
经典数独在 9 × 9 9\times 9 9×9 大小的棋盘格内进行，每一行、每一列、 9 9 9 个 3 × 3 3\times 3 3×3 的小方块内，数字 1 − 9 1-9 1−9 恰好出现一次。
扫雷是一款在棋盘格内进行的游戏，中心数字表示周围 8 8 8 格包含地雷的数量。
现给定一个 9 × 9 9\times 9 9×9 数字矩阵表示一个已经完成的合法经典数独，可以将里面的数字替换成地雷，但必须保留至少 1 1 1 个数字，求一个合法的扫雷游戏布局。
解题思路
除了边缘之外，中间
7
×
7
7\times 7
7×7 范围内必然出现数字
8
8
8 。
这是一个特殊的数字，只需要把它保留，其余所有数字全部替换成地雷，就是一个合法的扫雷游戏布局。
参考程序
void solve()
{
vector<string> vs(9);
for(auto&s:vs) cin >> s;
int fl=0,i8,i8;
FORLL(i,1,7){
FORLL(j,1,7){
if(vs[i][j]=='8'){
i8=i; i8=j; fl=1; break;
}
} if(fl) break;
}
FORLL(i,0,8){
FORLL(j,0,8){
if(i==i8&&j==i8) cout << '8';
else cout << '*';
}
cout << endl;
}
}