2019-Sp052-lyk
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[[Image(1.png,700px)]]
[[Image(3.png,700px)]]
[[Image(2.png,700px)]]
[wiki:2019-team2 返回Runespoor]
[http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001459 contest]
== 流水账 ==
== 总结 ==
'''zqq: ''' 今天仍然打得不好。对于好多东西都不了解和不熟练。
比如D题的对时间分块，我几乎完全忘记了这种套路了。
F题的式子我们也没有推出来。对期望的东西技巧还需要提高。
然后就是读题要仔细的看清数据范围，给队友的说的时候也不要忘记了。比如我的H忘了告诉lyk高度时1e9，开始还以为是sb题
剩余的就是慢慢补题了，我感觉今年多校题真的要做一下，不然区域赛套路没有见过真的完蛋了。
=== 题解 ===
https://icpc.camp/twsf/Petrozavodsk%20Winter-2015.%20Michael%20Tikhomirov%20Contest%201
https://icpc.camp/new-meta/2017/3/22%20Petrozavodsk%20Winter-2015.%20Michael%20Tikhomirov%20Contest%201
* C ：这个C题很有意思，观察发现确定第一维其他维性质不变，用数学归纳法的思想，需要能够不打乱顺序的合并操作。并且写代码的时候一定要想清楚整个过程。其实就几十行但是我写了一个上午，因为递归的过程老是想不清楚。题解详见 new-meta
* D ： 对时间分块、每400次暴力重构。对于每个块，标记出被修改的点，对于其他点要么挂在往上跳第一个被标记的点上，要么直接统计出前缀和。每次询问可以暴力在被修改的点上查（二分），修改也可以暴力遍历所有关键点修改。对于单点修改，时间分块非常好用！
* E ： 每个点作为一个变量，高消。这种没有很强性质的图论，去想想最直接的数学做法。
* F ：一道非常好的期望题。虽然可以从方案数角度去推。但是如果对期望理解深入的话，直接用期望推！
a2(i) 表示第i项平方的期望， S2(i)表示前i项和的平方的期望
a2(i) = (2 * s2(i - 1) + 2 * i + suma2(i - 1)) / i / i
s2(i) = (s2(i - 1) * (1 + 4 / i) + a2(i)) 这个很难想到。主要是有一项：E(ai * s(i - 1)) 这个看成条件概率（听说是全期望公式然而暂时没有学），看成E(s(i - 1) * E(a(i) | S(i - 1)) , E(a(i) | S(i - 1) = 2 * s(i - 1) / i
主要是要对期望和随机变量有深入理解。这个序列上随机的题目，每个变量都是随机的，并且后面的变量的取值对前面的变量有依赖关系，应该往条件概率方向去想
* H ：冷静观察这个分形结构，一个格子在一个分形结构内有五种情况，区分方式是它连向走到外面的出口在哪：一是在内部，需要经过(mid,0)，二三四五是经过上下左右的边界。同时还需要确定这个格子走到边界需要的步数。
确定了这些之后可以分类讨论两个格子间的路径：两个点在同一个块且属于五种情况中的同种情况，就两个点继续分形下去；否则就变成两个单独的点走到某些边界后直接算出在两点在边界上的距离。细节非常多，感觉做法可能有点垃圾。
=== 补题 ===
* C : zqq
* D ： zqq
* F ： zqq
* H ： lyk
* I ： 
流水账
总结
zqq: 今天仍然打得不好。对于好多东西都不了解和不熟练。
比如D题的对时间分块，我几乎完全忘记了这种套路了。
F题的式子我们也没有推出来。对期望的东西技巧还需要提高。
然后就是读题要仔细的看清数据范围，给队友的说的时候也不要忘记了。比如我的H忘了告诉lyk高度时1e9，开始还以为是sb题
剩余的就是慢慢补题了，我感觉今年多校题真的要做一下，不然区域赛套路没有见过真的完蛋了。
题解
https://icpc.camp/twsf/Petrozavodsk%20Winter-2015.%20Michael%20Tikhomirov%20Contest%201
https://icpc.camp/new-meta/2017/3/22%20Petrozavodsk%20Winter-2015.%20Michael%20Tikhomirov%20Contest%201
- C ：这个C题很有意思，观察发现确定第一维其他维性质不变，用数学归纳法的思想，需要能够不打乱顺序的合并操作。并且写代码的时候一定要想清楚整个过程。其实就几十行但是我写了一个上午，因为递归的过程老是想不清楚。题解详见 new-meta
- D ： 对时间分块、每400次暴力重构。对于每个块，标记出被修改的点，对于其他点要么挂在往上跳第一个被标记的点上，要么直接统计出前缀和。每次询问可以暴力在被修改的点上查（二分），修改也可以暴力遍历所有关键点修改。对于单点修改，时间分块非常好用！
- E ： 每个点作为一个变量，高消。这种没有很强性质的图论，去想想最直接的数学做法。
- F ：一道非常好的期望题。虽然可以从方案数角度去推。但是如果对期望理解深入的话，直接用期望推！
a2(i) 表示第i项平方的期望， S2(i)表示前i项和的平方的期望
a2(i) = (2 * s2(i - 1) + 2 * i + suma2(i - 1)) / i / i
s2(i) = (s2(i - 1) * (1 + 4 / i) + a2(i)) 这个很难想到。主要是有一项：E(ai * s(i - 1)) 这个看成条件概率（听说是全期望公式然而暂时没有学），看成E(s(i - 1) * E(a(i) | S(i - 1)) , E(a(i) | S(i - 1) = 2 * s(i - 1) / i
主要是要对期望和随机变量有深入理解。这个序列上随机的题目，每个变量都是随机的，并且后面的变量的取值对前面的变量有依赖关系，应该往条件概率方向去想
- H ：冷静观察这个分形结构，一个格子在一个分形结构内有五种情况，区分方式是它连向走到外面的出口在哪：一是在内部，需要经过(mid,0)，二三四五是经过上下左右的边界。同时还需要确定这个格子走到边界需要的步数。
确定了这些之后可以分类讨论两个格子间的路径：两个点在同一个块且属于五种情况中的同种情况，就两个点继续分形下去；否则就变成两个单独的点走到某些边界后直接算出在两点在边界上的距离。细节非常多，感觉做法可能有点垃圾。
补题
- C : zqq
- D ： zqq
- F ： zqq
- H ： lyk
- I ：