SGU 153-252

 2020/10/06 

计划

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

题目

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，问题可以转化成在新图中找出欧拉回路。

而度数均为 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

题意已知正边形的两个点，按顺时针方向标号，第个点的坐标为，第个点的坐标为。求正边形的所有顶点坐标，按标号顺序输出。

分析计算几何。

229 Divide and conquer

题意

分析

230 Weighings

题意有个硬币，第个硬币重量为克，每个硬币放入无差别的盒子中。目前已知个重量关系，表示盒子的重量大于盒子的重量。求每个硬币放入的盒子编号，输出任一种方案，若无解输出 "No solution"。

分析拓扑序。

231 Prime Sum

题意求范围内的质数对，满足也是质数的数量。

分析除 2 外，质数都是奇数。而奇数+奇数=偶数，因此问题转化为质数对的方案数。

232 Infinite Fraction

题意给长为的数字串以及常数，构造无限循环小数，其中，其中表示第几个小数。在所有可能的小数中找出最大的小数。

分析每个无限循环小数的重复部分长度是一致的，因为步长和环长是固定的，并且长度为，因此比较大小时仅需要比较长即可。到这步时比较容易想到用后缀数组处理，将前个的重复部分拼接起来比较各个的序即可。但是这种做法空间复杂度为，不适用于很大的情况。考虑的重复部分包含了等部分，复用这部分数据仅需要将的重复部分再复制一份即可，总共需要额外的空间（这里表示循环个数）。

233 The Greatest Angle

题意个测试，每次测试给一个圆以及点，点，在圆上找到一点 C 使得角 ACB 最大。若有多解输出任一解。

分析

234 Black-White King Strikes Back

题意给大小为的棋盘，需要在棋盘上放置卫兵，但是卫兵会攻击上下左右的所有生物，即包括其他卫兵。在有些格子不能放置卫兵的前提下，求最多能放置多少个卫兵使得卫兵不会互相攻击。

分析二分图的最大独立集。假设每个格子的坐标为，则根据的奇偶性可划分出 2 个点集，并且冲突仅出现在两个点集之间，点集内部没有冲突。将冲突表示成边的话，问题就转换成找出二分图的最大独立集。

Konig定理

假设二分图的最大匹配数为 M，最小覆盖数为 m，则有:

m ≤ M。令最大匹配的点集为 C，二分图为 <V, E>。假设有 m > M，所以存在点 a, b ∉ C 且 (a, b) ∈E，这与最大匹配的定义矛盾，因此假设不成立。
m ≥ M。在最大匹配中，每对匹配没有公共点，因此覆盖匹配边至少需要 M 个点，因此有 m ≥ M。

综上二分图有：最小覆盖数 = 最大匹配数。

二分图最小点覆盖的构造方案

基于二分图中最小点覆盖数等于最大匹配数的结论来构造方案，首先有两个认知：

每对匹配有且仅有一个点在方案中；
没有配对且有连边的点，由有匹配的点来覆盖其之间的连边。

那么根据上面的认知，则有构造方案：

选取二分图左侧无匹配的所有点，根据认知 2 这些点必须由右侧在匹配中的点来覆盖（理论上，此时无匹配的左侧点也找不到无匹配的右侧点，否则就违反了最大匹配的定义）。
在选取了部分右匹配点进方案后，根据认知 1，相应的左侧匹配点就不能选择了。之后，将这些不能选择的左侧点视为无匹配点，寻找其他右匹配点来覆盖非匹配边。
在步骤 1,2 中未访问过的点，只剩匹配点之间自己的连边，可以任选一点。

步骤 1,2 本质上是在寻找增广路，并且覆盖了左侧无匹配点与右侧之间的连边。在最大匹配的前提下，步骤 1,2 找不到新匹配，因此增广路的终点必然是左侧。

右侧无匹配点与左侧之间的连边情况也是类似的，仿照步骤 1,2 即可。显然，处理左侧无匹配点和右侧无匹配点不存在冲突，因此可以在一次 BFS 中处理。

235 The Queen

题意在大小为的国际象棋棋盘上，有且仅有一个白棋皇后以及其他种类的白棋和黑棋。白皇后只可以攻击黑棋，在仅有白皇后可以移动的前提下，求白皇后在步后可以到达哪些位置。

分析模拟。

236 Greedy Path

题意给个点，条边的带权有向图，每条边有权值和。求一个环使得最大。

分析

237 Galaxy X: Episode I - Masters of Mind

题意给定长度为 255 且包含 '*','?','!' 的正则表达式，基于该正则构造长度和字典序都是最小的回文串。各符号含义：'*' 匹配任意长度的任意字符；'?' 恰好匹配一个字符；'!' 恰好匹配三个字符。

分析 DP；'!'替换成 3 个 '?'。

238 Uncle Vasya and Bags for Potatoes

题意（将题目中的地板抽象成一个点）给一棵大小为的树，每次操作将根节点的一个儿子节点替换成根。在给定初始状态后，经过若干次操作可以得到多少种不同的状态。

分析每种状态根据只与树根编号有关，因此答案为（特判时答案为 1）。

239 Minesweeper

