翻译 题目描述 给你一棵树，和它的树根 $P$，并且节点从 $1\rightarrow n$ 编号，现在定义 $f(i)$ 为 $i$ 的子树中，节点编号小于 $i$ 的节点的个数。 输入格式 有多组数据 (不超过 10 组)，对于每组数据： 第一行两个整数 $n,p$ $(n\le 10^5)$ 表示树有 $n$ 个节点，树根是 $p$。 接下来的 $n-1$ 行，每行两个整数，代表一条树边。 输入以两个零作为结束。 输出格式 对于每组测试数据，输出一行 $n$ 个整数 $f(1),f(2)……f(n)$，每两个数字之间以一个空格分格。 解题思路 显然，我们想要求 $f(i

解题思路 首先肯定是要二分答案的嘛，因为要最大化最小值啊。 那如何判断一个答案是否可行呢？ 我们只需要先对一行进行判断，如果能将这一行分成大于等于 $mid$ (二分出来的答案) 的蛋糕 $B$ 块以上，就证明这一行可以单独劈成一条，如果不行的话，就和下一行一起放在一条中去判断，还不行的话就在加一行，观察一下，这样子分出来的条数是极限情况，也就是说，如果还不能分成大于等于 $A$ 条的话，那就不可能行了。反之，如果到最后大于等于 $A$ 条，那这个答案就是可行的。 中间的过程可以加入二维前缀和优化。 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1

解题思路 既然是最小化最大值，那就二分答案啊。 每次用0/1背包判断能否满足题目中给出的条件。那岂不是很简单喽。 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include #include #include #include using namespace std; const int maxn = 1003; int n, p,

阅读全文 »

解题思路 一开始自己想了一个贪心，虽然贪心的主要思路是对的，但并不会统计游客用的旅行时间。所以就去题解里面看看，第一篇是最小费用最大流，会比较麻烦，所以就去看了看底下的贪心，第一篇贪心被卡掉了，看第二篇，嗯，好像还行。再看看第三篇，写的好简略。不过看懂了。 贪心的主要思路就是在经过游客最多的路上使用加速器，但是还要注意，如果在一条路径的终点，有的游客到达的时间比现在公交车到达的时间还要晚的话就没必要用加速器了，因为再早到达你也必须等着游客上车吧。 考虑用优先队列保证得到最大的价值（经过的游客的数量），如果有一个点满足下面的条件： 最晚到达的乘客的到达时间比公交车的到达时间还要晚。

解题报告—9.21 $\text{T1}$ 相遇 反思 T1 考到了 LCA，之前觉得没必要学，虽然也看过些文章，但大部分都没看懂，所以一直都不会，结果今天出上了这样的一道题，真尴尬，想着写写暴力吧，发现暴力也是求 LCA，无奈，遂放弃，考完试的下午就开始学 LCA，以后有能力学的东西尽量学学，不能老想着偷懒。 解题思路 画几个图会发现 $a\rightarrow b,c\rightarrow d$ 两条路径如果能够相交的话，需要满足其中一对点的 $\text{LCA}$ 在另两个点之间的路径上。 而一个点 $x$ 在一条路径 $s\rightarrow t$ 上的

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub. Quick Start Create a new post 1 $ hexo new "My New Post" More info: Writing Run server 1 $ hexo s