SGU-351-400

 2021/09/12 

400 The last hour of the contest

题意已知 ICPC 封榜前的榜单以及封榜后发放的气球总数，求你所在队伍可能的最高排名和最低排名。

分析贪心+模拟。

399 Berodoskar Development

题意给 15×15 的网格图，每个格子有 2 种类型：'X' 表示蓄水池，'.' 表示空地。有公共边的 'X' 相互连通成一个大蓄水池。现需要从地图边缘搭建管道引流到至少 2 个蓄水池上，管道可复用。求最少需要的管道长度。

分析贪心。

398 Friends of Friends

题意给 50 个人的好友列表。若 c 不是 a 的好友，且存在 b 是 a 和 c 的好友，则 a 和 c 互为 friend of friend。求给定 x 的 friend of friend 列表。

分析模拟。

397 Text Editor

题意（光标模拟）。

分析模拟。

396 Dance it up!

题意背景类似劲舞团游戏。给长为的按键序列，序列由和构成。每个节拍需要按一个键，表示空操作（但即使按了任意键也没有惩罚）。

游戏开始时，角色左手在 LEFT 键上右手在 RIGHT 键上，每个节拍角色有以下行动模式：

空操作，不花费任何能量。
不移动手的位置，但手按下其所在位置的键，花费 1 单位能量。
将一只手移动到一个空按钮上（即另一只手不在该键上），然后按下该按钮。若这只手前一节拍没有按键行为，花费 3 单元能量，否则花费 9 单元能量。
将两只手移动到任意位置并按下该位置下的键，花费 10 单元能量。

不允许出现左手在 RIGHT，右手在 LEFT 的情况，该情况视为游戏失败。

求完成游戏序列的最小能量花费，并给出任一方案。

分析 DP。状态转移只与前一节拍的左右手状态相关，按游戏序列动态规划即可。

395 "Binary Cat" Club

题意给条按时间序但可能部分缺失的日志，日志有 3 种类型：

“+ name”：表示名字为 name 的人进入 club；
"- name"：表示名字为 name 的人离开 club；
"= visitors"：表示当前 club 有 visitors 个人。

由于日志可能存在缺失导致连续出现 "+ A", "+ A"，此时中间需要补充 "-A"。求最少需要补充的日志条数。

分析对于需要补充 "+ name" 和 "- name" 都有一个区间，当有 "= visitors" 查询操作时，贪心利用即可。

394 Berhatton

题意给二维平面上个点，每个点覆盖曼哈顿距离不超过的点。求哪些点被覆盖至少次。

分析扫描线+线段树。将点坐标进行变换，则曼哈顿距离变成切比雪夫距离，每个点的覆盖范围是一个正方形。套用扫描线+线段树的做法覆盖点，线段树维护区间最大值，当最大值大于等于时，将该点删除（置为无穷小，保证后续操作不会重复删除即可）。因为每个点最多只会被删除一次，因此整体时间复杂度仍然是。

393 Bergamot Problem

题意前个小写字母构成大小为的字典，每个单词仅由 2 个字母构成。设计一个按键布局，放置每个字母到不同的按键上，使得 2 个按键对应唯一的一个单词。求最少的按键数量。

分析状压 DP。

392 Cyclic Troubles

题意给的网格图，每个格子上都有一小写字母以及一个方向，指向相邻的格子。有个询问，每个询问给定压缩长度为的字符串，判断是否能从某个格子出发拼出该询问字符串。数据保证不存在嵌套压缩，且询问字符串的原始长度不超过。若存在多个可行的起点，输出最小的 pair 对。

分析因为每个格子的出度为 1，每个格子最多落入到一个环中。主要难点在于压缩字符串和环上字符串的匹配问题。用表示匹配到压缩字符串位置和环上字符串位置的循环长度。

391 Mr. X

题意在网格图上有个标记点。每次操作允许沿连续两行或两列的中线进行对折，判断是否能通过若干次对折使得所有的标记点叠在一起，并且非标记点不与标记点重合。

分析 x，y 两坐标轴相互独立。

390 Tickets

题意给定阈值，当若干连续值的数位和不小于时，计数器加一。求区间的计数器的值。

分析数位 DP 。表示到第位时，数位和为的计数值和数位和，即 <count, new_ds>。

389 Strange Planet

题意给定维的超立方体上的三个点。点坐标为，点坐标格式相同。求超立方体上到点曼哈顿距离相同的点的数量，结果对取模。

