2016-C07-team2

从 Trac 迁移的文章

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

原文章内容如下：

||Time||Problem||Lang||Result||
||13:15||C||C||AC||
||12:24||G||CPP||AC||
||12:03||K||CPP||AC||
||11:47||K||CPP||WA||
||11:21||I||C||AC||
||11:07||B||CPP||AC||
||10:31||F||CPP||AC||
||10:15||D||C||AC||
||10:10||E||CPP||AC||
||09:35||H||CPP||AC||
||09:21||J||C||AC||
||09:16||A||CPP||AC||
== 流水账 ==
=== TsReaper ===
今天没什么锅，学长们很强。

开场后很快'''A1y6'''，'''J1y11'''。Starve学长看到H是简单题，写题的时候虽然碰到了一点细节问题，但是仍然'''H1y25'''。hzf学长似乎会做I，写了一段时间后发现并不能过样例，貌似数据范围搞错了...Starve学长就先写几何题E，碰到了一点问题，我就先写小模拟D。很快Starve学长发现了问题，'''E1y60'''，我的小模拟也'''D1y65'''。顺便也把小模拟F写好了，'''F1y81'''。Starve学长想了K的费用流做法，但我写完后才想到费用和流量有关，学长的做法并不正确。

因为hznu的学长们纷纷过了B，学长们觉得虽然时间复杂度可能不够科学，但是B应该就是二分图匹配。Starve学长写了B，加了一点简单的优化后'''B1y117'''。Starve学长写题的过程中我根据样例猜了I的结论，虽然不知道是否正确但是还算好写，写完用数据与hzf学长之前写的程序对拍也没有问题，提交后'''I1y131'''~~然而到现在也不知道自己的结论为什么正确~~。hzf学长想到了K的dp做法，Starve学长上机'''K2y177'''。

午饭后我写搜索题G，学长们讨论C。'''G1y194'''后，学长们不久也得到了C的dp做法。搞好了麻烦的输出方案后'''C1y245'''~~其实有一些东西没有考虑到，只是数据太水~~。

=== hzf ===
开场从后往前看，看到k感觉有dp思路，接着j就被学长们写啦，于是看i，结果看错题了...感觉被图误导了，完全忽视了数据范围...惨，上机写，样例都过不了...之后学长们h也过了，于是我接着想了想i，没有特别强的思路...于是和tsr学长讲了k和我认为的做法，学长觉得没问题。又和starve学长讲了题意，starve学长给了一种费用流做法，没有看出问题所在...而且感觉费用流的复杂度比dp科学~~dp好像太快啦！~~于是接着等tsr学长写完了F就和tsr学长说了K的费用流想法...结果发现忘记考虑费用和流量有关...惨...学长们过b的时候我想了I的一个结论...感觉比较科学，和tsr学长讲的时候tsr学长根据样例猜了一个无比好写的正确的结论！很快tsr学长写了一波代码，和我之前的暴力对拍了一发，发现没问题...提交后过了，太强啦！

之后发现只有C G K题了，因为K题我之前有一个dp思路，便和学长们重新说了一番，感觉没有大问题，starve学长上机过了K。之后tsr学长上机写双向bfsG，1A，好强...期间我和starve学长开始想C，starve学长说了一个网络流的神奇做法，我再次感觉很科学，~~于是我准备开始挂机~~，不过准备写时发现了一些小问题...恰好我对之前dp的思路做了一些改进，和学长们讨论了一番，终于得出了状压dp的解法，tsr学长上机，结果在输出方案时遇到了很大的麻烦...最后水过了输出方案...运气太好啦！

== 总结 ==
=== TsReaper ===
 * 费用流的费用和流量有关，网络流也只能限制二元关系。

=== 3z ===
 * 有思路后要经过仔细思考再告诉队友，等队友写完后发现是错的就会很麻烦
 * 写题的时候思路还是要清晰，对于程序的每个部分都要考虑清除边界条件
 * 写题之前要考虑清楚，写到一半写不下去会很尴尬。

