# 某帅气的哥群周刊第五刊
**[第一期 Link](https://www.luogu.com.cn/article/e7l583bi)**
**[第二期 Link](https://www.luogu.com.cn/article/jyivt87v)**
**
最近更新
**置顶公告：**
- Sleeping Cup #7 已经开赛，欢迎参加！
- Sleeping Cup #8 即将开赛，欢迎参加！
- 网址：http://8.136.99.126/
---
欢迎来到 Sleeping Cup！
这是一个以 Hydro 做框架搭建的网站，但又又不只是一个以 Hydro 做框架搭建的网站。在这里，我们将努力打破你对 OI 的传统认知：
- 与众不同的体
拓扑排序，是 Toposort 的音译。
对于一个有向无环图，如果顶点 $u$ 能到达顶点 $v$，那么在序列中 $u$ 在 $v$ 的前面，最后由 $n$ 个顶点形成的任意一种（因为可能由多个序列均满足情况）序列叫做拓扑序列，求拓扑序列的过程叫拓扑排序。
由于只有有向无环图才有拓扑序列，所以有向无环图也叫做拓扑图。
由于顶点 $u$ 能到达顶点 $v$，那么在序列中 $u$ 在 $v$ 的
Prim 也是一种求生成树的算法，它与 Dijkstra 的写法基本相同，只是将更新距离从求和变成了取最小值，并且答案为每次最小距离的和，以及多了一些判断。
代码：
```cpp
int prim(int n, int s) {
memset(dis, INT_INF, sizeof dis);
dis[s] = 0;
int res = 0;
for (int i = 1; i <=
### 上转[NOI2024联合省选，寄](https://www.luogu.com.cn/article/gtf9fk30)。
### 4.12
晚上疯买零食……
### 4.13
T1 写了一个字符串读入，5min 结束（没想到直接可以用 scanf），T2 用数学方法 20 min 写完，想 T3，T4。
看 T3，没啥思路，直接写 T4 暴力 dp 转移，写了个寂寞，发现写法假
## [CSP2024，遗憾告别赛……](https://www.luogu.com.cn/article/370gtqlu)
又是一年，今年我高一了，目标不是 CSP1=，而是 NOIP1= 了，这一次的高中，我只给了我一次机会，高一一次定胜负，不论有无达线，高中后两年年都不会花时间在信息学上了，大悲。
### 7.1
被学校强行拉过去搞信息学了（只因我自主招生时交了证书？）。
## 7月
1. 用链式前向星时 `add_edge` 函数类型为 `void`，否则本地能过而提交会RE（原因未知）。
1. 边权为1用BFS，其余正权图用 Dij（+Priority Queue）负权边用 SPFA，SPFA一个点遍历到n次即产生负权环。
1. 有向图可能反向建边可以简化问题。
1. 通过在不同关键节点跑最短路的方法简化问题。
1. 建立对偶图转化问题。
1. 对于数据较小却有明
# [T1 U593635 交换](https://www.luogu.com.cn/problem/U593635?contestId=272916)
## 思路
~~这需要讲吗~~
用 `swap()` 按题意交换三个变量即可。
## 代码
```cpp line-numbers
#include<bits/stdc++.h>
#define int long long
using
Kruskal 是用来求生成树的一种算法。
给你一个图，要求删除一些边，使这个图成为一棵树，并让所有边的总和最小，成为这个图的最小生成树；反之则为最大生成树。
Kruskal 算法基于并查集，如果要求最小生成树就将所有边按权值从小到大排序；否则从大到小排序。随后遍历边，此时考虑是否将这条边保留在原图中，如果这条边的起点与终点处在一棵树上，就无需保留；否则因为排过序，为了保持树的连通一定是越往前
本篇题解将细致讲解本题的思路，并给出一种长度短而可读性高的解法。
[您可在我的博客中查看本文，谢谢！](https://www.cnblogs.com/crab-in-the-northeast/p/luogu-p8866.html)
[P8866 NOIP2022 喵了个喵 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/
# 主要条件(必须全部满足，除非次要条件全满足)：
1.不是灰，棕名。
2.排名$20.0k$以上。
3.不是被棕过的。
4.通过$300+$。
###### 次要条件：
###### 1.有勾。
###### 2.等级分>=200。
###### 3.估值>=130。
```
朋友如春日暖阳，温柔照耀心房，
在困境中伸出援手，如灯塔指引方向。
快乐时光，我们并肩徜徉，
忧愁时刻
创作原因（2025/8/26 11:34）：
> @[\_Kagamine\_Rin\_](https://www.luogu.com.cn/user/260985) : 会慢得跟屎一样，最关键的是我要封装 || @[AKPC](https://www.luogu.com.cn/user/540363) : 用数组手写双端队列 || @[\_Kagamine\_Rin\_](https://www
2025/8/15 开坑
2025/8/23 公开
202？/？/？ 完结
~~别问我为什么几乎不提 T4，你看我像是会的样子吗（~~
### 8/11
NOIP 模拟，展现真实水平。100 + 0 + 36 + 0 = 136，T2 是神秘反悔贪心，一分不会，T3 正解码量较大，考场上不卡 T2 估计也没啥机会。
### 8/12
从今天开始是联考，作为新初三选手根本不慌（划掉。
既然题目都说了用离散化，那么自然就要用离散化去写。
### 什么是离散化？
举个例子，给出一个集合 $\{ 1,100000,999,15\}$，那么离散化后就是 $\{1,4,3,2\}$。
我想你能看出来离散化是干啥的了，那这么做的目的是什么？
比如[这道题](https://www.luogu.com.cn/problem/P1496)，如果对每一个位置都建立一个桶，那显然空间会炸，
**注**：为便于理解，笔者对概念和结论进行了简化和不严谨概括。关于抽象代数之群论，见 [抽象代数学习笔记](https://www.cnblogs.com/alex-wei/p/18134522/Abstract_Algebra)，其中轨道-稳定子定理是结论 4.2。
### 什么是群
简单地说，群可以理解为一族描述操作的元素 $\{g_1, g_2, \cdots, g_n\}$ 构成的集
luogu.me 的 $\LaTeX$ 太旧了，无法显示我标为 `无法显示`。
# 基础符号
|ASCII 96$^{[1]}$|`\sim`|`!`|`@`|`\#`|
|:-|:-|:-|:-|:-|
|$`$|$\sim$|$!$|$@$|$\footnotesize{\tt\color{red}无法显示}$|
|`\$`|`\%`|`\land`/`\wedge`|`\And`/`\&`|
### C++基础头文件库及主函数+关闭输入输出流
```cpp
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cout<<"Hello World"<<'\n';
return 0;
}
```
### int1
## 刚学完状压DP，写个博客总结一下
------------
### 状压是什么
状压是状态压缩的简称，就是把一种状态变成一个数，但是状态必须是$0,1$组成。“变”的过程就是把这个状态**看成一个二进制数，转成十进制**。
为什么要状压？因为如果用数组存储状态，不但空间放不下，遍历时还会超时，所以用数的状态来存储。
------------
### 状压与DP
用状压结合上DP，其
我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？我的假期？
::::epigraph[声明]
本文章内所有内容不保证覆盖考纲，由于篇幅原因，也不会详细介绍每一个算法，仅用于选手们查阅复习。
::::
**CSP-J/S第一轮测试的考察题型是：**
1. 选择题，共 15 题，每题 2 分，共 30 分；
2. 阅读程序题，共计 40 分。一般（特殊标记除外）三道程序题目，判断题每题 1.5 分，选择题每题 3 分；
3. 完善程序题，共计 30 分，选
让我们来看这两个公式：
$$
sin'(x) = cos(x)
\\
\
\\
cos'(x) = -sin(x)
$$
从我们学习函数开始我们就见过它俩，但为什么 $sin/cos$ 导数是这样的？
我们今天用一种特殊的方法来证明一下，那就是使用欧拉公式 $ e^{ix} = cos(x) + i \cdot sin(x)$ ，如果不知道这种展开的朋友可以先去自行学习一下再来看
我们先求
[cnblogs](https://www.cnblogs.com/StarsIntoSea/p/18946566)。
# 前言
大部分定理的证明是参考的相关资料，因为我是菜狗 qwq，但都是在学习后自己独立写出来的。
因为写的时候是在不同时间写的，所以通读的时候会有一点割裂感。
我一开始写只是方便自己快速复习的，但是写着写着就感觉是在给别人看一样，也不重要了。
带 * 的是不知道放哪
# 今日比赛[8.28](https://www.luogu.com.cn/contest/273101)
::::::info[T1]{open}
## [U593675](https://www.luogu.com.cn/problem/U593675?contestId=273101)
:::::success[赛时代码&得分]
$$
\color{green}{Accepted\not10
一天，石室华清给四十九打来电话。他说：“你敢不敢和我举行联考大战？”四十九豪爽的答应了：“我当然敢！”，8月28日下午在各校机房举行，谁不来谁就是怂货。
四十九原本以为恐吓了华清，华清应该躲在家，不敢找四十九，可正当这时，我听见了音乐声，原来是四十九学校座机响了，一看，竟然是华清打来的电话，华清还真有勇气，四十九接通了电话，听道电话那头骂道：“小 $fvv$ ，你怎么还不来，再不来【点击输入文本
[题目传送门 CF741D](https://codeforces.com/problemset/problem/741/D)
题目大意：一棵树的边上有一些字母。对于每颗子树，要找到该子树中一条链，这条链所经过的边上字母经过调整后可以形成回文串。
---
算法：树上启发式合并 $+$ 状压优化。
可以将 $a$ 表示成 $2^0$，
将 $b$ 表示成 $2^1$，
将 $c$ 表示成
# 你被骗了
$内容 ooc，作者现在活的很好（$
:::epigraph[——Spooky]
不知道是哪时候遇见了你，也不知道是哪时候对你产生了感情；一切都来得那么突然，去得也突然……
:::
去年年初，我意外注册了洛谷，甚至是背着家长的。
当时的我以为洛谷就是一个做题网站，所以很少上线，名字颜色就一直停留在蓝，甚至有段时间还变灰了。
我从 ht 那里发现了一个用户，就关注了他，于是我的洛谷页面里就出
## 借我一片繁星，还你半生天明
> 以点点繁星，汇日日天明。
### 第一章：邂逅
“还有二十分钟，现在跑过去还来得及做两道题！”程一耀边奔跑着，边低头看了眼表。
正是这低头看表的瞬间，他转过一个弯，迎面撞上了一个人。
“啊！”一声惊呼和随后碰撞带来的疼痛让程一耀不得不抬起头正视面前的一切。
一个身材娇弱的女生坐在了地上，纤细的双手捂着额头。
程一耀刚想开口质问她怎么不看路，那个女
### [补题链接](https://vjudge.net/article/9636)
### Day 1 贪心构造交互思维
::::success[CodeChef-MINORPATH]
看到这种位运算的题目就立马想到按位考虑，从高到低，显然高位为 $0$ 比低位更优。对于每一位，贪心地考虑其能否为 $0$，$O(n)$ 跑一遍数列即可 check（每次能到达更大的就取 $\max$，不能走
**更新中**
- 我感觉我又要垫底了。
- 我在思考T3那么简单，为什么我没有过。是因为我过了前两题满意于现状了。
- 我觉得T3拿不到40分的都是傻逼。
- 感觉人生没有意义。
- 我觉得我又要挂分了。
- 可恶，我怎么一早上都没有过一道紫题。
- 我感觉我来到这里好自卑，你们都会top tree，我不会，我是不是要退役了。
- 我好自卑，我今天早上7道题一道都没有首切，我好废物啊。
- wh
**T1 交换**
AC
```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,c;
int main()
{
cin>>a>>b>>c;
swap(a,b);
swap(a,c);
cout<<a<<" "<<b<<" "<<c<<" ";
return 0;
}
```
---
[题面传送门](https://www.luogu.com.cn/problem/P3592)
## 1.寻找算法方向
##### 1.1 数据范围
首先我们发现，n竟然只有50！
说明我们肯定是要多次枚举位置的
时间复杂度估计在$O(n^2m)$至$O(n^3m)$之间
##### 1.2 初步暴力
暴力的目的是求出在解题过程中我们大致需要枚举的量
首先我们可以枚举每个点的取值，然后统计
### [[AGC001D] Arrays and Palindrome](https://www.luogu.com.cn/problem/AT_agc001_d)
### [[AGC001E] BBQ Hard](https://www.luogu.com.cn/problem/AT_agc001_e)
$\color{#9d3dcf}10.2$
化一下问题，现在要求：
$$
\sum_
本鬼是个抽象，很爱发疯，~~如果有跟我一样喜欢发疯的我很欢迎你~~。
本鬼现在初二，学校两周放一次假，所以有时候你给我发消息我十天不回是很正常的，如果我放假在家我会发犇犇说明我活着。
节假日和寒暑假一般每天在线。
以下是我在不同平台的联系方式：
* 微信：微信号 Ghosty_Neutrino，申请时记得说明你是洛谷的谁（打上你的洛谷用户名）
* QQ：
* b站：[up主の链接，麻烦给个关
[设定集](https://www.luogu.com.cn/article/zpnyawlz)
**经过协商，我与歌者决定各自运营一本章二**
---
无边无际的黑暗中，身着红衣的女孩睁开了双眼。她看了看四周，没有任何有异常的地方。“我是谁？这里是哪里？我该做什么？”，她努力的回想着，但却想不起任何事情，似乎回想本身也只是一个习惯性的动作。
一块赤红色的光点浮现在她的面前，她警觉地挪开了
考场里弥漫着铅笔划过纸张的沙沙声，还有那种熟悉的、略带紧张感的寂静。
我猛地睁开眼，发现自己正坐在一个略显陈旧的课桌前。桌上放着一份试卷、一张答题卡，还有一支削尖的2B铅笔。答题纸上赫然写着几个大字：
| **CSP-J/S第一轮认证 考生编号：AC-114514** *2024年10月21日 14:00-16:00*|
|:-:|
再向下望：
`考生姓名:wujinyu2012`
### 《借我一片繁星，还你半生天明》万字深度解析
#### 引言：星光与伤痕的双重奏
《借我一片繁星，还你半生天明》这个标题本身，就是一首凝练的诗，一个完整的寓言。它预设了一种交换关系：“借”与“还”，而交换的媒介是“繁星”与“天明”。这暗示了故事的核心将是关于**救赎**——不是单方面的施舍，而是双向的、互惠的疗愈。“繁星”象征着在黑暗中闪耀的理性、灵感、希望与陪伴；“天明”则代表着走出长
1. 复制别人的 `__client_id`（在别人的账号上）：
- 打开洛谷首页
- `F12`
- `>>`
- `Application`
- `Cookies`
- 复制`__client_id`右侧的乱码，这个乱码就是 **JC** 别人的关键（如果是 `Microsoft Edge` 就是在 `Application` 处改为应用程
# [SMI-Garbage](https://www.luogu.com.cn/problem/P3520)
## 题目描述
有一个可以看成无向图的城市，上面有 $n$ 个点和 $m$ 条边。
每一天，有若干辆垃圾车按照**环形**来跑一圈。并且，**对于一辆垃圾车，** 除了起点以外不能跑两次。
一条路有 $2$ 种状态：清洁的（用 `0` 表示）或不清洁的（用 `1` 表示）。每次垃
大家好，我没有死........
(每日睡觉(¦3[▓▓] 晚安）1/1))
ok啊，作者开启了抽象人生~qwq
**正题开始：**
小说背景：|额(⊙o⊙)…，好吧其实就是作者在家玩过家家，然后娃娃里有个阎王|呵呵确实过于抽象|（但不抽象作者也涨不了粉丝qwq）
|捕捉一只无聊小作者|
舆情：喵~o( =∩ω∩= )m，带上小花花就是我的人啦~~|贴贴|
**另一边：**（地府）
马上七夕节了，给大家安排一个表白小技巧，从零到一，十分详细。
## 观察
首先，你要确定你暗恋的人是不是对你有一定的好感度，表白只是确定关系的形式，并非发动**进攻**的**号角**，如果贸然表白，可能收到的就不是惊喜而是**惊吓**了。
## 方法
永远记住：**真诚是永远的必杀技！！！**
### 接下来对于人群进行分析：
- 腼腆内向性：
核心要点：在私底下，不要在公共场合，要
从去年联赛后就感觉自己颓过头了...甚至连 wzp 都在婊我太颓了...
开个 blog，~~假装~~督促一下自己。
之前写过的题就不写了。
~~如果没补完，或者进度太慢我可能又会把这篇 blog 删了~~
## 2.23
##### 「JOISC 2017 Day 2」门票安排
神仙题。
首先有一个结论，所有翻转的区间的并不为空。
然后就有了一个多项式做法。
# 扩展中国剩余定理 exCRT
## 算法介绍
要想学会扩展中国剩余定理，要先学会 [exgcd](https://www.luogu.com.cn/problem/P5656)，至于中国剩余定理，这并不重要。
中国剩余定理给了你一个一元线性同余方程组：
$$\begin{cases}x\equiv b_1\pmod{a_1}\\x\equiv b_2\pmod{a_2}\\\dots\\x
你谷系统维护，原博客看不了了 : (
**转载请在文章页面明显位置注明出处。**
出处：<https://www.luogu.com.cn/blog/IowaBattleship/latex-gong-shi-tai-quan>
PS：资料来源于 Wiki，凑合着看吧，不过洛谷的 LaTeX 对有些符号或功能并不支持，我就没有打上。
本文纯手打。
排版不好，见谅。
Updat
本文章同步发表在[博客园](https://www.cnblogs.com/LcukyCat/p/19043640/QianTanCDQFenZhi)。
---
CDQ 好强，拜谢 CDQ /bx
CDQ 是我教练的学姐喵！
---
# 什么是 CDQ 分治？
CDQ 分治一般用于求解偏序问题，二维偏序问题一般可以不使用 CDQ 分治而用普通分治或树状数组轻松解决，三维偏序问题 CDQ
## 引子
这是一段非常普通的代码。
```
#include<bits/stdc++.h>
using namespace std;
int main(){
double c=3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117068;
快进到 DP 式子：
$$
\begin{aligned}
f(i) &= \min \{f(j) + (h_i - h_j)^2 + s_{i-1}-s_j\} \\
&= \min \{f(j) + h_i^2 + h_j^2 - 2h_ih_j + s_{i-1} - s_j\} \\
&= \min \{-2h_ih_j + f(j) + h_j^2 - s_j\} + h_i^2 +
## 引入
提到 Python，多數人會先想到它「簡潔易讀」的語法、「萬物皆物件」 的設計，或是在資料分析、爬蟲、AI 領域裡開箱即用的豐富函式庫。但很少有人注意到，這門語言還藏著許多「不走尋常路」的巧思。
~~(疊個甲，我在澳門 Python 解難大賽拿過冠軍)~~
---
### 1. 海象運算符 (:=)
海象運算符允許你在表達式中進行賦值，簡化重複計算或賦值。
```py
if (d
考虑二维偏序。
我们将所有点按某一维排序，然后按照这一位扫描线。这样操作的目的是把这一维变成时间维。
然后维护一个树状数组，在扫描的过程中做在线的一维偏序。这是简单的。
这给了我们一个启示：离线的 $x$ 维偏序与在线的 $x - 1$ 维偏序的难度相同。做法就是将某一维转化成时间维。
同理对于三维偏序我们要做在线的二维偏序。考虑 cdq 分治。
首先按 $x$ 排序。
定义函数 $\
线段树合并。
考虑合并两颗线段树，设它们分别以 $root_x$ 和 $root_y$ 为根。我们递归合并这两颗线段树上的每个节点：
```cpp
void merge(int &x, int y, int l, int r) {
if (!x) x = y;
else if (!y) return;
else if (l == r) {
tr[x].v.first +=
路径加可以树上差分。即令 $res_{i, j}$ 表示答案中第 $i$ 个节点上 $j$ 种类的数量，$d_{i, j}$ 为其差分数组。每次操作 $(x, y, z)$ 等价于：
$$
d_{x,z} \gets d_{x, z} + 1 \\
d_{y,z} \gets d_{y, z} + 1 \\
d_{lca,z} \gets d_{lca, z} - 1 \\
d_{fa_{
MX-C day1 T1。
### 题意
数轴上有 $n$ 个点，构成了 $\frac{n(n+1)}2$ 个线段。令所有线段为全集。问有多少子集，满足这个子集内的线段，在两两不交的情况下能选出的最多线段数恰好为 $k$。$k \le n \le 500$。
### 做法
如果暴力 dfs，那么 check 的做法是经典贪心。即将所有线段按照**右端点**排序，然后顺次判断能不能选这条线段
MX-C day1 T2。
### 题意
给定 $k$ 个两两互质的正整数，求 $1 \sim n$ 中有多少数不能被任意一个数整除。
### 做法
「多少数不能被任意一个数整除」= $n - $ 「多少数能被任意一个数整除」。
考虑 DP。设 $f(n, k)$ 表示有多少个 $1 \sim n$ 的数，能被 $a_1,a_2\dots a_k$ 中的任意一个数整除。
很妙的转移！
MX-C day1 T3。
### 题意
[太长了回去看吧](https://mna.wang/contest/1242/problem/3)。
### 做法
我们给每个空隙一个属性：
$$
a_i = \left\{ \begin{matrix} 1&, s_i = \texttt {//} \\
-1 &,s_i = \texttt{\\\\} \\
+\infty&,s_i = \
MX-WF-C 8.14 最难题。
## 题意
给定一个 $n \times s$ 的矩阵。保证 $s$ 是 $2$ 的幂。你需要给出一种将矩阵的每一行重排的方案，使得对于每个矩阵中出现的数而言，在所有列中的出现次数的极差 $\le 1$。
## 做法
首先考虑 $s = 2$。不妨设这个矩阵形如 $[[u_1,v_1],[u_2,v_2]\dots[u_n,v_n]]$。
我们考虑将每
MX-C 8.16 模拟赛 T4。
对楼上大佬的题解做的一些详细解释。
## 题意
一条数轴上放了 $n$ 个球，第 $i$ 个球放在了位置 $x_i$，一个位置可能有多个球。
你需要从起点 $s$ 出发，捡起所有 $n$ 个球（一个球捡起了就不能放下了），回到终点 $t$。如果你能在规定时间 $T$ 内完成，则算你成功。
已知：拿起 $1$ 个球需要 $1$ 单位时间；带着 $x$ 个
> 给定一个网格，网格上有敌人，每次可以同时消灭某一行或某一列上的所有敌人。求消灭所有敌人需要的最小操作次数。
我们将每个敌人的所在行与所在边连边，问题转化成：
> 在图中选择最少的点，使得每条边的两个端点中至少有一个被选择。
这是最小点覆盖。而最小点覆盖等于最大匹配，所以直接 dinic 做完了。
太摆了丢个代码跑路：
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e7 + 10;
vector<vector<bool>> g;
int n, m, k, sx, sy, tx, ty;
vector<vector<bool>> st;
vector
### 题意
给定一张无向图。求有多少 $u < v$ 满足在 $u, v$ 间连一条边权为 $l$ 的边后，$s \rightsquigarrow t$ 的最短路 $\le k$。
### 做法
首先判掉最开始 $s \rightsquigarrow t$ 的最短路已经 $\le k$ 的情况。答案是 $\binom n2$。
否则，若原来最短路 $> k$，但加上 $(u, v)$ 这
不难发现：
$$
f_i = A_if_0 + B_i
$$
其中 $A_i = \prod_{j = 1}^i a_j, B_i = \sum_{j=1}^i b_j \times \prod_{k=j+1}^i a_k$。是关于 $i$ 的常数。
那么条件就变成了：
$$
\left\{
\begin{matrix}
A_1f_0 + B_1 \equiv 0 \pmod {p_1}
本题解的复杂度分析中均视求 $\gcd$ 是 $\mathcal O(1)$ 的。
## 题意
给定 $n$ 的排列 $a$。对于每个数字 $i$，求将排列中值为 $i$ 的数修改为 $1$ 后，所有区间的 $\gcd$ 的种类数。$n \le 2 \times 10^5$。
## 做法
令 $p_i$ 表示值 $i$ 在 $a$ 中的出现位置。有 $p_{a_i} = a_{p_i}
# vscode 高效配置和进阶（避坑指南）
为了简单易懂，我直接写了很多快捷键，大家请放心按。
身为一个换了 4 台电脑都每次能用 vscode 的人，我觉得这个配置方法还是很使用的。
同时我也再开了一个虚拟机重测了一遍，保证无误。
因为老是用，所以写的很详细，绝对是针对 OIER 最详细的配置指南。
---
以上都是吹嘘，太绝对了，但虚拟机上实测的确无误。
先上效果图（其实效果不
### 题意
令 $y^2$ 是距离 $x$ 最近的完全平方数，若有不止一个最近的直接输出 $\texttt{Game Over}$ 结束程序。定义 $f(x) = (-1)^{y+1}y$。
求 $\sum_{i=l}^r f(i)$。$l, r \le 10^{18}$。
### 做法
$\texttt{Game Over}$ 是不可能的。
显然第一步差分。问题变成求 $[1, r]
# 题意
给定一张 $n$ 个节点 $m$ 条边的简单无向图，和一个整数 $k \in [1, 3]$。你需要将每个点黑白染色。令在一种方案中，有 $m$ 条边的两端点都是黑色。求所有方案的 $m^k$ 的和。
# 做法
$m^k$ 很难受。我们可以理解成有 $m$ 条边，你要从中**依次**选择 $k$ 条边的方案数。**选择的边可能相同**。
例如，$(3,3,2)$ 和 $(2, 3
求二维 LIS。
首先将所有值按一维排序，在另一维上求解朴素的 LIS 即可。
<https://atcoder.jp/contests/abc369/submissions/57332899>
二分答案 $m$。
我们需要判断是否存在一个序列 $\{d_n\}$ 表示对于每个 $i$，第 $i$ 棵树如果在第 $d_i$ 天种下，都要达到 $a_i$ 的高度。
显然一棵树种的越早越好。我们可以求解一个 $f(i)$ 表示第 $i$ 棵树最晚在第几天种可以满足要求。
假设我们已经求好了。不难发现一个必要条件是：
> 对于所有 $1 \le i \le n$，满足 $f(u) \le
有两个序列，长度分别为 $a, b$。你需要将这两个序列合并成一个长度为 $a + b$ 的序列，且原序列中的元素的相对位置关系不发生变化。求方案数。
答案是 $\dbinom {a+b}a$。
https://www.luogu.com.cn/problem/P5689
## 题意
小 L 和小 Q 绝顶聪明。
给定长度为 $n$ 的 $a$ 和长度为 $m$ 的 $b$。$q$ 次询问，给定 $l_1,r_1,l_2,r_2$。小 L 要选择一个 $x \in [l_1, r_1]$，小 Q 要选择一个 $y \in [l_2,r_2]$。小 L 希望最大化 $a_x \times b_y$，小 Q 希望最小化 $a_x \times b_y$。求最后的 $
## 题意
$q$ 次询问，给定一个数 $r$。求从公元前 4713 年 1 月 1 日起 $r$ 天后的日期。
特别的：
- 公元 1582 年 10 月 15 日（含）以后：与现在相同。
- 公元 1582 年 10 月 5 日（含）至 10 月 14 日（含）：不存在，这些日期被删除。
- 公元 1582 年 10 月 4 日（含）以前：年份是 $4$ 的倍数就是闰年。
- 公元零年并
注意到数据范围很小，于是考虑直接搜索。
字典序最小意味着越靠前的指令应尽可能用编号较小的服务器，这也就确定了我们的搜索顺序，接着直接枚举就好了，找到第一个答案就直接输出。
代码：
```
#include<bits/stdc++.h>
using namespace std;
const int N = 10 + 1;
int n, m;
int a[N], b[N], u[N], f[N];
做这道题需要用到的：[The On-Line Encyclopedia of Integer Sequences, OEIS](https://oeis.org/)。
---
首先 $7$ 分暴力是极易的。
```cpp
cin >> a;
bool flg = false;
for (int b = 1; b <= 100 && !flg; ++ b )
for (int c = 1;
注意到，这是一道假扮成 OI 题的语文阅读理解题。
## 题意
有 $n$ 个细胞和 $n$ 种病毒，编号均 $1 \sim n$。
每个时刻每个细胞都会感染恰好一个病毒。令当前细胞 $i$ 中感染的病毒编号为 $c_i$。最开始第 $i$ 个细胞感染的病毒是 $i$，即 $c_i = i$。
在每个细胞心目中都有对每个病毒的能力的排名。即给定一个 $n \times n$ 的矩阵 $a$
很好很好的算答案方式。
> 小 D 有一个长度为 $n$ 的序列。如果序列不是非降的，他会选择一个元素删去，直到序列变成非降的，这时停止操作。求操作序列种类数，对 $10^9+7$ 取模。
>
> 两个操作序列不同，当且仅当它们长度不同或者某一次操作删除的元素位置不同。
>
> $n \le 2000,1 \le a_i \le 10^9$。
这个问题的难点在于，如果此时序列已经非降了那么此时
我们用 $(a, b) \xrightarrow{t, k} (c, d)$ 表示将数对 $(a, b)$ 通过参数为 $k$ 的类型-$t$ 的操作变化成 $(c, d)$ 的过程。如 $(2, 2) \xrightarrow{1, 2} (1, 4)$。
显然一次变化 $(a, b) \xrightarrow{t, k} (a', b')$ 后乘积不会变大，即 $a'b' \le ab$。
对于任意一个 $n + 1$ 的排列 $p$，不难发现有且仅有一个 $s$ 是满足 $p$ 被贡献入 $f(s)$ 的计算的。例如 $p=[1,3,2]$ 仅对应一个 $s = [\texttt <,\texttt>]$。
也就是如果我们从贡献的角度考虑，每个排列都被贡献进了答案恰好 $1$ 次。而排列总共有 $(n+1)!$ 个，每个贡献 $1$，所以答案为 $(n+1)!$。
```cpp
交互题真好玩。虽然我不会做。
## 题意
有 $n = 1000$ 枚硬币，其中有 $m = 10$ 个是假币，剩下的是真币。你需要用不多于 $q = 950$ 次询问交互库任意两枚硬币的真假是否相同。最后输出哪些是假币。
## 做法
显然你可以通过 $k - 1$ 次询问得到 $k$ 个硬币的相对真假关系。每次拿它和第一个问即可。
那么我们可以通过 $10$ 次操作得到 $11$ 个硬
经典题。
考虑 DP。设 $f(i, j, k, 0/1)$ 表示只考虑 $s_{1\dots i},t_{1\dots j}$，总共选了 $k$ 个**非空**子串，且 $s_i, t_j$ 是否**匹配**。
这里比较重要的是第四维。**匹配**的意思是指，$s_i, t_j$ 最终都被选择，且都被选择在了同一个（也就是第 $k$ 个）子串里。同理，不匹配就是指 $s_i, t_j$ 中有
**题目保证了输入 $a_i$ 递增。**
因为是二叉排序树，所以**树上每颗子树都能对应序列上一个区间**。或者说，这棵树的中序遍历就是给定的序列。
有个性质：$[l, r]$ 对应的子树里，$l$ 是最小值，$r$ 是最大值；且从根开始一直向左走最后到达的点是 $l$，一直向右走最后到达的点是 $r$。如果你学过笛卡尔树理解这些是容易的。
考虑区间 DP。设 $f(l, r, k)$ 表
注意到图中没有距离 $\ge 2$ 的路径等价于所有点的出度为 $0$ 或入度为 $0$。
我们令 $c_i = 0/1$ 表示 $i$ 的出度为 $0$ 还是入度为 $0$。
注意到相邻两点 $u, v$ 的 $c$ 一定不同。证明的话，如果这条边定向为 $u \to v$，那么 $c_u=1,c_v=0$。$u \gets v$ 同理。
因此变成了一个二分图染色的问题。
stO stO stO stO stO stO stO stO stO stO [](https://www.acwing.com/solution/content/3710/) Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz
---
给定一个长 $n$ 的行向量 $A$ 和 $n \times n$ 的矩阵 $G$。$q$ 次询问给定一个整数 $k$ 求 $A \times G^k$。显然其结果是一个向量。
直接矩阵快速幂能做到 $\mathcal O(n^3q \log k)$。若要求复杂度小于四方呢？
我们可以预处理 $G^1,G^2,G^4,G^8,\dots$ 等 $G$ 的 $2$ 的幂次方的矩阵。时间复杂度是
$a$ 在模 $P$ 意义下存在逆元当且仅当 $\gcd(a, P) = 1$。
在存在逆元的情况下，$a^{-1} \equiv a^{P-2} \pmod P$ 当且仅当 $P$ 为质数。
在存在逆元且 $P$ 不为质数的情况下，exgcd。
这是一篇树状数组优化 DP 的题解。
有显然 DP：设 $f(i, 0/1)$ 表示只考虑前 $i$ 个数，且第 $i$ 个数一定被划分到了子序列中，且 $i$ 是在这个子序列的奇数还是偶数位置的方案数。
转移可以枚举子序列中倒数第二个元素的位置：
$$
f(i, 0) = 1 + \sum_{j=1}^{i-1} [a_j = a_i] f(j, 1) \\
f(i, 1) = 1 + \
注意到当 $q$ 确定时 $r$ 也能随之唯一确定。因此问题变成了求有多少合法 $q$。
何为合法？$\left \lfloor \dfrac nq\right \rfloor = k$。
显然合法的 $q$ 是连续的。因此我们可以二分出 $q$ 的最小和最大取值 $q_{\min},q_{\max}$。那么 $q_{\max}-q_{\min}+1$ 即为答案。
注意需要特判：
- $b
不妨只考虑对金牌数排序的情况。按银牌/铜牌数量排序的情况类似。
显然如果有 $j$ 个小朋友的金牌数**严格大于**小朋友 $j$ 的金牌数，那么他的排名一定不小于 $j+1$。
而且题目告诉了你「如果自己和别的小朋友并列，那么他可以把自己写在最前面」。所以小朋友 $j$ 的排名可以取 $j +1$ 且这样最优。
于是问题变成了如何对于每个小朋友 $i$ 都计算出有多少小朋友的金牌数严格大于
我们将每个三目运算符抽象成二叉树上的一个点。然后令其左儿子为「数值1」，右儿子为「数值2」。特别的，若这两个儿子是十进制数，则单独为这样的十进制数做编号。
不难发现，这样建出的二叉树的叶子节点一定都是十进制数。
我们在这颗树上进行 dfs。在从根往叶子递归的过程中，维护 $L, R$ 表示只有当 $L < x < R$ 时程序才会进行到这个树点。特别的，若 $R - L \le 2$ 则停止递
如图。请用 $x, y$ 表达 $x',y'$。
推导过程不重要。答案为 $x'=\dfrac{\sqrt 2}2(x+y),y'=\dfrac{\sqrt 2}2(x-y)$。
在某些场合，我们并不注重具体值，此时我们可以将 $\dfrac {\sqrt 2}2$
点 $B = (b_1,b_2,\dots,b_n)$ 与点 $A =(a_1,a_2,\dots,a_n)$ 在同一条对角线上等价于：
> 存在一个整数 $k \ge 0$，使得对于每个 $1 \le i \le n$，都有 $|a_i-b_i|=k$。
显然点 $B$ 如果合法，那么这个 $k$ 是唯一的。我们不妨枚举 $k$ 然后统计有多少个合法点 $B$。
形式化的，我们令 $c_i
youyou $\to$ Alice，yy $\to$ Bob。
Bob 交换的列一定一黑一白，否则没有意义。
如果这一列都是黑，Alice 都选择一定最优。
如果这一列都是白，Alice 能只选一个就只选一个。这里【能】指可以使得左右连通起来。
所以最难做的是一黑一白的列。
Alice 在一黑一白的列上，要么只选黑，要么都选（选黑白）。
于是对于这些列 Alice 有两种策略：
1
SCC 缩点：
```cpp
int n, m, a[N];
vector<int> g[N];
int dfn[N], low[N], ts, stk[N], top;
bool st[N];
int id[N], cnt;
void Tarjan(int u) {
dfn[u] = low[u] = ++ ts;
stk[ ++ top] = u;
st[u] = true;
跟物理啥的没任何关系啦，题面给的一坨公式是为了让你看懂样例解释，虽然我没看。
我知道后面的贪心是经典问题。但是我不会于是自己造了个别的贪心。
## Description
一条长度为 $L$ 的道路上，有 $n$ 辆车和 $m$ 个测速仪。其中：
- 第 $i$ 辆车将从 $d_i$ 的位置出现，以 $v_i$ 的初速度和 $a_i$ 的加速度从左向右做匀加速运动。
- 第 $i$ 个测速
令 $fa_u$ 为 $u$ 的父亲，$son_u$ 表示 $u$ 的儿子组成的集合。
首先预处理 $f(u)$ 表示 $u$ 的子树内最深的点的深度。
对于一次询问，首先把答案的初始值设为 $f(u)$，表示一步也不向上走。
考虑处理 $g(u)$，表示从 $u$ 走到 $fa_u$ 后，接下来再从别的子树往下走，能走的最多的步数。其实就是我们强制了原题中只能向上走恰好 $1$ 步的答案。
upd：原来的代码锅了。
考虑转化成一个概率论的问题，即每个点的权 $01$ 随机，求期望点权和。这个东西再乘 $2^n$ 即答案。
显然节点 $u$ 在时刻 $t$ 时的值，是**初始所有（$u$ 子树内）距离 $u$ 为 $t$ 的点的点权异或和**。这里若 $u$ 子树内没有距离为 $t$ 的点则 $u$ 点权必为 $0$。而当这种情况发生及之后其贡献都为 $0$，也就不需要考虑了。令这
# T1
我们直接 DP 即可。
$dp_i$ 表示最大值为 $i$ 的满足集合条件的最大可选数量。
```cpp
#include<bits/stdc++.h>
using namespace std;
int n, x, dp[10000005], cnt[10000005], ans;
signed main()
{
cin>>n;
int maxi=0;
for(int i=1;
这有蓝？最开始还是紫？建议降黄/绿。
显然一条路径合法等价于前面只走 $0$ 边后面只走 $1$ 边。不妨枚举转折点。
令其为 $x$。现在我们要求有多少 $u, v$ 使得 $u \sim x$ 路径上的边都是 $0$，$x \sim v$ 路径上的边都是 $1$。
显然可以分别求然后乘法原理。以求 $u$ 的数量为例。
注意到，合法的 $x$ 在树上一定是一个连通块，且这个连通块内的边
首先 $\left\lfloor \dfrac {\lfloor \frac ab \rfloor}c \right\rfloor = \left\lfloor \dfrac a{bc} \right\rfloor$。所以我们只需要求解路径上所有边的边权乘积，以及支持单点（边）修改。树链剖分套线段树即可。
乘积会很大。而当它超过 `long long` 时除完下取整一定是 $0$。所以标记一下。
首先把区间长度 $\le 2$ 的提前计算好。接下来我们只计算长度 $\ge 3$ 的区间的答案。
考虑 CDQ 分治。
```cpp
void solve(int l, int r) {
if (r - l + 1 <= 2) return;
int mid = l + r >> 1;
solve(l, mid), solve(mid, r);
// work
}
```
不妨枚举警察局放在哪。设为 $u$。考虑求解”所有最短路中经过的安全边个数”。
不妨枚举这条安全边 $(u, v)$，然后计算有多少条最短路经过它。对于每个 $v$ 都算一遍然后加和即为答案。
首先，如果 $dis(1,u)+1+dis(v,n)\ne dis(1,n)$ 则无解。这里 $dis(i, j)$ 表示 $i \rightsquigarrow j$ 的最短路长度。
然后做最短路计
显然输入顺序是无所谓的。首先用个桶统计每个数的出现次数。
注意到 $3$ 张相同的「连续牌」在效果上完全等价于 $3$ 张「相同牌」。例如 $((1,2,3),(1,2,3),(1,2,3))$ 可以视作 $((1,1,1),(2,2,2),(3,3,3))$。
所以相同的「连续牌」的数量一定 $\le 2$。
考虑 DP。设 $f(i, a, b, c)$（$a,b,c \in [0,2]
## bellman_ford算法，朴素贪心
其原理为连续进行松弛，在每次松弛时把每条边都更新一下，若在n-1次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成。
### 贪心思路、描述性证明
首先指出，图的任意一条最短路径既不能包含负权回路，也不会包含正权回路，因此它最多包含|v|-1条边。
其次，从源点s可达的所有顶点如果存在最短路径，则这些最短路径构成一个以s为根的最短
显然可以转化成：
- $A < B$：$S_{A+1\sim B} < S_{A\sim B-1}$；
- $A>B$：$S_{B \sim A - 1} < S_{B+1\sim A}$。
我们第一种情况为例。
$S_{A+1 \sim B} < S_{A \sim B - 1}$，相当于从 $A$ 开始，第一个不满足 $S_i \ne S_{i+1}$ 一定是 $S_i > S_{i-1
可能写的有点烦琐。想省事的直接看后面的总结吧。
---
我们称在某两个相邻 $\texttt {AA}$ 间添加 $S_{\texttt{AB}}$ 为“$S_\texttt{AA}$ 操作”。其余类似。
首先第一步一定是 $S_{\texttt {AB}}$ 操作。即 $s = \texttt A + S_{\texttt {AB}} +\texttt B$。不妨对 $S_{\texttt
设 $f(i)$ 表示考虑前 $i$ 天，且第 $i$ 天一定不打卡的最大能量值。
转移枚举上一次不打卡的时间 $j$：
$$
f(i) = \max_{j=\max(0,i-k-1)}^{i-1}f(j) - d(i-j-1)+w(j+1,i-1)
$$
其中 $w(x, y) = \sum_{x \le l_i \le r_i \le y}v_i$，即若 $x\sim y$ 都跑步能获得的奖
为了方便我们从 $0$ 开始下标。
考虑倍增。设 $f(i, j)$ 表示从 $i$ 开始，移动 $2^j$ 次后，实际位置的偏移量。转移：
$$
f(i, j) = f(i,j-1)+f((i+f(i,j-1)) \bmod n, j-1)
$$
考虑 $f(i, 0)$，也就是移动 $1$ 次走的实际步数怎么求。
先令 $g(l, r)$（$0 \le l,r < n$）表示 $[l, r
首先不可能按原价买。因为 $b_i \le a_i$。
我们先默认所有物品都是按折扣价 $b_i$ 买。然后尝试用优惠券让答案变小。
不难发现给物品 $i$ 使用优惠券 $j$ 后，答案会减小 $v_j-a_i+b_i$。当然前提是 $a_i \ge w_j$。我们当然是希望让这个东西的和最大。令 $c_i=a_i-b_i$，也就是希望最大化 $v_j-c_i$ 的和。
于是我们将所有物品按
期望是假的。只需要求每种字典序下的排名和。再除以 $26!$ 即真实答案。
考虑排名的定义。在一种字典序的定义下，如果存在 $j$ 个字符串 $k$ 满足 $S_k < S_i$。那么 $i$ 的排名就是 $j+1$。
所以只需要对于每个对 $(i, k)$（$i \ne k$），计算有多少种字典序的定义满足 $S_k < S_i$。将这个值累加进 $i$ 的答案。最后输出时别忘 $+1$ 才
> 称长度为 $n$ 的正整数序列 $a$ 是合法的，当且仅当 $1 \le a_i \le k$ 且 $1 \sim k$ 在 $a$ 中都有出现。
>
> 令 $b_i = \min_{a_j \ne a_i} |j-i|$。求所有合法 $a$ 对应的 $b$ 有多少种。
>
> $n \le 2 \times 10^5$，$k \le 10$。
~~这个 $k$ 的范围很诈骗啊。~~
考
令 $[l, r]$ 中有 $a$ 个金币，$[l,r]$ 外有 $b$ 个金币。$[l, r]$ 中有 $c$ 个银币，$[l, r]$ 外有 $d$ 个银币。
不妨枚举 $[l, r]$ 中有多少银币的价值为 $1$，$[l, r]$ 外有多少银币的价值为 $1$。令为 $x, y$。那么如果 $(x, y)$ 满足以下条件，就应将 $\dbinom cx \dbinom dy$ 累加入答案
[官方题解](https://ceoi2013.hsin.hr/tasks/tasks_and_solutions.pdf)的图：
显然 $(r, c)$ 能一步到达的点在 **左上** 和 **右下** 这两块灰色区域。
两步能到达的点呢？
$ 个数中的某个。所以我们只需要快速计算这些数的价值。
不难发现这三种奖励条件都可以化归成一个或多个区间。区间型条件当然就是 $[L, R]$，相等型条件是 $[A, A]$，不等型条件是 $(-\infty, B-1]$ 和 $[B+1,\infty)$。我
结论是**每个划分的区间都单调**最优。
考虑差分。令 $b_i = a_i - a_{i-1}$。那么一个区间 $[l, r]$ 单调，等价于 $b_{l+1} \dots b_r$ 同号。此时对答案的贡献是 $\sum_{i=l+1}^r |b_i|$。
注意这里并没有把 $b_l$ 算进去。也就是说，如果一段区间 $[x,y]$ 被划分成了 $[x,m-1],[m,y]$，那么贡献是 $
~~C++ 入门之递归算法。~~
这个让一批批人上场的过程很像染色。一种颜色的刷子只能用一次。
考虑如何完成 $[l, r]$ 的合法染色。
- 如果 $a_l = a_r$。先对整个区间染色成 $a_l$。然后递归处理。令 $p_0,p_1,\dots,p_k$ 为 $[l, r]$ 内颜色 $a_l$ 的出现位置。则递归处理 $[p_0+1,p_1-1],[p_1+1,p_2-1],\d
考虑类似 LIS 的 DP。
令 $f(i)$ 表示只考虑前 $i$ 棵郁金香，且第 $i$ 棵一定选的方案数。
枚举上一个选的郁金香 $j$。
$$
\begin{matrix}
f(i) = 1+\max f(j)&(j \le i - 1 \land i \ge j + r_j + 1 \land j \le i-l_i-1)
\end{matrix}
$$
把后面那个条件化简一下得
类似题是 [CF2033G](https://www.luogu.com.cn/problem/CF2033G)。[我的题解](https://www.luogu.com.cn/article/04w4e8nz)。这两道题思想几乎完全一样。
既然 $E$ 这个点这么特殊，不妨把 $E$ 定为这棵树的根。
断掉树边 $(fa_u, u)$ 后，$x$ **不**能到达根，等价于 $x$ 在 $u
先考虑如何判断 $(x,y)$ 是否在直径为 $2r$ 的地毯的角上。
不难发现一个必要条件是 $r \mid x \land r \mid y$，即 $r \mid \gcd(x, y)$。
满足这个条件的 $(x, y)$ 在图上是这些：
然后猜出充分条件是
# 不 是 你 怎 么 又 被 骗 了
https://atcoder.jp/contests/abc380/tasks/abc380_g
唉。
> 给定 $n$ 的排列 $p$。你需要随机选择一个长度为 $k$ 的区间，并将其随机打乱。求期望逆序对。
不妨枚举打乱的区间为 $[l, l+k-1]$。此时一个逆序对 $i < j$ 会有 $6$ 种情况。
1. $l \le i < j \le l+k-1$：不难发现恰好有一半的
显然 $x_i=1$ 的加油站不可能使用。因为速度没变，而且还多浪费了 $t_i$ 的时间。
而且注意到同一种 $x$ 的加油站最多只会使用 $\log_x V$ 次。比如已经使用了 $40$ 次 $x_i=2$ 的加油站了，也就是说此时你的速度至少是 $2^{40}$。而此时距离终点最多 $10^9$，也就是不需要 $1$ 秒就能到达。但是再使用一次 $x_i=2$ 的加油站所花的时间 $t_
> 求最小的 $d$，使得可以在深度为 $d$ 的满二叉树上删除若干点后，与给定的树同构。
>
> 这里删掉点 $u$ 后，$u$ 的所有儿子都会连到 $u$ 的父亲上。
>
> $n \le 10^6$。
显然树形 DP 是必要的。$f(u)$ 表示 $u$ 子树的答案，即最小的合法满二叉树的深度。
如果 $u$ 是叶子（没有儿子）：$f(u)=1$；
如果 $u$ 只有一个儿子：$f(u
显然 DP。设 $f(i, j)$ 表示考虑前 $i$ 个数，划分成 $j$ 段的答案。
令 $s_i = (a_1+a_2+\dots + a_i) \bmod p$。转移 $f(k,j-1) + (s_i-s_k) \bmod p \to f(i, j)$。
注意到 $s_i - s_k = \begin{cases} s_i - s_k & s_i \ge s_k \\ s_i - s_
考虑最朴素的 DP。设 $f(i, j)$ 表示消除 $a_{1 \dots i},b_{1 \dots j}$ 的代价。转移显然：
$$
f(i, j) = \begin{cases}
\min(f(i-1,j),f(i,j-1))+1 &a_i = b_j \\
\min(f(i-1,j), f(i,j-1),f(i-1,j-1)) + 1 & a_i \ne b_j
\end{cases}
meet-in-the-middle。
考虑将 $n$ 个质数分成前 $\lfloor n/2\rfloor$ 个和后 $n-\lfloor n/2\rfloor$ 个。也就是说这两组的大小都 $\le 8$。分别暴力（dfs）枚举一组内的数能得到的数（即，哪些数的质因子只包括前 $\lfloor n/2\rfloor$ 个质数）。
可以发现这样得到的两个数组的大小很小。验证发现当一组是 $2
考察一个序列先手必胜的条件。
对于后手，如果有相邻的 $0,1$ 是一定要操作它们的，因为这样能减少 $0$ 的数量。
注意到序列是环形，那么存在相邻的 $0,1$ 等价于序列不全相同。显然序列全相同时胜负能定。所以后手只能操作 $0,1$ 而不是 $1,1$。
令序列中 $0,1$ 的个数分别为 $c_0,c_1$。注意到一轮操作后 $0$ 会少三个，$1$ 会少一个，也就是最多能操作 $
# 中考冲刺笔记
总计：201天
## Day 1 Mon
在学校待完了一天，体验了正常的生活。
## Day 2 Tues
心态没平衡（没能去打 Noip）回到家后学习了：电学（物理）。
## Day 3 Wed
在学校初步适应。
学习了：走进实验室（化学）。
## Day 4 Thur
硬啃下了数学当前的进度，三角函数还是不会。
学习物理：电压表。
## Day 5 Fri
回忆起来了反比
成就与快乐不可兼得。
曾经坚定的信念，明确的理想与目标，如此热爱的事物，就这么种下了怀疑的种子。
我必须要意识到 NOIP 的难度是我不可预估的，并且摒弃自己的幻想老老实实去拼暴力。
连正常的生活也无法做到吗
可笑啊
人们的性情总是调和折中的，如果你说 NOIP2025 有 4 个 DS，大家一定会来喷你；但如果你主张做大模拟,他们就来调和，愿意做 DS 了。
一滩烂泥。
OI 好
### 8.19
- Cyaneous Rain
- 写出化简形式辅助证明、理解，不能乱猜结论。
- 可以捆绑在一起处理的数据，尝试等价成同样个数的平均值数据。
- [P4229](https://www.luogu.com.cn/problem/P4229)
- 带限制的填数问题应该快速想到 dp。
- 实现技巧：只需将区间限制施加在区间最后被限制的位置上。
- [P11
说是番外实际上是第一次突破外带点前传。
（有绫有天依有言和，干脆我来混一个Moke，再找个人混龙牙，直接组一个乐队怎么样（笑
（半神突破大纲写完了，天使突破思路也有了，前面一个给定信仰的技能基础，后一个给个大范围领域增强。）
（Moke设定参照的希寇。当然本体也行。）
（删了一些大纲。你可以看到里面剧情跨度比较大的地方可能就是因为那里本来是会发生一些事情但是没了。比如水之地本来是打算写比较
~~应该没人写了笔记吧但还是放一个黑板~~:
# [U593635 交换](https://www.luogu.com.cn/problem/U593635)
~~这题太难了不会写。~~
```cpp
#include<iostream>
using namespace std;
i
### [B3617 古籍翻译](https://www.luogu.com.cn/problem/B3617)
思路：
直接把 $8$ 进制转 $10$ 进制再转成 $16$ 进制显然超出 long long，所以考虑优化。$4$ 个 $8$ 进制能拆成 $12$ 个二进制，$3$ 个 $16$ 进制也能拆成 $12$个二进制，所以把 $8$ 进制按照 $4$ 位 $4$ 位的拆开
- 后期恐龙打架。
- 还有什么八大将，离谱。
- 抽象。
当然，这都是 lxl 说的。
补一篇游记~
毫无准备，直接裸考（又不算成绩）。
我爸直接把我从地下车库送出来，结果我的同学们都在门口拍大合照。影响不大的。4考场有很多同班大佬，就我一个s*。
打完缺省源就开考了。（键盘左右括号还装反了，老师来修）。
开T1，laopiao的妈妈给laopiao开门了，加上建文件夹和打代码5min过掉，没测其它的数据。
开T2，心里一抖，以为是像2018的数论，仔细康康还好。先加个二分
~~在CSP2022初赛之前补完~~
# DAY -n
初赛。
~~由于水军太多~~随便考了一下就过了，大概70pts，分数线只有50pts左右。
# DAY -7~-2
参加集训。
感觉模拟赛打起来真的好难受啊（~~另外其他时间都在摸鱼~~
# DAY -1
本人AH，因此考场在HF。
由于疫情，赛前试机取消了（欲哭无泪
全校十几个学信竞的一起坐车去，初一初二初三的都有。
# T2
多输出了个空格。（细节句号。）
```cpp
#include<bits/stdc++.h>
using namespace std;
int a , b , c , d , e , f , x;
int main()
{
cin >> a >> b >> c >> d >> e >> f >> x;
int dism = 0 , disq = 0;
dism += x / (a+
# T2
把两个极值放在$0$和$r$上，然后进行模拟，如果两个数最后都在同一个位置，就是成功。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
int r , n;
cin >> r >> n;
int sum1 = 0;
int sum2 = r;/
那么问题来了。我坐在这里干什么呢？
把昨天T1改了，找luqyou要了一套题，然后呢？好像也没干什么了。
真可笑，总不能我跟luqyou因为题目的事扯了一天吧？
——但好像没有其他合理的解释了。
总想着现在压力这么大能不能释放一下，但你tm一天开个题面在这里死盯着看又不动脑子的，还时不时瞟两眼别人的聊天和动态，你有个78的压力啊？
现在在机房里唐得跟个奶龙一样，视奸监控随机游走还时不时退
$LifeGame$
```cpp
#include<bits/stdc++.h>
#include<windows.h>
#include<conio.h>
using namespace std;
const int dx[]={0,0,0,1,1,1,-1,-1,-1},dy[]={0,1,-1,0,1,-1,0,1,-1};
int n,m,t,a[60][110],b[60][110],
为什么最大前缀和想不到倒着做！tell me why！
如上述，对于求最大前缀和一个很好的想法是从后往前扫，维护 $s$ 表示当前 $[i,n]$ 的最大前缀和，然后 $s\gets \max(s+a_i,0)$，这样只需要维护一个变量，在 dp 时也只需要维护一个状态。
考虑回答 $[1,l]$ 的答案，相当于从 $(l,0)$ 开始走，从 $(i,j)$ 以 $p_i$ 概率走到 $(i-
外婆的信件修正问题
这是一个典型的动态规划问题，我们需要从给定的字符串中删除尽可能少的字符，使得剩余的字符能够组成一个或多个合法的单词。
方法思路
问题分析：
我们需要从字符串中删除最少的字符，使得剩余的字符可以被分割成若干个合法的单词。
每个单词必须按顺序出现在字符串中，但可以不连续。
动态规划设计：
定义状态：dp[ $i$ ] 表示处理到字符串的第 $i$ 个字符时，最少需
投票，有建议请私信 qwq。
有多个票数相等就随机选。
1. 锐评（@inscape、@\_\_lalala\_\_）
2. 爆机房照片（@Livermorium）
3. 爆照片（@YangTL）
---
# 写在前面
1. 为了大家方便更改、使用到任务计划中、魔改、保存等，准备了[\<云剪贴板版本\>](https://www.luogu.com.cn/paste/zh8hedle)。
2. 可以搬运，但需著名原作者 @[lym12](https://www.luogu.com.cn/user/782768)。
3. 本文目前为**第一版**。
4. 更新日志：
- $\textt
NOI Linux通常指的是用于NOI（全国青少年信息学奥林匹克竞赛）的特定Linux发行版，它主要用于编程竞赛和算法学习。在NOI Linux中进行文件操作，与传统Linux系统类似，但考虑到竞赛环境的限制和安全性，一些常规的文件操作可能会有所不同或受限。以下是一些基本的文件操作方法，包括如何在NOI Linux环境中进行文件管理：
## 1. 打开终端
在NOI Linux中，首先需要打开终
### LCA
##### 练习一：
给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
###### 思路：
直接用倍增法求LCA即可
##### 练习二：
给定一棵树，有 $q$ 个询问，问树上点 $a$ 到点 $b$ 的最短路径和点 $c$ 到点 $d$ 的最短路径是否会经过至少一个相同的节点
###### 思路：
先求出点 $a$ 和点 $b$、点 $c$ 和点 $d
# P13849 题解
哇！这题能写题解，赶紧交一发。（好像写的很繁琐）
## 题面简述
给你先后两张值班表，问每个人的值班时间的变动。
## 思路
发现字符串不太好处理，但我们有 `map` 啊。所以可以用 `map` 存储一个人在第一个表中的值班时间，和在第二个表的值班时间。不过有一个特别坑的点是，有可能一个人只在一张表出现，所以还要记录所有出现过的人名。接下来的事就简单了，我们按字
模拟赛的最后一题，赛时没做出来，听了讲解后会了来写个题解。
### 思路
看到 $M$ 和 $K$ 的范围，就知道不能遍历这两个。
考虑找到一个区间，使得里面所有的 `x` 都可以被变成 `o`。左边界从 $1$ 枚举到 $N$，再通过改变右边界来找到满足条件的区间。注意到肯定不能对处理后的字符串进行操作，于是不难想到将原字符串中 `x` 的数量映射到处理后的字符串，再通过本次需要改变的 `
知识点：LCA（最近公共祖先）
定义：一棵树上两点的公共祖先中，离根节点最远的那个。
求解方法：
1.朴素算法：
每次找深度较大的那个点，让它往上跳，若两点深度相同则一起向上跳，最终第一次相遇的节点就是它们的最近公共祖先。（时间复杂度为 $O(n*q)$，每次查询的复杂度为 $O(n)$）。
2.倍增法：
朴素算法的改进算法。将朴素算法中“走”的步骤转化为“跳”。
预处理出每个节点的
突然想写了。
----
### 8.31 $\tiny\textbf{写于9.13}$
住宿，于是开始收拾行李。
往年 fzyz 高一军训时间都在九月末，今年居然调到了 9 月 1 号？？？
人工降雨救一下啊。
----
### 9.01 $\tiny\textbf{写于9.13}$
宿舍环境还算不错（毕竟住过比这差的）
食堂倒是很好吃！
----
### 9.02-9.07 $\ti
## 题目大意
给定一个边长为 $N$ 的立方体，顶点坐标范围为 $[0,N]^3$。用平面 $x+y+z=K$ 将立方体切割，求包含原点 $(0,0,0)$ 的那一部分体积的 $6$ 倍。
## 解题思路
显然根据 $K$ 的不同取值范围分类讨论。
### $K \geq 3N$
平面 $x+y+z=K$ 在立方体 $[0,N]^3$ 的"上方"，整个立方体都包含在 $x+y+z \le
**~~口胡警告~~**
### T1
求个差分，那么最终的差分数列应该是在某个分界点前全是正的，之后全是负数的。考虑区间+1的含义：差分数列的某个位置+1，其后的某个位置-1。于是枚举最终的那个分界点，求它之前的差分不合法位置之和和他之后的差分不合法位置之和取个max，再全局取min就行
### T2
可以一个log，但是太懒了，写的俩log
就是在x[i]和x[i+1]之间二分分界点
# U593635 交换
$\color{#52c41a} 100pts$
### 思路
模拟
## 代码
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int a
拿到题，旁边的都说全做过，直接懵了。
---
前三题写的比较简略，因为考场都快想到正解了。
# T1
[P2679 [NOIP 2015 提高组] 子串](https://www.luogu.com.cn/problem/P2679)。
## 考场想法
```
f[i][j][k] 表示现在到了 i，已经选了 j 个子串，B 已经填到了 k
f[i][j][k] = f[i-1][j][
### 全青之前
在花园刷出黄卡和一个3rd eye（common即可）。
（玄学）在评论区发10个 `China number 1!`，会完成一个achievement然后获得1star。用1star去商店买红air。买完后去jungle找trader（找不到就换服继续找），你就获得了你的第一个红，虽然也许很菜但是是红，只要不是fries和candlestick就能用。
如果真的trad
# 落忆枫音
反正感觉没啥题做，要不要补一下 ZROI 呢？
希望一两天内改完。
## Day3 C
先随机赋权，然后：
- $k = 1$，简单的，对应着一种 hash
- $k = 2$，考虑二进制分组，一定有一位不一样。
- $k = 3$，只需要找出来一个位置即可，一定存在一个位置满足这三个数不在一个位置，注意判定即可。
std 采用了大神哈希优化。
## Day5 D
注
不错的计数题目，但是场上想出来的是斜率优化的形式，没有优化的可能了，赛后看了计数的做法茅厕顿开，写个题解记录一下。
我们考虑在抽奖机存在时间长度固定的情况下我们获取的收益是什么。首先我们获得的钱仅取决于最后一次抽奖的时间，因为每天的 $p$ 都增加 $\frac 1n$。
那么我们可以发现最优策略其实就是根据 $n,w$ 选择一些抽奖的固定时间点 $a_1,a_2,\dots,a_m$（设 $
# 2022-2023上半赛季复盘
翻车，天天翻车。
## 先来看看上半个赛季都干了啥。
九一开学先来一个月 whk，然后就去停课准备 CSP了。
然后期中化学调层调到三层了，但是没看懂怎么做到的，我学化学的总时长大概不到年级那帮人的三分之一，而且我也估了一下分数，和化三平均分差一车。
然后有三科全卡线及格了。
然后 CSP 就崩掉了。前段打的十分开心啊，T1T2虽然先被恶心了一下但是
# 分数
**估分：**
T1:100
T2:30
T3:0
T4:0
**实际：**
T1:90
T2:30
T3:0
T4:0
**原因：**
T1:由于$n\le10^6$，而我没有任何输入优化，导致最后2个点TLE。
T2:无。
T3:无。
T4:无。
# $miller$版题解
## T1:zero
[原题](https://www
这大概是这段时间最后一次上洛谷了叭
从2017年自招完的暑假到现在，两年半叭
梦一样地就过去了
还记得初学语言语法时的轻松，那时候教室还是满的，大家都怀着OI梦
学完循环，就有很多人听不懂了，教室里人开始减少
二期开课了，讲算法，我开始迷糊
现在校内的最强者、当时还没有在一起的前男友，也是在那时候和我们一起上课的
现在想想，好像已经不记得学递归、搜索、贪心之类的时候的绝望了
毕竟后
## P2689 东南西北
1. **时间复杂度**：
$ O(T) $
2. **错误原因**：
开了x1和y1的全局变量导致报错
2. **正确思路**：
看看每次按照输入的方位移动是否会接近目标位置
3. **正确代码**：
```cpp
#include <bits/stdc++.h>
using namespace std;
int ax1, ay1,
又是一个晚自习
我初赛过了，yeah
这几天我开始每天跑机房了，内心很慌
我们班算是我校学习氛围最好的了，安静下来最早，自习违纪最少
所有人都在努力学习，所有人压力都很大
总觉得自己不学的时候别人都在学，都在赶超自己
毕竟能学的人太多了
我也不例外
所以我很慌，我怕信竞到最后没有成果，文化课还会落下
哪怕只是一段时间的一些自习
所以我一回教室就开始低头学习
可总觉得会落下很多
## Part 0 总结
预期：
$\textrm{50pts + 30pts + 100pts + 16pts = 196pts}$
实际：
$\textrm{0pts + 45pts + 100pts + 0pts = 145pts}$
打的一坨，不想评价。
队内 $\textrm{rk~8/20}$。
## Part 1 考场
- `0min` 开考了，可我由于起晚了还在
又是一节咕掉的体育课
进了机房就发现上面的字全没了，我懵懵？
今天是挺惨的一天，惨到出门才发现没带手机
最近又发生了好多事呢
分手两个月整了，我似乎已经走出来了
但每次碰到他还是忍不住一阵尴尬
隔壁班和隔壁的隔壁班也有一对分手了，女方提的，月考的时候男方整个人都崩了
怎么说，这对的性格，女方像我前男友，男方像我
唯一相同的大概就是女生提的分手吧
好在分手风波并没有影响我的学习，月
最近发生的事还是挺多的叭
2019.8.25，当我作为一个真正的高三学生踏入高三楼时，我就明白是时候拼了
NOIP没有了，改成了csp，但很明显换汤不换药
2019.8.12，开学前不久，我和我家傻子分手了，至今难以忘怀，难以接受这个现实
一年半多了，说散就散了啊
期初全市统考了，语文爆炸，总分爆炸，大概是学了半个暑假信竞的后果
（语文全班倒一物理全班第一我能说啥）
不得不说，这些事
### 偏序问题
所谓偏序问题，就是给定一些元素，每个元素有一些初始值：$a_1 , a_2 , \cdots , a_n$，有时还会多加上几维，也就是还有 $b_1 , b_2 , \cdots , b_n$。
偏序问题，就是给定一些条件，比如规定必须 $a_i \le a_j , b_i \le b_j$，然后让我们求最长的子序列（或给定一些权值，求最大的子序列权值和，本质都是一样的）。
注:代码内的所有图片地址为我自己电脑上的地址，素材均为手绘，若有需要加我微信拿
```cpp
#include<stdio.h>
#include<easyx.h>
#include<conio.h>
int pan[3][3];
void end(int jx, int jy) {//一局终了，显示胜者
if (pan[jx][jy] == 1) {
settextcolor(0xff0
唔本来想开学就写这篇文章的，结果我这个拖延症患者愣是拖到月考都过去一个周了x
又是一年开学季
转眼间我已经当高二学姐当了半年了
转眼间高三就还有两个月就要走了
转眼间我们就要搬进那栋与世隔绝的高三楼了
转眼间我和我家傻子已经一年多了
不得不感叹时间真的过得太快了，快到还没来得及把握就悄悄溜走了
开学后第一次踏进机房，迎接我们的是厚厚的灰尘和为了过年擦得干干净净的白板
上面那些陈年字
我这个人不是很会写文章，可另外两个(@[ZZK423](https://www.luogu.com.cn/user/836262) @[037hao](https://www.luogu.com.cn/user/837932))已经不想在高考前与OI有瓜葛了，所以我就写了。
12剩4，甚至有一个遗憾的提前离场，我们看着身边的队友一个个的退出，还是挺无奈的，他们绝大部分都没有撑到初赛来临，甚至有些
众所周知，$1\neq2$。
~~这不废话吗?~~
为了证明1=2，我们还需要知道一个东西：
### 1÷0
没错，就是这个。
肯定很多人认为这个算是是没有意义的，但是，它可以证明这个看似无理的东西！
我先给大家讲个故事：
>一个人有1个苹果，分给0个人，每个人能分到多少个苹果？
从这里不难看出，1÷0没有意义。
但是，请看证明：
我们因为不知道1÷0究竟等于多少，不妨将结果设为a
本人第一次写题解
废话少说上~~S山~~代码
```cpp
//我爱s山代码
#include <iostream> //我是注释我爱写注释我是注释我爱写注释我是注释我爱写注释我是注释我爱写注释我是注释我爱写注释我是注释我爱写注释我是注释我爱写注释我是注释我爱写注释我是注释我爱写注释我是注释我爱写注释我是注释我爱写注释我是注释我爱写注释我是注释我爱写注释我是注释我爱写注释我是注释我爱写注释我是注释
T1：【模板】树的中心
$50pts$：直接暴力，枚举根跑$dfs$，时间复杂度$o(n^2)$。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,maxx=0,dep[1000001];
struct node{
int v,w;
};
vector<node>g[1000001
# 强连通问题
1. 有向图的强连通：有向图的两个点 $x,y$ 彼此能够到达，称 $x$ 和 $y$ 强连通。
2. 强联通分量 $\text{(Strongly Connected Components,SCC)}$：表示有向图的一个极大子图 $G$，满足 $G$ 的任意两点都是强连通的。
+ 特殊情况：
* 单点算 $1$ 个 $\text{SCC}$；
* 有向图最少有 $1$
燕子去了，有再来的时候；杨柳枯了，有再青的时候；桃花谢了，有再开的时候。但是，聪明的，你告诉我，我们的AC为什么一去不复返呢？是有人偷了他们吧——那必定是OJ了！是他们自己逃走了吧：现在又到了哪里呢？
我不知道他们给了我们多少AC，但我的AC率确乎是渐渐下降了。在默默里算着，寥寥无几的AC已经从我手中溜去，像针尖上一滴水滴在大海里，我的AC滴在题目的流里，没有声音，也没有影子。我不禁头涔涔而
#### **一个重要点**
设$k$为直线的斜率。
则斜率优化中的成为“决策点”（即被选做用来转移的点）的点，一定满足如下条件：
- 假设这个点为$P_0(x_i,y_i)$，设凸壳上前一个点为$P_1(x_{i-1},y_{i-1})$，后一个点为$P_2(x_{i+1},y_{i+1})$，则：
$$
k_{P_0P_1}\le k \le k_{P_1P_2}
$$
**证明：*
基本格式：
```cpp
#include <...> // 不用 <bits/stdc++.h>
...
#include <...>
#include "..." // 我 需 要 吗
...
#include "..."
using namespace std;
const int MAX + 大写字母 = 题目中的数据范围 + 常数;
struct ... {
...
} ...;
c
这里是mcqueen，一名JS退役OIer。
与很多OIer不同，我的退役没有轰轰烈烈，也没有黯然失色。
我只是再一次拿到了1=，按计划继续回到文化课。
看着身边的队友，觉得自己仍是个幸运的人。
这个博客之后会记录我文化课的一些东西，或者我的一些随笔。
或许大学参加 ACM 的时候这个博客会变得像一个OIer的博客，但是最近可能不会了
或许寒假会写一个回忆录吧、
G 题竟然是个板子，还挺简单的。
现在的加入的数关系到上一个的答案，所以这题不能离线了。
注意到如果值域在 $10^5$ 以内我们可以用线段树直接解决了。
但现在的值域在 $10^9$ 里，那么用一个动态开点线段树就好了！
最多加入 $3\times 10^5$ 个数，$\log V$ 最大是 $30$，其中 $V$ 代表值域，那开 $9\times 10^6$ 的数组就行了。
别忘记开
周五晚上上数学课，数学老师讲完一个题后讲了一个故事：有一个青铜段位的最帅王子去打一个黄金段位的王子，肯定失败了，所以你们现在做题做不出来很正常，但是一天这个王子为了救一个美铝打败了黄金段位的王子，所以你们也要尽量去思考。
这时坐在前排的一个 beautiful girl 问：那我们这有美铝吗？
数学老师：你不就是吗？
beautiful girl ：那帅哥呢？
数学老师斜了一下眼，看到了坐
计算机科学请移步：[Link](https://www.luogu.com.cn/blog/317198/pu-ji-zu-chu-sai-tong-guo-zhi-na)
这篇博文与计算机科学除知识点外的不同点：
- 博主更强了
- 废话更少了
- 考点更精了
在您阅读这篇文章之前，请您将计算机科学部分指南通读（不背也没有太大关系，据博主观察这种题虽然考的概率极高但是 $60\%$ 均是常
预计 100 + 100 + 100 + 100 = 400，实际 100 + 100 + 100 + 100 = 400
比赛复盘：
四道题看了一眼都会，然后分别写完了，由于第一题需要高精度，怕错拍了一个小时，见没拍出来就不管了。第三题需要 __int128，因为编译器太低级不能用，所以先用 long long 调试过的样例提交时再换成的 __int128
做的好的地方：AK 了
做的不
# **P1019 [NOIP 2000 提高组] 单词接龙 题解**
## **解题思路：**
主要是运用**搜索**的算法。
先在**主函数**枚举以 $char$ 字母开头的单词，然后再递归枚举之后可以继续**合法**拼接的单词，如果没有了，就回溯。
### **是否合法的判断方式：**
1、不能完全包含，如：at 和 atide 间不能相连。
2、末尾需要有**部分包含**。
#
# 零，前言
其实有很多教你如何配置vscode的博客，洛谷日报里面也有。但是我都认为这些文章要么太繁琐，要么就是指示不全，我3次对照文章都没有配置起 ~~我曾三度遭到背叛~~ ，所以写作此文，专门帮学OI的小伙伴们简单、高效地配置vscode
# 一，为什么是vscode
>Visual Studio Code（简称“VS Code”）是Microsoft在2015年4月30日
叠甲：本文纯属虚构，作者和 npy 很幸福。
你离开成都那天，全城大雨瓢泼。
你说高铁延误了，如果我赶到成都东站，或许能再见你一面。
水已经有半个车轮那么高，滴滴出行的排队时间一再延长，我咬紧牙，挽起裤腿就往地铁站跑。
出现在你眼前时我好不狼狈，水顺着头发丝往下滴。我往前走了一步，想问你能不能抱抱我，你却皱眉，厌恶地摇摇头。
我把手中攥紧的花递给你，你却没有接。原来花瓣早就被暴雨淋得不剩
既然题目把哪些点在凸包上面都告诉你了，就不需要写个凸包上去了。
首先将 $x$ 坐标最小的点拎出来，从这个点开始逆时针考虑凸包上面每个条线段都是“左拐”，所以逆时针方向上的点与最小点连线的斜率是单调不降的。
直接将斜率拎出来排序，从小到大输出就可以了。$x$ 坐标为 $\displaystyle\min_{i=1}^{n} x_i$ 的按照 $y$ 坐标从大到小单独排序。
```cpp
#i
# 省流
求割点
1. 不用维护栈，**也就没有 vis 判据**，需要维护根和 $ch$
2. 内部求割点
3. 求割点的判据是**low[v]>dfn[x]**
4. 对于非根节点，只需要一个儿子满足判据
5. 特判根节点，需要至少两个儿子满足判据
求点双
1. 访问过的点塞栈里，但是用来记录 vdcc 的，没有**vis 判据**。
2. 内部求 vdcc
3. 不需要维护根和 ch
首先了解基础：https://www.luogu.com.cn/article/38ao5b2f
我们发现，因为一个人的力量总和不变，把每个人对其追求者的力连成一张有向图，这张图的边是有较大力量的，所以根据 XZ 定理（也叫 XZ 分压定理），一个人如果突然放弃或开始追求某人，那么对其他人的力有可能突然增大或缩小很多，这个时候会引起力的短暂不平衡，引发一条链的振动，简称链振，链振一般以两种形式结
## 壹.$\texttt{ST}$表是啥
$\texttt{ST}$表是一种数据结构，基于倍增思想，可以高效解决$\texttt{RMQ(range maximum/minimum query)}$问题（区间最值），在经过$O(nlog_2n)$的预处理后，可以实现在线$O(1)$查询区间$[l,r]$的 $\texttt{maximum/minimum}$。
## 贰.$\texttt{ST
这篇文章将以通俗易懂的方式教会你快速幂的原理！！！
那么，话不多说，$\texttt{let's go}!$
---
## 一.普通幂运算的弊端
我们之前的幂运算，都是循环累乘的，对于$n^k$的计算，时间复杂度为$O(k)$，当$k>1e8$时，就十分危险了，容易$\texttt{\blue{TLE}}$
## 二.快速幂的原理
举个栗子，现在我们要计算$n$的$6$次幂，那么我
> **最短路**，未免对我这个蒟蒻来说太难了
这篇文章就梳理一下最短路径算法，**let's go**
## Part1：总体梳理
**chart**
| | 时间复杂度 | 适用情况 |
|:-:|:-:|:-:|
| **dijkstra** | $O((n+m)logn)$ | $无负权边$ |
| **Floyd** | $O(n^3)$ | $无负环（总权
# 简介
这里是 Thrift's 猫武士报，Thrift 会不定期更新一些猫武士短文和一些有趣的发现哟！每一期的内容都是原创，敬请期待喵！
每一份报纸分为三版：**最新发现**、**自编小说**和**武士谜题**，每一版均有文章或谜题喵，货真价实。
最后希望你给我一个小小的关注谢谢喵。
[留言区](https://note.ms/thrift)
# 第一期
**Date**：$2025/0
前几天 jijidawang 在赛时写的科技，oiwiki 上都没有，赶紧学习了一下。
已知 $A_n=\sum_{i=1}^kF_iA_{n-i}$，求 $A_n$。
显然该式子可以用矩阵乘法优化，但是线性递推用矩阵乘法还是太慢了，居然有高达 $O(k^3\log n)$ 的复杂度，并且就算用对于 OI 几乎为负优化的一些理论更快的矩阵乘法，也还是更慢了一些。
那这时候有人就要问了：主播主
P9141 解题报告
```cpp
#include <bits/stdc++.h>
#define i64 long long
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define fdn(i,r,l) for(int i=(r);i>=(l);i--)
#define pii pair<int,int>
using na
NOIP2018结束了，分数也出完了，一切都已尘埃落定。拿了一等觉得自己没有实力冲省队的nyd和hjy退役了，高三学长wyl打完最后一次比赛也走了，机房里熟悉的身影突然都消失了。
不习惯，真的不习惯。
机房突然像是空了。
机房的白板上我们赛前写的东西还留着，却多了几行字。
“Creed吊打集训队”“Creed进队”“Creed省队预定”……一看就是hjy写的，可Creed已经走了。
那行
看到第一眼：限制这么强？好神秘啊。
第二眼：$N \le 15$。哦唐诗吧。
$N$ 这么小直接暴力就行了，$2^n$ 枚举出当前选中的点集，对于没有选中的点集跑凸包模板。做完了。
时间复杂度 $O(n(\log n+2^n))$。
评紫的原因难道是代码一坨吗？输出格式贼恶心。
```cpp
#include<bits/stdc++.h>
#define int long long
#d
优美，太优美。
注意到逆序对和 $\text{LIS}$ 都是只用关注相对大小的，所以设计状态的时候大抵是要跟相对大小的排名有关的。
$\text{LIS}$ 并不好放入状态，考虑将其设为 $\text{dp}$ 数组的答案。
那么考虑将成本为 $0$ 的时候最大得分是多少（转换一下把个数大于等于 $a_i$ 看成有贡献的）。
设 $f_{i,j}$ 表示考虑了前 $i$ 个位置，$\te
### 参考博客：
[https://www.cnblogs.com/acha/p/6735037.html](https://www.cnblogs.com/acha/p/6735037.html)
### 分析
  普通的费用流每次都要做一遍spfa，最坏是$O(n*m)$,而zkw只需要$O(n+m)$即可完成一次标号，并且可以加上当前弧、多路增广、时间戳优化。
## 目录
## 1.差分约束系统的定义
## 2.松弛操作
## 3.三角形不等式
## 4.差分约束的原理
## 5.关于无解
## 6.例题1
## 7.例题2
## 8.例题3
## 9.总结
### by szlhc
## 1.差分约束系统的定义
差分约束系统就是形如 $x_i$ - $x_j$ ≤ y 或 $x_i$ - $x_j$ ≥ y 的方程组。
$$ \begi
> You can view the [English version](https://www.luogu.com/article/oth85fqt/) of this solution.
> 图片托管于 Github，若加载失败请使用加速器。
考虑画出三个点的哈夫曼距离。
。
> The images are hosted on Github, use an accelerator if it fails to load.
Consider drawing the Huffman distance of three points.
注：带 * 代表不会的，带 / 对了一半，^ 表示代码挂了。
## 7.27
### CF1696E Placing Jinas *
::::info[题解]
把每一列直接平推肯定是最优的。
对于第 $x$ 行第 $y$ 列的格子要操作的次数 $f_{x,y}=f_{x-1,y}+f_{x,y-1}$，初始化 $f_{0,0}=0$。
然后发现 $f$ 实际上是一个杨辉三角，有 $f_{
好像是我初二的时候提出的一个问题，当时 u 群有人说存在 $O(n^23^{n/3})$ 做法，昨天晚上突然会做了！
考虑从前往后 DP，暴力是记录 $S$ 表示目前选择的数的集合，这样状态数仍然是 $O(2^n)$ 级别。
但我们注意到，设 $i$ 后面的数分别为 $x_1,x_2,\cdots,x_k$，我们只关心 $[1,x_1),(x_1,x_2),\cdots,(x_k,n]$ 这些
开个坑。
### 二项式系数与帕斯卡三角
**二项式系数：**符号$\dbinom{n}{k}$叫做二项式系数，可以表示从$n$个元素的集合中选$k$个元素作为自己的方案数，相当于组合数。
**帕斯卡三角：**即杨辉三角，帕斯卡三角形的第$n$行第$k$列表示$\dbinom{n}{k}$
如图：许多将使用到帕斯卡三角作为辅助
众所周知，洛谷是一个非常好的一个Coding网站，在这里，我们可以学习算法，练题，还可以和好朋友讨论and组队，我们知道，洛谷的主页有签到，我们可以用运气抽到各种标签（如大凶，中评，大吉，甚至吉你太美），那么我们如果抽到了凶怎么办？我有一计！修改底层逻辑。（但是一刷新就会恢复），有人就会说:"怎么修改呢？\0_0/",很简单我来教你，可以先看看我的实例:[成功实例](https://cdn.luo
2023年10月10日
16班zjy晚自习没穿校服出去上厕所，被18班班主任叫回去接着上晚自习，然后开始哭泣地奔跑（而且声音特别大），没错，从B区跑到A区厕所然后再跑回B区厕所（这路程总共将近200米），没错这一路上是哭着跑完的，然后18班班任慌了，给团委打电话，然后团委给16班班任打电话，16班班任穿着睡衣从家里开车到学校找（听说还是深V（bushi）（男班主任）），最后在厕所里找到的，那个厕
**题目大意**：
有 n 个人坐在一张圆桌旁，每个人的距离相等。每个人对应都有一个状态，不是 1 就是 0，请问能否连接若干个 1 ，将它们分别对应的点连在一起，使得所连成的图形是正多边形？
**样例分析1：**
3
1 1 1
可以将三个点全部连接为正三角形。
**样例分析2：**
6
1 0 1 1 1 0
可以将第一个点、第三个点、第五个点连接起来，这些点的间隔相同，可
在本次的HL CSP-S中，我们在390份文件中找到了783个 ``freopen``，当然包括被注释掉的7个 ``freopen``。
这次比赛中我们找到了32个CCF。
而我们只找到了三个***\*，HL素质有待降低（
**【游记前置曲】**
Alpenglow（映峰之霞） —— Elliot Hsu
### Day -3
提前开坑，祝 rp++。
### Day -2
你谷月赛 Div.2 AK 勒。涨了 $6$ 粉。
你说的对，但是怎么我写了 0.5h 的 A 是红题啊？写了 4k+2h 的 D 是蓝题啊？
喜报：A 升黄了。C 和 D 都升紫了。符合预期。C 和 D 应该是下位紫。
锐评：A
裸DP。感觉楼下的好复杂，我来补充一个易懂的题解。
f[i][0]表示走完第i行且停在第i行的左端点最少用的步数
f[i][1]同理，停在右端点的最少步数。
那么转移就很简单了，走完当前行且停到左端点，那么一定是从右端点过来的，那么从上一行左端点转移的话就是
f[i][0]=abs(上一行左端点的坐标-本行右端点的坐标+本行线段长度)
从上一行右端点转移同理。
不需要什么判断。边界f[1
若寻找全部的日记，请到[此处](https://www.luogu.com.cn/article/yh1f5ulg)（“日记”一栏）。
### Chapter 161 8.23（鲜花）
上篇日记足足咕了半个多月。
~~懒得写直说。~~
近距离观赏 cch 在这一天都怎么度过的。
早上 8 点。被老妈叫起。发现妹妹在咬我手。不管。还想睡。继续睡觉。
早上 9 点。吃早饭。真的非常早的早饭
# 题面翻译：
#### 问题陈述
有一个网格，网格中有 $H$ 行和 $W$ 列。让 $(i,j)$ 表示从上往下第 $i$ 行，从左往上第 $j$ 列的单元格。每个单元格的状态用字符 $A_{i,j}$ 表示，其含义如下：
- `.` ：空单元格。
- `#` : 障碍单元格。
- `S` ：起始单元格。
- `G` : 目标单元格。
- `o` : 打开的单元格。
- `x` : 关闭
现在已经有了三种似乎可行的做法
1. 通过调顺序，使得每个将要合并的树挨着，这样子就可以不合并反而使用树套树来进行查询，这样子就可以快乐的使用区间修改单个树而不用单点修改，从而打破 $h_2 - h_1 \le 10$ 的限制，听起来非常正确，复杂度大概是标准的 $O(\log ^2n)$。
1. 将合并操作看做连边直接大力 LCT 套线段树，时间复杂度是 $O(\log ^2n)$。
2. 发明
圆形是“你”，空心正方形是墙，实心正方形是雾，星星是终点，上下左右移动“你”。更新内容：
1. 基本不闪屏了（还有一点闪屏）
2. 有金币了，金币有音效，但还是没有怪物
3. 优化了体验
4. 本代码开源，但开源必须在博客下方留言，并标明原博客。
```cpp
#include <bits/stdc++.h>
#include <windows.h>
#include <queue>
#def
duel 时通过本题。
不难发现只需要快速处理出每个点的经过次数就与权值无关了，可以 $O(1)$ 完成单点修改。
考虑对每个点统计贡献，若一条路径经过了该点，则该点会把路径分为前后两部分。
令当前点为 $i$，起点为 $s$，终点为 $e$。根据路径的可逆性，容易转化为起点为 $s$，终点为 $i$ 的方案数乘上起点为 $e$，终点为 $i$ 的方案数。
现在问题转化为已知终点
[https://www.bilibili.com/video/BV1tA411P7Uv/](https://www.bilibili.com/video/BV1tA411P7Uv/)
# 这个视频有点水，下面补充一下
[这个是m3u8解析工具](https://blog.luckly-mjw.cn/tool-show/m3u8-downloader/index.html)
[小黄鸟抓包工具
## 问题简述
给定一个数列，多次查询求区间第 $k$ 小数。（可加单点修改）
数据范围：$1\leq n,q\leq 10^5,|a_i|\leq 10^9$。
## 静态问题的解决
### 算法 1：莫队+平衡树
将询问离线后使用莫队算法，并使用平衡树维护当前区间内的数。该做法的时间复杂度是 $O(n\sqrt{q}\log n)$，可能需要精妙的卡常技巧才能通过。
### 算法 2：
## B3687 [语言月赛202212] 数字口袋
### 题目大意
小 $A$ 有一个口袋，里面可以装整数。他从 $1$ 开始，按从小到大的顺序，依次将每个整数装入口袋。
但是口袋是有限的，大小为 $n$，这就是说，口袋里所有的数字的和不能够超过 $n$。
------------
### 解法
从 $1$ 开始枚举每个数字 $i$ ，如果可以装入口袋，则输出这个数字，然后将口
来点不用容斥的不一样的做法。
考虑 $a_i$ 值较小的那些对其他位置的影响是简单的，必定会减少恰好 $1$ 种可能情况。
所以我们考虑先确定 $a$ 值较小的位置，这启发我们用笛卡尔树。
我们建立小根笛卡尔树。
考虑对于笛卡尔树的一个子树，设其代表的区间为 $[l,r]$，分割点为 $p$。（这里我们只讨论 $1<l\le r<n,l<p<r$ 的情况，其他情况是简单的）
发现这个区间
**树形dp板子题**
## 分析
考虑每个节点：如果不是叶子节点，要么往左边走，要么往右边走，所以这个节点的答案就是他的两个子节点的答案之和。如果是叶子节点，那么他就只能到他自己，所以答案为1。
综上所述，我们对于每个非叶子节点，可以递归求出他的两个子节点的答案（这里`dp[i]`表示编号为 $i$ 的节点的答案），并将其累加得到这个节点的答案；对于叶子节点，直接返回1即可。
考虑到还有转
## 0b0000：前言
~~欸话说这是哪个唐诗**欧拉**筛取的这个标题？~~
本人将按难度升序排序，依次讲述有关欧拉的各类算法，希望大家能喜欢。（手动狗头）
## 0b0001：欧拉筛
### 介绍
欧拉筛是一种高效的素数筛法，能在 $\Theta(n)$ 的时间复杂度内筛出小于等于 $n$ 的素数，相比于大家比较常用的埃氏筛（时间复杂度 $\Theta(n \log n)$），欧拉
u295620，这是fzm对你的考验，加油少年。
做有机的小女孩
实验室里冷极了，没有窗户，不知道是白天还是黑夜。这是一周的最后一天——周 末。
在这又冷又黑的晚上，一个蓬头散发的小女孩在试验台前坐着。她从家里出来的时候 还穿着一件外套，但是有什么用呢？那是一件很大的外套──那么大，不知是哪一年买 的。她工作的时候的，就穿上白大褂了，实验室的师弟嘲笑说，何必穿实验服呢，你的破大衣都可以当抹布了。
小女孩只好一个人做实验，一双小手被溶剂弄得白
躲在草丛里的星星
张宸
杭州市创意城小学
（3年级/2班）
在这个世界上，星星们每天晚上都要出来值班，照亮夜空。
一天晚上，一颗星星不耐烦了。它想:我为什么每天晚上都要值班呢？还不如去睡个懒觉。于是，它偷偷地来到了大地上，躲在了一处草丛里。它想: 这下，我的伙伴们找不到我了，我可以安心的睡觉了。
这时，它的同伴们发现它不见了，于是正着急地找它呢。可是它们左找右找都没有找到，只好放弃。
化学方程式不会打……只能用文字描述了。
# 钠
钠的物理性质：银白色，有金属光泽，硬度比较小，密度比水小，比煤油大。
用石蜡和煤油保存：防止钠和外界空气反应。
钠的化学性质：
- 常温下和氧气反应，生成氧化钠。
- 加热或点燃时和氧气反应，生成过氧化钠。
- 钠可以和氯气等非金属单质直接化合。（非重点）
- 常温下和水反应，生成氢氧化钠和氢气。本质上是和水中游离的氢离子反应。
现
时间截止：寒假结束前。
### whk：
- 初中数理化学完，可以的话把高中数学的必修一学完。
- 英语：~~背完托福词汇~~。
### OI:
- 绿题100道，蓝题30道。
- 独立做出第一道蓝题。($\rm done.$)
- 算法：线段树、图论、动态规划。
### 其他：
坚持惩罚性锻炼，OI中每挂1分罚跑10m，满1000m结算。
|题目名|挂分情况|原因|惩罚|累计
## 大事记
### 名字颜色：
~~2023某月某日 蓝名祭~~
~~没有绿名 直接蓝升橙~~
2024.8.5 橙名祭
2024.8.19 红名祭
### 钩子：
2024.8.4 绿钩
2024.11.16 5级勾
### 杂项：
2024.8.19 百橙祭
2024.8.19 50黄祭
2024.10.24 80黄祭
2024.11.26 150橙，100黄祭
一个 dp。
首先我们将整条路径分别看作「有效路径」和「无效路径」。容易知道：
- 有效路径是不会被撤回的，且长度为 $n+m-1$。
- 无效路径都会被撤回。假设你位于点 $(i,j)$，那么你在这个点出发任意地走无效路径，最终都会回到点 $(i,j)$。
我们设 $F(i,j,k)$ 表示从点 $(i,j)$ 出发，走到终点 $(n,m)$，且使用 $k$ 次撤回的方案数。
容易得出转
#### 前排提醒
这位作者写总结时习惯形式化题意，个别形式化过长，读者可以选择跳过。
### T1 子串
从$A$中取$k$个子串，使其按序拼接起来与$B$相同。
这题很显然是DP，那么就开始考虑如何转移。
我试着定义过很多次$dp_{i,j,k}$代表什么，但是”大脑“转不过来，想不出转移方程（其中多半都是能写转移方程的，确实是我的问题）。然后一个小时就过去了。
发现浪费了太多时间，我就
教练让我们给新初一的同学讲课，然后我就抽到了折半搜索和【数据删除】。
然后就有了这篇博客。
## 折半搜索
折半搜索（双向搜索），又称 meet in the middle。
**这种搜索就是从初态和终态出发各搜索一半状态，产生两颗深度减半的搜索树，在中间交会、组合成最终的答案。**
面对一些使用dfs或bfs难以解决的题，我们可以使用折半搜索。
在一些时间复杂度为 $O(2^n)$ 的
## 模拟赛
### 赛时
看到 $\text{T3}$ 是概率 $\text{dp}$ 就先做了 $\text{T3}$. 写了 $\text{30min}$，弄了个 $n \times n \times 2n\ (n = 200)$ 的三维 $\text{dp}$ 数组，甚至觉得没啥问题，随便拍了拍把精度问题解决后就去看 $\text{T1}$ 了.
$\text{T1}$ 还挺好写
对于$ \frac{\sum a_i\times c_i}{\sum b_i\times c_i} $ ，$ c_i\in {0,1} $ ,通过对 $ c_i $ 的合理取值使结果最大化，这类问题被称为分数规划问题。
分数规划问题通常使用二分解决。
考虑二分到一个 $ mid $ 值，问题转化为判断 $ \frac{\sum a_i\times c_i}{\sum b_i\times c_i
### 分数规划与二分法
首先，什么是分数规划呢？
一般来说，分数规划会给你一串 $a_i$ 和 $b_i$，要求你给出一串最佳的 $w_i \in \{0,1\} $，使得 $ \large\frac{\sum\limits_{i=1}^{n} a_i \times w_i}{\sum\limits_{i=1}^{n} b_i \times w_i}$ 最大或最小。
当然，除了这些，题目一
# 自介
### 12年射手坐标重庆ISFJ
### 我是纯萌新，刚学OI
稀饭的游戏：光遇
我不喜欢那个学人精派对
[小恐龙](https://dinoswords.gg/)
# 属性图
一夫一妻：申厦蓝（甜唯）沈载伦（一体机）脑袋
前妻是Minnie过激梦，爱情向，不拒同担拒同梦
我还喜欢那个糊团H1key老三赵辉玹
内娱like张颜齐高瀚宇范世錡张艺凡
综艺
一觉醒来周围人智力翻 $10^{10^{100}}$ 倍而我不变？？？
待写。
## 简化题意：
给定一个初始为零的序列$a_i$，有$Q$次操作，第$i$次操作给定$x_i$和$k_i$，选定$a$的前缀$a_1 \sim a_{x_i}$，并重复以下操作$k_i$次：
选择区间内最小数并加一，若有多个值相同的数，则选择位置靠前的
## 解题思路
不难发现，由于每次操作均选择的是一个前缀，且优先选值小的增加1，因此整个序列应该是单调不增的
因此，每次操作等价于选择
今日，我在奶猫群接到消息称，有人未经允许使用了我的头像。
根据[此说明](https://www.luogu.com.cn/article/weu6cco2)中所提到的，使用奶猫的图片需要画师发放。
奶猫形象的最早来源是我在 Waifu labs 上定制的头像，由 \_Lamiris\_ 使用 AI 修改成奶猫，奶猫的表情包以及我现在使用的头像，由我使用豆包进行重制。
重点说明我现在的头像。
# [Replace](https://www.luogu.com.cn/problem/CF1707E)
[更好的阅读体验](https://www.cnblogs.com/wingheart/p/18470792)
## 题意
给你一个长度为 $n$ 的序列 $A$，有 $q$ 次询问，每次询问对于一个区间 $[l,r]$ 需要操作多少次才能变成区间 $[1,n]$，无解输出 $-1$。
现在我们已经把边连完了，并且是合法的。现在我们要求出一组具体的方案。
我们的规则是，对于一组对立的变量，我们要选拓扑序靠后的（即Tarjan更靠近叶子的）。
## 1. 反证法的假设
+ 对变量 $x_i$，存在 $(i,p)$，和 $(i,p\oplus1)$，其中 $f(i,p)<f(i,p\oplus1)$，按照规则我们应该选 $(i,p\oplus1)$。
+ 对变量 $x_j$，
### 本蒟蒻（小升初）第一次写题解，如有问题请见谅。
[题目传送门](https://www.luogu.com.cn/problem/P1096)
本题解介绍一种新的做法（使用递归，直接在字符串上操作）
### 题目大意
此题是小奥的改编题。
在小奥中，我们学过，如果将题中的 $2n$ 个圆盘改为 $n$ 个的话，最小的移动次数为 $2^n-1$。
在这题中，因为每个尺寸都有两个相
## 最小生成树
kruscarl 算法：先按照权值排序，能连就连。使用并查集维护。
prim 算法：维护一个点集，每次从中向外扩展最小的一条边。
### 例题1 棋盘的守卫者
>一个城市的道路成了像棋盘那样的网状，东西向的路有 N 条，并从北向南从 1 标记到 N，南北向的路有 M 条，并由西向东从 1 标记到 M，每一个交叉点代表一个路口。
>
>为了维护城市治安，需要在一些路口设置岗哨
# Limit 的线段树题单 总结
## 题目
P6186：求序列 $k$ 次冒泡排序后的逆序对数量，复杂度 $O(q\log n)$。
P6492：一个仅含``L``与``R``的字符串，字符单点修改，查询最长的``LR``交替的字串，复杂度 $O(q\log n)$。
CF620E：一棵树，$60$ 种颜色，初始每个节点有颜色，修改子树颜色，查询子树颜色种数，复杂度 $O(q\log
数据水炸的一道题
以至于我拿一个卡时的暴力过掉了还拿了rk1???
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int s[200000],a[200000],ans=1e9+7,kkk=0,n,k,p;
int getin()
{
int x=0;char ch=getc
观前提示：本文只是一个笔者能够自己做出来本题的思考，如果想学习严谨证明请观看其他题解。
感觉是很精妙的问题。
考虑这样一种构造。
$$1\to 2,2\to3 \dotsb n\to 1$$
上面是双向边的构造。
考虑其他边是怎样连的，一种很直接的想法就是 $\forall i,j,i<j$ 那么就有一条 $(i,j)$ 的边。但是这实际上是错的。那我们怎么办呢？
今日总结（8/26）
# T2
题目:
在一段序列中选最多的数
组成一个所有数互为倍数的集合
考虑倍数关系，如果一个数字 c 能被 b 整除， b 能被 a 整除，那么 c 一定可以被 a 整除。
那就可以考虑重复的情况
因为里面有很多数是原有的数里的倍数故可以考虑为唯一分解定理比如 6 答案的来源实际上是 2 和 3 ， 那么我们在处理后面 6 答案的时候可以只用 2 和 3 。
名字是我乱取的。[来源](https://www.luogu.com.cn/discuss/989432)。
[ABC219D](https://www.luogu.com.cn/problem/AT_abc219_d)
有 $n$ 个物品，每个物品能获得 $a_i$ 个 A，$b_i$ 个 B，给定 $x,y$，问最少物品数使得 $\sum a \ge x$ 且 $\sum b \ge y$
大家好，这是我的第一篇洛谷博客，即紧张又兴奋，我们今天就来说说简单的入门的c++语句吧！
# 本篇声明
1、该文章的全部内容由作者原创；
2、在本篇博客中，示例代码均要写如下基本框架：
```cpp
#include<bits/stdc++.h> //万能头文件
using namespace std; //使用标准命名空间
int main(){
/
# Solution
性质：如果最终 $u$ 是 $v$ 的父亲，那么 $h_u \le h_v$。
证明：
若 $c_u \ge c_v$，考虑进行下图变换，肯定不劣。
（点权相应修改）
若 $c_u < c_v$，考虑进行下图变换，肯定不劣。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1300005, INF = 1e18;
int n, tot = 0, root = 0, m, last = 0, ans_xor = 0;
struct tree {
int ch[2], a, fa;
## 前言
今天是 tht 的生日，据说膜拜他可以 AK IOI。我试了，虽然没有 AK IOI，并且 tht 的生日也不在今天，但我 AC 了 kkkw 比赛的 T1-T3。所以大家快来膜拜 tht。
## T1 最小中位数
[AT_abc203_d](https://atcoder.jp/contests/abc203/tasks/abc203_d)
手玩几组样例容易发现，一个 $k \t
### 1.21 Day 1
今天是 DAY 1。还没有碰到太过于难受的事。
前几天已经快崩溃了。希望可以趁状态好的时候多做点有意义的事。
寒假计划已经安排好了，今天行动起来。
现在是下午。数学走进重高并没有按照预想的进度推进。如果想要完成计划，就要努力一点。当然，完成不了也是没关系的。
还想做好多事情。
今天大概可以平和地结束吧。
昨天在火车上偷偷哭了很久。
临睡前稍微有点小 e