Mcginn's Blog

SGU 100~152

字数统计: 4.8k阅读时长: 19 min
2019/11/15 Share

计划

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

AC 代码库

题目

101 Domino

题意 多米诺牌两端标有 0 至 6 的数字,以 形式表示,每张牌均可翻转。要求将 100 个多米诺牌横向放置成一排,相邻的多米诺牌数字需要相同。如 <1, 2><2, 4>。判断是否存在方案,存在的话给出一种排列。

分析 将数字 0 至 6 视为图上的点,多米诺牌视为无向边,则问题转化成找出一条欧拉路径,而欧拉路径使用搜索+剪枝解决。


102 Coprimes

题意 给定 $1\le N \le 10^4$,求 $[1, N)$ 范围内与 $N$ 互质的整数个数。

分析 求欧拉函数值 $φ(N)=N\prod (1 - \frac {1} {p_i})$,$O(\sqrt N)$ 枚举质因子求解即可。


103 Traffic Lights

题意

分析


104 Little shop of flowers

题意 给 $1\le V \le 100$ 个花瓶和 $1\le F\le 100$ 朵花,以及第 $i$ 朵花放入第 $j$ 个花瓶的美观度 $A_{ij}$。在不改变花的相对顺序条件下,将所有花插入到花瓶中,求最大的美观度之和且输出一种方案。

分析 经典的动态规划题目。$dp(i, j)$ 表示前 $i$ 个花瓶中已插入前 $j$ 朵花的最大美观度之和,转移方程:


105 Div 3

题意 给出 1, 12, 123, 1234, …, 12345678910, … 的序列,求前 $1\le N \le 2^{31}-1$ 个元素中是 3 的倍数的个数。

分析 打表找规律,余数序列为 100100…,即每 3 个元素中有 2 个是 3 的倍数。


106 The equaion

题意 给定二元一次方程 $ax+by+c=0$,已知 $a,b,c$ 和解 $(x, y)$ 的范围 $x \in [x_1, x_2],y\in [y_1, y_2] $。数据保证所有的数字绝对值小于 $10^8$,求解 $(x, y)$ 的个数。

分析 使用扩展欧几里得算法计算 $ax_0+by_0=\gcd(a,b)$ 的一组特解 $(x_0, y_0)$,通过乘上缩放因子 $-c/\gcd(a,b)$ 得到 $ax_0+by_0+c=0$ 的特解,通解为

利用 $[x_1, x_2]$ 和 $[y_1, y_2]$ 分别计算 $k$ 的范围取交集即为解的个数。

需要注意的是:

  1. $a$ 或 $b$ 有可能为 0 而导致方程转换为一元一次方程和常数方程;
  2. 系数有可能为负数,注意上取整和下取整计算。

107 987654321 problem

题意 给定数字 $1\le N \le 10^6$,请求出数字位数为 $N$ 的数 $x$ 的数量,满足 $x^2$ 的末尾为 987654321。

分析 本质上求 $x^2\mod 10^9=987654321$,且 $x=v\times 10^9+m$。因为 $v\times 10^9 \equiv 0\pmod {10^9}$,所以只有 $x$ 末尾 9 个数字对结果有影响。此外,通过最后一位为 1 可推断 $x$ 的个位数是 1 或 9,剩下前 8 位可在 $10^8$ 枚举计算,最终有 8 个 9 位数字 $m$ 满足条件。最后分位数 $N<9,n=9,n>9$ 的三种情况讨论输出即可。


108 Self-numbers 2

题意 定义函数 $d(n)$ 为数字 $n$ + 数位和,如 $d(123)=123+1+2+3$。如果一个数 $x$,不存在数 $n$ 使得 $x=d(n)$,则数 $x$ 为 self-number。给定 $1\le N\le 10^7$ 和 $1\le K\le 5000$,进行 $K$ 次询问,第 $i$ 次询问第 $s_i$ 个 self-number,数据保证询问的 self-number 在 $[1,N]$ 中。

分析


110 Dundeon

