20231101 构造题记录
A. 人生的经验
可以对于每个长度为 \(l-1\) 的串建一个点,每个点有 \(c\) 个后继状态, 也有 \(c\) 个入边,所以一定可以找到一个欧拉路
因此答案为 \(c^l+l-1\) 即所有可能的串首尾相接拼起来的长度
考虑用一个圈套圈求欧拉路,即每次拓展一个点,用栈维护,如果不能继续拓展就弹栈记录答案,最后倒着输出即可
这个算法是 \(\mathcal{O}(n)\) 的
对于每个点不需要真的建图,可以记录当前扩展到哪个字符,然后处理下一个的 hash
值
B. 矩阵
先将一行染成全黑,再将这一行操作的到所有的列上
假设当前考虑 \((i,j)\) 这个格子且 \((i,j)\) 为 .
如果 \(j\) 一整列都不存在 #
则要操作 \(2\) 次, 否则 \(1\) 次
注意特判初始一整列都是 #
的情况
C. Divide
考虑构造一个序列使得对于所有 \(i,j(j<i)\) , 满足 \(a_i\leq a_j\) 或者 \(a_i>a_j\)
D. Hby的旅游之都
先处理 topsort
, 然后每 \(40\) 个分成一小块, 每 \(40\) 小块分成一大块
小块内连 \(R\) 边, 小块与小块连 \(G\) 边, 大块与大块之间连 \(B\) 边
E. 单调上升序列
考虑将原图分成 \(n-1\) 个完美匹配
每个匹配 \(n\) 个点, 有 \(\frac{n}{2}\) 调边
考虑这样构造,按 \((i+j)\mod{n-1}\) 分组,然后每个组内连边递增,这样最长的递增链最多长 \(n-1\)
标签:每个,记录,构造,小块,20231101,考虑 From: https://www.cnblogs.com/xiaruize/p/17803508.html