暴力出奇迹，贪心能A题。
从做题顺序开始说：
C.BZOJ4010: [HNOI2015]菜肴制作
这里有两道看起来十分相似的题目：
我们对比一下这两道题目：
查错要求：求一个拓扑序，使得字典序尽可能小。
拓扑编号要求：求一个拓扑序，使得1尽量往前，在此情况下，2尽量往前。一次类推。
需要注意，这两个要求肯定是不同的。
例如在拓扑编号中 4 1 2 3 5是比 3 1 4 2 5 （当然不一定合法）优的，因为2的位置比较靠前。
我们分别来叙述这两个问题的解法：
查错 只要按正常的拓扑排序，只不过把queue改成priority_queue即可。正确性显然。
拓扑编号 我们反向拓扑排序，每次取出出度为0的最大的节点，标号，然后用它去更新其他点的出度。
这个算法的证明我是在这里看到的：算法证明
这里再口胡一下：
不妨认为我们这样得到的不是最优解，那么令这样得到的序列为a，然后最优解是b。
我们从后往前开始找到第一位两个序列不同的一位设为k，那么a[k]!=b[k]，且a[k]>b[k]。（由a的构造方式可知）（先假设这个k存在，再证出矛盾）
再设a[k]出现的b的p位置，即b[p]=a[k]。再设b[p] b[p+1]……b[k]这个子序列为C。
那么b[p]一定不是C中的最小元素，因为有b[k]<b[p]=a[k]。
然后不妨设b[q]为C的最小元素。然后我们把b[p]移到b[k]的位置，得到序列bb。
如果bb合法的话，那么我们就得到了一个比b优的解，这与b是最优解矛盾。
（因为b[q]的位置前移了一位，我们要求编号小的尽可能靠前）
但bb显然是合法的。因为在a序列中k以及后面的是合法的，那么b后面也这么做一定也是合法的。
所以一定不存在某个k，使得a[k]!=b[k]。也就是说a=b。
所以算法正确性得证。（证法和链接里有点不一样，但我认为也是正确的）
B.BZOJ4009: [HNOI2015]接水果
丽洁姐姐的题。丽洁已经给今年省选出了5道树的题目了【捂脸熊】
ZJOI之后，我坚信暴力可以过丽洁的题。于是用暴力水了这题70分。虽然写挂了只有30分
暴力的话就事先将边排序，然后对于每个询问扫，扫到第k个它所包含的线段的时候break。判断是否包含用dfs序可以做到O（1）。
我们来看正解：
单个询问是满足二分性质的，假设当前二分的值为mid，那么就把权值<=mid的路径进行覆盖，然后看看完全覆盖该询问的路径数是否超过k。然后调整上下界。
单个询问就去二分这样显然复杂度太高，我们可以采用整体二分。（这个考场上真没想到，还是脑洞太小）
然后问题就是我们要实现插入一些路径，然后询问一些路径完整包含了多少条路径。
我们可以把一条路径用两个端点的dfs序标号来表示成二元组（a，b），从而将一条路径映射到一个二维平面上，而完整覆盖它的路径的二元组也可以表示成a∈[l1,r1],b∈[l2,r2]的形式，这就对应了二维平面上的一个矩形。（矩形怎么求这个问题之后细说）
，当然它完整覆盖的路径也可以表示成这样的形式。妈呀一条路径完整覆盖的路径的二元组好像不能表示成这样。
所以我们把能覆盖每个盘子的矩形区域内的店的权值全部++，然后我们只要判断询问的二元组的所在的该点的权值与它的k的关系就可以进行分配，然后进入下一层递归。
这样我们就把问题转化成了 在一个二维平面上进行 矩形加 然后 单点求值的问题。
这个问题可以用差分+树状数组+（扫描线？）解决。具体来说就是：
我们把（x，y，l，r）的+1操作先拆成（x，l，r，1）的操作和（y+1，l，r，-1）的操作。（-1类似）
然后把询问和操作都按照x轴排序。
每到一个x再把（x，l，r）的操作拆成（l，1）和（r+1，-1）的操作。然后这就只是个一维树状数组。容易看出这时前缀和y就代表 二元组（x，y）的权值。
（实际上这就是个二维差分，a[x][y]表示给[x,n][y,n]这个矩形区域整体加上的权值，而树状数组里表示的是a[x][y]的前缀和，即sigma（a[1……x][y])然后我们查询（x，y）的值就只需要求a[1……x][1……y]也就是树状数组的前y项和。突然发现这样差分好像很优越啊）
然后我们还剩下两个问题：
1）时间复杂度？我们总共递归log1e9层，然后每层的复杂度都是nlogn，所以总的复杂度是O(nlognlog1e9）。
2）如何将完整覆盖一条路径的所有二元组表示成a∈[l1,r1],b∈[l2,r2]的形式？
我们不妨认为该路径左端点为x，右端点为y。并且l[x]<l[y]。我们默认所有的二元组都按（l[x],l[y])的方式以及顺序存储。
那么如果x-y不是一条链的话。
其中l[x]表示进入x时的时间戳，r[x]表示离开x时的时间戳。（当然时间戳只在进来的时候++）
我们所求的路径的二元组就是形如a∈[l[x],r[x]],b∈[l[y],r[y]]。这很显然。
否则那么x是y的祖先，令z为x的出边中指向y的方向的这个点，那么
a∈[1,l[z]-1],b∈[l[y],r[y]] 以及 a∈[l[y],r[y]],b∈[r[z]+1],n] 都是完整覆盖该路径的二元组。
这是因为首先必须有一个端点在y的子树内，并且另一个端点不能在z的子树内，而整个dfs序实际上被z的子树分成了[1,l[z]-1]和[r[z]+1],n]这两部分
所以这两个矩形区域就是我们所求区域。
然后这题就做完了。
A.4011: [HNOI2015]落忆枫音
这道题考试的时候我根本不会做。。。想了枚举父亲但不知道为啥觉得很麻烦就弃疗了 于是打了20分的爆枚边。。。
事后看了题解发现DAG的生成树的个数就是除1以外的所有点的入度乘积！
证明其实很简单的。。。
一个2-n的父亲序列代表了一棵生成树，因为每个节点可以任意选择有边连向它的节点作为父亲而不受其他节点的影响，所以不同的序列个数就是所有点入度的乘积！！！
考场上真是智商不够用
然后这道题是求在DAG上加入一条边之后的生成树的个数（忽然意识到好像不能叫生成树，这是有向边
，算了，先这么叫）
我们如果直接套用上面的结论发现多计数了一下，多记了哪些呢？
就是出现了环，并且环一定包含新加的这条边，不妨设这条边是s到t。
那么我们多计数的就是一个环&&一棵不满n个点的生成树这种情况。
而这个环就一定有着从t到s的路径。
那么如果某个环所包含的集合是s（环的点数相同，但是边不一样算不同的环，好像不会出现这种情况？），那么这样的情况我们多记的是 剩下所有点的入度之积。
那么我们枚举这个环，累加答案。当然不行。环的数量很多。考虑继续挖掘题目的性质
因为这个环一定包含s到t这条边，所以这样的一个环实际上是和t到s的路径一一对应的。
而因为这是张拓扑图，我们就可以按拓扑序DP了。因为按拓扑序来DP可以求出从某个点到i的所有路径条数，稍微修改一下类似我们就可以求解这个问题。
然后剩下的应该就不是什么问题了。
这题主要在于能够想出上面的结论以及想到通过DP来计算不合法的方案数。Orz！
这大概是我目前写的最长的博文了？主要是因为我太能废话了HNOI的题目水平太高了
评论 (0)