题意 给 $1\le N\le 50$ 个三维空间中的球体以及一道激光,球体表面会发射激光。求前 10 个反射激光的球体编号。数据保证激光源在球体外部。

分析


111 Very simple problem

题意 给定数 $1\le X\le 10^{1000}$,求最大整数 $n$ 满足 $n^2\le X$。

分析


112 $a^b-b^a$

题意 给定数 $1\le a, b\le 100$,求出 $a^b-b^a$。

分析


113 Nearly prime numbers

题意 给定 10 个不超过 $10^9$ 的数,判断每个数是否能拆分两个质数之积,即 $n=p_1\times p_2$,其中 $p_1,p_2$ 是质数。

分析 根据题意,只需找出 $n$ 的一个约数 $f_1$,则另一个约数即为 $n/f_1$,判断两个约数是否为质数即可,总的时间复杂度 $O(\sqrt n)$。


114 Telecasting station

题意 一维数轴上有 $1\le N\le 1.5\times 10^4$ 个城镇, 城镇坐标为 $0\lt X_i \lt 5\times 10^4$,其人口数为 $0\lt P_i \lt 5\times 10^4$。现要修建一电视站 $Y$,使得居民的不满程度 $\sum_i P_i|X_i-Y|$ 最小。

分析 带权中位数经典题。


115 Calendar

题意 输入 2001 年 $M$ 月 $N$ 日,输出该天是周几?

分析 模拟。


116 Index of super-prime

题意 定义素数序列为 $P_1\lt P_2\lt \dots\lt P_m\lt\dots$,超素数为素数序列中下标也是素数的数,例如3 的下标是 2,7 的下标是 4,因此 3 是超素数,7 不是超素数。现给定一正整数 $N\le 10^4$,将 $N$ 分解成最少数量的超素数之和,并将超素数从大到小输出。若 $N$ 无法由超素数之和表示,则输出 0。

分析 现将 $N$ 以内的素数筛选出来,进一步筛选出超素数,个数约 200 个。剩下的问题为完全背包问题,动态规划解决即可。


117 Counting

题意 给定三个整数 $0\lt N, M, K \lt 10001$,询问 $N$ 次:判断给定的数 $x_i^M$ 是否是 $K$ 的倍数。

分析 快速幂。


118 Digital root

题意 求 $A_1+A_1A_2+\dots+A_1A_2\dots A_N$ 的数根,其中 $1\le N\le 1000,0\le A_i\le 10^9$。

分析 数根公式:

原理 数 $x$ 可表示成

因为 $10^i \equiv 1\pmod 9$,所以有如下等式:

定义数位和函数 $f(x)=\sum a_i$,则等式 2 可写成:

数根 $DigitRoot(x)$ 使用 $f(x)$ 表示为:

根据等式 3 可得


119 Magic pairs

题意 给定三个正整数 $N, A_0,B_0\le 10^4$,求出所有的 $0\le A, B\lt N$ 对,满足:对于所有的 $(x, y)$,如果 $A_0x+B_0y$ 能被 $N$ 整除,则 $Ax+By$ 也能被 $N$ 整除。

分析 根据题意可得

联立公式 1 和公式 2 可得

两边同时对 $N$ 取模

该等式对于所有的 $x$ 均成立,即与 $x$ 无关,所以

根据公式 5 可知 $A:B$ 值等于 $A_0:B_0$,这缩小了解的搜索范围。然而这只说明了必要性,还需要进一步证明充分性。

利用扩展欧几里得定理,可求得

要使右式为 $N$ 的倍数,可两边同时乘上 $ N / \gcd(\gcd(A_0, B_0), N)$

其中,$X_0=x_0N / \gcd(\gcd(A_0, B_0), N)$,$Y_0=y_0N / \gcd(\gcd(A_0, B_0), N)$。

等式两侧同时除以 $\frac{\gcd(A_0, B_0)}{\gcd(\gcd(A_0, B_0), N)}$

其中,$A=A_0\frac{\gcd(\gcd(A_0, B_0), N)}{\gcd(A_0, B_0)},B=B_0\frac{\gcd(\gcd(A_0, B_0), N)}{\gcd(A_0, B_0)}$。

