Mcginn's Blog

SGU 153-252

2020/10/06

计划

计划一年内（截止 2021 年 1 月 1 日）把 SGU 500 刷完，形式以所有题目给出翻译后的简要题意和解题思路概要。

AC 代码库

题目

153 Playing with matches

题意 有 根火柴，Little 和 Petya 轮流取，每次能取 根火柴，判断先/后手必胜。

分析 当 较小时，可用 dp 计算火柴为 时状态（必胜/必败）。由于 ，每个点的状态只与前面的 9 个状态有关，从而每个状态的 SG 值最大为 10。并且根据 SG 值的定义，前面 9 个状态的 SG 值两两不同，因此 9 个状态的总数约为 ‬。通过找出循环节，即可计算 的 SG 值，从而判断胜负态。

154 Factorial

题意 求最小自然数 ，满足 有 个尾数 0。

分析 尾数 0 只与 的质因子 2 和 5 有关。求 中质因子 的个数： 显然， 5 的个数少于 2 的个数，因此尾数 0 只与 5 的个数相关。

上述公式具有非递减性质，因此可以二分计算最小自然数 。

155 Cartesian Tree

题意 给定 个 <key, value> 对，要求利用 key 值构造一棵二叉搜索树，并且满足小根堆的性质：如果 y 是 x 的父节点，则有 y.value < x.value。数据保证 key 值和 value 值两两不同。

分析 Cartisian Tree 模板题。

156 Strange Graph

题意 给 个点 条边的无向图，该图满足以下性质：

  1. 所有点的度数 。
  2. 当 时，与 相邻的两个点不相连。
  3. 当 时，存在点 ，满足：；。其中， 表示与 相邻的点集。

数据保证无重边和自环。

判断该图是否存在哈密顿回路，不存在时输出 -1；否则输出一种方案。

分析

当 时，点集 构成完全图，因此总是能构造出哈密顿路。

将点集 缩点，构造的新图中所有点的度数均为 2，问题可以转化成在新图中找出欧拉回路。

而度数均为 2 的图，只可能是多个环。因此剩余问题仅需判断新图是否联通即可。

157 Patience

题意 纸牌接龙游戏，A~K（共 13 张牌）放置到 14 个格子中，其中一个为空格且 A 固定到第 1 个格子中。在前 张牌有序的前提下，求能够将牌排好序且最后一格为空格的方案数。

移牌规则为：当空格左侧为 时，可将 直接移动到空格上。

分析 最后局面为 A23...JQK_，反向构造合法序列即可。注意正向移牌时， 的前一个数为 。因此反向构造时只有当 时，才能将 和空格交换形成新合法序列。

158 Commuter Train

题意 有长为 的公交路线。有 个乘客，乘客在坐标 处，坐标非递减排序（）。有 个站点，每个站点距离第 1 个站点的距离为 。

第 1 个站点位置 未确定，要求求出 使得每个乘客距离其最近的站点距离之和最大。

分析 在确定 后，乘客与最近站点的距离和可表示为关于 的一次函数。随着 的增大，每个乘客的最近站点会发生变化，但新的距离和仍可表示为一次函数，且在一段距离范围内该函数不会改变。

距离和函数改变点在于其中一个乘客的最近站点变化。由于乘客的最近站点随 增大的增大，因此总的变化次数为 ，且站点变化只会 +1。

159 Self-Replicating Numbers

题意 在 进制下，求 个位的数满足 。

分析 爆搜。

160 Magic Multiplying Machine

题意 给 个数 ，求最大得分 score： 并给出任意一种方案，按递增顺序输出取出值的下标。

分析 背包问题。

161

题意

分析

162 Pyramids

题意 给定四面体各边（AB, AC, AD, BC, BD, CD）长度，求体积。

分析 建个坐标系，强算各个点坐标。

163 Wise King

题意 给 个数 ，以及一个指数 。从 个数中取若干个数，使得 最大。

分析 模拟。

164 Airlines

