2017-Sp02-team3
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[[Image(0920.png,800px)]]
= 流水账 =
今天加训，三个人参赛。
今天前期很迅猛，5题的时候甚至冲到了全场第２，仅次于ddf，仰仗lzw的Ｅ和Ｈ写的又快又稳。之后三个人讨论了一下Ｃ，lzw提了一个算法，三个人都觉得挺稳的，johann上机写完，发现过不了样例，仔细思考了一下，才发现是错的。reku的Ｆ很快有了后缀数组的思路，就上去先敲板子。之后lzw和johann提出了靠谱的做法，终于过掉了，然后reku的Ｆ因为一个傻错误wa了一发，之后也过了。还没有封榜，就已经七题了，发现已经可以拿金了？后期题讨论了一下，感觉都没什么思路，就在旁边吹逼...最后发现七题罚时第一...
= 总结 =
== reku ==
本来决定打的还行，还能混到china final金牌，后来被教练们喷了，说每过一年，大家实力都会有个飞升，说明我们还是很菜...感觉后期题能力确实很差，再练一个月，再打一下去年的ccpc final吧，希望能有进步！
== lzw4896s ==
感觉敝队状态好的话可以做做中期题，但对后期题还是十分乏力，还是要多做做难题提高个人实力。写E题的时候因为不能灵活地使用python，只会把c翻译成python，写的比较慢，之后要抽出时间再学习一下python。
== Johann ==
前期比较咸鱼，讨论出算法后主要是两个学长在写签到题。中期lzw学长报了C的一个算法，我和reku学长觉得超有道理，(~~甚至还用到了线段树呢~~)。然后我就上机写，写完发现过不了样例。发现这个idea大爆炸了。当时我心态有点崩。但lzw学长很稳地，很快的想出了一个科学、精巧的做法（仰慕lzw学长），上机写出来之后就过了。要学习lzw学长迎难而上的心态。
后期更加咸鱼。七题之后看着去年一队A掉的B题和G题束手无策。G题最后还差一点。B题发现看错题了。有点难受，实力还要多多提升吧。qaq
= 教训 =
= 题解 =
* E题的java代码
* B: 问题可以转化为，求一个某些位确定的串，总共有多少符合条件的半回文串。这个问题其实很简单，O(N)扫一遍就好了。然后我们可以从前到后确定每一位，来确定答案。但是这样的话，时间复杂度就变成了O(N^2^)，可以发现如果到了200位左右，一定会有1e18个半回文串（打打表就发现了），这样时间复杂度就是200*N了，可以很轻松的过掉。感觉这个题目的确不难，没有做出来读错题是主要的锅！！！而且三个人都沉迷G题以及获得假金牌的喜悦中，很不好
* G: 比赛的时候想到离线做法：按询问的权值w从小到大排序，把比当前w小的边都加入，维护一个最小生成树，每个联通块维护一个线段树，然后启发式合并。 在线做法是维护最小生成树的时候，每加入一条边，把这条边转化为增加一个点z， z的左右儿子分别是它连接的两个联通块x和y，z点的权值就是边权。 每次询问(x, w)的时候，倍增从x往上找到深度最小的满足权值<=w的点，问题转化为求这棵子树的众数。 可以预处理每个子树对应的权值线段树，启发式合并维护即可。 ps： 以后写数据结构还是不要用指针了，调了好久TAT。
流水账
今天加训，三个人参赛。
今天前期很迅猛，5题的时候甚至冲到了全场第２，仅次于ddf，仰仗lzw的Ｅ和Ｈ写的又快又稳。之后三个人讨论了一下Ｃ，lzw提了一个算法，三个人都觉得挺稳的，johann上机写完，发现过不了样例，仔细思考了一下，才发现是错的。reku的Ｆ很快有了后缀数组的思路，就上去先敲板子。之后lzw和johann提出了靠谱的做法，终于过掉了，然后reku的Ｆ因为一个傻错误wa了一发，之后也过了。还没有封榜，就已经七题了，发现已经可以拿金了？后期题讨论了一下，感觉都没什么思路，就在旁边吹逼...最后发现七题罚时第一...
总结
reku
本来决定打的还行，还能混到china final金牌，后来被教练们喷了，说每过一年，大家实力都会有个飞升，说明我们还是很菜...感觉后期题能力确实很差，再练一个月，再打一下去年的ccpc final吧，希望能有进步！
lzw4896s
感觉敝队状态好的话可以做做中期题，但对后期题还是十分乏力，还是要多做做难题提高个人实力。写E题的时候因为不能灵活地使用python，只会把c翻译成python，写的比较慢，之后要抽出时间再学习一下python。
Johann
前期比较咸鱼，讨论出算法后主要是两个学长在写签到题。中期lzw学长报了C的一个算法，我和reku学长觉得超有道理，(甚至还用到了线段树呢)。然后我就上机写，写完发现过不了样例。发现这个idea大爆炸了。当时我心态有点崩。但lzw学长很稳地，很快的想出了一个科学、精巧的做法（仰慕lzw学长），上机写出来之后就过了。要学习lzw学长迎难而上的心态。
后期更加咸鱼。七题之后看着去年一队A掉的B题和G题束手无策。G题最后还差一点。B题发现看错题了。有点难受，实力还要多多提升吧。qaq
教训
题解
- E题的java代码
- B: 问题可以转化为，求一个某些位确定的串，总共有多少符合条件的半回文串。这个问题其实很简单，O(N)扫一遍就好了。然后我们可以从前到后确定每一位，来确定答案。但是这样的话，时间复杂度就变成了O(N2)，可以发现如果到了200位左右，一定会有1e18个半回文串（打打表就发现了），这样时间复杂度就是200*N了，可以很轻松的过掉。感觉这个题目的确不难，没有做出来读错题是主要的锅！！！而且三个人都沉迷G题以及获得假金牌的喜悦中，很不好
- G: 比赛的时候想到离线做法：按询问的权值w从小到大排序，把比当前w小的边都加入，维护一个最小生成树，每个联通块维护一个线段树，然后启发式合并。 在线做法是维护最小生成树的时候，每加入一条边，把这条边转化为增加一个点z， z的左右儿子分别是它连接的两个联通块x和y，z点的权值就是边权。 每次询问(x, w)的时候，倍增从x往上找到深度最小的满足权值<=w的点，问题转化为求这棵子树的众数。 可以预处理每个子树对应的权值线段树，启发式合并维护即可。 ps： 以后写数据结构还是不要用指针了，调了好久TAT。