2016-SE01-team1

从 Trac 迁移的文章

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

原文章内容如下：

||User||Problem||Result||Memory||Time||Language||Length||Submit Time||
||Siunaus||K||WA||  ||  ||C++11 5.3.0||7902||2016-07-28 19:46:05||
||Siunaus||K||WA||  ||  ||C++11 5.3.0||7783||2016-07-28 19:38:11||
||Siunaus||K||TLE|| ||  ||C++11 5.3.0||7615||2016-07-28 19:30:02||
||Siunaus||H||AC||0||345||C++11 5.3.0||2001||2016-07-28 19:26:23||
||Siunaus||H||WA||  ||  ||C++11 5.3.0||1993||2016-07-28 19:23:04||
||Siunaus||H||RE||  ||  ||C++11 5.3.0||1994||2016-07-28 19:18:32||
||Siunaus||H||RE||  ||  ||C++11 5.3.0||1983||2016-07-28 19:16:06||
||Siunaus||G||AC||0||239||C++11 5.3.0||3152||2016-07-28 17:27:35||
||Siunaus||D||AC||0||79||C++11 5.3.0||1366||2016-07-28 17:10:04||
||Siunaus||G||WA||  ||  ||C++11 5.3.0||3162||2016-07-28 17:03:53||
||Siunaus||D||WA||  ||  ||C++11 5.3.0||787||2016-07-28 16:51:06||
||Siunaus||D||RE||  ||  ||C++11 5.3.0||717||2016-07-28 16:34:40||
||Siunaus||I||AC||0||316||C++11 5.3.0||1091||2016-07-28 16:01:49||
||Siunaus||E||AC||0||3||C++11 5.3.0||1757||2016-07-28 15:47:08||
||Siunaus||F||AC||0||6||C++ 5.3.0||861||2016-07-28 15:20:09||
||Siunaus||C||AC||0||3||C++11 5.3.0||480||2016-07-28 14:55:00||
||Siunaus||C||WA||  ||  ||C++11 5.3.0||599||2016-07-28 14:50:55||
||Siunaus||B||AC||0||3||C++ 5.3.0||803||2016-07-28 14:43:43||

比赛链接: http://acm.hust.edu.cn/vjudge/contest/124586#overview

jtjl & sficion

== 流水账 ==

== 总结 ==

== 题解 ==

BC签到题，略去不表。

=== D. Laptop Chargers [JTJL] ===

考虑到充电线可以无线随时切换，问题的本质只需要考虑总体的电量输入和消耗情况。
查询的时候要注意不是总量足够就一定能够用，因为电量不能在laptop之间转移，本身如果有过多的电量也只能浪费掉，所以需要分段处理或者二分答案。

=== E. Poker End Games [JTJL] ===

容易写出转移方程，可以考虑对马尔科夫链进行迭代或者直接高斯消元解概率。
但是由于本题的特殊性，转移的结果状态一定至少有一个是端点，所以其实是一对一的转移，所以只要找终点（可能是点也可能是环），递推系数求一元一次方程即可，然后倒推出答案，复杂度为O(n)。

=== F. Overlapping Characters [sfiction] ===

bitset暴力求出每个字符是否有唯一为非空的位置。

=== G. Reduce the Maintenance Cost [sfiction] ===

只有双连通关键边权值非0，且构成一棵树，二分答案后在树上贪心即可。权值计算需建树后DFS。稍麻烦，但思路非常自然。

=== H. Team Mathematics Olympiad [sfiction] ===

状态压缩DP。dp[i][j] 表示前 i 道题，每个人做题次数是 j(mask)，因为 fail 的状态会有持续影响，需要分成 i-1 有没有 fail 两种状态。

=== I. Learning Vector [sfiction] ===

注意到解一定是个凸线（类似排序不等式），因此先对向量按斜率排序。dp[i][j][k] 表示前 j 个取了 i 个，结束高度为 k 的最大值。因为后续向量贡献计算需要使用高度但不需要使用x坐标，因此状态只保留高度信息。


== 补题 ==

AJK
UserProblemResultMemoryTimeLanguageLengthSubmit Time
SiunausKWA C++11 5.3.079022016-07-28 19:46:05
SiunausKWA C++11 5.3.077832016-07-28 19:38:11
SiunausKTLE C++11 5.3.076152016-07-28 19:30:02
SiunausHAC0345C++11 5.3.020012016-07-28 19:26:23
SiunausHWA C++11 5.3.019932016-07-28 19:23:04
SiunausHRE C++11 5.3.019942016-07-28 19:18:32
SiunausHRE C++11 5.3.019832016-07-28 19:16:06
SiunausGAC0239C++11 5.3.031522016-07-28 17:27:35
SiunausDAC079C++11 5.3.013662016-07-28 17:10:04
SiunausGWA C++11 5.3.031622016-07-28 17:03:53
SiunausDWA C++11 5.3.07872016-07-28 16:51:06
SiunausDRE C++11 5.3.07172016-07-28 16:34:40
SiunausIAC0316C++11 5.3.010912016-07-28 16:01:49
SiunausEAC03C++11 5.3.017572016-07-28 15:47:08
SiunausFAC06C++ 5.3.08612016-07-28 15:20:09
SiunausCAC03C++11 5.3.04802016-07-28 14:55:00
SiunausCWA C++11 5.3.05992016-07-28 14:50:55
SiunausBAC03C++ 5.3.08032016-07-28 14:43:43

比赛链接: http://acm.hust.edu.cn/vjudge/contest/124586#overview

jtjl & sficion

流水账

总结

题解

BC签到题，略去不表。

D. Laptop Chargers [JTJL]

考虑到充电线可以无线随时切换，问题的本质只需要考虑总体的电量输入和消耗情况。

查询的时候要注意不是总量足够就一定能够用，因为电量不能在laptop之间转移，本身如果有过多的电量也只能浪费掉，所以需要分段处理或者二分答案。

E. Poker End Games [JTJL]

容易写出转移方程，可以考虑对马尔科夫链进行迭代或者直接高斯消元解概率。

但是由于本题的特殊性，转移的结果状态一定至少有一个是端点，所以其实是一对一的转移，所以只要找终点（可能是点也可能是环），递推系数求一元一次方程即可，然后倒推出答案，复杂度为O(n)。

F. Overlapping Characters [sfiction]

bitset暴力求出每个字符是否有唯一为非空的位置。

G. Reduce the Maintenance Cost [sfiction]

只有双连通关键边权值非0，且构成一棵树，二分答案后在树上贪心即可。权值计算需建树后DFS。稍麻烦，但思路非常自然。

H. Team Mathematics Olympiad [sfiction]

状态压缩DP。dp[i][j] 表示前 i 道题，每个人做题次数是 j(mask)，因为 fail 的状态会有持续影响，需要分成 i-1 有没有 fail 两种状态。

I. Learning Vector [sfiction]

注意到解一定是个凸线（类似排序不等式），因此先对向量按斜率排序。dp[i][j][k] 表示前 j 个取了 i 个，结束高度为 k 的最大值。因为后续向量贡献计算需要使用高度但不需要使用x坐标，因此状态只保留高度信息。

补题

AJK

附加文件