Mcginn's Blog

SGU 153-252

字数统计: 5.1k阅读时长: 20 min
2020/04/15 Share

计划

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

AC 代码库

题目

153 Playing with matches

题意 有 $1\le N \le 10^9$ 根火柴,Little 和 Petya 轮流取,每次能取 $1, P_1, P_2, \dots , P_m(2\le P_i \le 9, 0\le m \le 8)$ 根火柴,判断先/后手必胜。

分析 当 $N$ 较小时,可用 dp 计算火柴为 $n$ 时状态(必胜/必败)。由于 $P_i\le 9$,每个点的状态只与前面的 9 个状态有关,从而每个状态的 SG 值最大为 10。并且根据 SG 值的定义,前面 9 个状态的 SG 值两两不同,因此 9 个状态的总数约为 $10!=3,628,800‬$。通过找出循环节,即可计算 $N$ 的 SG 值,从而判断胜负态。


154 Factorial

题意 求最小自然数 $N$,满足 $N!$ 有 $0 \le Q \le 10^8$ 个尾数 0。

分析 尾数 0 只与 $N!$ 的质因子 2 和 5 有关。求 $N!$ 中质因子 $p$ 的个数:

显然, 5 的个数少于 2 的个数,因此尾数 0 只与 5 的个数相关。

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


155 Cartesian Tree

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

分析 Cartisian Tree 模板题。


156 Strange Graph

题意 给 $3\le N \le 10^4$ 个点 $M\le 10^5$ 条边的无向图,该图满足以下性质:

  1. 所有点的度数 $deg(v)\ge 2$。
  2. 当 $deg(v)=2$ 时,与 $v$ 相邻的两个点不相连。
  3. 当 $deg(v)>2$ 时,存在点 $u\in N(v)$,满足:$deg(u)=2$;$\forall w_1, w_2\in N(v), (w_1, w_2)\in E$。其中,$N(v)$ 表示与 $v$ 相邻的点集。

数据保证无重边和自环。

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

分析

当 $deg(v)>2$ 时,点集 $N(v)/u$ 构成完全图,因此总是能构造出哈密顿路

将点集 $N(v)/u$ 缩点,构造的新图中所有点的度数均为 2,问题可以转化成在新图中找出欧拉回路

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


157 Patience

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

移牌规则为:当空格左侧为 $x$ 时,可将 $x+1$ 直接移动到空格上。

分析 最后局面为 A23…JQK_,反向构造合法序列即可。注意正向移牌时,$x+1$ 的前一个数为 $x$。因此反向构造时只有当 $a[i+1]=a[i]+1$ 时,才能将 $a[i+1]$ 和空格交换形成新合法序列。


158 Commuter Train

题意 有长为 $0<L\le 5000$ 的公交路线。有 $0<M\le 300$ 个乘客,乘客在坐标 $P_i$ 处,坐标非递减排序($0\le P_1 \le \dots \le P_M \le L$)。有 $0< N\le 300$ 个站点,每个站点距离第 1 个站点的距离为 $D_i(0=D_1<D_2<\dots < D_N\le L)$。

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

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

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


159 Self-Replicating Numbers

题意 在 $2\le b \le 36$ 进制下,求 $1\le n\le 2000$ 个位的数满足 $x^2\equiv x\pmod {b^n}$。

分析 爆搜。


160 Magic Multiplying Machine

题意 给 $1\le N \le 10^4$ 个数 $1\le a_i\le M(2\le M \le 10^3)$,求最大得分 score:

并给出任意一种方案,按递增顺序输出取出值的下标。

分析 背包问题。


161

题意

分析


162 Pyramids

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

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


163 Wise King

题意 给 $1 \le N\le 100$ 个数 $a_i, |a_i|\le 3$,以及一个指数 $0<E\le 3$。从 $N$ 个数中取若干个数,使得 $\sum a_i ^E$ 最大。

分析 模拟。


164 Airlines

题意 有 $1\le N\le 200$ 座城市,每两个城市都有一条航线(双向飞行),每条航线属于 $M$ 家公司中的其中一家。现要求收购不超过 $\lfloor \frac{M+1}2\rfloor$ 家公司,使得任意两个城市最多飞 3 条航线可达。

分析 根据抽屉原理,至少有一座城市所有航线关联的公司为 $\lfloor\frac {2M}N \rfloor \le \lfloor \frac{M+1}2\rfloor$,因此以城市为中心,收购该城市所有公司即可满足任意两座城市之间最多飞 2 条航线即可到达。


165 Basketball

题意 有 $1\le N \le 6000$ 名球员,每名球员的身高 $h_i$ 在 [1.95, 2.05] 范围内。现要求给球员排序,使得任意两个球员之间满足 $|\sum_{i=1}^{K} (h_i - 2)| \le 0.1$。给出一种球员顺序或判断无解。

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


166

题意

分析


167 I-country