分析组合数学。

每一维对距离的贡献都是独立的，因此只需要考虑种情况。若，则其他点到的曼哈顿距离不会发生变化，此时只需要考虑种情况。但是根据两个方程显然不足以解决问题。

进一步地，其实我们只需要知道第维是否等于，是否等于，是否等于即可计算到三个点的距离。将三者全等的情况排除掉后，若，则蕴含了。设的情况数为，当分别为 0 和 1 时会有 2 种情况：或者。不失一般性，假设中有种情况使得点到点的距离都加 1，则有。

3 种情况下可以计算出，列出 2 个方程后剩一个自由元，枚举计算即可。

388 Soap Opera

题意有个演员，Juan 和 Rosa 给这些演员进行配对，每对演员都是一男一女。给定 Juan 认为可行的个可行方案，保证这对不相同。同理给出 Rosa 认为可行的个可行方案。（题目应该蕴含了 Juan 和 Rosa 的配对方案没有交集）。求最大演员数量，使得 Juan 和 Rosa 都能让这个演员两两配对。

分析

387 Lazy Judges

题意给条线段，使用线段上的点构造正方形，求面积的期望值。

分析

386 Happy Birthday, Jedi Knight!

题意

分析

385 Highlander

题意个人玩游戏，一开始每个人拿到印有数字的卡片。当 A 手上有 B 的卡片时，A 可以淘汰 B 并获取 B 手上的所有卡片。当没有人能被淘汰时，游戏结束且手上有最多卡片的人获胜（若卡片相同时，则两人同时视为冠军）。求游戏结束冠军人数的期望值。

分析组合数学+动态规划。能互相淘汰的人一开始就在同一个环上，本质上是对人分群求方案数。表示前个人组成个最大环为的方案数。

384 Country

题意给个点和条边的无向图，保证任意两个点之间有且仅有一个公共点。进行次操作，操作分 2 种类型：将第条边删除；询问之间的距离。

分析根据任意两个点之间有且仅有一个公共点这个性质，可以发现原图是多个三角形共享同一个顶点，将这些顶点找出来即可。

383 Caravans

题意二维平面上有个点。进行次询问，最小化从到所需要的两点间最大距离。

分析 整体二分。单次询问，二分从到所需要的最大两点间距离，然后将两点距离不超过的边构造生成树，判断是否在同一联通块中即可。因为不同询问在相同下的处理是一样的，因此可以通过整体二分将复杂度降至。

剩下的问题在于如何构造二维平面点的最小生成树。Delaunay triangulation（三角剖分）可以将平面点分割出级别的三角形，利用三角形边构造最小生成树即可。

参考

382 Cantor Function

题意给定康托函数以及整数，求的最简分数形式。 $$ $分析将积分分段积分，即。对于区间根据分段函数形式并换底：$ {0}^{ 3} f(x)^ndx = {0}^{ 3} {2^n} dx \ =_{0}^{1} 3 {2^n} dt \ = {3^n} _0^1 f(t)^ndt $$ 换底后与原问题相同。

而对于区间 [2/3, 1]，因为有常数项的存在，需要用二项式展开，然后会发现需要对都进行积分得到相应值。

假设二项式展开除外的和为，则有：

381 Bidirected Graph

题意给个点的和条边的有向图，每条边均定义了边权。允许对任意点进行变换：对于所有边，使得。当所有边都满足时，此时有向图可视为无向图。

判断通过点变化是否将有向图转换成无向图，若能输出至少需要几次点变换并输出任一方案。

分析模拟。一个联通块中的点确定是否变换后，随后该联通块的其他点变换状态也固定了。因此，选取联通块任意点并枚举状态后，取点变换数量少的方案即可。

380 Synchronised Alpinism

题意两个人从山的左右两个山脚开始爬山，要求两个人每时每刻都必须在同一高度，判断两个人最后是否能够相遇。山简化成多边形，其顶点为，其中。

分析

代码 380.cpp

379 Elevator

题意层楼高的建筑中仅有一部电梯，每次能承载个人。已知第层楼有个人在等电梯到 -1 层，电梯上升或下降一层楼需花费秒。电梯初始位置在 -1 层，求秒内最多能带多少人到 -1 层。

分析二分。二分人数。

378 Save the Fisher

题意

分析 (没看懂样例，skip)

377 The Lesson of Physical Culture

题意给的网格图，要求任意的正方形中有且仅有 2 个 1，求方案数。

