2017-Sp245-team2

从 Trac 迁移的文章

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

原文章内容如下：

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

== 流水账 ==
上午出门半小时cjb单打，然后yzc加入，到中午12点过9题跑路，后shb过了A保住第一。多校开始后，先看题，yzc读了E感觉很傻，上机'''E1y41'''，然后cjb上机写D，换yzc写F超时，之后cjb D wa了，yzc上机写F，'''F2y83'''。cjb继续猛wa D题，感觉是个智障。yzc上机写悬线法也wa了，双重签到失败。之后yzc找到了bug，变成tle后去掉了sort，'''H4y118'''。继续艹D，发现做法的本质错误，之后终于'''D6y144'''。sub上机'''A1y152'''，'''B1y183'''，yzc上机试了发C发现不仅tle了，甚至题意也是错的。之后sub写I，tle后展开优化常数'''I2y254'''，和咖啡鸡题数相同，输了罚时rk2。
=== chenjb ===
两训累累，这个D写到自己失去意识了有点不应该。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：n=1特判，其他情况在除0之外所有位置平分概率。

 * B：n=-1特判，其他情况直接用特征多项式优化矩乘递推。

 * C：cjb

 * D：经典的增量找k小模型，按权值从小到大重标号，初始将最小点加入优先队列，之后每次取出权值最小的S，转移考虑把权值最大的点记为maxp，考虑把maxp改成maxp后第一个可加入团的点，或者考虑加入和S一起，maxp之后第一个成团的点，不断直到生成第k小，注意空集也是一种。

 * E：线段树维护矩乘。

 * F：暴搜，枚举每个人放在哪一边，在放的时候就把自己后面的人选某一边的贡献给确定下来，这样跑得比较快。

 * G：sub

 * H：悬线法

 * I：枚举所有横线，一共4条，变成f[i][0/1/2][0/1/2]代表第一个矩形，第二个矩形的出现状态，循环展开优化常数即可。

 * J：yzc

流水账

上午出门半小时cjb单打，然后yzc加入，到中午12点过9题跑路，后shb过了A保住第一。多校开始后，先看题，yzc读了E感觉很傻，上机E1y41，然后cjb上机写D，换yzc写F超时，之后cjb D wa了，yzc上机写F，F2y83。cjb继续猛wa D题，感觉是个智障。yzc上机写悬线法也wa了，双重签到失败。之后yzc找到了bug，变成tle后去掉了sort，H4y118。继续艹D，发现做法的本质错误，之后终于D6y144。sub上机A1y152，B1y183，yzc上机试了发C发现不仅tle了，甚至题意也是错的。之后sub写I，tle后展开优化常数I2y254，和咖啡鸡题数相同，输了罚时rk2。

chenjb

两训累累，这个D写到自己失去意识了有点不应该。

oipotato

subconscious

题解

• A：n=1特判，其他情况在除0之外所有位置平分概率。
• B：n=-1特判，其他情况直接用特征多项式优化矩乘递推。
• C：cjb
• D：经典的增量找k小模型，按权值从小到大重标号，初始将最小点加入优先队列，之后每次取出权值最小的S，转移考虑把权值最大的点记为maxp，考虑把maxp改成maxp后第一个可加入团的点，或者考虑加入和S一起，maxp之后第一个成团的点，不断直到生成第k小，注意空集也是一种。
• E：线段树维护矩乘。
• F：暴搜，枚举每个人放在哪一边，在放的时候就把自己后面的人选某一边的贡献给确定下来，这样跑得比较快。
• G：sub
• H：悬线法
• I：枚举所有横线，一共4条，变成f[i][0/1/2][0/1/2]代表第一个矩形，第二个矩形的出现状态，循环展开优化常数即可。
• J：yzc

附加文件

• 1.png by chenjb