CodeForces 986B Petr and Permutations
原题链接 Petr 要打乱排列。他首先有一个从 \(1\) 到 \(n\) 的顺序排列，然后进行 \(3n\) 次操作，每次选两个数并交换它们。 Alex 也要打乱排列。他与 Petr 唯一的不同是他进行 \(7n+1\) 次操作。 给定一个 \(1\) 到 \(n\) 的排列。问是由谁打乱的。如果是 Petr，输出"Petr"，否则输出"Um_nik"（不是 Alex）。 （by AKEE） 首先我们考虑怎么快速还原这个序列。 很显然的一个贪心策略就是假设序列为 \(\{a_i\}\)，不断把 \(a_{a_i}\) 与 \(a_i\) 交换直到 \(a_i=i\)。 这样做我们发现交换次数是 \(\mathcal{O}(n)\) 级别的，因为 \(a_{a_i}\) 最多被选 \(n\) 次。 然后我们发现要一个序列交换后形成交换前的序列交换次数只能是偶数。所以该交换次数与 Petr…
20180706 模拟赛 T3 -- 神经衰弱
文件名： card 题目类型： 传统题 时间限制： 1 秒 内存限制： 128 MB 编译优化： 无 天然少女小雪非常喜欢玩一个叫做神经衰弱的游戏。 游戏规则是，有若干种牌，每种牌有若干对，开始时全都正面朝下放置。 然后每次同时翻开两张牌，假如这两张牌是同一种类，则拿走这两张牌，否则再次翻回背面。 小雪虽然看上去傻乎乎的但是玩这个游戏非常厉害，所以可以认为她是绝对聪明的，即会采取最优决策和有着完美的记忆力。 现在小雪想要知道，对于某一副牌局，她期望拿多少次可以拿走所有牌。 需要注意的是小雪玩的神经衰弱和普通神经衰弱有所不同。普通神经衰弱是依次拿走两张牌，而小雪的神经衰弱是同时拿走两张牌。 第一行一个整数 \(n\) 表示牌的种类数 第二行 \(n\) 个整数 \(a_{i}\) 表示第 \(i\) 种牌有多少对 一个整数，表示期望 \(\mod998244353\) 即假如答案是…
20180711 模拟赛 T3 -- 聚变
文件名： fusion 题目类型： 传统题 时间限制： 3 秒 内存限制： 256 MB 编译优化： 无 知名科学家小 A 在 2118 年在计算机上实现了模拟聚变的过程。 我们将她研究的过程简化。 核子共有 26 种，可以用 a 到 z 共 26 个字母表示。 核子聚变的过程可以用一个字符串描述。 按照顺序从左到右的顺序，假如有两个相同核子相邻，两个核子就会相互吸引发生聚变生成一个序号 +1 的核子，特殊的，两个 z 核子相邻会湮灭没有新的核子生成。 每当两个核子聚变时，就需要重新从左到右重复找到两个相邻的相同核子直到不存在为止。 比如 zyzzy->zyy->zz-> 小 A 为了做出足够有效的实验，每次会从一个字符串中选定一个子串操作。 她想要知道每次实验这个子串中的核子能否最终全部湮灭。 第一行一个只有小写字母的字符串。 第二行一个数 \(n\) 表示询问次数 接下来 \(n\)…
CodeForces 468B Two Sets
原题链接 DOWNLOAD AS PDF 给出 \(n\) 个各不相同的数字，将它们分别放入 \(A\) 和 \(B\) 两个集合中，使它们满足： （by \(\color{red}\sf{Uranus}\)） 感觉网上全是并查集的题解。 没有贪心？ 感觉贪心比并查集好想啊…… 首先我们想到的肯定是开个 set 大力匹配，然而发现对于一个 \(x\) 可能 \(a-x\) 和 \(b-x\) 都在序列中，于是我们就陷入两难了。 如何解决这个问题呢？ 现在我们假设 \(a\ge b\)。 我们每次贪心地选出没有匹配过的数的最小值，设其为 \(x\)。 假设我们发现 \(a-x\) 和 \(b-x\) 都在序列中且都没有被匹配过。 我们会发现 \(x\) 一定与 \(a - x\) 匹配。 假设答案是 \(x\) 与 \(b - x\) 匹配，那也就是说 \(a - x\) 不在 \(A\)…
ZJOI2014 璀灿光华
金先生有一个女朋友没名字。她勤劳勇敢、智慧善良。金先生很喜欢她。为此，金先生用 \(a^3\) 块 \(1 \times 1 \times 1\) 的独特的水晶制作了一个边长为 \(a\) 的水晶立方体，他要将这个水晶立方体送给他见过最单纯善良的她。 由于水晶立方体太太，不好运送，金先生还是将它拆开来送出。他相信拼好这个水晶立方难不倒聪明的她。 没名字收到了礼物后果然不一会儿就根据说明将水晶立方体拼好了。没名字发现，有 \(n\) 块水晶在漆黑安静的夜晚会随机以等概率向上下左右前后六个方向的一个发出光。被光照到的水晶显得格外好看。没名字给每一块不会发光的水晶定义了一个好看程度。水晶立方体在夜晚中的好看程度就是每块被光照到的水晶的好看程度之和。没名字想知道，水晶立方体在夜晚中的好看程度的最小值和最大值。 第一行是 \(a\)，表示水晶立方体的边长。 接下来 \(a^3\) 行，每行若干整数。…
一个关于二叉树问题的证明
回家路上，跟 yg 大佬讨论了一个问题：对于一棵二叉树，其拥有两个儿子的节点个数为 \(n\)，要求的是叶子节点的个数。答案应该是 \(n+1\)，下面给出我的证明： 这是我一开始想到的方法： 首先对于一棵满二叉树（深度为 k，且有 \(2^{k+1}-1\) 个节点的二叉树），正确性显然。打过线段树的都知道，对于一个节点 x，我们可以用 x<<1 表示其左儿子，x<<1|1 表示其右儿子。我们可以把一棵满二叉树用类似线段树的方法标号，如果标号最大的有两个儿子的节点编号为 \(x\)，则其右儿子编号为 \(2x+1\)，不难发现其右儿子是编号最大的节点，所以该树一共有 \(2x+1\) 个节点，而有 \(x\) 个有两个儿子的节点，所以叶子节点有 \(x+1\) 个。 那么我们考虑一棵有 \(x\) 个有两个儿子的节点的二叉树，并设它的叶子节点有 \(y\) 个。那么如果我们从该树中删除…
题解：[HAOI2008] 下落的圆盘
时空限制：1000 ms / 128 MB 原题链接： 有 \(n\) 个圆盘从天而降，后面落下的可以盖住前面的。求最后形成的封闭区域的周长。看下面这副图, 所有的红色线条的总长度即为所求. 第一行为 1 个整数 \(n\)，\(n\le1000\) 接下来 \(n\) 行每行 3 个实数，\(r_i,x_i,y_i\)，表示下落时第 \(i\) 个圆盘的半径和圆心坐标。 最后的周长，保留三位小数 两页的爆蛋记录（来自蒟蒻的无助）。 orz 千古神犇 wzp 一眼秒题。 这种题一定要耐心地做（初中数学老师一直这么对我说）。 首先，我们来看其简化版： 我们把 \(\odot B\) 覆盖在 \(\odot A\) 上，我们发现我们需要求出 \(\angle A\) 的度数。我的方法是连结 \(CB,AB,BD,AB\)（如图）。我们发现…