题解1071 cf

好厉害。 首先发现一件事情，就是假如存在一个 $p | i$，那么假如某次操作为 $i | j, i| k$，那么我们选 $p|j, p|k$ 是不会更劣的。那么这就意味着，一定存在一些数 $p$ 满足没有数是它的因数，而这些数很显然也是不可能被删除的。我们找出这样的数的集合 $T$，剩下的数的集合 ......

题意：构造一个 $n$ 大小的锦标赛图，即每两点之间恰有一条有向边，满足任意点对 $(u,v)$，都存在一条从 $u$ 到 $v$，长度不超过 $2$ 的路径。 #### 方法一 考虑奇数情况，假设我们的点是在环上排列的，那么我们对任意的跨越不超过半个环的边都连上，也就是说，我们把点看成圆上的若干个 ......

## A [CF题面](https://codeforces.com/contest/1338/problem/A) 假定用到的最大的数是 $x$，那么一个数最大可以增大 $2^x-1$。题目只要求不降，所以求出将 $a_i 点击查看代码 ``` #include #define ull unsig ......

最近好像一直懒得写题解，但是感觉还是写一写比较好。 首先若干个向量组成一个凸包有经典做法，就是把向量按照极角排序，然后按照极角顺序依次拼接，得到的就是一个凸包，且方案唯一（由于本题限制不存在共线的两个向量）。 那么我们实际上只需要知道每个向量最终用了多少就可以了。设第 $i$ 个向量用了 $c_i$ ......

源网站 最近导航网站经常被流量攻击，疯狂跑网站流量，两个小时20G左右吧，一直困扰着我， 后来在电报群里的大神指点下，用上了CF的WAF的防火墙规则！ 添加防火墙规则表达式 第一 (cf.threat_score ge 5 and not cf.client.bot) or (not http.re ......

可以看做一个人手中有一些宝石，并将宝石分成两组，一组的编号为 1 至 n×m/2，二组为 n×m/2+1 至 n×m+1。当两组两个宝石编号相差为 n×m/2 为一对。现在要遍历一个 n×m 的方阵，只能走上下左右，且每个格子必须且仅能到过 1 次。并在遍历同时对每一个格子放入宝石。即遍历的第 i... ......

### 前言： 最近在做哈希的题，发现了这道好题，看题解里很多大佬的方法都很巧妙，自己就发一个较为朴素的方法吧。 ### 题意： [题目传送门](https://www.luogu.com.cn/problem/P3498) 给你一个序列，需要求出数 k，使划分的子串长度为 k 时，不同的子串数量最 ......

可以把每一个食物看成一个测试点。那么就是要计算出每个节点被哪条贪吃虫占领和每条贪吃虫最终停留的地方。 很明显，对于这两个要计算的值，可以通过两次 dfs 来求。 ......

因为连续四个格子一定是 2 黑 2 白，所以如果确定了 (i，j) 点任意方向上与其连续的三个点的颜色，就可以推出 (i，j)（即确定的三个中较少的那种颜色）。例如： 上图中第一行，由于前三个格子已经确定，要想符合条件，第四个只能是较少的黑色。 竖和斜也是同理，~~图有点丑，就不放了~~。 ......

[传送门](https://www.luogu.com.cn/problem/P2221) 输入时将 $r$ 先减 1。 发现收费之和为 $$ans = \sum\limits_{i = l} ^ {r} a_i \times (r - l + 1) \times (i - l + 1 )$$ 化简 ......

## 吐槽在前面 太菜了赛后6min过掉的G1，本来以为是因为G1没出没上蓝，结果System Test直接给我C题卡掉了，一看发现我数组开小了一倍，最后险些掉分。 总之就是状况频出的滑铁卢战役qwq。 ## [A](https://codeforces.com/contest/1840/probl ......

## 前言 去年 11 ~ 12 月写了一车训练小记，选了一些当时写的题解凝炼成这篇博客。转眼半年过去了，感觉自己的能力，码风乃至题解风格都变化不小啊！ ## [P7961 [NOIP2021] 数列](https://www.luogu.com.cn/problem/P7961) 显然是一个 $d ......

## [A](https://codeforces.com/contest/1839/problem/A). The Good Array ### 题目大意 给定两个整数 $n$ 和 $k$，规定一个$01$数列为好的的条件是，对于$1\sim n$中任意的 $i$，都有： - $a$ 的前 $i$ ......

这个分治策略其实跟整体二分差不多，但是它的应用面比较单一和具有针对性。 通常是 $dp_1,dp_2,dp_3,...,dp_n$ 只有 $O(d)$ 段。然后我们通过分治来看 $dp_i=v$ 的应该是哪一段。 ``` def solve(l,r) if dp(l)==dp(r) fill dp( ......

2021-03-16 ## 大致题意 给你一串数字，然后告诉你每一个格子能与哪些格子中的数字交换，问你最后能不能得到给你的一组排列。 ## 思路 对于位置i,可以与位置(i+d[i])和（i-d[i]）位置的数交换 则可以考虑把位置i可以交换的位置放入一个集合里，就想到用并查集来解决。 如样例2，合 ......

简化题意：给定一个无向联通图，给边两两配对，要求一对边有公共顶点，求最多配对数。 我们对原图 dfs。遍历到一个顶点，如果它连接偶数条边，全部配对。否则，保留它到父亲的边，其余全部配对。 最后至多 $1$ 条连接根的边没有被配对。 答案显然为 $\lfloor \frac{m}{2} \rfloor ......

## 前言 [题目传送门！](https://www.luogu.com.cn/problem/AT_abc277_g) [更好的阅读体验？](https://www.cnblogs.com/liangbowen/p/17464231.html) 好题，记录一手拆贡献的 trick。 ## 思路 我 ......

[题目链接](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$ ......

首先考虑为什么会有一个白格子四联通的限制，这意味着没有封闭的白格子区域。 那么我们将每列都划分成一些黑格子的连续段，有相邻格子的连续段之间连边，会形成一棵树。 然后考虑如何在树上求两个格子之间的距离。可以找到他们的 $lca$ 然后把 $lca$ 的每个格子放进队列里进行一次 $bfs$ ，得到两个 ......

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

先考虑正着做，我们只考虑整个 $b$ 序列中出现的第一个子序列 $a$。 这样，我们就是要往 $a$ 中插入 $m-n$ 个数，其中 $a_{i-1}$ 和 $a_i$ 之间不能有 $a_i$（否则就会有更靠前的子序列）。$a_1$ 前面不能有 $a_1$，$a_n$ 后面什么都可以有。 我们发现， ......

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

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