2017-Sp258-team2

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

 [[Image(1.png,500px)]]

== 流水账 ==
出门各自看题，sub口述题给cjb，cjb上机傻逼了，'''L3y15'''。sub上机写H，'''H1y33'''。sub写F，'''F1y63'''。cjb和yzc讨论E，上机'''E1y91'''。sub开出了B给cjb，cjb上机'''B3y131'''。sub上机写D,'''D1y186'''。yzc上机写K，'''K1y205'''。最后sub上机写J暴力，'''J1y265'''。最后rush A，tle了。
=== chenjb ===
总感觉最近做多校有点慢，自己签到罚时也有点多，不过我感觉A要想到正解可能还需要30min左右。
=== oipotato ===

=== subconscious  ===

== 题解 == 
 * A：造个最小割，S向监控相机连边，代价为hack他的代价，然后苹果节点向T连边，代表放弃这些苹果，然后相机向苹果连边代表依赖关系，费用inf，表示不能割。然后最小割=最大流，我们考虑f[i][j]表示i的子树里离i距离为j的节点能提供的流量，显然是按照距离降序来接收流量。用map存每个人子树里的f值，就能模拟这个最大流过程了。然后得到每个人对应的f，可以从儿子启发式合并过来。实际上，因为这个启发式合并关于深度，所以如果将树长链剖分，计算出每个点x子树内距离x最远的距离dep[x]，然后就将这个儿子继承给x，然后将别的儿子暴力插入，这样合并的复杂度就变成O(n)了，总共O((n+m)logn)。

 * B：倒着做，当且仅当删去的点是已确定最长子序列的一部分时暴力重找。

 * C：建一张n+1个点的图，点i代表前缀i的和。对于[l,r]的和，l-1和r连边，则如果该图连通，则所有人都能推出来。问题就变成从每个人那里拿k条边，图连通。反过来就是删除不超过c-k条边。删边后图连通等价于存在生成树，生成树是图拟阵的基，所以是图拟阵的对偶矩阵M1，每个边集不超过一定数量，则是划分拟阵M2。所以是要找到两个拟阵交的大小为Σ(c-k)的最大权值独立集，套用拟阵交解决...具体看claris的题解吧。

 * D：按照斜率排序，每次插入节点之后可以二分求得交于哪条xy线段上，闵可夫斯基和。

 * E：离散化后，枚举上边界，每次扩展用线段树维护最大子段和即可。

 * F：可以求出在每一个x或者y分成的段落内，mod 60=k分别有多少个，然后暴力计算合法性。

 * G：

 * H：k上下2^13^枚举。

 * I：将数字x拆成x个x，就能把问题转化成找k个不相交不下降子序列使得长度和最大，对此有个经典的杨氏图表做法，答案是最后形成的杨表前k行长度。这道题因为不能暴力拆解，所以考虑用map维护每一行的值和个数，插入后暴力往后消耗，往下传，每次插入至多使得一个人分裂并下传，所以是2^k^的。

 * J：赛场上用vector保留哪些有值的位置，合并注意break，合并结果sort后unique。实际做法是分根号内、外维护一个元素插入后结果，然后点分治树dp。

 * K：把问号取出来倒过来dp，维护目前前面已经填完了情况到这里余x还有多少方案，然后在这个数组上走即可。

 * L：排序后从大到小奇偶分配。

 * L for Ptz：考虑计算两人差值，注意到如果存在连续a,b,c满足b>=a,c，那么决策肯定是ac和b，所以可以把其变成一个a+c-b，考虑随机性，所以合并后的元素不会很多，于是用线段树储存各段线段结果，暴力取出后从两边贪心往里取即可，注意这样算出的是差值。

 * J for Ptz:  考虑计算前缀，后缀的合并结果，每个询问就是一个前缀和后缀的合并，所以只需要找到高效的合并方式即可。考虑一个区间[l,r]，在和别人合并的时候，只有两侧的点会有新的边，将它们称为关键点。显然，如果子树中没有关键点，那这棵子树就能永久的保持，就删掉，直接加进答案。对于连续的一些度为2的非关键点，显然这条链被替换一次之后，效果是最大边删掉，链断开为两端的关键点的子树，又可以删去，所以可以直接将链合并为两端关键点之间的一条边，边权为链上的最大值，其他值加进答案。这样处理之后，树上所有非关键点都是分叉点，那么非关键点数量最多为叶节点数量，也就是关键点数量，关键点数量为2N，所以树大小最多为4N。直接kruskal暴力合并即可，复杂度(M+Q)*NlogN。