分析构造。考虑第一行状态，若存在相邻的 2 个 1 或 0，那么下一行的状态便固定了。当第一行不存在相邻的相同数字时（即 101010.. 或者 01010...），下一行与第一行相同或者互补。

376 Berland All-Round Competitions

题意个选手参与竞赛：先游泳，然后进行段赛马。每匹马有不同的速度，先到达某一阶段的选手优先选下一阶段的马（若存在同时到达的选手，力量值的选手优先）。按照选手到达顺序，求选手的排名。

分析模拟。

375 Amplifiers

题意 Shurik 想利用电压放大器得到标准电压的倍电压。电压放大器有两种：从 X 放大至 2X-1；从 X 放大至 2X+1。求最少需要几个电压放大器，或判断无解。

分析 二进制。显然必须是奇数。根据题意有或者且二进制位末位是 1，因此 ±1 会影响倒数第二位。当二进制位倒数第二位是 1 时，此时只能 - 1 否则 +1 会导致新的不为奇数。当二进位倒数第二位是 0 时，此时必须 +1 否则同样导致新不为奇数。

因此向下转化时路径是固定的。

374 Save Vasya

题意求多项式的系数和，其中。

分析模拟。令，则问题转化成。

373 Carlsson vs. Winnie-the-Pooh

题意一块圆形披萨被切了 4 刀，Carlsson 和 Winnie 轮流取一小块披萨吃，花费的时间与披萨面积成正比。每个人都希望最大化自己最终吃到的披萨，求最后两人吃到的披萨面积。

分析计算几何+DP。圆形切 4 刀最多划分出 11 个区域，表示每个披萨未被吃/被 Carlsson 吃了/被 Winnie 吃了三种状态，依据状态可以计算出下一个取披萨的人。

剩下的问题就是如何求各块小披萨的面积了。

372 Tea Party

题意一场聚会上有个客人，Alice 会在客人离开时送茶包。茶包有红茶和绿茶两种品类，但有不同类型。Alice 会给不同客人不同类型的茶包，但不允许连续 3 个茶包都是红茶或绿茶。已知个茶包的价格以及品类，求 Alice 至少需要花费多少费用。

分析贪心。从结果角度入手，假设送出包红茶以及包绿茶且。因为不能连续送出 3 个茶包，因此。先按价格排序，若不满足该限制条件，则根据条件补充相应品类的茶包。

371 Subway

题意构造地铁路线方案：地铁由若干 circle lines 和 radial lines 构成，但需要满足：

每个 circle line 至少 3 个站点，但不超过 10 个站点；
Circle lines 通过换乘站串联起来形成一条链；
Radial lines 站点之一在 circle line 上，而另一个站点不在任何 circle lines 上；
Radial lines 之间不能有相同站点；
任意站点最多在 2 条 lines 上，即换乘站不能作为 radial line 的站点之一。

给定站点数和站点对数，求任一方案或判断无解。

分析构造。站点本质上可以分为 4 类：换乘点、circle line 经过点、radial line 终点、radial line 起点，其数量分别记为。

根据题意有共 3 个等式，可以枚举来求解其他 3 个值。注意条件一会限制之间的关系。之后根据求解值构造即可。

370 Rifleman

题意在大小为网格图中，从位置需要设置几条射线以覆盖所有格点。

分析容斥原理。网格图的一条射线可以使用表示，其中互质，问题可以转化为：给定，求中与互质的数的数量。

因为，因此的质因子数量不超过 7 个。根据容斥原理可以在求出互质数的数量。

369 Game

题意二维平面上给个点。若三个点构成了矩形的三个点，则会填充矩形的第四个点。求最终平面上有多少个点。

分析模拟。假设直线有个若干个点，对于直线上的给定点，会在其他直线上填充新点，最后形成一个网格图，其坐标值域是由给定点所决定的。也就是说，我们只关心哪些或者哪些出现过。

当其他点落在网格图直线上时，可以沿新点垂直于该点所在直线上覆盖其他给定点。

368 Tests

题意

分析？模拟？

367 Contest

题意有道题目，解决第道题目需要花费单位时间。题目之间有种依赖关系：解决问题之间必须先解决问题，保证。求在时限内最多能解决多少道题目。

分析图+贪心。因为有，所以必然会优先解决。

366 Computer Game

题意游戏中有道题，主角答对第道题会获得的愉悦度和的得分。主角只会答对其中的道题，因此程序需要选择其中的道题使得尽可能小其次最大化，其中。

