2017-Sp246-team2

从 Trac 迁移的文章

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

原文章内容如下：

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

== 流水账 ==
出门各自看题，sub上机写H，'''H1y15'''，之后sub猜了个结论I wa，yzc让cjb敲了个tarjan干B，结果做法是错的。sub fix了做法，签了I和L，'''I3y41'''，'''L1y63'''。cjb上机写M，中途sub丢了F给yzc，'''F3y103'''，之后'''M2y108'''。sub上机'''E120'''，cjb上机敲lct，yzc '''A1y136'''。之后yzc上机写D，'''D3y159'''。sub上机G1y166。分别开题，开出了J和B和K，yzc上机写J，'''J2y242'''，cjb上机写B，sub上机写K，赛后20分钟都过了，比较可惜。
=== chenjb ===
封榜后想B和K同时写还是过于冒进，主要是没有预料到B的样例十分难调，以及sub的K听他表达起来还是很好写的。求稳的话，B肯定是能过的，单写K也是这样，封榜后没有完全估计清楚形势。另外这个M和詹哲远聊过之后增进了理解，以后要记好。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：lct模板题

 * B：先把每个点向四个方向最后能到的点连边，tarjan缩点，显然上下和左右分别为同一个强连通分量，每个星星必须属于其中一个，因此规约成2-sat问题。考虑任意两个强连通分量的可达性，以及起点到这些点的可达性，最后考虑每个星星必须属于上下或者左右之一，跑2-sat判定即可。

 * [https://petr-mitrichev.blogspot.com/2018/12/a-rolling-week.html Petr做法和上述相同]

 * C：sub/cjb

 * D：拓扑排序，每次选取l到达要求的点中，后继节点r最小的那个。

 * E：每次把重边并起来，度数为2的点可以消成1条边，最后消成1条单边即成功。

 * F：从n出发，每次扩展n/2和(n+1)/2。

 * G：f[i][0/1/2][j][k]代表目前到i，最后第i块0代表没有，1代表被覆盖，2代表本身是光照点，j和k分别代表没有被点亮和将被点亮分别移了多少个。

 * H：枚举化简之后的分数，直接计算会出现多少次。

 * I：一刀分成两个多边形，按定义计算sg函数。

 * J：对于每个高度，找到他作为最低高度的支配区间，则所有方案都被包含在了n个支配区间中，先二分答案，求出l的答案，过程中需要用到计算方案数的函数f(u,v,len)表示最低的高度在当中，左边还有u列，右边还有v列，选出长度小于等于len的并且一定跨中心的方案数。得到l的答案之后，再推出每个人取掉前l-1个面积之后，当前的矩形宽度和剩余方案数，从l枚举到r，每次从n个当中选择面积最小的，如果选走了最后一个，就把对应宽度+1，再计算方案数，取最小这一步用堆维护。

 * K：f[i][j]代表目前吃药区间是(i,j)的最大值，倒过来做是O(n^2^)，注意到只有O(n)个关键点，把关键点取出来数星星。

 * L：暴力做出1到n的答案，预处理连续不下降或上升的最长距离，复杂度是O(nlogn)的。

 * M：二分一个值加到边权上，然后用dp跑最大权匹配。注意考虑在凸壳上二分，共线的点可能只会取到其中一端，此时答案是正确，但是检验的话可能边数量不符合，另外要保证二分的方式不会使得二分到该直线的时候被跳掉，事先要用inf判不可能，而不能事后检查。

流水账

出门各自看题，sub上机写H，H1y15，之后sub猜了个结论I wa，yzc让cjb敲了个tarjan干B，结果做法是错的。sub fix了做法，签了I和L，I3y41，L1y63。cjb上机写M，中途sub丢了F给yzc，F3y103，之后M2y108。sub上机E120，cjb上机敲lct，yzc A1y136。之后yzc上机写D，D3y159。sub上机G1y166。分别开题，开出了J和B和K，yzc上机写J，J2y242，cjb上机写B，sub上机写K，赛后20分钟都过了，比较可惜。

chenjb

封榜后想B和K同时写还是过于冒进，主要是没有预料到B的样例十分难调，以及sub的K听他表达起来还是很好写的。求稳的话，B肯定是能过的，单写K也是这样，封榜后没有完全估计清楚形势。另外这个M和詹哲远聊过之后增进了理解，以后要记好。

oipotato

subconscious

题解

A：lct模板题
B：先把每个点向四个方向最后能到的点连边，tarjan缩点，显然上下和左右分别为同一个强连通分量，每个星星必须属于其中一个，因此规约成2-sat问题。考虑任意两个强连通分量的可达性，以及起点到这些点的可达性，最后考虑每个星星必须属于上下或者左右之一，跑2-sat判定即可。
Petr做法和上述相同
C：sub/cjb
D：拓扑排序，每次选取l到达要求的点中，后继节点r最小的那个。
E：每次把重边并起来，度数为2的点可以消成1条边，最后消成1条单边即成功。
F：从n出发，每次扩展n/2和(n+1)/2。
G：f[i][0/1/2][j][k]代表目前到i，最后第i块0代表没有，1代表被覆盖，2代表本身是光照点，j和k分别代表没有被点亮和将被点亮分别移了多少个。
H：枚举化简之后的分数，直接计算会出现多少次。
I：一刀分成两个多边形，按定义计算sg函数。
J：对于每个高度，找到他作为最低高度的支配区间，则所有方案都被包含在了n个支配区间中，先二分答案，求出l的答案，过程中需要用到计算方案数的函数f(u,v,len)表示最低的高度在当中，左边还有u列，右边还有v列，选出长度小于等于len的并且一定跨中心的方案数。得到l的答案之后，再推出每个人取掉前l-1个面积之后，当前的矩形宽度和剩余方案数，从l枚举到r，每次从n个当中选择面积最小的，如果选走了最后一个，就把对应宽度+1，再计算方案数，取最小这一步用堆维护。
K：f[i][j]代表目前吃药区间是(i,j)的最大值，倒过来做是O(n²)，注意到只有O(n)个关键点，把关键点取出来数星星。
L：暴力做出1到n的答案，预处理连续不下降或上升的最长距离，复杂度是O(nlogn)的。
M：二分一个值加到边权上，然后用dp跑最大权匹配。注意考虑在凸壳上二分，共线的点可能只会取到其中一端，此时答案是正确，但是检验的话可能边数量不符合，另外要保证二分的方式不会使得二分到该直线的时候被跳掉，事先要用inf判不可能，而不能事后检查。

附加文件

1.png by chenjb