Mcginn's Blog

SGU-253-300

2021/04/24

300 Train

题意 给定水平/垂直方向的火车轨道顶点顺序，在不发生碰撞的前提下，求火车的最大长度。轨道顶点数为 ，点坐标 。

分析 模拟。将点坐标离散化成 的网格图，记录当前火车所占据的线段以及车头/车尾坐标，模拟火车行进和碰撞。模拟过程中，记录火车的最大长度。

299 Triangle

题意 有 个大数 ，找出 3 个数使之能构成三角形的边。

分析 模拟+大数。排序，取相邻的 3 个数判断即可。

298 King Berl VI

题意 个变量 ， 个约束：。要求解 ，且最小化 。判断是否有解，若有解输出任一方案。

分析 差分约束。

  1. 差分约束系统 是 元一次不等式组，有 个变量 以及 个约束条件 。求一组解 满足所有的约束条件。

  2. 对于形如 的约束条件，可以转换成 ，这与单源最短路中的三角不等式 类似。将变量 视为有向图中的节点，约束条件 视为一条边权为 且从 向 的有向边，同时添加从超级源点到每个点的有向边，边权视情况设置。从而将差分约束问题转化成单源最短路问题。

  3. 在某个变量确定的情况下，形如 约束条件的问题下，单源最短路给出一种最大解。对于从超级源点 到 的任意一条路径 ，有约束条件： 相加得到 ，其中 。

    记 为最短路，有 ，即 的最大值为 。

  4. 对于形如 的差分约束问题，类比单源最长路 的三角不等式，将问题转换成单源最长路问题，得到的解为最小解。

  5. 如何求解单源最长路？单源最长路和单源最短路问题是对偶的。定义原图为 ，有向边为 。将边权取反后得到对偶图 ，新的有向边为 。对于任一路径 有 。显然，对偶图 的最短路对应原图 的最长路。

  6. 回到 SGU 298 问题上，要让 尽可能小，想法是让 尽可能大而 尽可能小。做法是先构造 让 尽可能大，然后构造 让 尽可能小。

参考 OI Wiki-差分约束；最短路、最长路与差分约束的最大解、最小解。

297 Fair-play

题意 （简单题）

分析 模拟。

296 Sasha vs. Kate

题意 给一大数 ，求从 去掉 个数位后的最大值。

分析 贪心。

295 Identifier Duplicated!

题意 给定一字符串，求长度介于 等价的字符串数量。若一个字符串经过若干次操作转换成另一字符串，则这两个字符串等价。允许的操作有：

  1. 使用相同的拉丁字符替换成俄文字符，反之亦然。
  2. 改变单词之间的空格符数量，但不能完全删除。
  3. 添加前导/尾部空格。

分析 模拟。

294 He's Circles

题意 使用 2 种颜色对长度为 的项链染色，在旋转置换的条件下求本质不同的染色方案。

分析 Polya+BigNumber。

293 Game with Q an C

题意 有长度为 且仅包含 'Q', 'C' 俩字符的字符串，按顺序逐个添加字符构造新字符串，每次添加一个字符后可选择性地交换 2 个位置上的字符。要求当新字符串长度为奇数时是回文串，判断是否可行，若可行则输出任一方案。

分析 构造。考虑一次性添加 2 个字符，维护 格式，其中 表示回文中心， 表示连续字符 Q，分 CC, CQ, QC, QQ 四种情况考虑即可。

292 Field for the Cemetery

题意 在 的棋盘上最多能放置多少个 个长方形。

分析 模拟。

291 Evolution

题意 在 大小的网格图上有 种细菌族，第 种细菌族初始位置为 且第 秒才开始分裂。细菌族每秒钟从 向 四个方向分裂：不会向已有细菌格子的方向分裂。求 秒后第 中细菌族占领的格子数量。

分析 模拟。BFS。

290 Defend the Milky Way

题意 给三维空间中 个点，求在凸包顶点/平面上的点。

分析 计算几何。

289 Challenging Tic-Tac-Toe

