距离 NOI2023 还有 109 天,不能再沉溺于省选的成功了。开始更新博客!
4 月重点在 whk 上,不会更很多,为了调和 whk 的。
1.[NOI 2023 联合省选] 填数游戏
考虑对于第 \(i\) 个数,把 \(T_i\) 中的两个数连边,特别地,只有一个数连自环。
此时每个连通块只能是树/基环树。
基环树是好做的,因为后手只有两种取法,算一算就好了。
对于树,可以转化成:点有权值,对于一些边可以子树内+1/子树外+1,要使得最小点权最大。
有结论:取子树内的边一定是根到某个点 \(x\) 路径上所有能取的边。
原因是,考虑两个没有祖先关系的子树,同时取子树内不如同时取祖先外;对于两个有祖先关系的 \(x,f\) ,\(x\) 取子树内,\(f\) 取子树外不如 \(x\) 取子树外,\(f\) 取子树内。
可以画图理解一下。
由此,两遍 dfs ,第一次把每个子树的点权最小值算出来,第二次计算每个 \(x\) 的答案即可。复杂度是线性的。哎,这个没做出来很拉。
2. [NOI 2023 联合省选] 城市建造
开坑。
3.P4769 [NOI2018] 冒泡排序
首先观察到有 \(x>y>z\) 就寄了,继而发现没有 \(x>y>z\) 这个条件是充要的,而这个又能用某 D 氏定理转化成,能够拆成两个上升子序列。
先做没有字典序的限制,考虑取的两个子序列,一定有一个的末端是全局最大值。\(f_{i,j}\) 表示还要填 \(i\) 个数,其中 \(j\) 个数 > 另一个子序列末端。
讨论一下发现 \(f_{i,j}=\sum\limits_{k=0}^j f_{i-1,k}\) 。把图画出来就一目了然了,就可以把 \(f\) 写成两个组合数相减的形式。
至于有字典序的限制,枚举相同的前缀后,大概需要求一个 \(\sum\limits_{k=0}^p f_{n,k}\) ,根据定义这就是 \(f_{n+1,p}\) ,就做完了。
标签:两个,省选,个数,取子,树内,序列,杂题 From: https://www.cnblogs.com/cwhfy/p/17284149.html