9.27

· · 个人记录

是越来越懒了。。

很简单的乱搞题。。找出结论乱搞切掉了。。 其实可以发现一个很显然的结论：对于一个不能走的区间$[x,y]$，显然$[x\%k,y\%k]$也不可以走，所以就可以把每一个黑块映射到$[1,k]$这一个区间上乱搞即可。 $T2$：大意就是给你一棵树，树上每个节点有不同的权值，这些权值还分了类，要求查询一个节点的子树内的所有节点中哪一种的权值最大，输出哪一种和那一种的权值和。 听说正解是线段树合并，并没太听懂，自己考场想了一个树上启发式合并，首先可以很容易到对于每个节点直接暴力统计，很明显的会爆炸，考虑一些优化，可以想到，因为对于每一个重链，总可以保证在同一颗子树内并且拥有很多节点，便考虑用树链剖分的思想，对于重链上的答案用桶记录下来，而对于轻儿子则暴力求，每次存到桶中，用完就退。 $T3$：给两个只含$a$和$b$的串，每次可以交换$ab$和$ba$，求一个变化方案 鬼知道他到底是什么算法，并没有题解，也并没有找到，反正考场并没有人想出来，但似乎是先判断可行移动，再通过移到一边来处理。