题意 OOXX 游戏。给定一个初始局面，假设玩家都玩得很好的情况下，判断先手必胜/必败/平局/非法。非法是在游戏过程中不可能出现的局面。

分析 模拟。总共局面数为 种。

288 Best Tournament Schedule

题意 有 支队伍参加巡回赛，所有队伍两两之间都需安排一次比赛，要求同一巡回赛中每支队伍最多只参加一场比赛。求最少巡回赛轮数，并输出任一方案。

分析 构造。

当 为偶数时，巡回赛最少轮数为 。 为偶数的构造方案如下：

  1. 前 行，；
  2. 第 行， 。

当 为奇数时，巡回赛最少轮数为 。添加一支虚拟队伍转化成队伍数为偶数的情况构造。

代码 sgu 288

287 Amusing Qc Machine

题意 在 中猜一个秘密数字，程序每次返回猜测值和秘密值的大小/相等关系。但是存在 延迟：第 次猜测结果在第 次猜测后返回。求最坏情况下猜中秘密数字的猜测次数。

分析 表示 轮交互后猜测值的数量。因为延迟 存在，第 次猜测只能基于前 轮交互的已知结果。前 轮共有 个值，划分成 个区间，第 轮猜测值必然是在这些区间中，因此共有 枚举值。

则转移方程为 。

286 Ancient decoration

题意 个点的无向图，已知每个点的度数为 且 为偶数。要求给边染色使得每个点恰好在 2 条染色边上，判断是否存在可行方案，若存在则输出任一方案。

分析

Tips 欧拉回路。

285 What? Where? When?

题意 已知有 13 个问题，除第 13 个问题有 个候选外，1 至 12 号问题仅有一个候选。每次随机从 1 至 13 个问题中随机抽取一个问题，若答题者回答正确则 +1 分否则提问者 +1 分，答题者或提问者率先取得 6 分则游戏结束。给定答题者对于所有问题回答正确的概率，求所有可能局面（'6:0', '6:1', '6:2', '6:3', '6:4', '6:5', '5:6', '4:6', '3:6', '2:6', '1:6', '0:6'）的概率。

分析 状压 DP。

284 Grammar

题意 有 个字符串 ，由基本字符 'a', 'b' 或 构成。给定查询字符串 ，求串 在 中的出现次数。数据保证 。

分析 KMP 算法。对于每个字符串 记忆 ，表示从 位置开始匹配 最终成功匹配 的次数， 表示匹配完 后匹配 的前缀长度。

283 Mechanics

题意

分析

282 Isomorphism

题意 给 个点的完全图，每条边染上 种颜色中的一种。如果一张图完全图通过重标号点构成另一张图，定义这两张图同构。求本质不同的异构图数量，结果对 取模且 为素数。

分析 该问题本质上是在求边的置换然后使用 polya 定理计数，而边置换是通过点置换得到的，因此从点置换入手。

假设有一条边 ，分点 是否在同一点循环置换中考虑。

  1. 若点 在相同 k-循环中，即循环中的元素为 个。显然，边 所在的边循环置换同样有 个元素，而 个点的子图共有 条边，因此边循环个数为 。

    注意，当 为偶数时且 在点循环置换中间隔 时，边 所在的边循环置换中仅有 个元素。因为经过 次置换后，边 重复出现了。将这种边循环单独考虑，此时边循环个数为 。

    综上所述，若点 在相同点循环置换中，相应的边循环个数为 。

  2. 若点 不在相同点循环中时，假设两个点循环的元素个数分别为 ，那么边 所在的边循环置换有 个元素以及总共有 条边，因此边循环个数为 。

在已知边循环个数 的前提下，根据 polya 计数本质不同的染色方案数为 。

剩下的问题便是枚举点置换方案，然后计算相应的边循环个数即可。在枚举点置换方案时，只关心各个循环的大小而不是具体元素，问题转化成将 拆解成 使得 且 ， 表示第 个点循环的元素个数。

