@
目录- A. Constructive Problems(800)
- B. Begginer's Zelda(1100)
- C. Largest Subsequence(1400)
- D. Cyclic MEX(2000)
- E. One-X(2400)
- F. Field Should Not Be Empty(2600)
- 提交记录
A. Constructive Problems(800)
注意到,对于 \(n\times n\)的矩阵,只需要把对角线全染黑即可。
推广到 \(n\times m\) 的矩阵,不妨令 \(m>n\),那么我们染 \(n\) 个格子把左边 \(n\times n\)的矩阵全染黑,而后对于剩下的矩阵随便找一行全染黑即可,所以:\(ans=\max(n,m)\)
B. Begginer's Zelda(1100)
考虑每次合并一对叶子节点,只剩一个时和根节点合并,这样次数最小。
随便口糊一下证明:因为每一个叶子结点都要合并,那肯定是跟其他叶子结点合并最优。
C. Largest Subsequence(1400)
考虑最终情况,即将典序最大的子序列变成 从小到大 的再插回原序列中,即可判断是否有解和次数。
Tips:
找典序最大的子序列 可以从后往前,没找到一个比自己大的就直接替换,可以证明是对的。
D. Cyclic MEX(2000)
考虑模拟每一次操作。
先求出前缀 mex,则每把一个数 \(a_i\) 扔到后面,则前缀 mex 中 \(<a[i]\) 的不变,\(>a[i]\) 的变为 \(a[i]\),由于前缀 mex 单调不减,考虑用单调队列维护即可。
注意需要维护权值跟出现次数两个东西。
E. One-X(2400)
正难则反,考虑计算每一个节点作为 lca 被计算了多少次。
设节点 \(x\) 所对应的区间为 \([l,r]\),区间长度\(len_x=r-l+1\),那么 \(x\) 的左儿子对应区间为 \([l,\left \lfloor \frac{l+r}{2} \right \rfloor ]\),长度为 $\left \lfloor \frac{l+r}{2} \right \rfloor -l+1=\left \lfloor \frac{r-l+2}{2} \right \rfloor =\left \lfloor \frac{len_x+1}{2} \right \rfloor $,用 \(L\)表示,同理, \(x\) 右儿子所对应区间长度为 $\left \lfloor \frac{len_x}{2} \right \rfloor $,用 \(R\) 表示。
若 \(x\) 节点作为 lca 有贡献,那么它的左右子树内都至少选一个点,多的不限,所以合法方案数为 \((2^L-1)\times (2^R-1)\) (除了全不选其他都和法)
又发现对于不同的点 \(x\),若它们对应区间长度相同,那么合法方案数都一样,根据乘法分配律可以将它们节点的值合起来。
于是正解来了:
考虑直接记忆化搜索。
令 \(f[x]\) 表示对应区间长度为 \(x\) 的节点值之和,\(g[x]\) 为长度为 \(x\) 的区间个数。
得出转移公式:
若 \(x\ne 1\),那么:
其中 \(ls,rs\) 为 \(x\) 的左右儿子。
为什么呢?
回到建树过程:
void buuild(int x,int l,int r){
//
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
}
就是这两行,懂?
于是我们就可以欢乐记忆化暴搜了。
对了,忘记证明时间复杂度了,关键是 线段树上长度不同的区间个数是 \(\log n\) 级的,这就能保证时间复杂度了。
F. Field Should Not Be Empty(2600)
这里用 \(a\) 代替题目中的 \(p\)。
观察到一个数是好的,当且仅当 \(a[i]=i,\max_{j=1}^ia[j]=a[i]\)
瞪眼法可知,我们只会换逆序对,除非没有(所以要特判),因为这样原来是好的还是好的,原来不好的有可能变为好的,可证明是最优的。
那我们考虑对于一个不好的点,记录那些操作能把它编号,最终我们取最大的即可。
考虑分类讨论:
-
\(a[i]=i\),则能把 \(a[i]\) 从不好变为好 当且仅当只有一个 \(j<i\),使得 \(a[j]>a[i]\),则调换一下 \(a[j]\) 和\(i\) 后面那个小于 \(a[i]\) 的即可。
-
\(a[i]>i\) 此时只有可能把 \(i\) 和 \(a[i]\) 位置调换才有可能,判断一下即可。(这里不详说,留给读者仔细思考)
-
\(a[i]<i\) 同上