题意 给 $N\times M(1\le N, M\le 15)$ 的网格,每个网格有个价值 $0 \le V_{ij}\le 10^3 $ 。允许占领其中 $K$ 个网格,要求任意两个格子之间使用上下左右四个方向中的两个方向可达,求最大的价值和并给出一种方案。

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


168 Matrix

题意 给定 $N\times M(1\le N, M\le 1000)$ 大小的矩阵 $A$,求矩阵 $B$ 满足

分析 随便做。


169 Numbers

题意 定义 $P(n)$ 为 $n$ 的所有数位之积;如果 $P(n)\neq 0 \and P(n)|n$ 定义 $n$ 是 good number; 如果 $n$ 和 $n+1$ 都是 good number 定义 $n$ 是 prefect number。给定 $1\le K \le 10^6$,求所有 $K$ 位的 perfect number 数量。

分析 显然的事实是 $n$ 的个位数在 [1, 8] 范围内,如果 $n = 10x+y$,则 $n+1=10x+y$ 且 $P(n)=y\times P(x), P(n+1)=(y+1)\times P(x)$。因为 $n,n+1$ 都是 good number,所以有 $P(n)|n\and P(n+1)|(n+1)$,推断出 $P(x)|n\and P(x)|(n+1)$。又因为 $n,n+1$ 是互质的,所以 $\gcd(n, n+1)=1$,进而得出 $P(x)=1$。最后 $n=11\dots1w$ 的形式。


170 Particles

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

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


171 Sarov zones

题意 有 $1\le K\le 100$ 赛区,每个赛区选 $N_i$ 个人,总共 $\sum N_i$ 个人,每个人有个能力值 $P_i$ 以及权重 $W_i$,相应的赛区有强度值 $Q_i$。若选手能力值大于赛区强度 $P_i > Q_j$ 则晋级。求一种方案使得晋级选手的权重和最大。

分析 先选权重大的选手,选取最大 $Q_j < P_i$ 即可。


172 eXam

题意 $1\le M \le 30000$ 学生从 $1\le N \le 200$ 门课中选 2 门考试,学校安排所有考试在两日内,求一种方案或判断不可能。所有学生的考试课程不同在同一天考试。

分析 二分图染色。


173

题意

分析


174 Walls

题意 给定 $1\le M \le 200000$ 条线段,坐标范围 $|x_i|,|y_i|\le 10^9$,保证线段只在端点相交。求第几条线段加入后有封闭多边形。

分析 并查集。


175 Encoding

题意 假设有字符串 $W=w_1w_2\dots w_n$,编码函数 $phi(W)$ 如下:

其中 $K = \lfloor \frac {len(W)}2 \rfloor$。

先给定 $1\le len(W)\le 10^9$ 长度以及原字符串的位置 $q$,求编码字符串中对应原位置 $q$ 的位置。

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


176 Flow construction

题意 有 $1\le N\le 100$ 个结点和 $M$ 条管道,管道从结点 $U_i$ 流向 $V_i$ 且容量上限为 $Z_i$。化学物质从结点 1 经过若干管道流进结点 $N$,现要求部分管道必须流满($C_i = 1$)的前提下,该管道网络的最小流量。

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


177 Square

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

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


178 Golden chain

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

分析 假设最终切出 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 + (k + 1) + 2(k + 1) + … + 2^k(k+1)=2^{k+1}(k+1)-1$ 天的支付需求,枚举 k 即可。


179 Brackets light

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

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


180 Inversions

题意 $1\le N\le 65537$ 个数 $0\le A_i\le 10^9$ 的逆序对数。

分析


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

题意 初始有 $2\le N\le 10^4$ 个白球,可花费 $1\le C_i\le 10^4$ 染料将第 i 个球染成黑球。现要求在任意连续 $2\le M\le 100$ 个球中至少有 2 个黑球,求最少需要花费多少染料。

分析 $dp(i, j)$ 表示将第 $i$ 个位置染黑的前提下,前一个黑球位置 $p \ge i-j$ 的最小代价。

状态转移方程为


185 Two shortest

题意 给 $2\le N\le 400$ 个点带边权的无向图,找出两条无共用边的两条最短路(允许有交点)。

分析 最小费用流。


187 Twist and whirl - want to cheat

题意 (splay 模板题)


188 Factory guard

题意 有 $1\le N\le 20$ 个人站在 1000 长度圆环上的整数点位置,每个人有行走速度 $-100\le V_i \le 100$ 以及两两不同的位置 $0\le L_i\le 999$。$V_i \lt 0$ 表示逆时针行走,$V_i \gt 0$ 则表示顺时针行走。每个人会向对面走来的人打招呼,求 $1\le T\le 50$ 时间后每个人打招呼的次数。

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

todo 数据范围能否变大?


190 Dominoes

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

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


192 RGB

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

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


193 Chinese Girls’ Amusement

题意 有 $3\le N\le 10^{2000}$ 玩丢手绢游戏,手持手绢的人将手绢传递给顺时针方向的第 $1\le K\le \lfloor\frac N2\rfloor$ 个人,当手绢丢回第一个人时游戏结束。要求游戏过程中每个人都要拿过手绢,求最大满足要求的 $K$ 值。