在得到各个点循环大小后，通过排列组合将具体元素放进循环中，得到本质不同的点置换方案即可。首先，假设 两两不同，则点分配方案数为 。如果存在若干个相同的 ，即存在相同大小的点循环，这些循环本身没有先后之分，但是前述枚举会重复统计。将点置换方案重新记为大小为 的循环有 个，则点分配方案数为 。此外，一个循环中的元素是有顺序的，大小为 的循环有 种排列方案：循环本质上是一个环，将第 个元素插入有 个元素的环时，有 个位置可以插入，利用归纳法得到 种排列。 最终点置换的方案数为 。

利用 burnside 定理，不等价着色方案数为 参考 SGU 282 Isomorphism

281 Championship

题意 有 只队伍参加了 2 场比赛且已知各比赛的排名，现要依据 2 场比赛排名生成最终排名：如果前 支队伍在 2 场比赛中是相同集合，则最终排名的前 支队伍也是该集合。如果无法确定队伍之间的相对排名，则按照队伍名称字典序排序。输出最终排名结果。

分析 模拟。

280 Trade centers

题意 给 个点的树，在树上标记若干点使得树上所有点到最近标记点的距离不超过 ，求最少需要标记点的数量。

分析 进阶问题 - HDU 5290 Bombing plan。 表示点 u 向上覆盖 步的最优值， 表示点 u 需依赖父节点向下覆盖 步的最优值。

279 Bipermutations

题意 有 个对象 ，已知存在偏序关系：; 。定义 if 否则 以及 等于 的数量，已知序列 ，判断是否存在满足条件的偏序序列，若存在输出任一方案。

分析 假设从大到小放置，经过模拟可以发现几个性质：(1)放置对象 时，只会影响 的 ；(2)放置 时会影响 的 ；(3)放置 之后才能放置 。

首先每次挑选 的对象 放置，如果存在多个 的对象 ，显然选取下标最小的对象 ，否则根据性质 (1) 会导致下标最小的对象 的 发生变化。

当找不到 时，依次放置已经放置 的 ——依次是指 相对顺序不能发生变化，然后修改 的 。

278 Fuel

题意 给定 种燃油，每种燃油单位质量下体积为 , 成本 和强度 ，其中 。已知汽车的油箱可容纳 体积的燃油以及成本限制 ，在允许任意混合燃油的情况下，求混合燃油的最大强度。

分析 假设有 2 种燃油 ，混合后可以得到 ，最终从一种比例的混合燃油中取得最大强度，即 。从几何角度看该问题，2 种燃油时混合燃油候选为一条线段，多种燃油时候选为凸多面体。

记 ，原问题可以转化成 。通过直线 划分 上限分别为 和 的情况，本质上都是线性规划问题，最优解必然在 extreme point（端点）上。

277 Heroes

题意 二维平面初始给 3 个点，随后逐渐添加 个点。每次添加点后，重新构造多边形包含当前所有点且周长最短，输出多边形的面积。

分析 加点维护凸包，参考模板

276 Andrew's Troubles

题意 （if else 模拟题）

分析 模拟。

275 To xor or not to xor

题意 给 100 个数 ，求一个子序列使得异或和最大。

分析 线性基。

274 Spam-filter

题意 写一个邮件地址 parser，判断地址合法性。

分析 Parser。

273 Game Po

题意 给定 200 个石子排成一排，并且每个石子染成蓝、红、黄、白其中一种颜色。四名玩家轮流选择 2 个相邻石子并使用 1 个替换规则颜色的石子替换，直到不能替换为止。游戏开始前，给定允许的替换规则，四种颜色分配给四名玩家，若游戏结束时仅剩 1 个石子，则该石子颜色对应的玩家获胜。求最后可能获胜的颜色。

分析 区间 DP。

272 Evacuation plan

题意 给 个点和 条边的无向图，起点集合 以及终点集合 ，保证 。现要找出若干等长路径使得尽可能多的点从 走到 ，需满足：1. 路径长度等于 ；2. 任意两条路径不能存在交点。求最多的点数以及路径长度，并输出一种路径方案。

随便构造一种方案，使得再也找不到一条从 A 到 B 的路径（不是找一个最优的方案）。

分析 BFS+DFS。

271 Book Pile

