Mcginn's Blog

SGU-253-300

字数统计: 4.8k阅读时长: 19 min
2021/04/24 Share

290 Defend the Milky Way

题意 给三维空间中 $1\le N\le 100$ 个点,求在凸包顶点/平面上的点。

分析 计算几何。


289 Challenging Tic-Tac-Toe

题意 OOXX 游戏。给定一个初始局面,假设玩家都玩得很好的情况下,判断先手必胜/必败/平局/非法。非法是在游戏过程中不可能出现的局面。

分析 模拟。总共局面数为 $3^9=19683$ 种。


288 Best Tournament Schedule

题意 有 $1\le N\le 2005$ 支队伍参加巡回赛,所有队伍两两之间都需安排一次比赛,要求同一巡回赛中每支队伍最多只参加一场比赛。求最少巡回赛轮数,并输出任一方案。

分析 构造。

当 $N$ 为偶数时,巡回赛最少轮数为 $C(N,2)/(N/2)=N-1$。$N$ 为偶数的构造方案如下:

  1. 前 $[1, N-1]$ 行,$f(i, j) = (i - 1 + j - 1)\pmod {N-1}$;
  2. 第 $N$ 行,$f(N, j)=(N-1+2j)\pmod {N-1}$ 。

当 $N$ 为奇数时,巡回赛最少轮数为 $C(N,2)/({N-1}/2)=N$。添加一支虚拟队伍转化成队伍数为偶数的情况构造。

代码 sgu 288


287 Amusing Qc Machine

题意 在 $[1, q]$ 中猜一个秘密数字,程序每次返回猜测值和秘密值的大小/相等关系。但是存在 $0\le c\le 10^6$ 延迟:第 $i$ 次猜测结果在第 $i+c$ 次猜测后返回。求最坏情况下猜中秘密数字的猜测次数。

分析 $f(i)$ 表示 $i$ 轮交互后猜测值的数量。因为延迟 $c$ 存在,第 $i$ 次猜测只能基于前 $i-c-1$ 轮交互的已知结果。前 $i-c-1$ 轮共有 $f(i-c-1)$ 个值,划分成 $f(i-c-1) + 1$ 个区间,第 $i$ 轮猜测值必然是在这些区间中,因此共有 $f(i-c-1)+1$ 枚举值。

则转移方程为 $f(i)=f(i-1)+f(i-c-1)+1$。


286 Ancient decoration

题意 $N$ 个点的无向图,已知每个点的度数为 $K$ 且 $K$ 为偶数。要求给边染色使得每个点恰好在 2 条染色边上,判断是否存在可行方案,若存在则输出任一方案。

分析

Tips 欧拉回路。


285 What? Where? When?

题意 已知有 13 个问题,除第 13 个问题有 $1\le N\le 1000$ 个候选外,1 至 12 号问题仅有一个候选。每次随机从 1 至 13 个问题中随机抽取一个问题,若答题者回答正确则 +1 分否则提问者 +1 分,答题者或提问者率先取得 6 分则游戏结束。给定答题者对于所有问题回答正确的概率,求所有可能局面(’6:0’, ‘6:1’, ‘6:2’, ‘6:3’, ‘6:4’, ‘6:5’, ‘5:6’, ‘4:6’, ‘3:6’, ‘2:6’, ‘1:6’, ‘0:6’)的概率。

分析 状压 DP。


284 Grammar

题意 有 $1\le N\le 30$ 个字符串 $S_i, 1\le i\le N$,由基本字符 ‘a’, ‘b’ 或 $S_j, j\lt i$ 构成。给定查询字符串 $T,|T|\le 100$,求串 $T$ 在 $S_N$ 中的出现次数。数据保证 $\sum |S_i| \le 500$。

分析 KMP 算法。对于每个字符串 $S_i$ 记忆 $dp(i, j)$,表示从 $T_j$ 位置开始匹配 $S_i$ 最终成功匹配 $T$ 的次数,$prefix(i, j)$ 表示匹配完 $S_i$ 后匹配 $T$ 的前缀长度。


283 Mechanics

题意

分析


282 Isomorphism

