2019-Sp051-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=001483 contest]
== 流水账 ==
== 总结 ==
'''zqq: ''' 今天我们很崩溃。
B题一开始没有想到势能分析是我的锅。
J题长链剖分的姿势还不够。不知道可以把值挂在dfs序上，这样才能开下数组。也没有想到点分会TLE成sb
感觉今天一开场就有好多题可以做，卡着卡着积累的题越来越多就有些混乱。比如E题推了很久，C的DP卡了，J也想了很久。
对于这种可做题特别多的场，要有适当的讨论，适当的多开。尽量不要出现已经有做法了其他人还再继续想。也不要三个人做不同的题但是都没有思路。还有对题目的选择，都可以做的时候需要一道道攻破。
'''虽然这两天代码能力有些下降，但是我还是应该更加自信一些，好多时候就是不够自信才很慌张。还有就是耐心的给队友讲做法。说不定lyk听懂长链剖分他就知道该怎么写了。'''
还有就是和队友交流题意和做法要更多，更清楚和耐心。对经典模型思维要敏锐一些，不会的多和队友讨论
'''建议认真听评讲，多和高中生交流。可以学到很多厉害的东西'''
=== 题解 ===
[wiki:2017-Sp268-team2 legilimens]
* B ： 势能分析线段树。lyk把它都归为segment beats。就是说考虑每一位，区间操作一些位后这些为都相同，然后就可以一起做了。考虑不同位的势能贡献，初始：O(nlogv) , 每次修改：O(mlognlogv)。然后线段树需要维护tag0，tag1表示当前有哪些位全部为0，全部为1。标记只需要维护把哪些位置0，哪些位置1，因为这个标记不可能相交，不存在先后顺序问题。再维护当前的还没有被确定的位的区间最小值。想清楚标记关系不难写。位运算最后用unsigned int,防止奇怪的事情。
* C ：f[i][j][k]表示考虑到第i个瓶子，当前段还剩j个，当前交换出去和交换进来差为k。注意交换进来的情况，很容易漏。
* I ：其实不需要推式子。因为角速度最大一定是离点最近。对每段都求一下这时的速度。
* J : 长链剖分统计。但是要注意写法。因为要对每种长度的链维护链表，不能直接开vector。应该利用长链剖分的性质，长链是dfn连续的一段，从而用O(n)的空间维护链表头。链表尾也需要维护。因为合并的时候必须是O（链长），不能是O（子树大小）。'''写代码的时候稍微灵活一点，其实很好写。主要是对长链剖分的写法不熟悉。'''还有100w的点分要非常谨慎，这道题开了4s时限，但是怎么都开不过去。点分太慢了，有专门卡的数据，虽然随机数据可能比较快。dsu on tree可以过。
* K ：发现连a[i] + a[j] - M的边更优。然后这样的边只需要把a[i]排序，找到对i最小合法的位置pi，连i - pi一直到i - p(i - 1)
证明可以发现其他的边一定是四边形（i,j,pi,pj）中最长的边，所以不可能需要
=== 补题 ===
* B ： zqq
* E :
* F ：
* G ：
* H ：
* J ： zqq
流水账
总结
zqq: 今天我们很崩溃。
B题一开始没有想到势能分析是我的锅。
J题长链剖分的姿势还不够。不知道可以把值挂在dfs序上，这样才能开下数组。也没有想到点分会TLE成sb
感觉今天一开场就有好多题可以做，卡着卡着积累的题越来越多就有些混乱。比如E题推了很久，C的DP卡了，J也想了很久。
对于这种可做题特别多的场，要有适当的讨论，适当的多开。尽量不要出现已经有做法了其他人还再继续想。也不要三个人做不同的题但是都没有思路。还有对题目的选择，都可以做的时候需要一道道攻破。
虽然这两天代码能力有些下降，但是我还是应该更加自信一些，好多时候就是不够自信才很慌张。还有就是耐心的给队友讲做法。说不定lyk听懂长链剖分他就知道该怎么写了。
还有就是和队友交流题意和做法要更多，更清楚和耐心。对经典模型思维要敏锐一些，不会的多和队友讨论
建议认真听评讲，多和高中生交流。可以学到很多厉害的东西
题解
- B ： 势能分析线段树。lyk把它都归为segment beats。就是说考虑每一位，区间操作一些位后这些为都相同，然后就可以一起做了。考虑不同位的势能贡献，初始：O(nlogv) , 每次修改：O(mlognlogv)。然后线段树需要维护tag0，tag1表示当前有哪些位全部为0，全部为1。标记只需要维护把哪些位置0，哪些位置1，因为这个标记不可能相交，不存在先后顺序问题。再维护当前的还没有被确定的位的区间最小值。想清楚标记关系不难写。位运算最后用unsigned int,防止奇怪的事情。
- C ：f[i][j][k]表示考虑到第i个瓶子，当前段还剩j个，当前交换出去和交换进来差为k。注意交换进来的情况，很容易漏。
- I ：其实不需要推式子。因为角速度最大一定是离点最近。对每段都求一下这时的速度。
- J : 长链剖分统计。但是要注意写法。因为要对每种长度的链维护链表，不能直接开vector。应该利用长链剖分的性质，长链是dfn连续的一段，从而用O(n)的空间维护链表头。链表尾也需要维护。因为合并的时候必须是O（链长），不能是O（子树大小）。写代码的时候稍微灵活一点，其实很好写。主要是对长链剖分的写法不熟悉。还有100w的点分要非常谨慎，这道题开了4s时限，但是怎么都开不过去。点分太慢了，有专门卡的数据，虽然随机数据可能比较快。dsu on tree可以过。
- K ：发现连a[i] + a[j] - M的边更优。然后这样的边只需要把a[i]排序，找到对i最小合法的位置pi，连i - pi一直到i - p(i - 1)
证明可以发现其他的边一定是四边形（i,j,pi,pj）中最长的边，所以不可能需要
补题
- B ： zqq
- E :
- F ：
- G ：
- H ：
- J ： zqq