qoj

[题面传送门](https://qoj.ac/problem/6508) 感觉网络流学艺不精，被薄纱了/kk 原题意是最少一个点的链，在此基础上最少三个点的链，比较难去用网络流考虑。换个思路：先最大匹配出两点链，然后让最多两点链合并上一个单点变成三点链。这样显然单点最少，并且保证了不会有 $3$ 个 ......

[题面传送门](https://qoj.ac/problem/6504) 感觉，非常高妙的随机化！ 考虑怎么判定一个序列合法，将每种颜色的奇数位置看成左括号，偶数位置看成右括号，则一个序列合法当且仅当其括号序列合法。 现在带修，我们维护的东西需要满足如下性质： - 可逆：将相邻奇数位的信息和偶数位的 ......

巧妙！ ## 简要题意 一个序列包含 $0, 1, 2$，有两种操作： 1. 给定区间 $[l, r]$，令其中所有 $a_i\gets (a_i + 1)\bmod 3$。 2. 给定区间 $[l, r]$，问如果每次删去该区间内的两个相邻相等元素，最终能不能将其删空。 $1 \le n,q \l ......

题意：大小为 $1 \times n$ 的棋盘上有一些棋子，一次可以选择一个空的位置，将左边第一个棋子往该位置拉一格，右边第一个往这拉一格，操作完这个位置也必须是空的（也就是左右至少得有一格的空隙），问能不能把所有棋子变成目标状态。 将棋子位置的前缀和 $s_i$ 求出，每次操作相当于将一个 $s_ ......

## 题目描述 [here](https://qoj.ac/problem/2559)。 ## 题解 首先，我们对所有区间离散化，删除一个区间时，我们暴力删除内部还存在的子区间。 如果没有区间包含是好做的，因为我们删除一个子区间时，将区间按照左端点排序，可发现包含这个子区间的区间是连续的一个区间。 ......

## 题解 赛时得分：60/? 写了个乱搞 首先考虑无解的条件。注意到一次操作后，所有点的度数都没有改变，所以无解的充分条件就是存在一个点的度数在两张图中不相等。接下来尝试构造策略，使得度数相等的时候都能出解。 我们可以将题意转化一下，变为对图 $G$ 和图 $H$ 都可以操作，使得最后产生的两张图 ......

## 题目描述 [here](https://qoj.ac/problem/1878)。 ## 题解 考虑一条路径上只有 $a$ 的前缀 $\max$ 才是有用的，不妨考虑按照前缀 $\max$ 来划分。可以发现，这些连续段直接存在单向边连接。 现在，我们考虑如何求出这些连续段。一个点 $i$ 可以 ......

# QOJ 6504. CCPC Final 2022 D Flower's Land 2题解 ## 题意简述 给你一个只含 $0,1,2$ 的序列，相邻两个相同的数字可以直接消掉。 询问包含两种 - 区间所有数 $+1$ 并对 $3$ 取模。 - 求一段区间能否用上述消除方式消完。 ### 样例输 ......

# 留待有缘人修补此题翻译 # qoj6662 外环路 [原题目传送门](https://qoj.ac/problem/6662?locale=zh-cn) ## 题目描述 在遥远的未来，人类进入了许多外星行星。行星X也是其中之一，太空探索公司MR在行星X上建立了基地，进行探测和资源采集活动。 行星 ......

> 本题转化为梯形面积就已经不是很好想了（赛时切掉，开心！） 进阶为静态区间查询。 使用不删除莫队+凸包合并 - 凸包合并就是把散块和整块的凸包合并 - 注意这里两个凸包的横坐标值域是无交的 - 于是可以使用二分套二分解决此问题 > 代码咕着，感觉非常难写 ......

$k$ 固定的版本：。 先转成 Cyclic Distance 的版本：对于所有 $k$，求出选 $2k$ 个点，最大的 $\sum_{i=1}^{k} dis(p_i,p_{i\bmod k+1})$。 首先可以猜测一个结论：选 $x+1$ 个点的最优方案是在选 $x$ 个点的方案上加一个点。 实 ......

考虑对于每个合法的序列 $b$ 对应出唯一序列的 $a$： $a_i$ 为所有对应区间 $[l_j, r_j]$ 包含 $i$ 的 $b_j$ 的最大值，若没有则为 $1$。这样填完之后所有 $a_i$ 均为其最小可能值，若所有 $b_i$ 的值都正确，则序列 $b$ 合法。容易发现这样的映射是单射 ......

兔队线段树题。 记 $\{a_i\}$ 的前缀和为 $\{S_i\}$，记距离 $i$ 位置最近的颜色相同位置为 $pre_i$，那当钦定某个点 $i$ 为右端点时，左端点最小可以为 $\max\limits_{1\le j\le i}\{pre_j\} + 1$。 考虑对于线段树上每个结点 $p$ ......

如果给出的线性基不是最小的，那么无解。 考虑简单转化一下问题。先把线性基消元，求出 $X$ 在线性基中的 $\text{Rank}$，再判一下全选是否无解。令 $X\to \text{Rank}(X)$，问题可以转化为：在 ${0,1,..,X}$ 的子集中选若干个数，使得子集线性基满秩（即秩等于 ......