题意 有 座城市，每两个城市都有一条航线（双向飞行），每条航线属于 家公司中的其中一家。现要求收购不超过 家公司，使得任意两个城市最多飞 3 条航线可达。

分析 根据抽屉原理，至少有一座城市所有航线关联的公司为 ，因此以城市为中心，收购该城市所有公司即可满足任意两座城市之间最多飞 2 条航线即可到达。

165 Basketball

题意 有 名球员，每名球员的身高 在 [1.95, 2.05] 范围内。现要求给球员排序，使得任意两个球员之间满足 。给出一种球员顺序或判断无解。

分析 将所有球员的身高 - 2，将球员身高分成负数和正数。从最小负数（或最大正数）开始取，根据前缀和的正负取异号身高的球员即可。由于球员身高限定在 [1.95, 2.05] 之间，因此不会违反限定条件。

166

题意

分析

167 I-country

题意 给 的网格，每个网格有个价值 。允许占领其中 个网格，要求任意两个格子之间使用上下左右四个方向中的两个方向可达，求最大的价值和并给出一种方案。

分析 最后占领的形状为菱形，使用 dp 解决上半部分（三角形）： 表示前 i 行共占领了 k 个网格且第 i 行占领的格子数为 j 的最大价值和。状态转移时保持 j 非递减即可。最后枚举中间行，将上下两个三角形合并成菱形。

168 Matrix

题意 给定 大小的矩阵 ，求矩阵 满足 分析 随便做。

169 Numbers

题意 定义 为 的所有数位之积；如果 定义 是 good number; 如果 和 都是 good number 定义 是 prefect number。给定 ，求所有 位的 perfect number 数量。

分析 显然的事实是 的个位数在 [1, 8] 范围内，如果 ，则 且 。因为 都是 good number，所以有 ，推断出 。又因为 是互质的，所以 ，进而得出 。最后 的形式。

170 Particles

题意 有两个 5000 长度的 +- 序列，每次操作可以交换相邻的 +- 粒子。求最少操作次数将序列 1 转变为序列 2。

分析 （猜测）按序匹配 -/+，计算其距离之和即可。

171 Sarov zones

题意 有 赛区，每个赛区选 个人，总共 个人，每个人有个能力值 以及权重 ，相应的赛区有强度值 。若选手能力值大于赛区强度 则晋级。求一种方案使得晋级选手的权重和最大。

分析 先选权重大的选手，选取最大 即可。

172 eXam

题意 学生从 门课中选 2 门考试，学校安排所有考试在两日内，求一种方案或判断不可能。所有学生的考试课程不同在同一天考试。

分析 二分图染色。

173

题意

分析

174 Walls

题意 给定 条线段，坐标范围 ，保证线段只在端点相交。求第几条线段加入后有封闭多边形。

分析 并查集。

175 Encoding

题意 假设有字符串 ，编码函数 如下： 其中 。

先给定 长度以及原字符串的位置 ，求编码字符串中对应原位置 的位置。

分析 判断 在左右哪个子串中，划分成子问题求解即可。

176 Flow construction

题意 有 个结点和 条管道，管道从结点 流向 且容量上限为 。化学物质从结点 1 经过若干管道流进结点 ，现要求部分管道必须流满()的前提下，该管道网络的最小流量。

分析 有源汇上下界最小流。

177 Square

题意 给 的矩形，进行 次染色，每次将一个子矩形染成黑色或白色。初始所有格子都是白色的情况下，染色完后的白色格子数。

分析 扫描线+线段树；bitset。

178 Golden chain

题意 给长为 长的金链条，Peter 每天需要支付 1 长度的金条，支付的方式有两种：一种是直接支付 1 长度金条；另一种是支付大于 1 长度的金条并使用之前支付的金条找零。零钱的组成由 Peter 指定。Peter 每次可以从长金条上切掉 1 长度的金条，将长金条切分成 3 段。现想知道最少切几次可以满足 天的支出。

