2017-Sp103-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自读题，sub上机'''K1y4'''，yzc上机'''D1y8'''。cjb开J，上机初被sub打断，sub上机'''H2y33'''。cjb写J，'''J1y71'''。cjb写J的时候丢了个dp给yzc，yzc之后上机'''G1y90'''。sub上机写E，获得wa，cjb和yzc讨论完了A，yzc上机写A，wa后双哈希tle，之后卡了常数，期间E依然wa，'''A4y176'''。之后cjb和yzc讨论C，yzc上机写C发现复杂度不对，让sub丢了个四边形不等式wa，之后讨论得到一个贪心还是wa，最后发现贪心不行，还是要dp，但是决策点在两边，'''C5y244'''。最后一起刚E，疯狂提交，始终wa。
== 总结 ==
=== chenjb ===
前期很顺利，C感觉傻逼了，E大坑逼.....用map的时候，有时候要记得erase掉，而不是留着一个0值。
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：f[i][j]表示在第i张图上j的连通块编号，把每个点在每个图的编号哈起来，哈希值相同说明连通，对于每个图启发式合并维护哈希值，双哈希时要考虑常数。

 * B：cjb

 * C：每一次将当前要取的区间切成连续取的几个区间，递归处理，对于这一层的几个区间，dp，转移时只取两边即可。

 * D：倍增。

 * E：偏导，拉格朗日乘数法，得到一个小于0的概率则丢掉该物品。

 * F：???

 * G：f[i][0/1]表示前i个数字中第i个数字属于上升/下降，下降/上升序列的最大/最小值。

 * H：枚举质数，只有2sqrt(a)个区间，统计即可。

 * I：yzc

 * J：原点向任务连ci的边，把时间点离散后，对于每个段向汇点连时间长度*m的流量，对于每个任务向合法区间连该区间长度的流量，跑出来满流就是合法。

 * K：t为奇数时翻转数组，否则直接输出即可。
== 补题 ==

流水账

开场各自读题，sub上机K1y4，yzc上机D1y8。cjb开J，上机初被sub打断，sub上机H2y33。cjb写J，J1y71。cjb写J的时候丢了个dp给yzc，yzc之后上机G1y90。sub上机写E，获得wa，cjb和yzc讨论完了A，yzc上机写A，wa后双哈希tle，之后卡了常数，期间E依然wa，A4y176。之后cjb和yzc讨论C，yzc上机写C发现复杂度不对，让sub丢了个四边形不等式wa，之后讨论得到一个贪心还是wa，最后发现贪心不行，还是要dp，但是决策点在两边，C5y244。最后一起刚E，疯狂提交，始终wa。

总结

chenjb

前期很顺利，C感觉傻逼了，E大坑逼.....用map的时候，有时候要记得erase掉，而不是留着一个0值。

oipotato

subconscious

题解

• A：f[i][j]表示在第i张图上j的连通块编号，把每个点在每个图的编号哈起来，哈希值相同说明连通，对于每个图启发式合并维护哈希值，双哈希时要考虑常数。
• B：cjb
• C：每一次将当前要取的区间切成连续取的几个区间，递归处理，对于这一层的几个区间，dp，转移时只取两边即可。
• D：倍增。
• E：偏导，拉格朗日乘数法，得到一个小于0的概率则丢掉该物品。
• F：???
• G：f[i][0/1]表示前i个数字中第i个数字属于上升/下降，下降/上升序列的最大/最小值。
• H：枚举质数，只有2sqrt(a)个区间，统计即可。
• I：yzc
• J：原点向任务连ci的边，把时间点离散后，对于每个段向汇点连时间长度*m的流量，对于每个任务向合法区间连该区间长度的流量，跑出来满流就是合法。
• K：t为奇数时翻转数组，否则直接输出即可。

补题

附加文件

• 1.png by chenjb