7.27模拟赛总结

又在把自己心态搞崩的边缘大鹏展翅了

发现自己有个问题： 上一场打的一般-> 这一场就迫切的想在某道题上打出一个高的离谱的分数-> 占用别的题的合理时间 ->寄

而且好像比赛开题有一种奇怪的偏向性）

正式比赛也有 就省选时那个括号序列我也特别不想做） 对树形的就特别想认真做一会 甚至今天都没犯困）

而且好像对于题目给的样例的依赖太强了）

今天T2挂了25 T3挂了20

一个特别不好的地方：

T1编了特别久最后还是暴力
T2挂分原因：指数上取模应该模phi(x)

时间安排

8.30-9.30

看题 T1树形dp T2感觉可以根号分治 T3不懂 （看见括号就开始头大

想了一会T1 编了一个不知道真不真的dp 但是复杂度$n^5$ 左右 而且感觉空间开不下

9.30-11.10

写T2 写完之后测样例 发现样例能过开始打表

同时优化了一下

然后整理T2的表 卡进12kb

11.10-11.40

写T3的暴力

11.40-12.10

写T1的暴力

题目分析

T1

感觉可以边权挪到点权之后 从下往上差分 然后考虑 一个对于链$x,y$ 的操作就是

1. 如果$x$ 是 $y$ 的祖宗 $x$ 点-1 $y$ +1

2. 设lca为 $z$ ,$z$-2 ,$x$+1 $y$+1

要求最后差分数组和dp数组相等

$f[x,i,j,k]$ 表示点$x$ 的子树内 有$i$ 个点向上并且没有匹配左点 $j$ 个点向上并且没有匹配右点 $k$ 个点左右都没有匹配时的方案数

转移时可以考虑两个点以$x$ 为lca 或者$x$和下面的一个点合并了

（不知道对不对 没写） 算不清楚复杂度 嘎） 应该是n^3?

upd

蚌不住了 订暴力订了半天 最后发现自己订暴力的时候把正解的式子推出来了）

$g[x,w]$ 表示在$x$的子树内序列上有$w$ 个颜色块的方案数

然后正解和暴力的区别是

暴力枚举父亲边代表的颜色块 左右选了多少

正解是直接放到树背包里一起做

我的暴力以为是不用做树背包 但发现会被3344这样的hack 然后看了看代码恍然大悟）

老实说 真的有人写60吗

感觉只要注意到树背包 把父亲边转换进去非常显然 就考虑父亲边要求左右各有一个 所以空隙数量少一 设去掉左右之后剩下$v$ 个 合并$x$ 个 那么方案就是 $C_{v+1}^x$ 其他的都不变化

T2

考虑小于80的时候 出现大于一次的只有2 3 5 7 ,所以这几个数存入状态 其他的二进制维护

T3

考试时的做法写得太草率了） 感觉就是因为括号匹配系列的题 模拟赛/考试基本没怎么拿过分然后一看就觉得麻木了） 感觉非常不好

正确暴力方法：考虑把所有操作都放进栈里然后模拟） 一定要模拟出那个括号！！！