题意在的扫雷游戏中，地雷只会出现在第 1 列，已知第 2 列数字的前提下，求所有可能埋雷的方案数。

分析 dp(i, mask)。

240 Runaway

题意给个点，条边的无向图，每条边有初始温度，每秒温度增长值，通过该边的时间。角色最高能忍受的温度为，已知当前角色位置为，需要从个出口中离开地图，希望最小化路径中的最高温度。

分析 dp。

241 The United Fields of Chessboardia

题意给大小分别为和的棋盘，第 2 个棋盘的左下角与第 1 个棋盘的右上角重叠一部分。求放置个车的方案数，满足任意 2 个车不互相攻击。

分析状压 dp。

242 Student's Morning

题意有个学生以及所学校。需要去访问所有学校，但每所学校至少需要 2 个学生，并且每个学生都有自己的学校偏好列表，求解是否存在一种方案，若有则输出一种。

分析最大流可解。

243 Broken Chessboard

题意大小为的正方形棋盘碎成若干个连通块，这些连通块散落后可能会发生翻转 90/180/270 的情况。现要求复原该正方形，输出任一方案。

分析搜索+剪枝。

244 Height, Bisector and Median

题意给 △ABC 的高 AH, 角平分线 AD 以及中位线 AM（所有长度不超过 100）。判断是否能构造出 △ABC，若能输出任一方案。

分析

245 Black-White Army

题意给大小为的国际象棋棋盘，主角有且仅有一个棋子（可从 pawn, rook, knight, bishop 和 king 中选一类型），对手棋子散布在棋盘上不会主动移动但如果可以就会攻击主角的棋子。主角若击杀对方棋子，可根据棋子类型获得不同的分数。现给定双方棋子的位置，求主角最多能获得多少分数。

分析因为棋盘上的路径是可逆的，那么主角击杀棋子的顺序是无关的，即可贪心地击杀对方棋子。在击杀对面棋子后，一些原本不可达的位置可能就可以在不被对方攻击的情况下到达了，这个更新需要遍历整个棋盘，可以 lazy update。

246 Black & White

题意给长度为长度由黑色/白色珠子构成的项链，其中有个黑色珠子。如果项链能找到 2 个黑色珠子将项链分成两部分且其中一部分长度为，则定义为好项链。找出最小的使得所有项链都是好项链。

分析记项链长度，将问题转化成最多能放置多少个黑色珠子使得两两之间的长度不为。考虑最坏的情况，位置放置黑珠，位置放置白珠，位置放置黑珠，以此类推。最后会回到位置，即，到这步可以解出，即在这个循环中有个位置，按照黑色交替染色最多可以放置。因为项链长度为，这样的循环共有个，整个项链最多可以放置个黑子珠子满足两两之间长度不为。

247 Difficult Choice

题意次测试，每个测试给一个奇质数，需要从中选取个数满足和是的倍数，求方案数。

分析将数分为集合和集合。假设从中取，从中取，满足且，则有推论：记，有 $，$ ，即在有一组合法解的前提下可构造不出个非法解。

首先证明序列和序列不一致，使用反证法证明：，使得。因为是的一个置换，可以计算出每个循环的长度为。在没有全选集合 的情况下有，故假设不成立从而有和不一致。

因为有且是质数，所以，则。

综上，在所有选取方案（包括非法）中，每组有一组解，因此方案数为，常数 2 表示全选 A 和全选 B。

248 Integer Linear Programming

题意整形线性规划问题，给定个变量，最小化目标函数为，约束为，其中。求解非负整数解。

分析将变量视为空间为价值为 1 的物品，问题转化成完全背包问题。

249 Matrix

题意使用的所有数构造大小的矩阵，满足相邻格子中的数在二进制表示下仅一位不同。矩阵是环形的，即第一列和最后一列相邻，第一行和最后一行相邻。

分析将二进制位拆分成两部分，第一部分占位，第二部分占位。构造思想：同一行的数前位相同，通过后位造环；不同行的数后位按列一一对应，仅前位中有一位不同，即通过前位构造行之间的环。因为第一部分和第二部分是相互独立的，所以本质上是求的环构造方案。

使用数学归纳法构造方案：

当时，有 00, 01, 11, 10。
当时，假设的序列为，基于构造，新构造的两个数仅一位不同，并且可以构造出新序列。显然，新序列也是符合题意的环。

250 Constructive Plan

题意给大小的 01 矩阵，求一个由全 0 构成的 C 字形最大面积。C 字形由三个矩形构成，左边界在同一列，中间矩形的宽度严格小于上下两个矩形的宽度。

分析枚举 C 字形的上下边界，处理出三个矩形的公共矩形，之后需要考虑 2 种情况。一种是不向外扩展，则在公共矩形右边界所在列中部挖一个孔，形成 C 字形。另一种是向右侧扩展，因为上下矩形两者宽度互不影响，因此只需要预处理以给定矩形左上角顶点的最大矩形和以给定矩形左下角顶点的最大矩形，然后尝试扩展形成更大的 C 字形。

251 Polymania

题意已知有个二维平面上的点，每个点有正整数权重且。要求任意 3 个点构成三角形面积等于权重之和，若有解输出所有点坐标。