2017-C05-team3

从 Trac 迁移的文章

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

原文章内容如下：

= 流水账 =
  今天还是只有两个人打，Johann学长继续鸽，今天大爆炸了。

  几个签到题都还挺顺的，然后reku看了A觉得好像步数似乎只有80，好像很简单的样子，跟lzw学长讨论了一下，lzw说了说其中一个部分的贪心，reku没有听的很清楚，但是lzw学长看上去很有自信，就让他去写。结果写一写发现有很多问题，甚至复杂度都不是非常合理。但是两个人想先把这个题变成TLE，然后在做下一步的打算（因为罚时已经很高，当时已经不在乎了）。然而A题一直在WA，最后五分钟才发现是字符串比较写错了。

  还有一个半小时的时候，也试图挽救一下比赛节奏。开了J题，但是reku和lzw理解的题意是信号不能被分割，这样好像并不能网络流。而且手上的A题也很难受，所以就没有接着讨论J，希望两个人能把A过掉，最后也没过，大爆炸。
= 总结 =

== reku ==
  比赛之后J题随便想想就想到了。感觉开题如果先开J的话，状态会好很多。A题卡的时间太久了，卡了两个多小时。其实做法本身就有问题，还是不想放弃题目。如果有三个人的话，另外两个人就能讨论开题了。
== lzw4896s ==
  今天大爆炸主要还是我的锅,A题reku学长发现步数最多只有80,状态数很少，用f[i][j]表示前i个数有序，花了j步能让第i个数最小能变成多少，时限有5秒，随便想了一个贪心的转移方法，感觉肯定能过。结果还是代码实现上出了很多很蠢的问题，浪费了很多的时间。 之前的CCPC网络赛也是代码实现上出了很多问题，感觉代码实现的能力还是有待加强，需要多做一些个人比赛提高短时间内写对代码的能力。 最后一个小时看J题感觉有两种题意，不确定是哪一种，手上还有A题没过掉，心里就很虚，根本没心思去想解法，所以就五题滚粗了。 和队友的配合上应该没什么问题，个人的基本功还是不够扎实。
== Johann ==

= 教训 =

= 题解 =
 * A: f[i][j]表示前i个数有序，花了j步能让第i个数最小能变成多少, 由于只有n个数,可以让每个数的前两位互不相同，所以最多花2n步,j最大是80. 转移的时候枚举需要改变次数k,问题转化为给出s1, s2,改变s2的k个数字使得s1 <= s2 且s2 尽可能小。  可以dp一下,dp[i]表示 使得s1[i...m] <= s2[i...m] 的最少步数，然后从左到右依次确定即可。  另外一种做法：dp[i][l][r][lim] 表示处理i...m列, l...r行, 且第i列的数字必须>=lim的最优解。   转移的时候枚举第i列 第l...p行全变成数字k, dp[i][l][r][lim] 由 dp[i + 1][l][p][0]  dp[i][p + 1][r][k + 1] 转移过来。时间复杂度O(100 * M * N^3)
 * B: 题目保证环的大小不会超过5. 那么对于每个强联通分量, 暴力算出内部两两之间的最长路, 然后把强连通分量的每个点拆成两个点, 一个点表示强联通分量的入口, 一个点表示出口。 建好新图后跑最长路即可。
 * D: 首先是如何还原树。 可以先随便拿两个点,形成一条链, 然后对于其他点，看一下它是应该连到这条链的哪个位置(即它应该是哪个子树)。对于每个子树再分别递归建树即可。  建好树之后，只要算出每条边对答案的贡献。 一条边上有len + 1个点, 分3种情况，一种是 边内部的len - 1个点互相之间的贡献，一种是内部的点连到外面，一种是外部的点跨过这条边。  需要额外增加的点数不超过n个。 因为不存在度为2的点，有n个叶子,假设增加了k个点, 那么有 n + 3*k <= 2 * (n + k - 1) 得到 k <= n - 2。
 * J: 网络流做法：建立分层图，每个管道的流量要么当天流掉，要么留到下一天(留到下一层图里相应的节点)。  贪心做法： 先模拟一遍，可以求出对于每个管道，有一些DDL(x, y), 表示在第i天前这个管道至少要释放y的容量。 然后再做一遍模拟，每次释放容量的时候，选择时间最近的DDL来满足。