上述过程可将 $X_0, Y_0$ 替换成通解形式,结论仍然成立。

则 $\forall i\in [0, N)$, $(iA\mod N, iB\mod N)$ 均是解,但是可能存在重复。


120 Archipelago

题意 给出正 $3\le N\le 150$ 边形的第 $N_1$ 个点坐标和第 $N_2$ 个点坐标,按序求出所有点的坐标。

分析


121 Bridges painting

题意 给点数为 $1\le N\le 100$ 的无向图,给图中的每条边进行黑白染色,要求当顶点度数大于 1 时,该顶点至少与一条白边和一条黑边相连接。

分析


122 The book

题意 给点数为 $2\le N\le 10^3$ 的无向图,每个点至少与 $[\frac {N+1}{2}]$ 个点相连,求一条哈密顿回路

分析


123 The sum

题意 求前 40 个斐波那契值的和。

分析 模拟。


124 Broken line

题意 给一边数为 $4\le K\le 10^4$ 的多边形,以及一个二维坐标点 $(X_0, Y_0)$,判断该点在多边形的内部、外部亦或边界上。数据保证多边形顶点坐标为整数,$X_0, Y_0$ 也为整数。

分析


125 Shtirlits

题意

分析


126 Boxes

题意 有两个盒子,两个盒子分别有 $A,B$ 个球,在移动球时要放入盒中已有的等量的球,即操作一次后两个盒子的球数可能为 $2A, B-A$ 或 $A -B, 2B$ 两种情况。求最少的操作次数使得一个盒子为空。数据保证 $0\lt A+B\lt 2147483648$。

分析 考虑反向操作,记 $S=A+B$,则判断状态 $(0, S)$ 是否能导出 $(A, B)$。逆操作从状态 $(A, B)$ 可推出 $(\frac A2, B+\frac A2)$。

因为总和固定为 $S$,对于一个状态可以用两者的最小值表示,则状态有

可以发现有效状态构成了一棵高度最大为 $\log(S)$ 的二叉树。反过来考虑,对于任一有效状态转移到根状态 $(0, S)$ 的操作数不超过 $\log(S)$。因此对于初始状态 $(A, B)$ 在 32 步内判断是否根状态 $(0, S)$ 即可。


127 Telephone directory

题意 给 $0\lt N\lt 8000$ 个号码,电话本每页能记录 $0\lt K \lt 255$ 个电话号码,要求号码按序记录在电话本上,并且首位不同的号码记录记录在不同页,要求计算记录号码的页数。

分析 模拟。


128 Snake

题意 给定 $4\le N\le 10^4$ 个整点 $-10^4\le x_i,y_i\le 10^4$,要求构造满足以下条件的多边形:

  1. $N$ 个点均为多边形的顶点;
  2. 每个顶点均构成一个直角;
  3. 多边形的边与坐标轴平行;
  4. 多边形无自交;
  5. 多边形的周长最短。

如果能构成多边形,则输出多边形的周长,否则输出 0。

分析 考虑 $y$ 坐标相同的若干个点 $(x_1, y), (x_2, y),\dots, (x_m, y)$。因为每个点连接一水平线段和一竖直线段,所以第一个点 $(x_1, y)$ 只能与 $(x_2, y)$ 相连,$(x_3, y)$ 与 $(x_4, y)$ 相连,以此类推。这要求 $m$ 必须是偶数,否则无解。

上述步骤完成后,需要判断所有点是否联通以及是否存在线段相交。对于线段相交问题,可以使用扫描线+线段树/树状数组解决。


129 Inheritance

题意 给有 $3\le N \le 400$ 个点的凸包,以及 $2\le M\le 1000$ 条线段,判断每条线段被凸包包含的长度。

分析


130 Circle

题意 圆上有 $2k$ 个点,其中 $1\le k \le 30$。现要求将点用线连接起来,使得:每个点都有线连接;圆被划分的区域数量最少,求不同的划分方案数以及最小区域数。

