题解codeforces round 1805

[比赛地址](https://codeforces.com/contest/1839/my) ## A.The Good Array 题意：定义一个数组是good的要求有： 从左往右所有的i，前i个数中至少有[i/k]个数是1 从右往左所有的i，前i个数中至少有[i/k]个数是1 问good数组对于 ......

[题目链接](https://www.luogu.com.cn/problem/P4119) 首切 Ynoi QAQ 调了4个小时 ## 题目描述 写个支持以下操作的数据结构： 对于长度为 $n$ 的序列 $a$， - 给定 $l,r,k$, 求序列 $a$ 在该区间的 kth - 给定 $l,r, ......

[题目链接](https://www.luogu.com.cn/problem/AT_arc142_d) 大佬讲解的太精简了，做点蒟蒻视角的思考补充。下面记摆放棋子的点为黑点，没有摆放棋子的为白点。 因为进行无数次操作后，占据节点集合总是唯一，所以黑点一定是在反复横跳；每个位置上只能存在一个黑点，所 ......

前两天忘发出来了，补一下QAQ ## [题目链接](https://www.luogu.com.cn/problem/AT_abc300_f) ## 题意简述 给定一个长度为 $n$ 且只包含 $\texttt{o}$ 和 $\texttt{x}$ 的字符串 $s$ 以及正整数 $n$ $m$ $k ......

可以得到： $$\varphi(ij)=\dfrac{\varphi(i)\varphi(j)}{\varphi(\gcd(i,j))}\gcd(i,j)=\varphi(\mathrm{lcm}(i,j))\gcd(i,j)$$ 证明考虑 $\varphi$ 的展开式。 选取中间的式子带进去化简。 ......

###题目大意 题目真的是不说人话...... 有一个国家的国旗是由一个 N * M 的方格组成的。如果想要这面国旗合法，就必须满足要求： - 国旗从上到下必须是白色、蓝色和红色，顺序不能改变。 - 每一种颜色都至少有一行。 小a这时候捡到了一块破布，希望你通过涂颜色的方式，把破布成合法的国旗，并且 ......

[传送门](https://www.luogu.com.cn/problem/P4556) 如题目所言，这就是个线段树合并的板子题。 ## 题目大意 ### 题目描述 首先村落里的一共有 $n$ 座房屋，并形成一个树状结构。然后救济粮分 $m$ 次发放，每次选择两个房屋 $(x, y)$，然后对于 ......

#### 题意 给定一个主串 $s$ 和一些模式串 $p_i$，问主串中是否存在两个不相交的非空字串，拼起来和模式串相同。 考虑如何拼接 $p_i$。我们可以从前向后匹配一遍主串，找到 $p_i$ 的所有长度的前缀在主串中最先出现的位置，并记录下来；然后再从后向前跑匹配，每次匹配上一个后缀，就判断该 ......

[Luogu](https://www.luogu.com.cn/problem/CF1559D2) | [Codeforces](https://codeforces.com/problemset/problem/1559/D2) ### 题意 给定两个森林 $A$ 和 $B$，均有编号 $1$ ......

2023.6.6 C. Scoring Subsequences（二分）（1300） C. Where is the Pizza?（并查集判断环）(1400) D. Vertical Paths (dfs，写法上对于处理叶子节点可以优化)（1300） ......

交了整整 2 页，本来想用随机化卡过去的，后来发现我的实现跑得太慢就写正常做法了。 首先发现最优答案对应的四个点只可能有以下两种可能： - $a,b$ 间有边，$c,d$ 间有边，此时答案是 $a,b$ 边权值加 $c,d$ 边权值。 - $a$ 与 $b,c,d$ 三个点间都有边，此时答案是三条边 ......

看到 `shortest paths` 来做的。 首先有一个贪心的策略，对于当前点 $u$ 若不能直接往后走则肯定是选择经过的点中 $w_i$ 最大的加。 很好理解，证明就不需要了。 所以可以定义状态 $f_{u, mx}$ 为 $u$ 点最大能加的值为 $h_{mx}$ 的最优状态，$h$ 是 $ ......

显然无法用 polylog 的数据结构维护，序列分块也不行，考虑询问分块。每 $B$ 个询问处理一次。 将这个询问中 $2,3$ 操作涉及到的点设为“关键点”，那么容易发现，环上每一段以关键点结尾的链在这块操作的过程中始终保持不变，也就是说我们可以把它们缩在一起。 先预处理出每个块的增量对每组询问的 ......

不知道怎么放到 div1F 的，感觉没啥亮点。 首先对于一条 $1$ 到 $n+1$ 的路径而言，它经过的点的编号一定是递增的，也就是说，如果我们将关键点大小排个序，那么答案就是相邻两点间最短路的和。删 / 加点造成的变化是 $O(1)$ 的，所以问题等价于，多次询问这张图中 $x,y$ 之间最短路 ......

先考虑一个平方的做法。我们先问出 $1,n$：遍历所有元素，删掉它以后问一下剩余 $n-1$ 个元素形成的集合，如果是 $n-1$ 的倍数说明这个元素要么 $1$ 要么 $n$，由于两个排列是镜像的所以任意钦定一个是 $1$ 一个是 $n$ 即可。删掉两个元素以后归纳问剩余部分也可以知道 $2,n- ......

[洛谷传送门](https://www.luogu.com.cn/problem/CF1838E "洛谷传送门") [CF 传送门](https://codeforces.com/problemset/problem/1838/E "CF 传送门") **结论：$a_i$ 对答案没有影响。** 考虑 ......

数据结构好题。 先考虑如果 $s_i$ 全是 $1$ 怎么做。考虑一个非常特殊的状态：如果当前最靠左的舞蹈者跳一步就能跳到最靠右的舞蹈者的右边，那么这样的局面性质其实是非常完美的。因为容易归纳证明，这样的局面下，每一步最靠左的舞蹈者跳一步都能跳到最靠右的舞蹈者的右边，这样一来，如果维护出了初始局面下 ......

在MySQL中，可以使用ROUND函数对数字进行四舍五入并保留指定位数的小数，语法如下： `ROUND(number, decimals)` 其中，number参数表示要进行四舍五入的数字，decimals参数表示要保留的小数位数。 例如，要对数字3.1415926进行四舍五入并保留两位小数，可以使 ......

一、题目描述： 给你一个长度为 $n$ 的字符串 $s$ ，$s_i$ 要么是 $\#$ ，要么是 $.$ 。 求有多少种长度为 $n$ 的字符串 $t$ ，恰好由一个长度为 $\frac{n}{x}$ 的字符串循环 $x$ 次得来, 且对于每一个 $i$ 使得 $s_i$ 为 $.$，$t_i$ ......

设 $f(x,t)$ 为 $t$ 时刻 $x$ 的水平。 手玩一下发现 $f(x,t)$ 开始的一段时间是 $a_x$ 或 $a_x+t$，后面的一段时间是 $f(p_x,t-1)+1$。 更加具体地，有 $f(x,t) = \max(\min(f(p_x,t-1)+1,a_x+t),a_x) \q ......

[DRTREE - Dynamically-Rooted Tree](https://www.luogu.com.cn/problem/SP14943) 本题建议评蓝。 ### 思路： 题目就是要对一颗不定根树求子树权值和。 这题不带修，如果带修难度会增加一点，就跟 [遥远的国度](https:// ......

[Meteors](https://www.luogu.com.cn/problem/SP10264) 蒟蒻初学整体二分，写一篇题解记录一下思考与看法。 ### 题目大意 在一个环形的轨道上分别着若干国家的空间站，在接下来的一段时间内会出现若干次陨石，每次出现在环形的某一段轨道，每个国家都想收集一定 ......

[Full Tank](https://www.luogu.com.cn/problem/UVA11367) ### 题目大意 给定一张 $n$ 个点，$m$ 条边的连通无向图，在每个点有一个加油站，油价为该点的点权，每条边的油耗为该边的边权。现给出若干询问，问一辆油箱容量为 $c$ 的车子是否能从 ......

[Visible Lattice Points](https://www.luogu.com.cn/problem/SP7001) ### 题目大意 给定一个 $N×N×N$ 的由若干点组成的立方体，点的坐标从 $(0,0,0)$ 到 $(N,N,N)$，求从点 $(0,0,0)$ 处可以看见多少个 ......

[We Need More Bosses](https://www.luogu.com.cn/problem/CF1000E) ### 题目大意 给定一张图，找到两个点，使得这两个点之间的所有路径必须经过的边最多。 ### 思路分析 我们先来思考一下如果已知两个点，怎么求两个点之间必须经过的边的数量 ......

[Substring of Sorted String](https://www.luogu.com.cn/problem/AT_abc285_f) 写篇题解纪念一下蒟蒻第一次赛时切出的 F 题。 ### 题目简述 对一个字符串进行单点修改，区间判断操作。 修改操作为将一个字符修改为另一个，判断操作 ......

[镜面通道](https://www.luogu.com.cn/problem/P3260) ### 题目大意 在一个二维平面内，给出一个镜面通道和若干个镜面元件，每个元件可能是圆形或矩形。求出为了能够使光从通道左边通过通道到达右边，至少需要拿走的元件个数。 ![](https://i.imgloc ......

[P5344 逛森林](https://www.luogu.com.cn/problem/P5344) ### 题目大意 ~~原题的题目大意已经很明确了要这个干嘛~~ 给定一些孤立点，将要进行两种操作： - 若两点之间不可以通过 $1$ 类边连通，则在两点之间连双向 $1$ 类边 - 若 $u_1, ......

[OTOCI](https://www.luogu.com.cn/problem/SP4155) ### 题目大意 给定 $n$ 个带权的点，需要进行四种操作：查询两点连通性；加边；修改点权；查询两点路径的权值和。 ### 思路分析 首先观察题目，我们会发现，在所有的操作结束后，所有的点构成一个森林 ......

[旅游](https://www.luogu.com.cn/problem/P3976) ### 题目大意 对一颗树进行两种操作：将一条从 $u$ 到 $v$ 的链上的点的权值增加 $x$；查询从 $u$ 到 $v$ 的链上最大的 $p_i-p_j(dis_{ui} using namespace ......