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\)（如图）。我们发现…