分析动态规划。因的值域较小，的值域为 [-50, 50] 共 101 种可能。相同差值中根据最大化固定了选取顺序，因此仅需要枚举道题，替换原先的枚举。

365 Ships of the Desert

题意当一个个数位的数字，其数位先单调递增后单调递减，则定义该数字为幸运数字。允许有前导 0 的前提下，统计幸运数字的数量。

分析动态规划。表示有个数位且最后一位为的方案数。

364 Lemmings

题意有只旅鼠每隔秒从点出发，以 1cm/s 的速度朝右前继直至从平台掉落，掉落速度也为 1cm/s。旅鼠会从一个平台掉落至另一个平台或者永远在下落状态。

我们可以停止行进中的旅鼠使其保持在原地，当其他旅鼠碰到停在原地的旅鼠会改变行进方向。

旅鼠的最终目的在终点，求最多能让几只旅鼠到达终点，此外让最小化最后一只旅鼠到达时间。

分析最短路。关键点只有旅鼠在其他平台的落点，依据这个构造图，使用表示到点方向为的最少停止旅鼠数量以及最短耗时。

363 Baggage Room

题意有个人和个柜台，已知每个人的到达时间和处理时间。当一个人到柜台前时会优先选择排队人少的柜台办理业务，有多种选择时优先考虑编号小的柜台。求每个人选择的柜台编号以及离开时间。

分析模拟。

362 Robot-Annihilator

题意一个机器人欲遍历的网格图，按照下左上右顺序挑选下一步格子，每个格子仅能被遍历一次。求机器人的执行序列。

分析模拟。

361 National Flag

题意用红色和蓝色给网格图染色，要求所有和的子矩阵都必须刚好有 2 个蓝色，并且整张图的蓝色数量最少。求任一种染色方案。

分析构造。对于任意的正方形，填充 3 个不同行、不同列的蓝色方格即可满足题意。

360 B++ Interpreter

题意给的网格图以及朝向顶部的机器人，图上有若干个目标点，用表示。机器人根据给定指令序列行动：指令序列由主函数 m() 开始，调用其他函数或者执行基本操作符。

分析模拟。

359 Pointers

题意给 4 个 integer 类型的指针，有 3 种操作：给指针所在地址赋值常数/其他指针所在地址的值；修改指针指向地址。对于 writeln 操作输出相应指针所在地址的值。

分析模拟。

358 Median of Medians

题意给 3 组数，每组 3 个数。先求每组数中的中位数，然后再求这些数的中位数。

分析模拟。

357 Remote Control

题意电视有 0 到 99 的频道，遥控器可以通过 ↑↓ 键切换至相邻频道或者通过 -- 和数字键直接切换到指定频道。遥控器部分按键损坏了，问从频道切换至频道最少需要按键几次。

分析构图跑最短路。

356 Extrasensory Perception

题意有对夫妇但不知谁和谁配对，求刚好猜中对的概率。

分析组合数学。枚举猜中的夫妻对，剩下进行错位排列。

355 Numbers Painting

题意给的数字染色，要求若整除，则两者颜色不同。求最少需要的颜色数，并给出其中一种染色方案。

分析本质上是求数的约数个数。

354 Just Matrix

题意有一的矩阵，且。已知表示第列中满足的个数和表示第行中的个数。要求构造矩阵使其满足上述条件，若无解则输出 0。

分析从单行的前 2 个元素入手，根据可比较这 2 个元素的大小。（再走一步），考虑第 3 个元素，根据也可以推断出前 3 个元素的大小关系。以此类推，我们可以知道单行/单列的所有元素的大小关系，进而可以构造一张 DAG。

根据 DAG 的拓扑序填充即可。

353 Billing

题意（模拟）

分析

352 Beerland Attacks

题意个点条边的无向图，给定以 1 为根的一棵最短路径树。对于除 1 外的点，当的最短路径树上的父边不可用时，1 到 i 的最短距离。

分析最短路算法。

351 A Mission for a Scout

题意给定二维平面一个圆，圆外两点，以及一常数表示能在圆行走的最大距离。求从点到点的最短距离，输出其中一种方案。

分析（计算几何）

原文作者：Mcginn

原文链接：http://mcginn7.github.io/2021/09/12/SGU-351-400/

发表日期：September 12th 2021, 12:19:52 am

更新日期：May 4th 2024, 5:07:17 pm

Next Post

SGU-401-450
Previous Post

SGU-301-350

CATALOG