算法
暴力
容易发现双指针可以找到每一个区间 \([L, R]\), 使得这个区间覆盖 \(1\) ~ \(n\) 的每一个数, 也即区间外覆盖 \(1\) ~ \(n\) 的每一个数, 这是 \(O(n)\) 的
考虑判断
对于两个数列 \(A\), \(B\)
显然, 在 \(A\) 中先取出的要在 \(B\) 中最后取出, 所以把 \(A\) 压入栈中, 判断栈顶是否在 \(B\) 的两端出现, 完事之后记录一下
正解
发现瓶颈在 \(O(n)\) 找区间上
如果假设第一次取左端
那么与之相对应唯一确定的一个数就必须最后一个取
于是分成两段
于是易得
代码
??? 有时间补
总结
善于运用基础数据结构
分析瓶颈之后想办法优化
标签:瓶颈,一个,2021,区间,CSP,回文 From: https://www.cnblogs.com/YzaCsp/p/18450102