20221012考试总结

发表于 更新于 分类于

考试总结

考试

发挥一般

T1

很趣味的题，考虑计算答案的过程，首先从某个点开始，遇到

T2

平衡树模板，不做评价，权当练习使用 pb_ds。

其实有平衡树之外的多种解法。

值域分块

对这个东西其实一直不熟悉，如果序列分块不容易解决或者复杂度多一个 \(\log\)，那么考虑对值域分块，记录和每块数值有关的信息。

\(O(1)\) 改可以只改对应数值块和自身的数据，\(O(1)\) 查可以对块和块内维护前缀信息或者其它预处理信息。

树状数组上二分

写过若干次，但不熟练。

以前缀和树状数组为例，它每个节点 \(x\) 维护的信息是 \((x-lowbit(x),x]\) 区间的全部信息。

更新时一直 +lowbit，保证了恰好能够维护这些信息。

所以如何二分也比较明晰了。

1
2
3
4
5
6
7
8
9
int now=0,sum=0;
for(int i=18;i>=0;i--){
    // 现在认为在 (now,now+1<<i+1]
	if(1<<i|now<=n&&sum+c[now|1<<i]<k){//在 (now|1<<i,now|1<<i+1]
        now |= 1<<i;
        sum += c[now];
    }
}
int res = now + 1;

T3

有些价值的题，"优化状压DP" 还是有一些话题可谈。

T4

李超树模板题，类似 CDQ 分治的思路或者平衡树维护凸包其实很趣味，但是没有什么启发意义。

等有时间了写一份斜率优化的总结。