=== hzf ===
 * 读题需要认真，图片有助于理解，但不应把图片所描述的情况作为该题可能出现的唯一情况
 * 对于队友的想法还应在讨论时认真验证，不应该随便肯定其正确性
 * 如果一些标记数组需要频繁初始化，可以在使用标记数组的不同阶段对数组打不同的标记，以在不memset的情况下表示阶段间的无关性

== 题解 ==
=== B - Flipping Cards ===
虽然二分图匹配可过，但是rkmxtxwd队的学长们想了更科学的做法：把牌看作边，牌上的图案看作点，这样问题就转化为“如何把若干个点分给若干条边，每条边能且只能分到一个点，每个点只能分给连接自己的边”。很显然，对于每个连通块，如果边数大于点数就无法分配了，否则由于一条边连接着两个点，一定存在一种符合要求的分配方案。

=== C - Amazing Race ===
状压dp，记f[mask][i]表示已经参加了mask中的活动，现在位于第i个活动的最短耗时。对于一个没有参加过的活动j，若f[mask][i] + dis[i][j] + t[j] <= d[j]，则f[mask][i]可以转移到f[mask|(1<<j)][j]。如果参加的活动集合相同，那么最后获得的收益也相同。枚举mask和i，看看能否在规定时间内赶到终点即可。注意输出方案时按排序后的字典序输出最小的最优方案。

=== I - Matrix Keypad ===
如果某一行全是0，或者某一列全是0，说明这一行/列肯定不会被按。把所有全是0的行/列去掉后，如果矩阵里还剩下0就是impossible。否则，如果剩下的矩阵长宽都大于1，则对应位置的按钮都是可能被按的；如果有一个是1，则对应位置的按钮都是一定被按的。结论正确性不知道怎么证明...

=== K - Bundles of Joy ===
因为礼包间要么有包含关系，要么互不相交，所以所有的礼包构成了一个树形结构。通过树dp计算购买一棵树包含的所有物品的最小花费即可。

如果我们想要买到以x为根的子树中包含的所有物品，可以这样考虑：如果x的所有儿子的并集与x相同，而且合起来的价格更便宜，就买它所有的儿子，否则买它。

== 补题 ==

Time	Problem	Lang	Result
13:15	C	C	AC
12:24	G	CPP	AC
12:03	K	CPP	AC
11:47	K	CPP	WA
11:21	I	C	AC
11:07	B	CPP	AC
10:31	F	CPP	AC
10:15	D	C	AC
10:10	E	CPP	AC
09:35	H	CPP	AC
09:21	J	C	AC
09:16	A	CPP	AC

流水账

TsReaper

今天没什么锅，学长们很强。

开场后很快A1y6，J1y11。Starve学长看到H是简单题，写题的时候虽然碰到了一点细节问题，但是仍然H1y25。hzf学长似乎会做I，写了一段时间后发现并不能过样例，貌似数据范围搞错了...Starve学长就先写几何题E，碰到了一点问题，我就先写小模拟D。很快Starve学长发现了问题，E1y60，我的小模拟也D1y65。顺便也把小模拟F写好了，F1y81。Starve学长想了K的费用流做法，但我写完后才想到费用和流量有关，学长的做法并不正确。

因为hznu的学长们纷纷过了B，学长们觉得虽然时间复杂度可能不够科学，但是B应该就是二分图匹配。Starve学长写了B，加了一点简单的优化后B1y117。Starve学长写题的过程中我根据样例猜了I的结论，虽然不知道是否正确但是还算好写，写完用数据与hzf学长之前写的程序对拍也没有问题，提交后I1y131然而到现在也不知道自己的结论为什么正确。hzf学长想到了K的dp做法，Starve学长上机K2y177。

午饭后我写搜索题G，学长们讨论C。G1y194后，学长们不久也得到了C的dp做法。搞好了麻烦的输出方案后C1y245其实有一些东西没有考虑到，只是数据太水。

