2016-C02-team5

从 Trac 迁移的文章

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

原文章内容如下：

== 流水账 ==
=== jcq1234 === 
这场比赛炸了，我们首先还是跟昨天一样分开读题。读完D题感觉毫无头绪，又开始读E，还是不会做，这个时候A题又WA了一次，感觉不太妙。之后wth学长把A和B过了，'''A2y20''', '''B1y33'''。然后我和wth学长一起商量F题，一开始题目读错了，以为是个水题，排序就能过了，和wth学长说了思路之后就让他继续码，果断WA。之后triomino学长G题有思路了，'''G1y78'''。然后我把F题甩锅给了另外两个学长，开始做H，H题是个水题，数据量小，直接用unordered_set就能过的，我当时没想到，就用Trie做，因为Trie是用结构体内部存储数据，数组开太大不能运行，就只开了一万左右，提交runtime error两次，之后用全局变量存才过了，'''H3y98'''。之后和wth学长讨论了J题，很快就有正确思路了，感觉用凸包做非常科学，就让wth学长开始做J，之后和triomino学长讨论F，感觉有点坑，一直没有结果。这时候I题有学长过了，和triomino学长看了题目感觉应该是个费用流或者匹配，感觉并不会用模板，就暂时放着。然后继续看E题，给triomino学长讲明了题意和我的初步思路之后，学长很快就想出了尺取法，然后思路就明确了。

后面实在是黑历史，最后的时间我们一人死磕一个题，我做E，triomino学长做F，wth学长做J，每次都感觉就差一点就能过了，但是一直都有奇怪的bug，提交了好多次，wth学长还剩半个小时终于过了J，'''J10y268'''，剩下的两道题一直都没有过。最后我们队罚时爆炸，题数爆炸垫底...

== 总结 ==

=== jcq1234 ===
 * 代码能力还是不行，E题最早想出思路但是一直都有bug
 * 还是太粗心了，F题读错了题目。
 * 比较害怕做模板题，还是要多学习一个。
 * 以后一定要学会取舍，后期我们都死磕一个题目，效率太低。
=== wtthhh ===
 * 今天我主要要背锅，上来A题WA开头不顺，后面死磕J题，卡了2个多小时，浪费了太多时间
 * C题看过原题，但当时没有做，印象不深没有上来就写，后面过了J题已经没时间了。。补题很重要，不然后悔死。。
 * I题大概有思路，也是因为时间问题
 * J题一度以为是凸包的问题。。。赛后终于查出来。。是爆int了。。叉积没有用LL。。要格外注意cross 和 dis 要用 long long
 * 提高代码能力，该抄模板就得超
 * 缺少团队配合，基本上一个搞一个题轮着debug，这很不ACM

