2020-team1-067

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team1 返回]
== 概述 ==
solved: 8/10  dirt: 43%
rank: 8
[[Image(Rank.png,800px)]]
== 总结 ==

== 题解 ==
A: 二分线段树
B: 矩阵一定不改变可行性，行互不相同列互不相同一定不改变可行性，根据关系判断相对位置，最后把能收缩的列收缩掉。
C: 枚举
D: 枚举点对(x,y)，考虑x对y的贡献的期望，显然是1/m，m是x到y的链上的点数，那么就是需要对于每个x，统计距离为x的点对的数量，这个东西点分fft
E: 
F: 举个n=8的例子：a5-a1-a6-a2-a7-a3-a8-a4；n=7的例子：a4-a1-a5-a2-a6-a3-a7-a4，这里是个环，需要把最小的diff给cut掉
G: 从第1小推到第k小，用堆维护
H: 
I: n=2特判，找个deg>1的点做根，树上贪心+讨论
type=0：未匹配时不会答案+1；type=1：未匹配时会答案+1；type=-1：已匹配
叶子->type=0
答案+=type=(0/1孩子数-1)/2
奇数type=0/1孩子且没有type=0孩子->type=1
奇数type=0/1孩子且有type=0孩子->type=0
偶数type=0/1孩子且没有type=0孩子->type=-1，答案+=1
偶数type=0/1孩子且有type=0孩子->type=1
根type=1->答案+=1
J: 先考虑移走1，拼出最长的0，然后用剩余的步数把0移进来，和0的总数取个min，那么我们枚举每个右端点，考虑和每个左端点组成的区间内所有1全部移走的代价，再拿询问的步数减去这个代价作为额外的0加进来，这个东西可以对每个询问用单调栈搞一搞，需要精细的实现？

[/wiki/2020-team1 返回]

概述

solved: 8/10 dirt: 43%

rank: 8

总结

题解

A: 二分线段树

B: 矩阵一定不改变可行性，行互不相同列互不相同一定不改变可行性，根据关系判断相对位置，最后把能收缩的列收缩掉。

C: 枚举

D: 枚举点对(x,y)，考虑x对y的贡献的期望，显然是1/m，m是x到y的链上的点数，那么就是需要对于每个x，统计距离为x的点对的数量，这个东西点分fft

E:

F: 举个n=8的例子：a5-a1-a6-a2-a7-a3-a8-a4；n=7的例子：a4-a1-a5-a2-a6-a3-a7-a4，这里是个环，需要把最小的diff给cut掉

G: 从第1小推到第k小，用堆维护

H:

I: n=2特判，找个deg>1的点做根，树上贪心+讨论

type=0：未匹配时不会答案+1；type=1：未匹配时会答案+1；type=-1：已匹配

叶子->type=0

答案+=type=(0/1孩子数-1)/2

奇数type=0/1孩子且没有type=0孩子->type=1

奇数type=0/1孩子且有type=0孩子->type=0

偶数type=0/1孩子且没有type=0孩子->type=-1，答案+=1

偶数type=0/1孩子且有type=0孩子->type=1

根type=1->答案+=1

J: 先考虑移走1，拼出最长的0，然后用剩余的步数把0移进来，和0的总数取个min，那么我们枚举每个右端点，考虑和每个左端点组成的区间内所有1全部移走的代价，再拿询问的步数减去这个代价作为额外的0加进来，这个东西可以对每个询问用单调栈搞一搞，需要精细的实现？

附加文件