流水账

今天还是只有两个人打，Johann学长继续鸽，今天大爆炸了。

几个签到题都还挺顺的，然后reku看了A觉得好像步数似乎只有80，好像很简单的样子，跟lzw学长讨论了一下，lzw说了说其中一个部分的贪心，reku没有听的很清楚，但是lzw学长看上去很有自信，就让他去写。结果写一写发现有很多问题，甚至复杂度都不是非常合理。但是两个人想先把这个题变成TLE，然后在做下一步的打算（因为罚时已经很高，当时已经不在乎了）。然而A题一直在WA，最后五分钟才发现是字符串比较写错了。

还有一个半小时的时候，也试图挽救一下比赛节奏。开了J题，但是reku和lzw理解的题意是信号不能被分割，这样好像并不能网络流。而且手上的A题也很难受，所以就没有接着讨论J，希望两个人能把A过掉，最后也没过，大爆炸。

总结

reku

比赛之后J题随便想想就想到了。感觉开题如果先开J的话，状态会好很多。A题卡的时间太久了，卡了两个多小时。其实做法本身就有问题，还是不想放弃题目。如果有三个人的话，另外两个人就能讨论开题了。

lzw4896s

今天大爆炸主要还是我的锅,A题reku学长发现步数最多只有80,状态数很少，用f[i][j]表示前i个数有序，花了j步能让第i个数最小能变成多少，时限有5秒，随便想了一个贪心的转移方法，感觉肯定能过。结果还是代码实现上出了很多很蠢的问题，浪费了很多的时间。 之前的CCPC网络赛也是代码实现上出了很多问题，感觉代码实现的能力还是有待加强，需要多做一些个人比赛提高短时间内写对代码的能力。 最后一个小时看J题感觉有两种题意，不确定是哪一种，手上还有A题没过掉，心里就很虚，根本没心思去想解法，所以就五题滚粗了。 和队友的配合上应该没什么问题，个人的基本功还是不够扎实。

Johann

教训

题解

• A: f[i][j]表示前i个数有序，花了j步能让第i个数最小能变成多少, 由于只有n个数,可以让每个数的前两位互不相同，所以最多花2n步,j最大是80. 转移的时候枚举需要改变次数k,问题转化为给出s1, s2,改变s2的k个数字使得s1 <= s2 且s2 尽可能小。 可以dp一下,dp[i]表示 使得s1[i...m] <= s2[i...m] 的最少步数，然后从左到右依次确定即可。 另外一种做法：dp[i][l][r][lim] 表示处理i...m列, l...r行, 且第i列的数字必须>=lim的最优解。 转移的时候枚举第i列 第l...p行全变成数字k, dp[i][l][r][lim] 由 dp[i + 1][l][p][0] dp[i][p + 1][r][k + 1] 转移过来。时间复杂度O(100 * M * N^3)
• B: 题目保证环的大小不会超过5. 那么对于每个强联通分量, 暴力算出内部两两之间的最长路, 然后把强连通分量的每个点拆成两个点, 一个点表示强联通分量的入口, 一个点表示出口。 建好新图后跑最长路即可。
• D: 首先是如何还原树。 可以先随便拿两个点,形成一条链, 然后对于其他点，看一下它是应该连到这条链的哪个位置(即它应该是哪个子树)。对于每个子树再分别递归建树即可。 建好树之后，只要算出每条边对答案的贡献。 一条边上有len + 1个点, 分3种情况，一种是 边内部的len - 1个点互相之间的贡献，一种是内部的点连到外面，一种是外部的点跨过这条边。 需要额外增加的点数不超过n个。 因为不存在度为2的点，有n个叶子,假设增加了k个点, 那么有 n + 3*k <= 2 * (n + k - 1) 得到 k <= n - 2。
• J: 网络流做法：建立分层图，每个管道的流量要么当天流掉，要么留到下一天(留到下一层图里相应的节点)。 贪心做法： 先模拟一遍，可以求出对于每个管道，有一些DDL(x, y), 表示在第i天前这个管道至少要释放y的容量。 然后再做一遍模拟，每次释放容量的时候，选择时间最近的DDL来满足。