题意 给 $1\le N\le 53$ 个点的完全图,每条边染上 $1\le M\le 1000$ 种颜色中的一种。如果一张图完全图通过重标号点构成另一张图,定义这两张图同构。求本质不同的异构图数量,结果对 $P$ 取模且 $P$ 为素数。

分析 该问题本质上是在求边的置换然后使用 polya 定理计数,而边置换是通过点置换得到的,因此从点置换入手。

假设有一条边 $(u, v)$,分点 $u, v$ 是否在同一点循环置换中考虑。

  1. 若点 $u, v$ 在相同 k-循环中,即循环中的元素为 $k$ 个。显然,边 $(u, v)$ 所在的边循环置换同样有 $k$ 个元素,而 $k$ 个点的子图共有 $C_k^2$ 条边,因此边循环个数为 $\frac {C_k^2}{k}=\frac{k-1}{2}$。

    注意,当 $k$ 为偶数时且 $u,v$ 在点循环置换中间隔 $\frac k2$ 时,边 $(u, v)$ 所在的边循环置换中仅有 $\frac k2$ 个元素。因为经过 $\frac k 2$ 次置换后,边 $(u, v)$ 重复出现了。将这种边循环单独考虑,此时边循环个数为 $\frac {C_k^2-\frac k2}{k}+1=\frac k 2$。

    综上所述,若点 $u, v$ 在相同点循环置换中,相应的边循环个数为 $\lfloor \frac k 2\rfloor$。

  2. 若点 $u, v$ 不在相同点循环中时,假设两个点循环的元素个数分别为 $k_1, k_2$,那么边 $(u, v)$ 所在的边循环置换有 $LCM(k_1, k_2)$ 个元素以及总共有 $k_1k_2$ 条边,因此边循环个数为 $\frac {k_1k_2}{LCM(k_1, k_2)}=GCD(k_1,k_2)$。

在已知边循环个数 $(f)$ 的前提下,根据 polya 计数本质不同的染色方案数为 $M^{(f)}$。

剩下的问题便是枚举点置换方案,然后计算相应的边循环个数即可。在枚举点置换方案时,只关心各个循环的大小而不是具体元素,问题转化成将 $N$ 拆解成 $k_i$ 使得 $\sum k_i=N$ 且 $k_i\le k_{i+1}$,$k_i$ 表示第 $i$ 个点循环的元素个数。

在得到各个点循环大小后,通过排列组合将具体元素放进循环中,得到本质不同的点置换方案即可。首先,假设 $k_i$ 两两不同,则点分配方案数为 $C_N^{k_1}C_{N-k_1}^{k_2}\dots=\frac {N!}{k_1!k_2!\dots k_m!}$。如果存在若干个相同的 $k_i$,即存在相同大小的点循环,这些循环本身没有先后之分,但是前述枚举会重复统计。将点置换方案重新记为大小为 $x_i$ 的循环有 $c_i$ 个,则点分配方案数为 $\frac {N!}{\prod (x_i!)^{c_i}c_i!}$。此外,一个循环中的元素是有顺序的,大小为 $k$ 的循环有 $(k-1)!$ 种排列方案:循环本质上是一个环,将第 $k$ 个元素插入有 $k-1$ 个元素的环时,有 $k-1$ 个位置可以插入,利用归纳法得到 $(k-1)!$ 种排列。 最终点置换的方案数为 $\frac{N!}{\prod x_i^{c_i}c_i!}$。

利用 burnside 定理,不等价着色方案数为

参考 SGU 282 Isomorphism


281 Championship

题意 有 $1\le N\le 50000$ 只队伍参加了 2 场比赛且已知各比赛的排名,现要依据 2 场比赛排名生成最终排名:如果前 $M$ 支队伍在 2 场比赛中是相同集合,则最终排名的前 $M$ 支队伍也是该集合。如果无法确定队伍之间的相对排名,则按照队伍名称字典序排序。输出最终排名结果。

分析 模拟。


280 Trade centers

题意 给 $1\le N\le 3\times 10^4$ 个点的树,在树上标记若干点使得树上所有点到最近标记点的距离不超过 $1\le K\le 100$,求最少需要标记点的数量。

