2017-Sp307-team2

从 Trac 迁移的文章

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

原文章内容如下：

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

== 流水账 ==
=== chenjb ===
罚时炸穿，进度拖沓，主要在我的F，一开始sub给了假题意，后面tle和wa，然后找重心的剪枝写错了....但是最后1h，我开出D丢给yzc，sub帮忙抠细节，我继续读F代码，封榜后过3题还是不错的，但是我不希望徐州有这种事情.....
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：显然是倒序对应，按要求输出。

 * B：f[i][0/1/2]表示i不是某条链一端、是某条链一端但是儿子里没有某条链一端、是某条链一端但是儿子里有某条链一端，转移比较麻烦。

 * C：x或y不在同一联通块显然平面亦然，分类讨论即可。

 * D：把行和列拿出来和询问串分别插入SA，这样对于每个询问串枚举断点，就可以得到在两个SA的区间，提前处理好第二个SA中每个位置映射到第一个中的位置，建主席树处理询问。

 * E：从后往前维护每个点可行区间，第一个人直接取可行的下界，后面每次贪心取出最小的，调整到可行区间内。

 * F：显然只能是重心，用无根树hash判定即可。

 * G：这个人会不会在第i天被裁员，等价于第i天要裁员的人数量-第i天以前留下的比它小的人的数量是否大于0，修改单点相当于在后缀上修改，线段树维护即可。

 * H：第二类显然，第一类把较小维放前面，然后直接从大到小扫一遍即可，然后对于每个人把两维交换，lower_bound一下即可，注意两维相等时候不要算进贡献。

 * I：sub

 * J： f[0/1][i][j][k]代表到第i个石头是否被用，用了j个石头，k是奇数区间数量的方案是否存在，贡献贪心讨论。

 * K：线段树维护矩阵乘法。

 * L：抠出环出来，网络流。

流水账

chenjb

罚时炸穿，进度拖沓，主要在我的F，一开始sub给了假题意，后面tle和wa，然后找重心的剪枝写错了....但是最后1h，我开出D丢给yzc，sub帮忙抠细节，我继续读F代码，封榜后过3题还是不错的，但是我不希望徐州有这种事情.....

oipotato

subconscious

题解

• A：显然是倒序对应，按要求输出。
• B：f[i][0/1/2]表示i不是某条链一端、是某条链一端但是儿子里没有某条链一端、是某条链一端但是儿子里有某条链一端，转移比较麻烦。
• C：x或y不在同一联通块显然平面亦然，分类讨论即可。
• D：把行和列拿出来和询问串分别插入SA，这样对于每个询问串枚举断点，就可以得到在两个SA的区间，提前处理好第二个SA中每个位置映射到第一个中的位置，建主席树处理询问。
• E：从后往前维护每个点可行区间，第一个人直接取可行的下界，后面每次贪心取出最小的，调整到可行区间内。
• F：显然只能是重心，用无根树hash判定即可。
• G：这个人会不会在第i天被裁员，等价于第i天要裁员的人数量-第i天以前留下的比它小的人的数量是否大于0，修改单点相当于在后缀上修改，线段树维护即可。
• H：第二类显然，第一类把较小维放前面，然后直接从大到小扫一遍即可，然后对于每个人把两维交换，lower_bound一下即可，注意两维相等时候不要算进贡献。
• I：sub
• J： f[0/1][i][j][k]代表到第i个石头是否被用，用了j个石头，k是奇数区间数量的方案是否存在，贡献贪心讨论。
• K：线段树维护矩阵乘法。
• L：抠出环出来，网络流。

附加文件

• 1.png by chenjb