流水账

出门各自看题，sub口述题给cjb，cjb上机傻逼了，L3y15。sub上机写H，H1y33。sub写F，F1y63。cjb和yzc讨论E，上机E1y91。sub开出了B给cjb，cjb上机B3y131。sub上机写D,D1y186。yzc上机写K，K1y205。最后sub上机写J暴力，J1y265。最后rush A，tle了。

chenjb

总感觉最近做多校有点慢，自己签到罚时也有点多，不过我感觉A要想到正解可能还需要30min左右。

oipotato

subconscious

题解

A：造个最小割，S向监控相机连边，代价为hack他的代价，然后苹果节点向T连边，代表放弃这些苹果，然后相机向苹果连边代表依赖关系，费用inf，表示不能割。然后最小割=最大流，我们考虑f[i][j]表示i的子树里离i距离为j的节点能提供的流量，显然是按照距离降序来接收流量。用map存每个人子树里的f值，就能模拟这个最大流过程了。然后得到每个人对应的f，可以从儿子启发式合并过来。实际上，因为这个启发式合并关于深度，所以如果将树长链剖分，计算出每个点x子树内距离x最远的距离dep[x]，然后就将这个儿子继承给x，然后将别的儿子暴力插入，这样合并的复杂度就变成O(n)了，总共O((n+m)logn)。
B：倒着做，当且仅当删去的点是已确定最长子序列的一部分时暴力重找。
C：建一张n+1个点的图，点i代表前缀i的和。对于[l,r]的和，l-1和r连边，则如果该图连通，则所有人都能推出来。问题就变成从每个人那里拿k条边，图连通。反过来就是删除不超过c-k条边。删边后图连通等价于存在生成树，生成树是图拟阵的基，所以是图拟阵的对偶矩阵M1，每个边集不超过一定数量，则是划分拟阵M2。所以是要找到两个拟阵交的大小为Σ(c-k)的最大权值独立集，套用拟阵交解决...具体看claris的题解吧。
D：按照斜率排序，每次插入节点之后可以二分求得交于哪条xy线段上，闵可夫斯基和。
E：离散化后，枚举上边界，每次扩展用线段树维护最大子段和即可。
F：可以求出在每一个x或者y分成的段落内，mod 60=k分别有多少个，然后暴力计算合法性。
G：
H：k上下2¹³枚举。
I：将数字x拆成x个x，就能把问题转化成找k个不相交不下降子序列使得长度和最大，对此有个经典的杨氏图表做法，答案是最后形成的杨表前k行长度。这道题因为不能暴力拆解，所以考虑用map维护每一行的值和个数，插入后暴力往后消耗，往下传，每次插入至多使得一个人分裂并下传，所以是2^k的。
J：赛场上用vector保留哪些有值的位置，合并注意break，合并结果sort后unique。实际做法是分根号内、外维护一个元素插入后结果，然后点分治树dp。
K：把问号取出来倒过来dp，维护目前前面已经填完了情况到这里余x还有多少方案，然后在这个数组上走即可。
L：排序后从大到小奇偶分配。
L for Ptz：考虑计算两人差值，注意到如果存在连续a,b,c满足b>=a,c，那么决策肯定是ac和b，所以可以把其变成一个a+c-b，考虑随机性，所以合并后的元素不会很多，于是用线段树储存各段线段结果，暴力取出后从两边贪心往里取即可，注意这样算出的是差值。
J for Ptz: 考虑计算前缀，后缀的合并结果，每个询问就是一个前缀和后缀的合并，所以只需要找到高效的合并方式即可。考虑一个区间[l,r]，在和别人合并的时候，只有两侧的点会有新的边，将它们称为关键点。显然，如果子树中没有关键点，那这棵子树就能永久的保持，就删掉，直接加进答案。对于连续的一些度为2的非关键点，显然这条链被替换一次之后，效果是最大边删掉，链断开为两端的关键点的子树，又可以删去，所以可以直接将链合并为两端关键点之间的一条边，边权为链上的最大值，其他值加进答案。这样处理之后，树上所有非关键点都是分叉点，那么非关键点数量最多为叶节点数量，也就是关键点数量，关键点数量为2N，所以树大小最多为4N。直接kruskal暴力合并即可，复杂度(M+Q)*NlogN。

附加文件

1.png by chenjb