分析 进阶问题 - HDU 5290 Bombing plan。$up(u, i)$ 表示点 u 向上覆盖 $i$ 步的最优值,$dw(u, i)$ 表示点 u 需依赖父节点向下覆盖 $i$ 步的最优值。


279 Bipermutations

题意 有 $2N,1\le N\le 1000$ 个对象 $1, 1’, 2,2’,\dots, n, n’$,已知存在偏序关系:$\forall i\in[1, n], i’\prec i$; $i\prec j \Leftrightarrow i’\prec j’$。定义 $b_{ij}= j’$ if $j <i$ 否则 $b_{ij} = j$ 以及 $a(i)$ 等于 $i\prec b_{ij}$ 的数量,已知序列 $a(1),\dots, a(n)$,判断是否存在满足条件的偏序序列,若存在输出任一方案。

分析 假设从大到小放置,经过模拟可以发现几个性质:(1)放置对象 $i$ 时,只会影响 $j<i$ 的 $a(j)$;(2)放置 $i’$ 时会影响 $j>i$ 的 $a(j)$;(3)放置 $i$ 之后才能放置 $i’$。

首先每次挑选 $a(i)=0$ 的对象 $i$ 放置,如果存在多个 $a(i)=0$ 的对象 $i$,显然选取下标最小的对象 $i$,否则根据性质 (1) 会导致下标最小的对象 $i$ 的 $a(i)$ 发生变化。

当找不到 $a(i)=0$ 时,依次放置已经放置 $i$ 的 $i’$——依次是指 $i\prec j \Leftrightarrow i’\prec j’$ 相对顺序不能发生变化,然后修改 $j>i$ 的 $a(j)$。


278 Fuel

题意 给定 $1\le N\le 75000$ 种燃油,每种燃油单位质量下体积为 $a_i$, 成本 $b_i$ 和强度 $c_i$,其中 $0\le a_i, b_i, c_i\le 100$。已知汽车的油箱可容纳 $1\le A\le 1000$ 体积的燃油以及成本限制 $1\le B\le 10000$,在允许任意混合燃油的情况下,求混合燃油的最大强度。

分析 假设有 2 种燃油 $(a_i, b_i, c_i), (a_j, b_j, c_j)$,混合后可以得到 $\forall w\in [0, 1], a=wa_i+(1-w)a_j, b=wb_i+(1-w)b_j, c=wc_i+(1-w)c_j$,最终从一种比例的混合燃油中取得最大强度,即 $ans = c\times min\{\frac Aa,\frac Bb\}$。从几何角度看该问题,2 种燃油时混合燃油候选为一条线段,多种燃油时候选为凸多面体。

记 $x_i = \frac {c_i}{a_i}, y_i=\frac{c_i}{b_i}$,原问题可以转化成 $\max z,z\le Ax_i, z\le By_i$。通过直线 $y=\frac AB x$ 划分 $z$ 上限分别为 $Ax_i$ 和 $By_i$ 的情况,本质上都是线性规划问题,最优解必然在 extreme point(端点)上。


277 Heroes

题意 二维平面初始给 3 个点,随后逐渐添加 $1\le N\le 10^5$ 个点。每次添加点后,重新构造多边形包含当前所有点且周长最短,输出多边形的面积。

分析 加点维护凸包,参考模板


276 Andrew’s Troubles

题意 (if else 模拟题)

分析 模拟。


275 To xor or not to xor

题意 给 100 个数 $A_i(0 \le A_i \le 10^{18})$,求一个子序列使得异或和最大。

分析 线性基。


274 Spam-filter

题意 写一个邮件地址 parser,判断地址合法性。

分析 Parser。


273 Game Po

题意 给定 200 个石子排成一排,并且每个石子染成蓝、红、黄、白其中一种颜色。四名玩家轮流选择 2 个相邻石子并使用 1 个替换规则颜色的石子替换,直到不能替换为止。游戏开始前,给定允许的替换规则,四种颜色分配给四名玩家,若游戏结束时仅剩 1 个石子,则该石子颜色对应的玩家获胜。求最后可能获胜的颜色。

分析 区间 DP。


272 Evacuation plan