hzf

开场从后往前看，看到k感觉有dp思路，接着j就被学长们写啦，于是看i，结果看错题了...感觉被图误导了，完全忽视了数据范围...惨，上机写，样例都过不了...之后学长们h也过了，于是我接着想了想i，没有特别强的思路...于是和tsr学长讲了k和我认为的做法，学长觉得没问题。又和starve学长讲了题意，starve学长给了一种费用流做法，没有看出问题所在...而且感觉费用流的复杂度比dp科学dp好像太快啦！于是接着等tsr学长写完了F就和tsr学长说了K的费用流想法...结果发现忘记考虑费用和流量有关...惨...学长们过b的时候我想了I的一个结论...感觉比较科学，和tsr学长讲的时候tsr学长根据样例猜了一个无比好写的正确的结论！很快tsr学长写了一波代码，和我之前的暴力对拍了一发，发现没问题...提交后过了，太强啦！

之后发现只有C G K题了，因为K题我之前有一个dp思路，便和学长们重新说了一番，感觉没有大问题，starve学长上机过了K。之后tsr学长上机写双向bfsG，1A，好强...期间我和starve学长开始想C，starve学长说了一个网络流的神奇做法，我再次感觉很科学，于是我准备开始挂机，不过准备写时发现了一些小问题...恰好我对之前dp的思路做了一些改进，和学长们讨论了一番，终于得出了状压dp的解法，tsr学长上机，结果在输出方案时遇到了很大的麻烦...最后水过了输出方案...运气太好啦！

总结

TsReaper

• 费用流的费用和流量有关，网络流也只能限制二元关系。

3z

• 有思路后要经过仔细思考再告诉队友，等队友写完后发现是错的就会很麻烦
• 写题的时候思路还是要清晰，对于程序的每个部分都要考虑清除边界条件
• 写题之前要考虑清楚，写到一半写不下去会很尴尬。

hzf

• 读题需要认真，图片有助于理解，但不应把图片所描述的情况作为该题可能出现的唯一情况
• 对于队友的想法还应在讨论时认真验证，不应该随便肯定其正确性
• 如果一些标记数组需要频繁初始化，可以在使用标记数组的不同阶段对数组打不同的标记，以在不memset的情况下表示阶段间的无关性

题解

B - Flipping Cards

虽然二分图匹配可过，但是rkmxtxwd队的学长们想了更科学的做法：把牌看作边，牌上的图案看作点，这样问题就转化为“如何把若干个点分给若干条边，每条边能且只能分到一个点，每个点只能分给连接自己的边”。很显然，对于每个连通块，如果边数大于点数就无法分配了，否则由于一条边连接着两个点，一定存在一种符合要求的分配方案。

C - Amazing Race

状压dp，记f[mask][i]表示已经参加了mask中的活动，现在位于第i个活动的最短耗时。对于一个没有参加过的活动j，若f[mask][i] + dis[i][j] + t[j] <= d[j]，则f[mask][i]可以转移到f[mask|(1<

I - Matrix Keypad

如果某一行全是0，或者某一列全是0，说明这一行/列肯定不会被按。把所有全是0的行/列去掉后，如果矩阵里还剩下0就是impossible。否则，如果剩下的矩阵长宽都大于1，则对应位置的按钮都是可能被按的；如果有一个是1，则对应位置的按钮都是一定被按的。结论正确性不知道怎么证明...

K - Bundles of Joy

因为礼包间要么有包含关系，要么互不相交，所以所有的礼包构成了一个树形结构。通过树dp计算购买一棵树包含的所有物品的最小花费即可。

如果我们想要买到以x为根的子树中包含的所有物品，可以这样考虑：如果x的所有儿子的并集与x相同，而且合起来的价格更便宜，就买它所有的儿子，否则买它。

补题

附加文件

• 2016-C07-team2.zip by TsReaper