分析 显然,最少区域为 $k+1$,每条连线不能有交点,根据该性质则连一条边后就生成两个子问题,于是使用动态规划解决。$dp(i)$ 表示 $2i$ 个点划分成最少区域的方案数,枚举该连线的左右两部分的规模进行转移:


131 Hardwood floor

题意 有一个 $N\times M$ 的网格,现使用 1×2 和 2×2 的方块填满网格(方块可旋转放置),求铺满网格的方案数,其中 $1\le N,M\le 9$。

分析 状压 DP。


132 Another Chocolate Maniac

题意 给定 $M\times N$ 的网格,使用 1×2 和 2×1 的方块填充,其中 $1\le M\le 70, 1\le N\le 7$。网格部分格子不能与方块重叠,求使用最少数量的方块填充网格,使得网格不存在相邻的空白格子,即不能再放置方块。

分析 轮廓线 DP。对于每个格子有 3 种状态:可放置、不可放置,必须放置。假设当前格子为 $(i, j)$ 且为空,上方的格子 $(i-1,j)$ 也为空,此时有两种方案:1. 在 $(i-1,j)$ 和 $(i, j)$ 中放方块;2. 不放方块,但是 $(i, j)$ 和 $(i+1,j)$ 必须放置方块。因此每个格子有 3 种状态,总的时间复杂度为 $O(NM3^N)$。


133 Border

题意 给 $1\le N\le 16000$ 个一维区间 $[A_i, B_i]$。若一个区间 $[A_i, B_i]$ 被另一个区间 $[A_j, B_j]$ 完全覆盖,即 $A_j\lt A_i$ 且 $B_i \lt B_j$,则去除该区间。求被去除区间的数量。

分析 按 $A_i$ 为第一关键字,$B_i$ 为第二关键字排序,按 $A_i$ 划分阶段,实时维护最大 $B_j$,若 $B_i<B_j$ 则去除当前区间。


134 Centroid

题意 求树的重心。

分析 遍历一遍树即可。


135 Drawing Lines

题意 在无限平面上画 $N$ 条直线,求平面划分的区域数。

分析 画图找规律,直线两两相交,结论为 $1+\frac {N(N+1)}2$。


136 Erasing Edges

题意 给定 $3\le N \le 10^4$ 点多边形的边的中点 $(x_i, y_i)$,判断是否能够根据边中点复原多边形顶点,如果能复原按序给出顶点坐标。

分析


138 Games of Chess

题意 有 $2\le N \le 100$ 个人轮流下象棋,每次两个人下棋并且胜者可继续下棋直至输棋。现已知每个人下棋的总局数,要求构造符合规则的一种方案,其胜者在第一个。数据保证有解,且所有人的总局数小于 $10^4$。

分析 构造。总棋局数为每个人的总局数之和除以二。然后按每个人的局数从大到小排序,假设顺序为 $(r_1, c_1), (r_2, c_2),\dots$,其中 $r_i$ 表示 $id = c_i$ 的棋局数。构造方案为 $(c_1, ?),(c_1,?),\dots,(c_2, c1),(c_2,?),\dots$,优先排列胜者,最后一局输给下一个胜者完成衔接,剩余的棋手则安排在败者局中。


139 Help Needed!

题意 十五数码问题。

分析


140 Integer Sequences

题意 给定长为 $1\le N \le 100$ 的序列 $0\le A_i\le 2\times 10^9$,判断是否存在序列 $X_i$ 满足

其中, $0\le B\lt P\le 10^4$。

分析 扩展欧几里得算法。


141 Jumping Joe

题意 一只青蛙在一维数轴的整数点上跳,每次能够向负轴或正轴方向跳 $x_1$ 或 $x_2$ 个整数距离,求能否刚好 $0\le K\le 2\times 10^9$ 次跳到整点 $-4\times 10^4 \lt P\lt 4\times 10^4$ 位置上。如果能到达位置 $P$,给出一种方案 $(P_1, N_1, P_2, N_2)$,$P_i$ 表示往正轴方向跳 $x_i$ ,$N_i$ 则表示往负轴方向跳 $x_i$。

