计划
计划一年内（截止 2021 年 1 月 1 日）把 SGU 500
刷完，形式以所有题目给出翻译后的简要题意和解题思路概要。
AC 代码库
题目
101 Domino
题意 多米诺牌两端标有 0 至 6 的数字，以 <a, b>
形式表示，每张牌均可翻转。要求将 100
个多米诺牌横向放置成一排，相邻的多米诺牌数字需要相同。如 <1,
2><2, 4>。判断是否存在方案，存在的话给出一种排列。
分析 将数字 0 至 6
视为图上的点，多米诺牌视为无向边，则问题转化成找出一条欧拉路径，而欧拉路径使用搜索+剪枝解决。
102 Coprimes
题意 给定 ，求 范围内与
互质的整数个数。
分析 求欧拉函数值 ， 枚举质因子求解即可。
103 Traffic Lights
题意
分析
104 Little shop of flowers
题意 给 个花瓶和
朵花，以及第 朵花放入第 个花瓶的美观度 。在不改变花的相对顺序条件下，将所有花插入到花瓶中，求最大的美观度之和且输出一种方案。
分析 经典的动态规划题目。 表示前 个花瓶中已插入前 朵花的最大美观度之和，转移方程： ---
105 Div 3
题意 给出 1, 12, 123, 1234, …, 12345678910, …
的序列，求前
个元素中是 3 的倍数的个数。
分析 打表找规律，余数序列为 100100…，即每 3
个元素中有 2 个是 3 的倍数。
106 The equaion
题意 给定二元一次方程 ，已知 和解 的范围 。数据保证所有的数字绝对值小于 ，求解 的个数。
分析 使用扩展欧几里得算法计算 的一组特解 ，通过乘上缩放因子 得到 的特解，通解为 利用 和 分别计算 的范围取交集即为解的个数。
需要注意的是：
- 或 有可能为 0
而导致方程转换为一元一次方程和常数方程；
- 系数有可能为负数，注意上取整和下取整计算。
107 987654321 problem
题意 给定数字 ，请求出数字位数为
的数 的数量，满足 的末尾为 987654321。
分析 本质上求 ，且 。因为 ，所以只有
末尾 9 个数字对结果有影响。此外，通过最后一位为 1 可推断 的个位数是 1 或 9，剩下前 8 位可在
枚举计算，最终有 8 个 9 位数字
满足条件。最后分位数
的三种情况讨论输出即可。
108 Self-numbers 2
题意 定义函数 为数字 + 数位和，如 。如果一个数 ，不存在数 使得 ，则数 为 self-number。给定 和 ，进行 次询问，第 次询问第 个 self-number，数据保证询问的
self-number 在 中。
分析
110 Dundeon
题意 给 个三维空间中的球体以及一道激光，球体表面会发射激光。求前 10
个反射激光的球体编号。数据保证激光源在球体外部。
分析
111 Very simple problem
题意 给定数 ，求最大整数
满足 。
分析
112
题意 给定数 ，求出 。
分析
113 Nearly prime numbers
题意 给定 10 个不超过
的数，判断每个数是否能拆分两个质数之积，即 ，其中 是质数。
分析 根据题意，只需找出 的一个约数 ，则另一个约数即为 ，判断两个约数是否为质数即可，总的时间复杂度
。
114 Telecasting station
题意 一维数轴上有 个城镇， 城镇坐标为 ，其人口数为
。现要修建一电视站 ，使得居民的不满程度 最小。
分析 带权中位数经典题。
115 Calendar
题意 输入 2001 年 月 日，输出该天是周几？
分析 模拟。
116 Index of super-prime
题意 定义素数序列为 ，超素数为素数序列中下标也是素数的数，例如3
的下标是 2，7 的下标是 4，因此 3 是超素数，7 不是超素数。现给定一正整数
，将
分解成最少数量的超素数之和，并将超素数从大到小输出。若 无法由超素数之和表示，则输出 0。
分析 现将
以内的素数筛选出来，进一步筛选出超素数，个数约 200
个。剩下的问题为完全背包问题，动态规划解决即可。
117 Counting
题意 给定三个整数 ，询问
次：判断给定的数 是否是 的倍数。
分析 快速幂。
118 Digital root
题意 求
的数根，其中 。
分析 数根公式： 原理 数 可表示成 因为 ，所以有如下等式： 定义数位和函数 ，则等式 2 可写成： 数根 使用
表示为： 根据等式 3 可得
119 Magic pairs
题意 给定三个正整数 ，求出所有的 对，满足：对于所有的 ，如果 能被
整除，则 也能被 整除。
分析 根据题意可得
联立公式 1 和公式 2 可得 两边同时对 取模 该等式对于所有的
均成立，即与 无关，所以 根据公式 5 可知
值等于 ，这缩小了解的搜索范围。然而这只说明了必要性，还需要进一步证明充分性。
利用扩展欧几里得定理，可求得 要使右式为
的倍数，可两边同时乘上 其中，，。
等式两侧同时除以 其中，。
上述过程可将
替换成通解形式，结论仍然成立。
则 ,
均是解，但是可能存在重复。
120 Archipelago
题意 给出正 边形的第
个点坐标和第
个点坐标，按序求出所有点的坐标。
分析
121 Bridges painting
题意 给点数为 的无向图，给图中的每条边进行黑白染色，要求当顶点度数大于 1
时，该顶点至少与一条白边和一条黑边相连接。
分析
122 The book
题意 给点数为 的无向图，每个点至少与 个点相连，求一条哈密顿回路。
分析
123 The sum
题意 求前 40 个斐波那契值的和。
分析 模拟。
124 Broken line
题意 给一边数为 的多边形，以及一个二维坐标点 ，判断该点在多边形的内部、外部亦或边界上。数据保证多边形顶点坐标为整数， 也为整数。
分析
125 Shtirlits
题意
分析
126 Boxes
题意 有两个盒子，两个盒子分别有
个球，在移动球时要放入盒中已有的等量的球，即操作一次后两个盒子的球数可能为
或
两种情况。求最少的操作次数使得一个盒子为空。数据保证 。
分析 考虑反向操作，记 ，则判断状态 是否能导出 。逆操作从状态
可推出 。
因为总和固定为 ，对于一个状态可以用两者的最小值表示，则状态有
可以发现有效状态构成了一棵高度最大为
的二叉树。反过来考虑，对于任一有效状态转移到根状态 的操作数不超过 。因此对于初始状态 在 32 步内判断是否根状态 即可。
127 Telephone directory
题意 给 个号码，电话本每页能记录
个电话号码，要求号码按序记录在电话本上，并且首位不同的号码记录记录在不同页，要求计算记录号码的页数。
分析 模拟。
128 Snake
题意 给定 个整点 ，要求构造满足以下条件的多边形：
- 个点均为多边形的顶点；
- 每个顶点均构成一个直角；
- 多边形的边与坐标轴平行；
- 多边形无自交；
- 多边形的周长最短。
如果能构成多边形，则输出多边形的周长，否则输出 0。
分析 考虑
坐标相同的若干个点 。因为每个点连接一水平线段和一竖直线段，所以第一个点
只能与 相连， 与 相连，以此类推。这要求 必须是偶数，否则无解。
上述步骤完成后，需要判断所有点是否联通以及是否存在线段相交。对于线段相交问题，可以使用扫描线+线段树/树状数组解决。
129 Inheritance
题意 给有 个点的凸包，以及 条线段，判断每条线段被凸包包含的长度。
分析
130 Circle
题意 圆上有
个点，其中 。现要求将点用线连接起来，使得：每个点都有线连接；圆被划分的区域数量最少，求不同的划分方案数以及最小区域数。
分析 显然，最少区域为 ，每条连线不能有交点，根据该性质则连一条边后就生成两个子问题，于是使用动态规划解决。 表示
个点划分成最少区域的方案数，枚举该连线的左右两部分的规模进行转移：
131 Hardwood floor
题意 有一个 的网格，现使用 1×2 和 2×2
的方块填满网格（方块可旋转放置），求铺满网格的方案数，其中 。
分析 状压 DP。
132 Another Chocolate Maniac
题意 给定 的网格，使用 1×2 和 2×1 的方块填充，其中 。网格部分格子不能与方块重叠，求使用最少数量的方块填充网格，使得网格不存在相邻的空白格子，即不能再放置方块。
分析 轮廓线 DP。对于每个格子有 3
种状态：可放置、不可放置，必须放置。假设当前格子为 且为空，上方的格子 也为空，此时有两种方案：1. 在
和 中放方块；2. 不放方块，但是 和 必须放置方块。因此每个格子有 3
种状态，总的时间复杂度为 。
133 Border
题意 给 个一维区间 。若一个区间 被另一个区间 完全覆盖，即 且 ，则去除该区间。求被去除区间的数量。
分析 按
为第一关键字，
为第二关键字排序，按
划分阶段，实时维护最大 ，若
则去除当前区间。
134 Centroid
题意 求树的重心。
分析 遍历一遍树即可。
135 Drawing Lines
题意 在无限平面上画 条直线，求平面划分的区域数。
分析 画图找规律，直线两两相交，结论为 。
136 Erasing Edges
题意 给定 点多边形的边的中点 ，判断是否能够根据边中点复原多边形顶点，如果能复原按序给出顶点坐标。
分析
138 Games of Chess
题意 有
个人轮流下象棋，每次两个人下棋并且胜者可继续下棋直至输棋。现已知每个人下棋的总局数，要求构造符合规则的一种方案，其胜者在第一个。数据保证有解，且所有人的总局数小于
。
分析
构造。总棋局数为每个人的总局数之和除以二。然后按每个人的局数从大到小排序，假设顺序为
，其中
表示 的棋局数。构造方案为 ，优先排列胜者，最后一局输给下一个胜者完成衔接，剩余的棋手则安排在败者局中。
139 Help Needed!
题意 十五数码问题。
分析
140 Integer Sequences
题意 给定长为 的序列 ，判断是否存在序列
满足 其中， 。
分析 扩展欧几里得算法。
141 Jumping Joe
题意
一只青蛙在一维数轴的整数点上跳，每次能够向负轴或正轴方向跳 或
个整数距离，求能否刚好 次跳到整点
位置上。如果能到达位置 ，给出一种方案 ， 表示往正轴方向跳 ， 则表示往负轴方向跳 。
分析 扩展欧几里得算法。
142 Keyword
题意 给长为 的字符串，该串只由 和
构成，求最短的不是该串子串的字符串，并给出一个解。如 的子串有 ，因此最短非子串长度为
2，一种解为 。
分析 因为 ，所以答案不超过
19，枚举长度并枚举该长度所有子串即可。后缀数组和后缀自动机也可以做。
145 Long Live the Queen
题意 给定有 的树，每个点的权值为 ，求一棵子树使得权重和最大。
分析 树 DP。
144 Meeting
题意 两个人约在
时间内碰面，约定先到的人等另一个人的时间不超过
分钟，求两个人能碰面的概率。
分析 。
148 B-Station
题意 背景中有 级蓄水池，每级蓄水池目前有 重的水量，最大蓄水量为
。释放第 级蓄水池的代价为 ，且第 级的水会流入第
级的水池中。如果水池中的水超过了容量，则水池中的所有水会继续流入下一级。现在
kbfz 想要释放第
级的水，求最小代价以及一种方案。
分析 为了释放第 级的水，一种是直接花费
的代价，另一种则是释放前面的水池，通过超容量来释放。假设第一个花费代价
释放水池 ，则下一个必须花费代价的水池满足： 即堆积的总水量不超过容量的第一个位置 ，该位置必须花费 的代价释放水。
使用前缀和 表示，则有 当固定第一个花钱释放的水池 后，在 中必须花钱的水池满足 ，其中
是定值。之后使用数据结构维护 所对应的代价即可。
149 Computer Network
题意 给 个点的树，求每个点
到其他点的最远距离 。
分析
每个点到树直径的端点的距离之一等于最远距离。
150 Mr. Beetle II
题意 给定起点 和终点 ，求起点和终点构成的线段穿过的第
个格子左下角坐标，只经过角点不算穿越该格子。每个格子可使用
表示，其中左下角点坐标为 。
分析
假设已知当前穿越的格子，则下一个可能穿越的格子为前进方向的相邻 3
个格子。线段穿越格子的充要条件：线段和格子的其中一条对角线严格相交。
!!! 151 Construct a triangle
题意 对于三角形 ABC，已知长度 ，其中 M 是线段 BC
的中点。求三个顶点的坐标，满足上述长度关系。
这道题数据有问题，允许三点共线。
分析 固定点 A 在原点，点 B 为 ，设点 C 坐标为 。根据长度关系可得： 利用这个等式可以很容易求出一组解，注意判断方程有解即可。
152 Making round
题意 已知 候选人的选票数 ，现要求将选票转换成整数的百分比形式，
使得总和为
100。对于转换后小数部分，每个候选人的选票可向上或向下取整（取整相互独立）。求一种方案，或判断无法转换。
分析 模拟。
xxx
题意
分析
