3658 4921 loj qoj

卡死人了。 数据随机写在上面，就是让你预估一下区间长度不会太长的，数据里最长的不超过 $2000$。 暴力扫 $2000$ 个显然过不了 $500000$ 的点，但是 $500000$ 的点 $m$ 为 $1$ 且必定询问整个序列。可以分析出，在随机情况下，前缀和最小最大数量是根号个的，平方后是四次 ......

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

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

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

[Problem Link](https://loj.ac/p/3629) 有一个长为 $n$ 的未知序列，给定 $m$ 个限制，每个限制形如给定 $i,j,k,x$，要求 $a_i,a_j,a_k$ 的中位数为 $x$。构造一个符合条件的序列或输出无解。 $n,m\le 10^5$。 首先这是一个 ......

[link](https://loj.ac/p/6160) 思维+容斥计数。 首先的转化比较妙，二分图转化为 $n\times n$ 的网格图染色。 > 与网络流的转化方向相反，值得注意。 然后发现两种颜色（红、蓝）如果独立染色，同一个格子可能会重复染色。 考虑容斥，式子很好列，直接容斥即可。 $$ ......

# 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上建立了基地，进行探测和资源采集活动。 行星 ......

经典问题，环形均分纸牌 设每个人的糖果数量为$a[1]$~$a[n]$ 设$b[i]$表示第$i$个人传递给第$i+1$个人的糖果数量（正负有意义），其中$b[n]$表示第$n$个人传递给第$1$个人的糖果数量 根据题意不难列出$n$个方程，看似$n$个未知数，只有唯一解，但其实只有$n-1$个方程 ......

惊奇地发现我的赛时做法也可以通过转化一下计算式优化到 $O(n+m)$。或许也算是一种另解？ 首先，我们考虑把后手的决策视为图上的一个自环或一条边。对于每条边，你要对其选择其连接的一个点，且使得其满足两两不同。 对先手的决策，则意味着对这个点 / 边的额外代价，包括 * 无额外代价。（$|S\cap ......

2023.7.3 [Problem Link](https://loj.ac/p/6669) 交互库有一棵 $n$ 个点的二叉树，你每次可以询问两个点之间的距离，猜出这棵二叉树。$n\le 3000$，询问次数上限 $30000$。 首先给你距离一定是先把每个点的深度问出来，确定一个大致的考虑顺序。 ......

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

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

注意到相邻两数的向下取整的差值不可能大于 $1$，也就是： $$ \lfloor \frac x k\rfloor-\lfloor \frac {x-1} k\rfloor \leq 1 $$ 稍微推广一下，我们得到： $$ x-1-\lfloor \frac {x-1} k\rfloor \leq... ......

首先不难想到一个贪心，就是先填出一个全黑的行，然后再用其填黑列。 而且在其中“填出一个全黑的行步数”我们应该最小化。 那么如何最小化“填出一个全黑的行步数”呢？我们发现关键所在是白点，我们可以进行操作填黑它。 我们设对应的操作为 $(x,y)$,白点为 $(a,y)$,则 $(x,a)$ 为黑。 ......

链接：[#10121. 「一本通 4.2 例 3」与众不同](https://loj.ac/p/10121) # summarization 给出一个长度为 $n$ 数列 $a$ 和若干个询问，询问某一段区间内最长的「完美序列」的长度。（「完美序列」：一段连续的序列满足序列中的数互不相同） # so ......

## loj6728 U 群把妹王 The most important part is the PIE coefficient. with out loss of generality, consider the case of 1 dimension. denote $p:n$ $p\in$ p ......

# 题目 [点这里](https://loj.ac/p/3406)看题目。 给定一张包含 $n$ 个顶点和 $m$ 条边的 **无向连通图**，Tom 和 Jerry 在图上进行了 $q$ 次追逐游戏。 在第 $i$ 次游戏中，Tom 一开始位于顶点 $a_i$，而 Jerry 一开始位于顶点 $b ......

做到这题，发现自己对$SAM$的一些性质还不知道，特此记录。 题目要求01字符串区间内前缀的最长公共后缀 由SAM parent tree性质可知，2个前缀的最长公共后缀就是它们在parent tree上lca的len值 如何去感性理解 我们知道，在parent tree上每个节点都代表了一个end ......

## 题目大意 有 $n$ 个物品，第 $i$ 个费用为 $w_i$ ，价值为 $v_i$ ，对于 $k\in[1,m]$ 求费用为 $m$ 时能获得的最大价值。 $1\leq n\leq 10^6,1\leq m\leq 5\times 10^4,1\leq w_i\leq 300,1\leq v ......

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

设当前询问的串为 $s_i$ 记为 $t$。考虑 $r$ 右移，维护每个 $l$ 对应的 $g(l,r)$ 和 $\max_{l}\frac{g(l,r)}{r-l+1}$ 即可。 最基本的观察是：当 $r$ 右移后，考虑 $t_{1..r}$ 在 AC 自动机上匹配到的点 $p$，那么对于 $p$ ......

# 题目 [点这里](https://loj.ac/p/3405)看题目。 有一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$。初始时，$\forall 1\le i\le n,a_i=1$。 接下来进行 $d$ 轮操作。每一轮操作会以 $\frac{a_i}{\sum_{j=1} ......

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

模拟赛考的题，但是模拟赛没有打，哈哈，摆烂。 考场上想到大致做法了，没继续推，去打 GP of Tokyo 了。 首先发现操作都在查询前面，所以我们只需要预处理出答案即可。 我们先记 $b_i$ 表示对 $i$ 进行的操作的总和，那么容易写出 $a_i$ 的式子： $$ a_i = \sum_{j ......

# 教主的魔法 ## 题目描述 教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给 XMYZ 信息组每个英雄看。于是 $N$ 个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为 $1, 2, \ldots, N$。 每个人的身高一开始都是不超过 $1000$ 的正整数。教主的魔法每次 ......

# 题目 [点这里](https://loj.ac/p/2462)看题目。 小 A 有一棵 $N$ 个点的带边权的树，树的每个节点有重量 $w_i$ 和价值 $v_i$。 现在小 A 要从中选出若干个节点形成一个集合 $S$，满足这些节点重量之和 $\leq M$ 并且构成一个连通块。小 A 是一个 ......

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

题目链接 题意 给定整数 $n(1\le n\le 10^{25})$，求 $n$ 以内 Powerful Number 的个数，以及它们的和。 题解 Part 1 如果 $x$ 是一个 Powerful Number，那么它一定可以表示成 $a^2b^3$ 的形式。 我们限制 $b$ 不含（大于 ......

有意思的题，做这题的时候也发现了不少有趣的东西~~虽然不会做~~。 考场上没有看出来建图。事实上本题复杂的性质基本决定它需要一步图论转化，而互不相同也是一个经典限制。可以得到如下建图转化：对于集合 $T_i$ 的两个数，在它们之间建立无向边，用定向表示选择，则我们需要给边定向使得每个点的入度不超过 ......