题意 已知有 个元素的栈，进行 次操作：1. 栈顶添加一新元素；2. 将栈顶 个元素翻转，其中 是常数。输出所有操作后的栈元素顺序。

分析 伸展树可做，但是大材小用了。操作上只有添加新元素且 为常数，一旦栈元素数量超过 ，除栈顶 个元素外其余元素已经固定了，这部分元素写入固定的栈中即可。而栈顶 个元素可能发生多次翻转，使用双端队列可以方便维护往“栈顶”添加数据。

270 Thimbles

题意 给定 个位置以及 次操作。一开始球在位置 1，每次操作交换 位置。已知操作集合但不知操作次序，经过 次操作后求解球可能的位置集合。

分析

269 Rooks

题意 有一个形状特殊的棋盘，该棋盘共 行，每行有 列。现要在棋盘上放置 个车，求车不互相攻击的放置方案数。

分析 行的顺序无关紧要，因此可以按列宽 排序。 表示前 行放置 个车的方案数即可，转移方程较简单。

268 Hyper Almost Permutative String

题意 若字符串包含前 个字符则定义为 permutative；若字符串去掉刚好一个字符后为 permutative 则定义为 almost-permutative；给定字符集 后若字符串所有长度为 的子串都是 almost-permutative 则定义该字符串为 hyper-almost-permutative。现给定 以及长度为 且为 permutative 的字符串 ，求最短 hyper-almost-permutative 字符串且 是其子串，多种方案输出任一方案。

分析

267 Optimist vs. Pessimist

题意 有 个矩形，每个矩形中有 2 个点。要求从这 个矩阵中选 个矩形，使得总面积和尽可能大。如果一个矩形能分成等面积的两部分且每部分都含有一个点，这个矩形会均分给 Optimist 和 Pessimist。Optimist 想知道最好情况下获得面积总和，Pessimist 想知道最坏情况下获得面积综合。

分析 等分面积线段必然经过矩形中心，即仅当矩形所包含的 2 个点和中心共线时无法均分。

266 Berlion

题意 给以原点为圆心半径为 的球体以及空间中两个点，求球体表面两个点的可视面积。

分析

265 Wizards

题意 有 个三维空间点，经过 次变换：平移，缩放和旋转变换，求经过变换后每个点的空间坐标。

分析 三种变换都可以使用矩阵表示，将 次变换融合成一个变换后应用于所有点即可。困难部分主要是旋转变换，参考绕任意轴旋转。

264 Travel

题意 有 个男生和 个女生，需要进行两两匹配。每个人有自己的偏好列表，若在一个匹配中出现双方都有更加偏好的异性存在时，该匹配是“不稳定”的。求解是否存在“稳定”的匹配方案，若存在输出任一方案。

分析 （稳定婚姻问题）。

263 Towers

题意 在长度为 的行上造塔。塔的定义为：连续位置均放置了方块且两侧都没有方块时，视为一个塔。有放置和询问两种操作：

  • 放置 1：在位置 x 放置 c 个方块；
  • 放置 2：在塔 t 的第 x 列放置 c 个方块；
  • 询问 1：目前塔的数量；
  • 询问 2：塔 t 中方块的数量；
  • 询问 3：塔 t 的长度；
  • 询问 4：塔 t 第 x 列上方块的数量。

分析 关键部分是如何快速找出塔 t，只有操作放置 1 时才会增加新塔。可以使用线段树维护每座塔的左边界点，快速查询塔 t 的位置。

262 Symbol Recognition

题意 有 个符号，每个符号由 的黑白网格构成。要求最少格子数使得能够区分出所有符号。

分析

261 Discrete Roots

题意 给两个质数 和整数 ，求解方程 的所有解。

分析

参考 一些数论概念与算法——从SGU261谈起

260 Puzzle

题意 有 个黑白格子，已知初始颜色。每个格子与若干格子绑定，若当前格子颜色改变时，与其相绑定的格子也会改变颜色。判断是否能够将所有格子改成同一颜色，若能给出任一方案。

分析 高斯消元。

259 Printed PR

题意 需要打印