题意 给 $1\le N\le 10^4$ 个点和 $1\le M\le 10^5$ 条边的无向图,起点集合 $A$ 以及终点集合 $B$,保证 $A∩B=\empty$。现要找出若干等长路径使得尽可能多的点从 $A$ 走到 $B$,需满足:1. 路径长度等于 $\min\{dist(a, b)|a\in A, b\in B\}$;2. 任意两条路径不能存在交点。求最多的点数以及路径长度,并输出一种路径方案。

随便构造一种方案,使得再也找不到一条从 A 到 B 的路径(不是找一个最优的方案)。

分析 BFS+DFS。


271 Book Pile

题意 已知有 $0\le N\le 40000$ 个元素的栈,进行 $0\le M\le 10^5$ 次操作:1. 栈顶添加一新元素;2. 将栈顶 $0\le K\le 40000$ 个元素翻转,其中 $K$ 是常数。输出所有操作后的栈元素顺序。

分析 伸展树可做,但是大材小用了。操作上只有添加新元素且 $K$ 为常数,一旦栈元素数量超过 $K$,除栈顶 $K$ 个元素外其余元素已经固定了,这部分元素写入固定的栈中即可。而栈顶 $K$ 个元素可能发生多次翻转,使用双端队列可以方便维护往“栈顶”添加数据。


270 Thimbles

题意 给定 $2\le N\le 100$ 个位置以及 $1\le M\le 1000$ 次操作。一开始球在位置 1,每次操作交换 $A_i < B_i$ 位置。已知操作集合但不知操作次序,经过 $M$ 次操作后求解球可能的位置集合。

分析


269 Rooks

题意 有一个形状特殊的棋盘,该棋盘共 $1\le N\le 250$ 行,每行有 $1\le B_i\le 250$ 列。现要在棋盘上放置 $1\le K\le 250$ 个车,求车不互相攻击的放置方案数。

分析 行的顺序无关紧要,因此可以按列宽 $B_i$ 排序。$dp(i, j)$ 表示前 $i$ 行放置 $j$ 个车的方案数即可,转移方程较简单。


268 Hyper Almost Permutative String

题意 若字符串包含前 $N$ 个字符则定义为 permutative;若字符串去掉刚好一个字符后为 permutative 则定义为 almost-permutative;给定字符集 $N$ 后若字符串所有长度为 $N+1$ 的子串都是 almost-permutative 则定义该字符串为 hyper-almost-permutative。现给定 $2\le N\le 26$ 以及长度为 $N$ 且为 permutative 的字符串 $S_1,S_2$,求最短 hyper-almost-permutative 字符串且 $S_1, S_2$ 是其子串,多种方案输出任一方案。

分析


267 Optimist vs. Pessimist

题意 有 $1\le N\le 1000$ 个矩形,每个矩形中有 2 个点。要求从这 $N$ 个矩阵中选 $1\le K\le 10$ 个矩形,使得总面积和尽可能大。如果一个矩形能分成等面积的两部分且每部分都含有一个点,这个矩形会均分给 Optimist 和 Pessimist。Optimist 想知道最好情况下获得面积总和,Pessimist 想知道最坏情况下获得面积综合。

分析 等分面积线段必然经过矩形中心,即仅当矩形所包含的 2 个点和中心共线时无法均分。


266 Berlion

题意 给以原点为圆心半径为 $1\le R\le 10$ 的球体以及空间中两个点,求球体表面两个点的可视面积。

分析


265 Wizards

题意 有 $1\le M\le 10^5$ 个三维空间点,经过 $1\le N\le 1000$ 次变换:平移,缩放和旋转变换,求经过变换后每个点的空间坐标。

分析 三种变换都可以使用矩阵表示,将 $N$ 次变换融合成一个变换后应用于所有点即可。困难部分主要是旋转变换,参考绕任意轴旋转


264 Travel

题意 有 $1\le N\le 800$ 个男生和 $N$ 个女生,需要进行两两匹配。每个人有自己的偏好列表,若在一个匹配中出现双方都有更加偏好的异性存在时,该匹配是“不稳定”的。求解是否存在“稳定”的匹配方案,若存在输出任一方案。

分析 (稳定婚姻问题)。


263 Towers