分析 假设最终切出 k 个 1 长度金条，那么将剩下的 N - k 长度视为完整的金条，允许切 k 刀划分成 k + 1 段。前 k 天直接支付 1 长度即可。第 k + 1 天切出 k + 1 长度金条，找零 k 个 1 长度从而k + 2 ~ 2k + 1 天继续每天支付 1 长度。第 2k + 2 天切出 2k + 2 长度金条，兑换出之前支付的金条又开始循环（假设切不出 2k + 2 长度，那么也能找出类似的策略来满足每天 1 长度的支付）。因此切 k 次的最多能满足 天的支付需求，枚举 k 即可。

179 Brackets light

题意 给长为 10000 合法的括号序列(仅包含 '(' 和 ')'，并且字典序 '(' < ')')，求下一个字典序的合法括号序列。

分析 从后往前找第一个能 '(' 转为 ')' 的位置，之后尽量填 '(' 来保证中间不会有更小字典序且满足题意的括号序列。尽量的意思就是在该位置填 '(' 后仍有足够的位置放置 ')'，这个可以通过前缀和思想解决。

180 Inversions

题意 个数 的逆序对数。

分析 。

181 X-Sequence

题意 。

分析 找循环节。

182 Open the brackets

题意 给由 10 个变量组成的布尔表达式，运算符包括：!, (), ||, &, <=>, =>, #，变量名从 ‘a’ 到 'j' 共 10 个。要求去掉括号 () 运算符的等价布尔表达式，字符数量小于 32768。

分析 10 个布尔变量的组合数为 2^10 = 1024 种，仅使用 !, ||, & 来枚举所有情况的字符数不会超过 32768：使用 || 拼接不同组合，数量为 2 * 2^10 = 2048；! 的数量为 10 * 2^9 = 5120；& 组合 10 个变量的数量为 9 * 2^10 = 9216，变量名的数量为 10 * 2^10 = 10240。

183 Painting the balls

题意 初始有 个白球，可花费 染料将第 i 个球染成黑球。现要求在任意连续 个球中至少有 2 个黑球，求最少需要花费多少染料。

分析 表示将第 个位置染黑的前提下，前一个黑球位置 的最小代价。

状态转移方程为

185 Two shortest

题意 给 个点带边权的无向图，找出两条无共用边的两条最短路（允许有交点）。

分析 最小费用流。

187 Twist and whirl - want to cheat

题意 （splay 模板题）

188 Factory guard

题意 有 个人站在 1000 长度圆环上的整数点位置，每个人有行走速度 以及两两不同的位置 。 表示逆时针行走， 则表示顺时针行走。每个人会向对面走来的人打招呼，求 时间后每个人打招呼的次数。

分析 可以求顺时针和逆时针第一次碰面的时间，之后再相遇的时间是固定的。

todo 数据范围能否变大？

190 Dominoes

题意 的棋盘上有 个格子被移除，判断能否用 1×2 或 2×1 的多米诺覆盖所有未被移除的格子且不相交。

分析 相邻格子的 x+y 奇偶性不同，因此原问题可以转变为二分图的最大匹配。

192 RGB

题意 给 300 条线段，每条线段的颜色为 RGB 三种中的一种，任意两条线段至多一个交点。将线段投影到 X 轴，每段投影的颜色为离 X 轴最近线段的颜色。求投影后每种颜色的长度之和。

分析 求出所有交点后划分投影线段区间，每段区间取中点并判断中点所在线段的颜色。

193 Chinese Girls' Amusement

题意 有 玩丢手绢游戏，手持手绢的人将手绢传递给顺时针方向的第 个人，当手绢丢回第一个人时游戏结束。要求游戏过程中每个人都要拿过手绢，求最大满足要求的 值。

分析 假设经过 次传回第一个人，那么有 ，而要求每个人都要拿过手绢，因此 ，也就是说 ，等价于 即 和 互质。

假设 ，当 时，。所以当 是奇数时，能取到上限 。

