如何找到网站是谁做的,南昌做网站哪家最好,手机wap网页,青岛外贸网站设计【原文链接】
比赛链接#xff1a;2024牛客暑期多校训练营3
A.Bridging the Gap 2
题目大意 n n n个人过河#xff0c;第 i i i 个人初始有 h i h_i hi 点体力。 由于船的限制#xff0c;每次过河#xff08;或返回#xff09;至少需要乘坐 l l l 人#xff08;来…【原文链接】
比赛链接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;vectorll v(n);for(autox: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 (sumturn*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)|axby gcd(a,b)∣axby 成立即 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_{i1}^n(h_i) gi1gcdn(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()
{vectorstring vs(9);for(autos:vs) cin s;int fl0,i8,i8;FORLL(i,1,7){FORLL(j,1,7){if(vs[i][j]8){i8i; i8j; fl1; break;}} if(fl) break;}FORLL(i,0,8){FORLL(j,0,8){if(ii8ji8) cout 8;else cout *;}cout endl;}
}
