2016-E01-team1
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
||Run ID||Time||Size||Problem||Language||Result||Failed test||View source||View report||
||227||4:51:42||1691||D||g++||OK||N/A||View||N/A||
||226||4:35:21||2682||A||g++||OK||N/A||View||N/A||
||225||4:33:43||1480||D||g++||Time-limit exceeded||18||View||N/A||
||224||4:23:06||2668||A||g++||Wrong answer||2||View||N/A||
||223||2:39:10||1717||K||g++||OK||N/A||View||N/A||
||222||2:33:49||1773||K||g++||Time-limit exceeded||12||View||N/A||
||221||2:27:38||1594||I||g++||OK||N/A||View||N/A||
||220||2:18:23||1446||I||g++||Wrong answer||11||View||N/A||
||219||1:56:51||616||H||g++||OK||N/A||View||N/A||
||218||1:37:53||1157||K||g++||Time-limit exceeded||12||View||N/A||
||217||1:18:42||344||F||g++||OK||N/A||View||N/A||
||216||1:05:57||2332||E||g++||Queries limit Exceeded||2||View||N/A||
||215||0:59:26||346||F||g++||Wrong answer||6||View||N/A||
||214||0:57:45||345||F||g++||Wrong answer||6||View||N/A||
||213||0:54:30||345||F||g++||Wrong answer||6||View||N/A||
比赛链接: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001463
== 流水账 ==
=== JTJL ===
今年第一次三个人训练，是在Skype上远程……~~（感觉效果很糟糕，刚开始还开错了奇怪的比赛~~[[BR]]
开场照例从E开始看，感觉E不是用三等分点二分一下就好了么，log(100) < 7，正好！冲上去写完发现算上最后的输出一共用了八次才能查完……= =[[BR]]
GG……QLE 2[[BR]]
之前刷了一下榜发现好多人过了F，就和队友说了F的题意，sf碎碎念的一段感觉会写了，就让他去写了……~~(结果好像猜错了结论？~~[[BR]]
之后开始神游？感觉没过E状态很糟糕~~（最后发现封榜前都没人过= =~~[[BR]]
后来听了I和K的题意，wxj觉得很可做……先是觉得K可以bitset暴力拧，自告奋勇接了锅去写，写到一半发现有个操作不会……~~（想了想感觉次数不会很多吧写个暴力好了~~，喜获TLE……然后放了K去看I[[BR]]
I是个TSP近似……感觉很蠢？（隐约记得ADS课本上有个结论），拿来套了套一下子过了样例，赶紧一交，又获1WA……[[BR]]
（脸好黑啊，下机看I，看了半天怀疑是不是边界写渣了，结果发现有个变量写错了……改了改终于过了……[[BR]]
（写I的时候wxj和sf在看我的K的代码，（被发现偷偷写了暴力，被喷啦（TUT……遂决定让sf(写完H后, H是个哈达马，大概sf和我说着说着就会了)来改K，手写bitset或者二分……[[BR]]
改完还是TLE……然后发现我三重循环可以优化6倍常数，改了改试了试居然过了……~~（卧槽又是一个大锅 TUT~~[[BR]]
然后学长们开始搞A，大家各有各的搞法，最后sf在我吃饭的时候提出了一个我听不懂的做法（后来发现是我之前想过但是不会维护的……），他说可以dfs序……我觉得很有道理，让他去写啦～[[BR]]
吃完饭看了看榜感觉只有D最可做，wxj提出了暴力的上届很松……我感受了一下举不出反例……看了看时间，讨论了一下set和map哪个方便哪个快后，决定等sf写完A去冲冲看……~~（反正10min就能写完，T了锅也不是我的……~~，不出所料T了……[[BR]]
趁sf去改A的时候，我想了想维护的值好像只会减少……感觉可以用vector+sort来大量减小常数……和学长说了，感觉很有道理，改了改就过了……[[BR]]
=== sfiction ===
尝试Skype远程，最后还是主要依赖手打了……
开场先看了ABCD，没一道会做的，只有A有点想法。刷榜看到F有人过，听JTJL说了题意之后就一直猜结论，结果猜错了，错误结论写错了两次，所以是WA了三次之后才开始检查结论，坑了很多罚时。
坑完A意识模糊，接着搞H，想了一段时间后和写完K的JTJL说了一下想法，说着说着发现自己想复杂了，一写就过了。
接着听了一下K的做法，把K的bitset改成手写并实现lowbit，还是T，检查了一下发现JTJL枚举了有序三元组，减少六倍常数后终于过了。
之后三个人一起坑了很久的A。我猜了个结论发现不会判定，重新梳理思路之后发现判定是O(1)的，看到机子空着说了一下开始写。写了好久，又错了个变量名。
== 总结 ==
=== JTJL ===
* 开场还是不要太心急，开错题，应该先把题目读完（要试着开始自己判断题目难度了，不完全看榜吧）
* 有些细节问题还是要多注意，打错变量啊什么的
* 复杂度估计好难啊 QAQ
=== sfiction ===
* 结论题验证不足
* 手速太慢，出错太多……
== 题解 ==
=== A. Arnold [sfiction] ===
给定一棵边权树及K个特殊点si，求出以多少点为根满足所有特殊点高度等于给定值hi。
从减少判定代价的方向入手，根据一对特殊点uv之间的距离及其hi即可求得可行解的一个范围，对这个范围内任意点w有dist(w,u)=dist(w,v)+(h(u)-h(v))，只需测试其中一个点，将(s0,si)这n-1个结果求交后即将判定代价减少到O(1)。求交部分可以用DFS序简化，范围求取需要树上倍增或其他方法。
=== D. Dirichlet [Akalm] ===
D题基本做法很裸，就是用一个数据结构维护每个点到已选集的最近距离dist，每次取最大即可。但直接用set等数据结构会TLE。
注意到更新顺序总是按照dist降序、dist也只减不增，且取值落在[1, n]。所以可以开 n 个队列，第 i 个队列维护当前dist[v] == i的顶点。虽然取下标最小的顶点的过程中仍需要sort，但常数比set, map, p_queue等小多啦。
~~快去补lct~~
=== F. Fourier [sfiction] ===
给定a0..an-1(n=2!^k)，求一组DFT均为实数的b(实数)，最小化sum(|ai-bi|)。
观察n=4和n=8的式子，发现ai和a(n-i)始终符号相异，于是考虑bi和b(n-i)取其平均值。
=== H. Hardmard [sfiction] ===
重排按给定方式构造的边长为2!^k的hardmard矩阵，使其主对角线为给定元素。
首先第一列只能为+。然后发现k=1时+-和++均可构造，递归构造矩阵时右上角和左上角相应位置均异号，因此i和2!^j+i交换与否即可分别满足当前行+-的要求。
=== I. Iwatani [JTJL] ===
贪心，从原点开始每次找最近的点即可，找出整条哈密顿回路。易证整条路径的长度不超过T的两倍。然后在原点和中间砍断找较小的那半条就是符合要求的解啦～
~~为什么别的队都是MST的？？~~
（卧槽，好像的确应该是MST才对，为什么记错结论被我水过去了……
=== K. Kuratowski [sfiction] ===
给定一个简单无向图(n<=400)，求其任意一个K5或K33子图。
用bitset记录邻接矩阵，枚举相异三点求与，如果count()>=3说明为K33，检查一遍即可（只发生一次，不考虑效率），否则若count()==2说明可能为K5，需要取出两元素判是否有边(手写bitset实现lowbit)。
== 补题 ==
BCEGJ| Run ID | Time | Size | Problem | Language | Result | Failed test | View source | View report |
| 227 | 4:51:42 | 1691 | D | g++ | OK | N/A | View | N/A |
| 226 | 4:35:21 | 2682 | A | g++ | OK | N/A | View | N/A |
| 225 | 4:33:43 | 1480 | D | g++ | Time-limit exceeded | 18 | View | N/A |
| 224 | 4:23:06 | 2668 | A | g++ | Wrong answer | 2 | View | N/A |
| 223 | 2:39:10 | 1717 | K | g++ | OK | N/A | View | N/A |
| 222 | 2:33:49 | 1773 | K | g++ | Time-limit exceeded | 12 | View | N/A |
| 221 | 2:27:38 | 1594 | I | g++ | OK | N/A | View | N/A |
| 220 | 2:18:23 | 1446 | I | g++ | Wrong answer | 11 | View | N/A |
| 219 | 1:56:51 | 616 | H | g++ | OK | N/A | View | N/A |
| 218 | 1:37:53 | 1157 | K | g++ | Time-limit exceeded | 12 | View | N/A |
| 217 | 1:18:42 | 344 | F | g++ | OK | N/A | View | N/A |
| 216 | 1:05:57 | 2332 | E | g++ | Queries limit Exceeded | 2 | View | N/A |
| 215 | 0:59:26 | 346 | F | g++ | Wrong answer | 6 | View | N/A |
| 214 | 0:57:45 | 345 | F | g++ | Wrong answer | 6 | View | N/A |
| 213 | 0:54:30 | 345 | F | g++ | Wrong answer | 6 | View | N/A |
比赛链接: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001463
流水账
JTJL
今年第一次三个人训练，是在Skype上远程……（感觉效果很糟糕，刚开始还开错了奇怪的比赛
开场照例从E开始看，感觉E不是用三等分点二分一下就好了么，log(100) < 7，正好！冲上去写完发现算上最后的输出一共用了八次才能查完……= =
GG……QLE 2
之前刷了一下榜发现好多人过了F，就和队友说了F的题意，sf碎碎念的一段感觉会写了，就让他去写了……(结果好像猜错了结论？
之后开始神游？感觉没过E状态很糟糕（最后发现封榜前都没人过= =
后来听了I和K的题意，wxj觉得很可做……先是觉得K可以bitset暴力拧，自告奋勇接了锅去写，写到一半发现有个操作不会……（想了想感觉次数不会很多吧写个暴力好了，喜获TLE……然后放了K去看I
I是个TSP近似……感觉很蠢？（隐约记得ADS课本上有个结论），拿来套了套一下子过了样例，赶紧一交，又获1WA……
（脸好黑啊，下机看I，看了半天怀疑是不是边界写渣了，结果发现有个变量写错了……改了改终于过了……
（写I的时候wxj和sf在看我的K的代码，（被发现偷偷写了暴力，被喷啦（TUT……遂决定让sf(写完H后, H是个哈达马，大概sf和我说着说着就会了)来改K，手写bitset或者二分……
改完还是TLE……然后发现我三重循环可以优化6倍常数，改了改试了试居然过了……（卧槽又是一个大锅 TUT
然后学长们开始搞A，大家各有各的搞法，最后sf在我吃饭的时候提出了一个我听不懂的做法（后来发现是我之前想过但是不会维护的……），他说可以dfs序……我觉得很有道理，让他去写啦～
吃完饭看了看榜感觉只有D最可做，wxj提出了暴力的上届很松……我感受了一下举不出反例……看了看时间，讨论了一下set和map哪个方便哪个快后，决定等sf写完A去冲冲看……（反正10min就能写完，T了锅也不是我的……，不出所料T了……
趁sf去改A的时候，我想了想维护的值好像只会减少……感觉可以用vector+sort来大量减小常数……和学长说了，感觉很有道理，改了改就过了……
sfiction
尝试Skype远程，最后还是主要依赖手打了……
开场先看了ABCD，没一道会做的，只有A有点想法。刷榜看到F有人过，听JTJL说了题意之后就一直猜结论，结果猜错了，错误结论写错了两次，所以是WA了三次之后才开始检查结论，坑了很多罚时。
坑完A意识模糊，接着搞H，想了一段时间后和写完K的JTJL说了一下想法，说着说着发现自己想复杂了，一写就过了。
接着听了一下K的做法，把K的bitset改成手写并实现lowbit，还是T，检查了一下发现JTJL枚举了有序三元组，减少六倍常数后终于过了。
之后三个人一起坑了很久的A。我猜了个结论发现不会判定，重新梳理思路之后发现判定是O(1)的，看到机子空着说了一下开始写。写了好久，又错了个变量名。
总结
JTJL
- 开场还是不要太心急，开错题，应该先把题目读完（要试着开始自己判断题目难度了，不完全看榜吧）
- 有些细节问题还是要多注意，打错变量啊什么的
- 复杂度估计好难啊 QAQ
sfiction
- 结论题验证不足
- 手速太慢，出错太多……
题解
A. Arnold [sfiction]
给定一棵边权树及K个特殊点si，求出以多少点为根满足所有特殊点高度等于给定值hi。
从减少判定代价的方向入手，根据一对特殊点uv之间的距离及其hi即可求得可行解的一个范围，对这个范围内任意点w有dist(w,u)=dist(w,v)+(h(u)-h(v))，只需测试其中一个点，将(s0,si)这n-1个结果求交后即将判定代价减少到O(1)。求交部分可以用DFS序简化，范围求取需要树上倍增或其他方法。
D. Dirichlet [Akalm]
D题基本做法很裸，就是用一个数据结构维护每个点到已选集的最近距离dist，每次取最大即可。但直接用set等数据结构会TLE。
注意到更新顺序总是按照dist降序、dist也只减不增，且取值落在[1, n]。所以可以开 n 个队列，第 i 个队列维护当前dist[v] == i的顶点。虽然取下标最小的顶点的过程中仍需要sort，但常数比set, map, p_queue等小多啦。
快去补lct
F. Fourier [sfiction]
给定a0..an-1(n=2!^k)，求一组DFT均为实数的b(实数)，最小化sum(|ai-bi|)。
观察n=4和n=8的式子，发现ai和a(n-i)始终符号相异，于是考虑bi和b(n-i)取其平均值。
H. Hardmard [sfiction]
重排按给定方式构造的边长为2!^k的hardmard矩阵，使其主对角线为给定元素。
首先第一列只能为+。然后发现k=1时+-和++均可构造，递归构造矩阵时右上角和左上角相应位置均异号，因此i和2!^j+i交换与否即可分别满足当前行+-的要求。
I. Iwatani [JTJL]
贪心，从原点开始每次找最近的点即可，找出整条哈密顿回路。易证整条路径的长度不超过T的两倍。然后在原点和中间砍断找较小的那半条就是符合要求的解啦～
为什么别的队都是MST的？？
（卧槽，好像的确应该是MST才对，为什么记错结论被我水过去了……
K. Kuratowski [sfiction]
给定一个简单无向图(n<=400)，求其任意一个K5或K33子图。
用bitset记录邻接矩阵，枚举相异三点求与，如果count()>=3说明为K33，检查一遍即可（只发生一次，不考虑效率），否则若count()==2说明可能为K5，需要取出两元素判是否有边(手写bitset实现lowbit)。
补题
BCEGJ