推荐理由： 细节较多的计算几何，适合一做。 Describe 在平面上有三个没有公共部分的圆，求平面上一点使得到三个圆的切线的夹角相等。 Solution 容易得出： 稍加转换： 那么我们只要找到一个点 ，满足他到 个点的距离符合给定比例。 我们设出 平方一下，然后乘以分母。可以得到 我们把 看做常数，那么原方程可以化成一个 有点常识的人就可以知道这是圆的一般方程，然后再分 种情况讨论。 那么 的轨迹是一条直线。 只需要把三个圆两两向交，再分开判断就行了。 code #include <cstdio> #include <cmath> #inc...

题目大意 有 个数连成环，可以互相和相邻的交换，问最少交换多少次使得每个位置上的数相同。 题解 首先最终状态是已知的。 这个问题有个很显然的性质是：必定有 个相邻的位置不用交换。 那么我们枚举交换的位置，就相当与把环化成了链。 那么接下来再考虑链怎么化？ 设 表示前 个人最少需要交换的次数, 是最终状态每一位的答案,它就是 因为太菜了，然后被教做人了。 所以发现好像之前的是错的。 那个东西好像还要推。 考虑对于每一个新位置 i 它应该会减去 因为换了一个开头，每一位都要往后更改。 然后取中位数是最小的。 所以最后答案就是 代码 #include <bits/stdc++.h...

生成函数简介 生成函数 \(\text{(generating function)}\)，又称母函数，是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。 by wiki 用人话来说生成函数就是把一个序列变成了一个函数。 一个形如 \(F(x) = \sum_{n > 0}{a_n \times x^n}\) 的函数可以理解为他是一个每一项分别为 \(a_n\) 的序列。 普通生成函数 重新引用上面的定义 \(F(x) = \sum_{n > 0}{a_n \times x^n}\) 这个 \(n\) 的定义域是到正无穷的，因为在序列的意义下，不存在的...

题目大意 给你一个长度为 \(n\) \(0/1\) 字符串，以及 \(m\) 个询问。 每个询问会告诉你一个 \(l, r\)。 问你在原字符串中有没有一个子序列和子串 \(s_l \to s_r\) 一样。 题解 你考虑只改变首或者尾，看能不能找到符合要求的子序列。 我们来验证，如果首 & 尾都无法找到一样的替代。 那么你也不能找到和首/尾 \(2\) 位一样的去替代，因为第一位都没有一样的了。 反之，如果你可以找到一个字符去代替首/尾，那么他已经是一个和原串相同的子序列了。 至于怎么找，就只要记录下前面第一次出现 \(0/1\) 的位置，记录下后面第一次出现 \...

