T1 数数
贪个心,比较显然
T2 数树
考虑求出不合法的部分,然后做容斥,但是容斥系数我不会配
T3 鼠树
大nb题
单点权实际上就是它的归属点的权,动态维护每个点的归属点是比较好做的,树剖一下拿个set维护重链上的黑点就行,注意求归属点时的细节,不是简单的prev upperbound。
考虑查询修改都怎么做。由上面的性质,我们实际上只需要维护黑点有关信息就行了。上线段树维护黑点的权,黑点的管辖点的个数,权与个数的乘积。
- 操作1
找到归属点,查询它的值。 - 操作2
直接在维护黑点信息的树上单点修改 - 操作3
子树内的黑点显然都是完全贡献的,与根相连的一个联通块的归属点可能在子树外,找到根的归属点的权,乘上这个联通块的大小就可以跑路了 - 操作4
直接在维护黑点信息的树上区间修改 - 操作5
计算出它的管辖点的个数,并继承它原来的归属点的权,修正它原来的归属点的管辖大小。 - 操作6
将这个点的权与上一层黑点的权作差下放到管辖点,实现就另开一棵线段树直接做子树加,然后调一次四操作把多的去掉。
T4 ckw的树
nb题 不会
T1 回文
比较水的Dp,枚举步数只记录行信息就能推出列信息,转移很显然。统计答案时分奇回文偶回文选一下交点就行
T2 快速排序
对着它给的Qsort优化是没有任何前途的。如果是nan就直接输出跑路,否则就是把比它严格小的数排好序丢到它前边,维护个当前扫过的数的最大值就行了。
T3 混乱邪恶
数学题,直接粘了,为什么错误的DFS和贪心能拿那么多分
T4 校门外歪脖树上的鸽子
最后俩字比较符合这题。
zkw线段树的思想。考虑把给的树剖掉,区间变成左开右开,跳一边维护另一边就行。
码咕了。