比赛的时候脑子糊了，简单结论题没想出来，最后乱搞了个二分过的（（ 思路 每次二分一个答案 \(x\) 。 那么 \(x\) 之前无法算进答案的数的个数显然是 \(\lfloor \frac{x}{n} \rfloor\) 所以若答案是 \(x\) ，则在它之前符合条件的数就是 \(x -\lfloor \frac{x}{n} \rfloor\) 每次判断一下在它之前符合条件的数是否大于等于 \(k\) 即可。 Code #include<iostream> #include<algorithm> #include<cstring> #inclu...

题目翻译 有一棵 \(n\) 个节点的树 ( $n \le 2 \times 10^5 $ )，现在要求选出 \(k\) 个节点，使得这 \(k\) 个节点到根节点的最短路径中，每个节点经过的剩余 \(n-k\) 个节点的数量之和最大。 思路 注： 这里所说的 \(u\) 的子树不包含 \(u\) 本身。 \(dep\) 指深度，\(siz\) 指子树大小（包含子树的根）。 先 dfs 一遍，把树的深度和子树大小处理出来，然后贪心。 如果直接按照深度或者子树大小排序都是错的，这是因为新选一个节点可能会导致答案减小。所以我们需要一种更优的排序策略。 因为选 \(u\) 答...

思路： 先考虑如果序列的形态全部已知，如何在线性的时间内判断该序列能否合并超过 \(2^k\) 。 可以记录一个和 \(sum\) 表示当前可能继续合并的后缀的和，那么这个后缀一定是最长不上升的。 例如这个后缀：16 8 4 2 4 ，最后一个 \(4\) 因为上升，无法合并到前面的序列中，与之前隔绝，所以不能加到前面的 \(sum\) 中。 那么分类讨论： 如果填的是 \(2\) ，由于 \(2\) 是最小的数，那么一定不会上升，直接将 \(sum+=2\) 即可。 如果填的是 \(4\) ，且 \(sum\) 中没有单独的 \(2\) ，即 \(sum\) 可以整除 \(4...

题目翻译： 有 \(n\) 个红方块和 \(m\) 个蓝方块 \((n,m \le 10^5)\)，现在\(A\) 和 \(B\) 两个人轮流搭方块 \((A\) 先手 \()\)，如果上下两个方块颜色相同，则 \(A\) 得一分，否则 \(B\) 得一分。问 \(A\) , \(B\) 的最大可能得分分别是多少。 思路： 很显然： 对于 \(A\)，放与上次相同颜色的方块一定更优。 对于 \(B\)，放与上次不同颜色的方块一定更优。 综合上述结论，我们开始分析。 对于 \(A\)，一直到选了 \(\min(n,m) \times 2\) 个方块时，每次 \(A\) 都只有自己的放置...

题目大意： 给你两个数 \(a\) , \(b\) ( \(a\) , \(b\) \(\le\) \(10^9\) )，每次用大的减去小的，问当某个数为 \(0\) 时，一共减了多少次。 思路： 假设 \(a\) 为大的数，\(b\) 为小的数，且两数相差很大 那么 \(a\) 最后可能会变成 \(a-b-b-...-b\) 将 \(-b-b-...-b\) 合并，就可以得到 \(- k \times b(k\times b \le a\) 且 \(a-k\times b < b)\) 这个 \(k\) 其实就是 \(a\) 整除 \(b\) 的结果 。 所以 \(a-b-b-....

CF56E 【Domino Principle】 $ $ 题目翻译： 有 \(n\) ( \(n \le 10^5\) ) 个多米诺骨牌在一条直线上，给定他们的坐标 \(x\)和高度 \(h\) ( \(x\) 越大则越靠右) ，求出当第 \(i\) 个骨牌向右倒下时会有几个骨牌倒下。第 \(i\) 块骨牌能压倒的范围在 \([x_i+1,x_i+h_i-1]\) 之间。 需要注意的地方： 输入中骨牌的 \(x\) 值不一定有序 被压倒骨牌可能也会压倒其他骨牌 思路： 直接暴力算肯定会T，二分的话因为会有重复部分所以也不好做，因此考虑动态规划。 先按...

题目传送门 这是一道贪心题。 求出 \(k\) 其实很简单，因为每个节点的边每天最多只能修一条，所以答案就是度数最大的节点的度数（也就是边最多的节点的边数）。 重点在于怎么求方案。 因为题目中的树是一颗无根树，所以我们默认 \(1\) 号节点为他的根节点。 接下来我们开 \(k\) 个集合，表示第 \(i\) 天要修的路的编号（这里可以用 vector 实现）。 划重点 然后开始从 \(1\) 号节点 dfs ，每走到一个节点，就把 它与它父亲之间的路 与 它与所有儿子间的路 放在不同的集合中，因为这些边的修筑 必须都有该节点参与 ，但是由于该...

题解:P1018【乘积最大】 前言： 这题的题解里好多人都用的动态规划，我一个蒟蒻居然用暴力全排列AC了。。。 . 思路： 利用一个b数组标记每一位之间是否分割。 利用STL里的 next_permutation 求出b的各种排列（即暴力枚举每种情况）。 由于本题数据规模大，所以要使用高精度计算每种分割的最后结果，并找出最大。 . next_permutation函数: 即STL里的求全排列函数,所求的数组必须是升序，否则将无法求出全部的排列方式（这和它生成群排列的方式有关），next_permutation正常和sort一样，有2个参数，分别是数组的首地...