2017-Sp15-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,600px)]]
== 流水账 ==
== 总结 ==
今天和三四队联合训练。开场各自看题，yzc认为A很签到，需要用java写，就打算让cjb翻译，后来讨论了一下后觉得用c++就好了不用大整数，就换下cjb，'''A1y14'''. sub让cjb去写K，cjb高速写完然后wa了，cjb打印调试，让yzc来写之前推了一下的B，cjb发现sub的题意有偏差，并不是欧几里得距离而是曼哈顿距离，修改后AC，'''K2y21'''. yzc不久后写完B，'''B1y28'''. 接下来的时候，cjb一个人在机上写博弈题C，sub和yzc在推J的公式。cjb觉得暴力能卡过去，然后就先wa再tle，只好打表找规律，打了出来之后发现很有规律，但是有四种情况，然后又觉得这个sg函数有一点奇怪，就和sub讨论了一下。yzc半推半猜搞了一个公式，上机敲了一发J，过了，'''J1y86'''. cjb调整了打表，打出了完全正确的表，三个人一起把四个规律写了出来，因为第四种规律恰好和前几天的16大连威佐夫博弈是一样的，所以就直接上了公式(实际上如果不知道就打表就好，因为只有1000种)，'''C3y120'''. 接下来打算开D和G，D大家都想到了非常暴力的高斯消元，但是担心会tle，sub表示自己能搞一个能过的算法，就让sub一个人去单挑了。cjb和yzc把剩下的题都读完了，开了下H，讨论完之后发现题看错了...最后只得到G的前面那个小结论，别的题并没有什么进展。sub在三个小时的时候终于写完了D，最后'''D1y193'''. 最后三个人开心地吃起了晚饭，然后四队过了G，我们决定继续挣扎，最后sub和yzc强行讨论了一个dp，yzc上机写，wa了一发后就不断讨论不断打补丁，最后终于通过了此题，'''G2y290'''. 在原榜我们排在第6，然而之前训过的Siunaus也是7题，但是罚时比我们优秀，排到了rk4.
=== chenjb ===
C题其实不应该交那发tle的...怀着一点侥幸心理，中间看错了一道题，不然感觉主席树其实可以想一想? 今天打得就比昨天好了，感觉适应了一些，虽然说不出来是哪里，但就是有那么种感觉。
=== oipotato ===
=== subconscious  ===
== 题解 ==
official:　[http://bestcoder.hdu.edu.cn/blog/2016-multi-university-training-contest-3-solutions-by-%E7%BB%8D%E5%85%B4%E4%B8%80%E4%B8%AD/ Bestcoder]
 * D：暴力高斯消元可以卡过，但是实际上可以做到m^3^,用第一行一直带着系数划到最后一行再处理，即确定了第一行之后可以把所有值都推出来。 所以把第2-n行的元素都用第一行的元素线性表示，最后一行的m个数再构成m个方程，这样方程式只有O(m)的.
 * E：求出root，也就是1号节点的dfs序，建一棵树，每个点的权值为它的深度减一，这样就可以求P=1的答案了。 考虑1的儿子u，u子树中节点的距离是到1的距离减一，不在u的子树中的节点是到1的距离加一，也就是对关于1号节点的线段树进行了区间的增减(因为一棵子树中的节点在dfs序中连续)，这就可以询问u的答案了。 那么对每个节点都如此操作，dfs对于每个节点建主席树，在主席树上维护区间求和，区间最大值，区间最小值。 询问就把区间并起来在第p棵树上查询所需要的东西就可以了。
== 补题 ==

流水账

总结

今天和三四队联合训练。开场各自看题，yzc认为A很签到，需要用java写，就打算让cjb翻译，后来讨论了一下后觉得用c++就好了不用大整数，就换下cjb，A1y14. sub让cjb去写K，cjb高速写完然后wa了，cjb打印调试，让yzc来写之前推了一下的B，cjb发现sub的题意有偏差，并不是欧几里得距离而是曼哈顿距离，修改后AC，K2y21. yzc不久后写完B，B1y28. 接下来的时候，cjb一个人在机上写博弈题C，sub和yzc在推J的公式。cjb觉得暴力能卡过去，然后就先wa再tle，只好打表找规律，打了出来之后发现很有规律，但是有四种情况，然后又觉得这个sg函数有一点奇怪，就和sub讨论了一下。yzc半推半猜搞了一个公式，上机敲了一发J，过了，J1y86. cjb调整了打表，打出了完全正确的表，三个人一起把四个规律写了出来，因为第四种规律恰好和前几天的16大连威佐夫博弈是一样的，所以就直接上了公式(实际上如果不知道就打表就好，因为只有1000种)，C3y120. 接下来打算开D和G，D大家都想到了非常暴力的高斯消元，但是担心会tle，sub表示自己能搞一个能过的算法，就让sub一个人去单挑了。cjb和yzc把剩下的题都读完了，开了下H，讨论完之后发现题看错了...最后只得到G的前面那个小结论，别的题并没有什么进展。sub在三个小时的时候终于写完了D，最后D1y193. 最后三个人开心地吃起了晚饭，然后四队过了G，我们决定继续挣扎，最后sub和yzc强行讨论了一个dp，yzc上机写，wa了一发后就不断讨论不断打补丁，最后终于通过了此题，G2y290. 在原榜我们排在第6，然而之前训过的Siunaus也是7题，但是罚时比我们优秀，排到了rk4.

chenjb

C题其实不应该交那发tle的...怀着一点侥幸心理，中间看错了一道题，不然感觉主席树其实可以想一想? 今天打得就比昨天好了，感觉适应了一些，虽然说不出来是哪里，但就是有那么种感觉。

oipotato

subconscious

题解

official:　Bestcoder

D：暴力高斯消元可以卡过，但是实际上可以做到m³,用第一行一直带着系数划到最后一行再处理，即确定了第一行之后可以把所有值都推出来。所以把第2-n行的元素都用第一行的元素线性表示，最后一行的m个数再构成m个方程，这样方程式只有O(m)的.
E：求出root，也就是1号节点的dfs序，建一棵树，每个点的权值为它的深度减一，这样就可以求P=1的答案了。考虑1的儿子u，u子树中节点的距离是到1的距离减一，不在u的子树中的节点是到1的距离加一，也就是对关于1号节点的线段树进行了区间的增减(因为一棵子树中的节点在dfs序中连续)，这就可以询问u的答案了。那么对每个节点都如此操作，dfs对于每个节点建主席树，在主席树上维护区间求和，区间最大值，区间最小值。询问就把区间并起来在第p棵树上查询所需要的东西就可以了。

补题

附加文件

1.png by chenjb