分析 扩展欧几里得算法。


142 Keyword

题意 给长为 $1\le N \le 5\times 10^5$ 的字符串,该串只由 $a$ 和 $b$ 构成,求最短的不是该串子串的字符串,并给出一个解。如 $aba$ 的子串有 $a,b,ab,ba,aba$,因此最短非子串长度为 2,一种解为 $aa$。

分析 因为 $2^{19} > 5\times 10^5$,所以答案不超过 19,枚举长度并枚举该长度所有子串即可。后缀数组和后缀自动机也可以做。


145 Long Live the Queen

题意 给定有 $1\le N \le 16\times 10^4$ 的树,每个点的权值为 $-10^3\le w_i\le 10^3$,求一棵子树使得权重和最大。

分析 树 DP。


144 Meeting

题意 两个人约在 $[X,Y]$ 时间内碰面,约定先到的人等另一个人的时间不超过 $0\lt Z\le 60*(Y-X)$ 分钟,求两个人能碰面的概率。

分析


148 B-Station

题意 背景中有 $1\le N\le 15000$ 级蓄水池,每级蓄水池目前有 $0\le W_i\le 15000$ 重的水量,最大蓄水量为 $0\le L_i\le 15000$。释放第 $i$ 级蓄水池的代价为 $0\le P_i \le 15000$,且第 $i$ 级的水会流入第 $i+1$ 级的水池中。如果水池中的水超过了容量,则水池中的所有水会继续流入下一级。现在 kbfz 想要释放第 $N$ 级的水,求最小代价以及一种方案。

分析 为了释放第 $N$ 级的水,一种是直接花费 $P_N$ 的代价,另一种则是释放前面的水池,通过超容量来释放。假设第一个花费代价 $P_j$ 释放水池 $j$,则下一个必须花费代价的水池满足:

即堆积的总水量不超过容量的第一个位置 $k$,该位置必须花费 $P_k$ 的代价释放水。

使用前缀和 $S_i$ 表示,则有

当固定第一个花钱释放的水池 $j$ 后,在 $[j, N]$ 中必须花钱的水池满足 $S_k-L_k \le S_{j-1}$,其中 $S_k-L_k$ 是定值。之后使用数据结构维护 $S_k-L_k$ 所对应的代价即可。


149 Computer Network

题意 给 $1\le N\le 10^4$ 个点的树,求每个点 $i$ 到其他点的最远距离 $S_i$。

分析 每个点到树直径的端点的距离之一等于最远距离。


150 Mr. Beetle II

题意 给定起点 $(x_1, y_1)$ 和终点 $(x_2, y_2)$,求起点和终点构成的线段穿过的第 $1\le n\le 10^5$ 个格子左下角坐标,只经过角点不算穿越该格子。每个格子可使用 $(x, y),(x,y+1),(x+1,y+1),(x+1, y)$ 表示,其中左下角点坐标为 $(x, y)$。

分析 假设已知当前穿越的格子,则下一个可能穿越的格子为前进方向的相邻 3 个格子。线段穿越格子的充要条件:线段和格子的其中一条对角线严格相交。


!!! 151 Construct a triangle

题意 对于三角形 ABC,已知长度 $|AB|=c,|AC|=b,|AM|=m$,其中 M​ 是线段 BC 的中点。求三个顶点的坐标,满足上述长度关系。

这道题数据有问题,允许三点共线。

分析 固定点 A 在原点,点 B 为 $(c, 0)$,设点 C 坐标为 $(x, y)$。根据长度关系可得:

利用这个等式可以很容易求出一组解,注意判断方程有解即可。


152 Making round

题意 已知 $1\le N\le 10^4$ 候选人的选票数 $0\le A_i\le 10^4$,现要求将选票转换成整数的百分比形式, 使得总和为 100。对于转换后小数部分,每个候选人的选票可向上或向下取整(取整相互独立)。求一种方案,或判断无法转换。

分析 模拟。


xxx

题意

分析

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