2017-C06-team3

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(Screenshot from 2017-08-24 22-38-13.png)]]
= 流水账 =
今天终于迎来了第一场组队赛！
= 总结 =

== reku ==
今天我的锅主要是C，WA了之后看了好久才发现错误，耽误了许多时间，中间还一度怀疑算法是错的，很菜。

然后就是H，对网络流时间复杂度的估计不够准确，像JSB学长一样经验丰富、知识扎实才可以对复杂度有着正确的判断。

今天学长们都有读错题和思路不够清晰的现象发生，以后要想清楚在上去写题，有问题也不要慌，一步一步的解决就好了，心态要平和。
== lzw4896s ==
今天发挥感觉还算可以。主要犯的错误在于G题看题目不够仔细，漏了条件，导致WA了2发。 B题我和Johann学长讨论出来的做法是DP+线段树优化,做法有些复杂，而且有个小地方想错了，导致写好了之后过不了样例。发现解法是错误的之后有些慌，我们两个一下子都卡住了，给reku学长讲了之后，reku学长一下子就想到怎么处理那个地方了，感受到了团队的力量。 最后不到一个小时开H题，我和reku学长讨论出一个最大费用最大流的做法，看了看时限8s，感觉一定是这么做的，结果写好之后TLE打出GG。 以后碰到不确定做法能否出解的题目一定要考虑清楚再写，而不是想到一个似乎可行的做法就像抓住救命稻草一样牢牢不放，盲目地去碰运气，最后走进死胡同。
== Johann ==
前面鸽了很多天，两位学长辛苦了qwq

第一次合作，感觉自己还不是太冷静。经常“突然兴奋”，有几次自己的想法不太对，让队友走了弯路。

一开始刷了几次榜，发现J是签到题，很快地就写了。没想到贡献了1WA，原因是把>=写成了>。提交前没有把代码再看一遍。菜醒*1

然后给lzw学长讲了D题的题面，他很快有了一个做法。但我忘了和他说持股数的限制，至于为什么会这样，可能是因为吃了脑残片吧。太不仔细了。菜醒*2

E题和lzw学长讨论出了完备的算法（orz数学天才lzw），没什么问题。然后和reku学长想C题，看了一段时间，都没有很好的想法。自己对模型转化的思路不是很敏感，需要提高。 菜醒*3

B题和lzw一起搞了一个trie预处理+线段树优化DP的做法。觉得非常精妙，也很好写。顺便把K看了，很快也有了思路（orz物理天才lzw）。

帮reku学长debug他的C时又没能看出一个挺明显的bug。菜醒*4

过了C之后lzw学长的B过不了样例。之后发现我的做法有点问题，还要再预处理一个数组。菜醒*5，之后B的讨论没再参与。

写K的时候还比较顺利，一个小bug改过之后就A了。

最后一个小时在对着H疯狂费用流。 和ccpc一样奋战到底，打出GG。 菜醒*6

集齐6菜，大概就是6个注意点吧。
= 教训 =

= 题解 =
  * H： 能堆起来的条件是底边互不相等。问题转化为对于每个矩阵，可以翻转交换ab，要使a互不相等，b的和最大。 对于a*b的矩形，在a,b之间连一条边，之后要给边定方向，a->b 表示这个矩形以a为基底，b为高。题目保证有解，那么定向后每个点的出度最大为1。 考虑每个联通块，要么是n-1条边，要么是n条边。 每个点的贡献是 权值*入度数 = 权值*（度 - 出度）。  n条边每个点的出度都是1，答案是定值。 n-1条边的情况有一个点的出度为0，其他为1，那么让权值最大的点出度为0最优。

流水账

今天终于迎来了第一场组队赛！

总结

reku

今天我的锅主要是C，WA了之后看了好久才发现错误，耽误了许多时间，中间还一度怀疑算法是错的，很菜。

然后就是H，对网络流时间复杂度的估计不够准确，像JSB学长一样经验丰富、知识扎实才可以对复杂度有着正确的判断。

今天学长们都有读错题和思路不够清晰的现象发生，以后要想清楚在上去写题，有问题也不要慌，一步一步的解决就好了，心态要平和。

lzw4896s

今天发挥感觉还算可以。主要犯的错误在于G题看题目不够仔细，漏了条件，导致WA了2发。 B题我和Johann学长讨论出来的做法是DP+线段树优化,做法有些复杂，而且有个小地方想错了，导致写好了之后过不了样例。发现解法是错误的之后有些慌，我们两个一下子都卡住了，给reku学长讲了之后，reku学长一下子就想到怎么处理那个地方了，感受到了团队的力量。 最后不到一个小时开H题，我和reku学长讨论出一个最大费用最大流的做法，看了看时限8s，感觉一定是这么做的，结果写好之后TLE打出GG。 以后碰到不确定做法能否出解的题目一定要考虑清楚再写，而不是想到一个似乎可行的做法就像抓住救命稻草一样牢牢不放，盲目地去碰运气，最后走进死胡同。

Johann

前面鸽了很多天，两位学长辛苦了qwq

第一次合作，感觉自己还不是太冷静。经常“突然兴奋”，有几次自己的想法不太对，让队友走了弯路。

一开始刷了几次榜，发现J是签到题，很快地就写了。没想到贡献了1WA，原因是把>=写成了>。提交前没有把代码再看一遍。菜醒*1

然后给lzw学长讲了D题的题面，他很快有了一个做法。但我忘了和他说持股数的限制，至于为什么会这样，可能是因为吃了脑残片吧。太不仔细了。菜醒*2

E题和lzw学长讨论出了完备的算法（orz数学天才lzw），没什么问题。然后和reku学长想C题，看了一段时间，都没有很好的想法。自己对模型转化的思路不是很敏感，需要提高。 菜醒*3

B题和lzw一起搞了一个trie预处理+线段树优化DP的做法。觉得非常精妙，也很好写。顺便把K看了，很快也有了思路（orz物理天才lzw）。

帮reku学长debug他的C时又没能看出一个挺明显的bug。菜醒*4

过了C之后lzw学长的B过不了样例。之后发现我的做法有点问题，还要再预处理一个数组。菜醒*5，之后B的讨论没再参与。

写K的时候还比较顺利，一个小bug改过之后就A了。

最后一个小时在对着H疯狂费用流。 和ccpc一样奋战到底，打出GG。 菜醒*6

集齐6菜，大概就是6个注意点吧。

教训

题解

  • H： 能堆起来的条件是底边互不相等。问题转化为对于每个矩阵，可以翻转交换ab，要使a互不相等，b的和最大。 对于a*b的矩形，在a,b之间连一条边，之后要给边定方向，a->b 表示这个矩形以a为基底，b为高。题目保证有解，那么定向后每个点的出度最大为1。 考虑每个联通块，要么是n-1条边，要么是n条边。 每个点的贡献是 权值*入度数 = 权值*（度 - 出度）。 n条边每个点的出度都是1，答案是定值。 n-1条边的情况有一个点的出度为0，其他为1，那么让权值最大的点出度为0最优。
附加文件