题解1203 div cf

## problem 给出 n 个数组 A1​ 到 An​ ，数组中的元素为 1 到 M 之间的数字。 数组之间也存在字典序，即从第一个数开始逐位比较，一旦某个数字大于另一个，则数组的字典序大于另一个，如果某一个是另一个的前缀，则前缀的字典序更小。 你可以选择一些大于 0 的数字执行减法操作，一旦选 ......

## 前置知识：高斯消元 已知 $n$ 元线性一次方程组。关于 $x_1,x_2,\cdots,x_n$。 $$ \begin{cases} a_{1, 1} x_1 + a_{1, 2} x_2 + \cdots + a_{1, n} x_n = b_1 \\ a_{2, 1} x_1 + a_{ ......

### 1753. [Codeforces Round #829 (Div. 1)](https://codeforces.com/contest/1753) Performance 2343. #### A2. Make Nonzero Sum (hard version) 如果序列和为奇数，即不 ......

题目链接：[D - Ball Sorting](https://codeforces.com/contest/1839/problem/D) 题目大意：需要对一个排列按照指定操作进行排序。操作一：在数字间插入一个特殊点，可执行不超过 $k$ 次；操作二：将在特殊点旁的数移动到任意位置。所有操作结束后 ......

https://codeforces.com/problemset/problem/570/E 双向DP，类似于摘樱桃：https://leetcode.cn/problems/cherry-pickup/ 记忆化搜索，超内存 ```cpp #include #include #include #i ......

# [SHOI2011]双倍回文 题解 > 看了一些写回文自动机的大佬的代码，我深感敬畏，于是我转身向Manacher走去 现在荣登最优解第一页……  说实话，这个方法的复杂度是很 ......

# 题意简述 在黑板上有两个数字，进行如下操作 $n-2$ 次： - 每次在黑板上选择任意两个数，将两个数的差的绝对值写在黑板上。 这样你会得到一个长度为 $n (3 \le n \le 100)$ 的序列。 一共 $t (1 \le t \le 100)$ 组数据。 每组数据给定操作后的序列，需要 ......

# The Child and Polygon 题解 > 这世界这么大，遇到了这个奇奇怪怪的题。 这道题其实可以很自然的联想到卡特兰数。 在卡特兰数的计数中，有这么一个意义：$C_n$ 表示把有 $n+2$ 条边的凸多边形分成 $n$ 个三角形的方案数。 利用这个意义可以得到 $C_n$ 的另一个递 ......

# P7959 [COCI2014-2015#6] WTF 题解 > 呃，是一道 `DP` 题 说实话，原题实际上是不要输出一种方法的……但是似乎放这道题的人想增加一点难度？ 这里有两种做法，但都是 `DP`。 ## 预备观察 我们首先观察一些性质，以方便解题。 - **循环不变**：我们可以观察到 ......

比赛链接：[【LGR-142-Div.4】洛谷入门赛 #13](https://www.luogu.com.cn/contest/109937)  rk288，比前几次差（可 ......

~~模拟赛题，数据水被 dfs 草过去了。~~ 我们可以把每个点分成两个点 $a_{i, j}, b_{i, j}$，设这一行中选取的数为 $v$，那么对于一行内 $\ge v$ 的点选 $a$，大于 $v$ 的点选 $b$，那么题目的限制相当于每个点只能够选一个颜色。 看起来就像网络流，考虑怎么转 ......

### 前言 XXX：你瞅你长得那个B样，俺老孙就(氧化钙)...... 这魔法(J8)少女能不能去死啊啊啊啊啊啊啊啊啊啊...... ### 正文 #### "LJJ你是来搞笑的吧" 你说得对, 但是这数据就是骗人的. 首先看题面: ![image](https://img2023.cnblogs ......

[题目链接](https://www.luogu.com.cn/problem/CF1610I) 从 $k = 1$ 开始考虑，即为[这道题](https://www.luogu.com.cn/problem/AT_agc017_d)。 > 记点 $u$ 的 SG 函数为 $f_u$，$v$ 为点 ......

# [AGC055B] ABC Supremacy 题解 ## 题目描述 给定两个长度为 $n$ 的字符串 $a$，$b$。 你可以进行若干次以下操作： - 若 $a$ 中的一个**子串**为 `ABC`，`BCA` 或 `CAB`，那么可以将这个子串替换为 `ABC`，`BCA` 或 `CAB`。 ......

[题目传送门](https://www.luogu.com.cn/problem/P3377) 这是一篇使用 Treap 的题解。~~其实本质还是随机堆但有些不一样的地方~~ Treap 是 Tree（树） 与 Heap（堆） 的结合，每个结点有 $\text{value}$，$\text{prio ......

[TOC] ## 潜入行动 一眼直接 DP。 设 $f_{i,j,0/1,0/1}$ 表示 $i$ 子树内放了 $j$ 个监听设备，$i$ 是否被子结点覆盖，$i$ 是否放了监听设备，$i$ 子树内除了 $i$ 都被覆盖的方案数。 转移是一个树形背包，时间复杂度 $\mathcal{O}(nk)$， ......

[题目传送门](https://www.luogu.com.cn/problem/CF1266A) 一道模拟题。 纯模拟肯定不行，考虑优化。$60 = 2^2 \times 3 \times 5$，也就是说我们判断组合后的数字能否被 $2$，$3$，$10$ 整除即可。 如果这个数能被 $2$ 整除 ......

[题目链接](https://www.luogu.com.cn/problem/CF547E) 温馨提示：做本题之前可以先尝试这个：[洛谷 P2414 阿狸的打字机](https://www.luogu.com.cn/problem/P2414)(是简单版的uwu)。 首先，这个题涉及多模式串匹配， ......

好厉害。 首先发现一件事情，就是假如存在一个 $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 ......