题意 在长度为 $1\le N\le 10^6$ 的行上造塔。塔的定义为:连续位置均放置了方块且两侧都没有方块时,视为一个塔。有放置和询问两种操作:

  • 放置 1:在位置 x 放置 c 个方块;
  • 放置 2:在塔 t 的第 x 列放置 c 个方块;
  • 询问 1:目前塔的数量;
  • 询问 2:塔 t 中方块的数量;
  • 询问 3:塔 t 的长度;
  • 询问 4:塔 t 第 x 列上方块的数量。

分析 关键部分是如何快速找出塔 t,只有操作放置 1 时才会增加新塔。可以使用线段树维护每座塔的左边界点,快速查询塔 t 的位置。


262 Symbol Recognition

题意 有 $2\le K\le 6$ 个符号,每个符号由 $N\times M, 1\le N,M\le 10$ 的黑白网格构成。要求最少格子数使得能够区分出所有符号。

分析


261 Discrete Roots

题意 给两个质数 $2\le P\le 10^9,2\le K\le 10^5$ 和整数 $0\le A\lt P$,求解方程 $x^K=A\pmod P$ 的所有解。

分析

参考 一些数论概念与算法——从SGU261谈起


260 Puzzle

题意 有 $1\le N\le 200$ 个黑白格子,已知初始颜色。每个格子与若干格子绑定,若当前格子颜色改变时,与其相绑定的格子也会改变颜色。判断是否能够将所有格子改成同一颜色,若能给出任一方案。

分析 高斯消元。


259 Printed PR

题意 需要打印 $1\le N\le 100$ 种订单,每种订单需要 $1\le T_i\le 1000$ 分钟打印以及 $1\le L_i\le 1000$ 分钟派送。目前仅有一台打印机但有充足的派送人员同时派送。求完成这 $N$ 份订单的最小总时间。

分析 二分答案;经典贪心,比较相邻元素。


258 Almost Lucky Numbers

题意 如果一个数字有 $2N$ 数位且前 $N$ 个数位和等于后 $N$ 个数位和,定义该数字为 lucky-number。如果一个数字修改一个数位使得新数是 lucky-number,定义该数字是 almost-lucky-number。求范围 $[A, B]$ 中的 almost-lukcy-number 数量,其中 $0\le A\le B\le 10^9$。

分析 数位 DP。


257 Debt

题意 主角分别欠三个人 $P, O, S(1\le P,O,S\le 10^5)$ 钱,目前手头上的抵押物在不同人看来有不同价值:S 只能抵押 1 货币,B 能抵押 2 货币。现给出主角 $1\le N\le 10^5$ 件抵押物在三个人眼中的价值矩阵,判断主角是否能偿情债务。

分析


256 Balloons

题意 有 $1\le N\le 10$ 个人和一台机器,需要使用机器填充 $1\le M\le 100$ 个气球,机器每分钟只能一个人使用。第 i 个人一分钟内能填充 $0\le A_i\le 10$ 个气球,但是之后需要休息 $1\le B_i\le 4$ 分钟才能继续工作。求填充 $M$ 个气球的最少分钟数。

分析


255 Winsock 3 Beta

题意 假设有密钥 $K$,当传送数据在 $[K+1, 2K]$ 之间且二进制位仅 3 位为 1 时能够发送出数据,否则会被拦截。给定数 $0\le M\lt 2^{31}$,判断是否存在唯一的密钥 $K$ 使得能发送的数据个数恰好为 $M$。

分析


254 Strange Random

题意 数字 1 至 $1\le N\le 2\times 10^6$ 顺时针依次放置在环上,模拟如下操作:去除当前方向的第 $1\le Q\le 10$ 个数字,移动到顺时针方向的下一个数,若这个数是奇数则改前进方向为顺时针,否则为逆时针。求被去除的最后一个数。

分析 空间限制严格,不能使用双指针来解决。直接使用数组模拟操作过程,中间穿插重构。


253 Theodore Roosevelt

题意 给 $3\le N\le 10^5$ 个点的凸包以及 $0\le M\le 10^5$ 个点,判断多边形是否至少包含 $0\le K\le M$ 个点。

分析 单次判断点是否在凸包内可以做到 O(LogN)。

CATALOG