当 时，若 ，则 ； 若 ，则 ，当 是偶数时，gcd = 1；若 ，则 ，当 是奇数时，gcd = 1。

综上， 的取值仅三种情况，分类讨论即可。

PS：上述结论可通过小数据打表辅助观察得到。

194 Reactor Cooling

题意 。

分析 无源汇上下界最大流。

195 New Year Bonus Grant

题意 有 名员工，每名员工有唯一上级（即上下级关系构成一棵树）。每名员工可以分配拨款给其中一名下属，或接受来自上级的拨款，但是不能同时分配和接受拨款。求拨款总和可能的最大值。

分析 树形 dp，每名员工根据是否分配了拨款划分成两个状态，分别记录最大拨款值即可。

196 Matrix Multiplication

题意 。

分析 模拟。

197 Nice Patterns Strike Back

题意 对长 宽 的矩形黑白染色，要求任意 2×2 的子矩形不能完全同色（即 4 白色或 4 黑色）。求合理的方案数，结果对 取模。

分析 按行染色，显然就是矩阵 + 快速幂，对于 的处理需要大数或者手动模拟整数除法。

198 Get Out!

题意 给平面上 个圆 表示岛屿，一个圆 表示船。判断这艘船能否自由航行，即不被岛屿与岛屿之间的缝隙卡住而无法走出群岛区域。

分析 将每个岛屿的半径增加 ，当两个新圆相交（不包括相切）时，船只无法通过这两个岛屿之间的缝隙。剩下的问题转化为判断一个点是否被多边形包围。

199 Beautiful People

题意 一个俱乐部中有 个人，每个人有能力值 和魅力值 。现想邀请尽可能多的人参加派对，但是当 时两个人存在矛盾。在不邀请有矛盾的两个人来派对的前提下，问最多能邀请多少人。

分析 按 排序，问题转变成最长上升子序列。

200 Cracking RSA

题意 给 个数 ，所有数的质因子是前 个质数。求 {1, 2, ..., m} 的所有子集数量，子集所对应 是完全平方数。

分析 是完全平方数，说明每个质因子的指数都是偶数，那么我们只关心 每个质因子的指数奇偶性，本质上就是解模 2 意义下的方程组解的数量（套高斯消元板子即可）。

201 Non Absorbing DFA

题意 给一个 个状态的有限状态自动机，字符集为小写字母。除了常规的状态转移外，还有转移 ：当 时正常转移；当 时不进行匹配，但是可以进入相应的状态（可以认为是等价状态的转移）。求长度为 的所有字符串中被该自动机接受的字符串数量。

分析 大数模拟。

202 The Towers of Hanoi Revisited

题意 塔汉诺塔问题，将 圆盘从第一柱塔移动到第 柱塔上，求最少的操作次数以及具体的移动方案。

分析 三塔汉诺塔推广，先将 个圆盘均摊到其他塔上，将第 个圆盘直接移动到目标塔上，然后重复操作将 个圆盘依次移动到目标塔上。

203 Hyperhuffman

题意 给 个字符在某一字符串的出现次数 ，使用哈夫曼编码字符，求编码后的字符串长度。

分析 由于 本身有序，因此对于合并得到的 可由队列维护（该队列天然也是有序的），因此总的时间复杂度是 。

204 Little Jumper

题意

分析

205 Quantization Problem

题意 给 编码表 ，需要编码 个数 ，规则：假设第 个数使用了第 列，则第 个数只能使用第 行的数来编码。求 的最小值。

分析 表示第 个数使用第 列编码的最小值。

206

207

208 Toral Tickets

题意 给 大小的橡胶板，按长边卷成圆柱体（底面周长为短边），然后再将圆柱体卷成环状（类似泳圈），每个格子可染色黑/白，求本质不同的环状物。当橡胶板为正方形时，有两种方案卷成圆柱体。

分析 当其中一条边为 1 时，本质上是项链染色问题。在本题背景下，仅需要多考虑一个方向上的旋转，但是不方便直接计算每个置换的循环数（polya 计数）。本题矩形大小较小，因此可以模拟计算每个置换的循环数。

