2017-Sp111-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，sub表示几何题能做，就让他上机，'''K1y22'''。cjb和yzc讨论B，yzc上机写B，之后cjb和sub讨论之后上机写I，'''I2y56'''，yzc发现了位运算的bug，'''B2y78'''。cjb上机写H，输出方案搞了一会儿，'''H2y107'''。sub上机写构造题J，wa，yzc之前和sub讨论了L，上机wa。之后sub想到了正确构造，上机'''J2y144'''，sub帮yzc调试，'''L3y156'''。cjb之前搞D，然后丢锅给yzc爆搜打表，'''D1y222'''。之后大力猜了F结论，估计要java，sub上机写C++，还剩40min的时候调试过，cjb上机写java，后来一直忙于调试，结束后交了第一发。之后疯狂tle，卡了好久，各种预处理，记忆化，终于卡了过去。
== 总结 ==
=== chenjb ===
gtmASC，java卡时卡了一辈子，出个逆元取模多好啊....
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：

 * B：枚举开头数字，递归处理。

 * C：大力生成函数，k^2^求出生成函数，n^2^求出分母的前n项，n^2^求出分子和分母前n项的卷积，直接输出。

 * D：暴搜所有塔防情况，暴力模拟打表。

 * E：cjb

 * F：答案一定是顺序序列，状态是拆分数，预处理拆分数的转移数组，矩阵乘法即可，需要高精度，可用java，注意各种常数优化(如离线预处理)。

 * G：yzc

 * G：考虑每块电路除了s和t以外的点，我们希望保证这些点中连接s的点在左上角(0,0)，连接t的点在右下角(p_i,q_i)。串联电路i和电路j时，将电路j的所有点平移(p_i,q_i+1)格，得到的新电路k的右下角坐标为(p_i+p_j,q_i+q_j+1)。并联电路i和电路j时，将电路i所有点平移(0,q_j+1)格，将电路j所有点平移(p_i+1,0)格，然后新建点x(0,0),y(p_i+p_j+1,q_i+q_j+1)，得到新电路k。按输入顺序模拟创建每一块电路，最后先输出起点s(-1,0)，然后按顺序输出电路n的每一个点，最后输出终点t(p_n+1,q_n)。 (by NJU)

 * H：S向i连Ai，i向T连Bi，i向j连ci，然后跑最小割，注意最小割输出方案应该取沿非满流边dfs，走到的满流边即割的位置，分成属于S(T)的集合。

 * I：显然按ti排序，f[i]表示前i个人的最小时间，f[i]+(n-i)*j -> f[j]

 * J：n=3时一种颜色，n<=6时两种颜色，到首都的用1212交替，环上用3号颜色即可。

 * K：对两个点分别在凸包上绕一圈，统计答案即可。

 * L：找到两棵树之间先序遍历中第一个不同的位置，在此之前的节点可以保留，在此之后的必须全部删掉。

流水账

开场各自看题，sub表示几何题能做，就让他上机，K1y22。cjb和yzc讨论B，yzc上机写B，之后cjb和sub讨论之后上机写I，I2y56，yzc发现了位运算的bug，B2y78。cjb上机写H，输出方案搞了一会儿，H2y107。sub上机写构造题J，wa，yzc之前和sub讨论了L，上机wa。之后sub想到了正确构造，上机J2y144，sub帮yzc调试，L3y156。cjb之前搞D，然后丢锅给yzc爆搜打表，D1y222。之后大力猜了F结论，估计要java，sub上机写C++，还剩40min的时候调试过，cjb上机写java，后来一直忙于调试，结束后交了第一发。之后疯狂tle，卡了好久，各种预处理，记忆化，终于卡了过去。

总结

chenjb

gtmASC，java卡时卡了一辈子，出个逆元取模多好啊....

oipotato

subconscious

题解

A：
B：枚举开头数字，递归处理。
C：大力生成函数，k²求出生成函数，n²求出分母的前n项，n²求出分子和分母前n项的卷积，直接输出。
D：暴搜所有塔防情况，暴力模拟打表。
E：cjb
F：答案一定是顺序序列，状态是拆分数，预处理拆分数的转移数组，矩阵乘法即可，需要高精度，可用java，注意各种常数优化(如离线预处理)。
G：yzc
G：考虑每块电路除了s和t以外的点，我们希望保证这些点中连接s的点在左上角(0,0)，连接t的点在右下角(p_i,q_i)。串联电路i和电路j时，将电路j的所有点平移(p_i,q_i+1)格，得到的新电路k的右下角坐标为(p_i+p_j,q_i+q_j+1)。并联电路i和电路j时，将电路i所有点平移(0,q_j+1)格，将电路j所有点平移(p_i+1,0)格，然后新建点x(0,0),y(p_i+p_j+1,q_i+q_j+1)，得到新电路k。按输入顺序模拟创建每一块电路，最后先输出起点s(-1,0)，然后按顺序输出电路n的每一个点，最后输出终点t(p_n+1,q_n)。 (by NJU)
H：S向i连Ai，i向T连Bi，i向j连ci，然后跑最小割，注意最小割输出方案应该取沿非满流边dfs，走到的满流边即割的位置，分成属于S(T)的集合。
I：显然按ti排序，f[i]表示前i个人的最小时间，f[i]+(n-i)*j -> f[j]
J：n=3时一种颜色，n<=6时两种颜色，到首都的用1212交替，环上用3号颜色即可。
K：对两个点分别在凸包上绕一圈，统计答案即可。
L：找到两棵树之间先序遍历中第一个不同的位置，在此之前的节点可以保留，在此之后的必须全部删掉。

附加文件

1.png by chenjb