分析 假设经过 $p$ 次传回第一个人,那么有 $pK \mod N = 0$,而要求每个人都要拿过手绢,因此 $p=N$,也就是说 $NK = lcm(K, N)$,等价于 $\gcd (K, N) = 1$ 即 $K$ 和 $N$ 互质。

假设 $N= 2n+1$,当 $K=\lfloor\frac N2\rfloor=n$ 时,$\gcd (K, N)=\gcd(n, 2n+1)=\gcd(n, n+1)=1$。所以当 $N$ 是奇数时,能取到上限 $\lfloor\frac N2\rfloor$。

当 $N=2n$ 时,若 $K = \lfloor\frac N2\rfloor=n$,则 $\gcd(K, N) = \gcd(n, 2n) = n > 1$; 若 $K=n-1$,则 $\gcd(K, N)=\gcd(n-1, 2n)=\gcd(n-1, 2)$,当 $n$ 是偶数时,gcd = 1;若 $K=n-2$,则 $\gcd(K, N)=\gcd(n-2, 2n)=\gcd(n-2, 4)$,当 $n$ 是奇数时,gcd = 1。

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

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


194 Reactor Cooling

题意

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


195 New Year Bonus Grant

题意 有 $2\le N\le 5×10^5$ 名员工,每名员工有唯一上级(即上下级关系构成一棵树)。每名员工可以分配拨款给其中一名下属,或接受来自上级的拨款,但是不能同时分配和接受拨款。求拨款总和可能的最大值。

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


196 Matrix Multiplication

题意

分析 模拟。


197 Nice Patterns Strike Back

题意 对长 $1\le N\le 10^{100}$ 宽 $1\le M\le 5$ 的矩形黑白染色,要求任意 2×2 的子矩形不能完全同色(即 4 白色或 4 黑色)。求合理的方案数,结果对 $1\le P\le 10000$ 取模。

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


198 Get Out!

题意 给平面上 $1\le N\le 300$ 个圆 $(x_i, y_i, r_i)$ 表示岛屿,一个圆 $(X, Y,R)$ 表示船。判断这艘船能否自由航行,即不被岛屿与岛屿之间的缝隙卡住而无法走出群岛区域。

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


199 Beautiful People

题意 一个俱乐部中有 $2\le N\le 10^5$ 个人,每个人有能力值 $1\le S_i\le 10^9$ 和魅力值 $1\le B_i\le 10^9$。现想邀请尽可能多的人参加派对,但是当 $S_i\le S_j\and B_i\ge B_j$ 时两个人存在矛盾。在不邀请有矛盾的两个人来派对的前提下,问最多能邀请多少人。

分析 按 $pair(S_i, B_i)$ 排序,问题转变成最长上升子序列。


200 Cracking RSA

题意 给 $1\le m\le 100$ 个数 $1\le b_i\le 10^9$,所有数的质因子是前 $1\le t\le 100$ 个质数。求 {1, 2, …, m} 的所有子集数量,子集所对应 $\prod b_i$ 是完全平方数。

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


201 Non Absorbing DFA

题意 给一个 $1\le K\le 1000$ 个状态的有限状态自动机,字符集为小写字母。除了常规的状态转移外,还有转移 $X(u, c) $:当 $X(u, c)=0$ 时正常转移;当 $X(u, c)=1$ 时不进行匹配,但是可以进入相应的状态(可以认为是等价状态的转移)。求长度为 $1\le N\le 60$ 的所有字符串中被该自动机接受的字符串数量。

分析 大数模拟。


202 The Towers of Hanoi Revisited

题意 $4\le M\le 65$ 塔汉诺塔问题,将 $1\le N\le 64$ 圆盘从第一柱塔移动到第 $M$ 柱塔上,求最少的操作次数以及具体的移动方案。

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


203 Hyperhuffman

题意 给 $2\le N\le 5×10^5$ 个字符在某一字符串的出现次数 $1\le P_i\le 10^9, P_i\le P_{i+1}$,使用哈夫曼编码字符,求编码后的字符串长度。

分析 由于 $P_i$ 本身有序,因此对于合并得到的 $P_i+P_j$ 可由队列维护(该队列天然也是有序的),因此总的时间复杂度是 $O(N)$。


204 Little Jumper

题意

分析


205 Quantization Problem

题意 给 $m×s,1\le m\le s\le 128$ 编码表 $A_{ij}$,需要编码 $1\le n\le 1000$ 个数 $1\le x_i\le 10^6$,规则:假设第 $i$ 个数使用了第 $k_i$ 列,则第 $i+1$ 个数只能使用第 $k_i\mod m$ 行的数来编码。求 $\sum|x_i-A_{k_{i-1}\mod m, k_i}|$ 的最小值。

分析 $dp(i, j)$ 表示第 $i$ 个数使用第 $j=k_i\mod m$ 列编码的最小值。

CATALOG
  1. 1. 计划
  2. 2. 题目