标签 Polya

209 Areas

题意 给平面上 条直线，这些直线会划分出有限面积和无线面积的区域，求有限面积的各个区域的面积。

分析 （未代码验证）直线交求出交点坐标，处理出各个交点的相邻交点。有限面积区域都是凸包，利用这个性质可以处理所有的有限面积区域。判重可以利用连续 3 个点 index 来区分。

TAG Geometry

210 Beloved Sons

题意 有 个男生匹配 个女生，每个男生有 个喜欢的女生。当男生和其喜欢的女生配对时，产生价值 ，否则无价值。求最大的 。

分析 KM 算法。

TAG KM

211 Strange Counter

题意 实现特殊二进制的累加器，特殊处在于每位能存 [0, 2] 之间的 3 个数。进行 次操作，每次加上 ，，并要求每次修改的位数不能超过 4。数据保证总和小于 。

分析 （未代码验证）模拟，过程中如果发生连续进位，在修改位数超过 4 时，不再进位。当加法没有发生进位时，在处理之前的遗留进位。

212 Data Transmission

题意

分析

TAG Network-flow

213 Strong Defence

题意 给 个点的无向图以及起点 和终点 。将边集划分成若干不相交的集合，使得去掉任意集合后 不联通。求最大集合数量。

分析

214 Weird Dissimilarity

题意 给 200 大小的字符集 ，字符 的距离给定为 。现给出长度不超过 2000 的字符串 ，要求找出两个等长的字符串 ，满足： 是 的子序列， 是 的子序列，且 最小。

分析 最长公共子序列。

215 PL/Cool

题意 表达式解析以及计算。

分析

216 Royal Federation

题意 给 大小的树以及常数 ，要求将树分割成若干大小介于 的区域，每个区域不一定联通但需要存在一个控制点连接该区域的点，找出一个可行方案。

分析 （理论）不断将树的大小二分，即找重心。

217 Two Cylinders

题意 给三维空间中无限长的两个圆柱体，半径分别为 ，其轴线相互垂直，求交区域面积。

分析

218 Unstable Systems

题意 有 台工作站和 个程序，工作站 运行程序 出错的不稳定性为 。在一台工作站运行一个程序的前提下，求解一个分配方案最小化不稳定性的最大值。

分析 （理论）二分最大值，求解二分图的最大匹配。

219 Synchrograph

题意 给 个点, 条边的有向图，边权是不超过 的非负整数。当一个点的所有入边边权均为正数时，视为激活状态并且可以将所有入边边权减一，所有出边边权加一。现要求判断每个点是否能经过若干操作后变成激活状态。

分析 （理论）考虑最简单的情况，相邻两个点存在双向边且边权均为 0，那么这 2 个点都不可能变成激活状态。

220 Little Bishops

题意 给大小为 的国际象棋棋盘，放置 个象。象只能沿对角线方向走，步数不限但会互相攻击路径上的其它象。求放置后不会互相攻击的方案数。

分析 dp。

221 Big Bishops

题意 （与 220 Little Bishops 相同），棋盘大小为 ，求方案数。

分析

222 Little Rooks

题意

分析

223 Little Kings

题意 在 的棋盘上放置国王，国王会攻击相邻的 8 个格子。求放置 个国王且不互相攻击的方案数。

分析 状压 dp。

224 Little Queens

题意

分析

225 Little Knights

题意

分析

226 Colored graph

题意 个点， 条边的有向图，每条边为三种颜色中的一种。求点 1 到点 N 的最短距离，要求路径上不能出现连续相同颜色的边。

分析 最短路

227 The art to the broad masses!

题意 给 个半圆弧，判断交点数量是否有限，若有限输出所有交点。

分析 本质上求解两圆交点，然后仅保留半圆上的点（可以利用叉积计算）。

228 Archipelago

题意 已知正 边形的两个点，按顺时针方向标号，第 个点的坐标为