题目大意 给你 \(n\) 个物体，体积为 \(w_i\) 。并且给你一个大小为 \(c\) 的背包。 要求你取若干个物品使得 : \(\lceil \frac{c}{2} \rceil \le \sum{w_i} \le c\) 并且输出取了哪些。 题解 考虑贪心。 排序后从大往小的地方去取。 如果当前取了会超过 \(c\) 就不取。 只要大于 \(\lceil \frac{c}{2} \rceil\) 就直接 \(break\) 这么证明这种做法是正确的？ 我们只要找到一种满足条件的，他没要求总和最多，也没要求取的数最多。 所以你只要先去最大的，如果当前取了超过 \(...

看到题，感觉预处理下 \(O(nm)\) 可以很容易的做到。 大概处理下每一个串作为前缀，后缀所可以选择的数的数量。 然后直接枚举，然后转移就行了。 再看一眼数据范围， \(n \le 10 ^ 15\)。 那没事了，很显然的矩乘的数据范围。 但是矩乘就不可以这么做了，要换一种转移方法。 你考虑把矩阵建成一个 \(50 \times 50\) 的矩阵，每一位 \((a,b)\) 的意义是 \(a\) 后面能否有 \(b\) 然后直接转移就行了。 感觉挺裸的，所以没太详细讲，不会矩乘的可以看下我的 博客 也可以私信。 代码: #include <bits/stdc++...

CF1387B1 题解 题目大意 给你一棵树，你可以把所有节点重排，不能回到原来的位置，移动一个点从 \(a\) 到 \(b\) 的代价是 \(2\) 点之间的边数。 题解 贪心的思路很显然，因为要总移动最小，那么一个点肯定只会和自己相邻或者隔2个点的点连边。 接下来考虑对于一个节点，他有若干的子节点，那么他会有一个子节点和他互换，其他的子节点相互互换。 但是这个的奇偶之类的细节很难处理。麻烦的死。 那可以换一种思路去考虑，你考虑先把每个节点第一次遍历的子节点和他互换，并用 \(flag[]\) 标记上。 最后从 \(1 \to n\) 跑一遍，让所有的子节点围成一个环，不让他...

什么是矩乘 一些好题 这里没什么板题，都是些比较妙的矩乘，逐步深入。 这是一个蒟蒻的刷题历程，大佬轻喷。 这里面的题目都没放代码，因为矩阵的代码一定要自己写一遍，每个人的都不一样的。 [NOI2012]随机数生成器 题目大意 给你很多数字：\(\text{m, a, c, x0 n, g}\) 和一个递推式： \[x_{n + 1} = (a \times x_n + c) \% m \] 要你求 \(x_n \% g\) 的数值。 数据范围：\(n, m, a, c, x0 \le 10^{18}, n, m \ge 1, a, c, x0 \ge 0\) 题解...

P4643 [国家集训队]阿狸和桃子的游戏 题目大意 有一张 \(n\) 个点 \(m\) 条边的图，点有点权，边有边权。 先手后手轮流染黑白两色，最后的得分是自己染的点权和 + 两端均为自己的颜色的边权和。 双方都希望自己的得分 - 对手的得分最大，求结果。 \(1 \le n \le 10000, 0 \le m \le 100000\) 题解 这题巨妙无比，真是妙蛙种子吃着妙脆角，秒进了米奇妙妙屋，秒到家了。 你可以考虑把每一条边都分到他所连的 \(2\) 个点上，各一半。 然后对于每条边，我们有 \(2\) 种可能，如下： \(2\) 边都是 \(A\) 取...

P3545 [POI2012]HUR-Warehouse Store Describe 一共 \(n\) 天，每天上午会进 \(A_i\) 的物品，中午会有一个客人想要买走 \(B_i\) 的物品，当然你也可以选择不买，问你最后最多可以交易多少次。 数据范围 : \(1 <= n <= 250000, 0 <= A_i, B_i <= 10^9\) Solution 首先，我们看到题目先会想到 \(01\) 背包。是个正确的作法，但是肯定过不了。 然后，我们考虑到这一定是个贪心/推式子的题目。 但是推式子的题目一般的特性在这里显然不符合(推式子的题目一般不...

CF1225D： 题意：\(a_i * a_j = x^k\) 求有多少组不同的\((i,j)\)对 很妙的一道hash题/雾 对于原来的柿子： \(a_i * a_j = x^k\) 我们可以转化成一种什么问题呢？ 看到后面的 \(x^k\)你就会想到分解原式，利用唯一分解定理可以得出： \[a_i = \prod_{i = 1}^{n}{p_i}^{A_i} \] \[b_i = \prod_{i = 1}^{n}{p_i}^{B_i} \] \[x = \prod_{i = 1}^{n}{p_i}^{C_i} \] 再看回原来的柿子，可以得到： ...

1. CF813D 题意： 给一个长度为\(n\)的序列,求两个不相交的子集长度之和最大是多少，能放入同一子集的条件是首先顺序不能变，然后每一个相邻的要么相差\(1\)或者相差\(7\)的倍数。 \(n < 5000\) 题解： \(f[i][j]\) 表示第一序列到了第 \(i\) 位,第二个序列到了第 \(j\) 位,符合条件的长度之和最大. 那么显然可以退出 \(O(n^3)\) 方程： i : 1 ~ n j : i + 1 ~ n k : 分两段。 第一段：1 ~ i，此时判一下a[k]有没有被j选中，如果没有在考虑转移i 第二段：j ~ n，此时就分别转移i,j就...

这题貌似没什么好讲的= = 大概就是对于每对 \(a, b\) 只可能有如下 \(3\) 种情况： a > b 此时显然可以知道你只会进行 \(a -> a / 2\), \(a -> a / 4\) 或者 \(a -> a / 8\) 这 \(3\) 种操作 然后根据贪心, 如果可以进行 \(a -> a / 8\) 操作, 并且变完以后 \(a\) 还是保证 \(a > b\) 那就用这个操作 \(a -> a / 2\) 和 \(a -> a / 4\) 都是一个道理 a < b 此时显然可以知道你只会进行 \(a -&...