2017-Sp321-team2

从 Trac 迁移的文章

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

原文章内容如下：

== 流水账 ==
=== chenjb ===
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：将小于X的视为-1，大于的视为1，记为a，处理出数组b，bi表示ai和ai-1是否不同。每次可以从b中删除两个相邻的1或者1个1，即动态维护b数组中每段1的个数/2上取整，线段树维护即可。

 * B：显然对于最优方案，按照x从小到大插入一定能满足。所以将x排序之后，f[i][j][k]表示前i个任务，第一级经验j，第二级k，注意j这一维能取到s1+s2，但是转移出去的时候必须小于s1。

 * C：sub

 * D：如果没有字母数量超过n，则直接升序输出；否则拆成两段，中间需要填两段不同的字母，可以把剩余字母升序排，然后第一段放1个字母，第二段放其余字母，注意判掉做不到的情况。

 * E：枚举几个老司机，前缀和后缀和预处理，需要和贡献的年龄，更新答案即可。

 * F：图上行走问题结论：若存在完美匹配，后手必胜。自底向上贪心即可。

 * G：极大值直接可以填的位置填满，极小值考虑每一层，构造一个对角线加一条直线即可。

 * H：

 * I：问题可以转化成A取一个，B再取一个的答案。

 * J：显然每个人的所有边需要两两匹配，排序之后相邻匹配即可。

 * K：

流水账

chenjb

oipotato

subconscious

题解

• A：将小于X的视为-1，大于的视为1，记为a，处理出数组b，bi表示ai和ai-1是否不同。每次可以从b中删除两个相邻的1或者1个1，即动态维护b数组中每段1的个数/2上取整，线段树维护即可。
• B：显然对于最优方案，按照x从小到大插入一定能满足。所以将x排序之后，f[i][j][k]表示前i个任务，第一级经验j，第二级k，注意j这一维能取到s1+s2，但是转移出去的时候必须小于s1。
• C：sub
• D：如果没有字母数量超过n，则直接升序输出；否则拆成两段，中间需要填两段不同的字母，可以把剩余字母升序排，然后第一段放1个字母，第二段放其余字母，注意判掉做不到的情况。
• E：枚举几个老司机，前缀和后缀和预处理，需要和贡献的年龄，更新答案即可。
• F：图上行走问题结论：若存在完美匹配，后手必胜。自底向上贪心即可。
• G：极大值直接可以填的位置填满，极小值考虑每一层，构造一个对角线加一条直线即可。
• H：
• I：问题可以转化成A取一个，B再取一个的答案。
• J：显然每个人的所有边需要两两匹配，排序之后相邻匹配即可。
• K：