=== triomino === 
 * 思路有点死，F题直接认定用贪心，到最后都没想到dp。
 * 缺乏debug能力(给自己以及队友）
 * wa多了心态有点乱，不应该急躁


 == 题解 ==

=== E ===
枚举左右边界，然后从上到下尺取法，预处理每一行的前缀和，然后可以得到每行0的个数，用两个multiset维护两个修补方法的行。枚举边界时，可以加一个优化，如果左右边界乘以行数都比当前答案小，就不用计算了。
=== C ===
求点双连通子图预处理，可以O(1)判断两个格子的连通状态，然后直接跑即可。。原题没做真是太蠢了。。
=== I ===
网络流建模，把必须点的费用设成极大极小之类的，常见套路。要注意的是最大费用流，不是最大费用最大流，加深对网络流理解
=== G ===
凸包模板爆炸。。
=== F ===
玩一局游戏之后，金钱期望x'=P(x+A)+(1-P)x(1-L)=PA+(1-L+PL)x，记做kx+b。对相邻两次游戏，结果为k[i+1](k[i]*x+b[i])+b[i+1],考虑交换i和i+1的条件，即k[i+1](k[i]*x+b[i])+b[i+1]<k[i](k[i+1]*x+b[i+1])+b[i],化简得(k[i]-1)/b[i]>(k[i+1]-1)/b[i+1]。按(k-1)/b从小到大排序，然后这个序列里进行dp，f[i][j]表示第i个游戏结尾取j个游戏得到的最大值。
转移f[i][j]=max(f[t][j-1])*k[i]+b[i], t=j-1,j,...,i-1.

流水账

jcq1234

这场比赛炸了，我们首先还是跟昨天一样分开读题。读完D题感觉毫无头绪，又开始读E，还是不会做，这个时候A题又WA了一次，感觉不太妙。之后wth学长把A和B过了，A2y20, B1y33。然后我和wth学长一起商量F题，一开始题目读错了，以为是个水题，排序就能过了，和wth学长说了思路之后就让他继续码，果断WA。之后triomino学长G题有思路了，G1y78。然后我把F题甩锅给了另外两个学长，开始做H，H题是个水题，数据量小，直接用unordered_set就能过的，我当时没想到，就用Trie做，因为Trie是用结构体内部存储数据，数组开太大不能运行，就只开了一万左右，提交runtime error两次，之后用全局变量存才过了，H3y98。之后和wth学长讨论了J题，很快就有正确思路了，感觉用凸包做非常科学，就让wth学长开始做J，之后和triomino学长讨论F，感觉有点坑，一直没有结果。这时候I题有学长过了，和triomino学长看了题目感觉应该是个费用流或者匹配，感觉并不会用模板，就暂时放着。然后继续看E题，给triomino学长讲明了题意和我的初步思路之后，学长很快就想出了尺取法，然后思路就明确了。

后面实在是黑历史，最后的时间我们一人死磕一个题，我做E，triomino学长做F，wth学长做J，每次都感觉就差一点就能过了，但是一直都有奇怪的bug，提交了好多次，wth学长还剩半个小时终于过了J，J10y268，剩下的两道题一直都没有过。最后我们队罚时爆炸，题数爆炸垫底...

总结

jcq1234

代码能力还是不行，E题最早想出思路但是一直都有bug
还是太粗心了，F题读错了题目。
比较害怕做模板题，还是要多学习一个。
以后一定要学会取舍，后期我们都死磕一个题目，效率太低。

wtthhh

今天我主要要背锅，上来A题WA开头不顺，后面死磕J题，卡了2个多小时，浪费了太多时间
C题看过原题，但当时没有做，印象不深没有上来就写，后面过了J题已经没时间了。。补题很重要，不然后悔死。。
I题大概有思路，也是因为时间问题
J题一度以为是凸包的问题。。。赛后终于查出来。。是爆int了。。叉积没有用LL。。要格外注意cross 和 dis 要用 long long
提高代码能力，该抄模板就得超
缺少团队配合，基本上一个搞一个题轮着debug，这很不ACM

triomino

思路有点死，F题直接认定用贪心，到最后都没想到dp。
缺乏debug能力(给自己以及队友）
wa多了心态有点乱，不应该急躁

题解

E

枚举左右边界，然后从上到下尺取法，预处理每一行的前缀和，然后可以得到每行0的个数，用两个multiset维护两个修补方法的行。枚举边界时，可以加一个优化，如果左右边界乘以行数都比当前答案小，就不用计算了。

C

求点双连通子图预处理，可以O(1)判断两个格子的连通状态，然后直接跑即可。。原题没做真是太蠢了。。

I

网络流建模，把必须点的费用设成极大极小之类的，常见套路。要注意的是最大费用流，不是最大费用最大流，加深对网络流理解

G

凸包模板爆炸。。

F

玩一局游戏之后，金钱期望x'=P(x+A)+(1-P)x(1-L)=PA+(1-L+PL)x，记做kx+b。对相邻两次游戏，结果为k[i+1](k[i]*x+b[i])+b[i+1],考虑交换i和i+1的条件，即k[i+1](k[i]*x+b[i])+b[i+1](k[i+1]-1)/b[i+1]。按(k-1)/b从小到大排序，然后这个序列里进行dp，f[i][j]表示第i个游戏结尾取j个游戏得到的最大值。

转移f[i][j]=max(f[t][j-1])*k[i]+b[i], t=j-1,j,...,i-1.

附加文件