NOI2025 结束了，谨以此篇告别我的 OI 生涯
小学的时候就对编程挺向往的，当时听说要学编程(Scratch)，当时兴高采烈地去微机室，然后被马蜂制裁了(哦不)，它当时停我耳朵上，我以为是只苍蝇就挥手赶了一下，然后就寄了。
虽然第一节课没能上成，但是我并没有丧失对编程的热情，我找到了一个 Scratch 社区 [慧编程](https://mblock.makeblock.com/)，我在
最近更新
# 某帅气的哥群周刊第五刊
**[第一期 Link](https://www.luogu.com.cn/article/e7l583bi)**
**[第二期 Link](https://www.luogu.com.cn/article/jyivt87v)**
**
**置顶公告：**
- Sleeping Cup #5 已经开赛，欢迎参加！
- 网址：http://8.136.99.126/
---
欢迎来到 Sleeping Cup！
这是一个以 Hydro 做框架搭建的网站，但又又不只是一个以 Hydro 做框架搭建的网站。在这里，我们将打破你对 OI 的传统认知：
- 与众不同的体验，从 [试机题目](http://8.136.99.126/
Dev C++ 功能不够？
vscode 不会配置还臃肿？
试试 [OICPP](https://oicpp.mywwzh.top)！
## 功能概览
OICPP 定位为专供 OI 使用，~~杂交了 Dev C++ 和 vscode 的部分设计~~。
截至目前，OICPP 最新版本为 1.0.0-alpha4，功能有：
- [x] 代码编辑与运行
- [x] 多标签页支持
- [x]
不知道为什么要做 NOIP2024
VPVPVPVP
+ 12：00 开题！
+ 12：10：啥呀，T1，没看懂，跳了
+ 12：20：T2 这不推狮子就行了嘛？遂开始推。。。
+ 12：40 狮子退完了，开写
+ 13：00？过了小样例，大样例死活过不去。
+ 13：20 绷，过了大样例，我好T呀！！开T1
+ 13：50 呀，贪心好像过了？玄学？？
+ 14：20 通过了 T1 所有的大样例
### 7.12 $\texttt{day} \text{ -1}$
抵达北京。
下雨面积尺子失败，然后到学校面到了 muxi @无钩七不改名。
然后被王津叫去组 D/E 班模拟赛。
---
### 7.13 $\texttt{day} \text{ 0}$
中午面到了 lk @MeowScore。
原本想在北航吃，但那个餐厅被包场了喵喵。
出来吃 lk 请吃烧烤，爽吃。
然后到
# $abc 276 G \space \space Count \space Sequences$
## 前言
比赛的时候想了个阴间的容斥，调了 $1h$ 。
## 题意
计算满足以下条件的序列 $a$ 的数量：
1. 长度为 $n$ 。
2. $0\leq a_1 \leq a_2 \leq \dots \leq a_n \leq m$
3. $a_i\neq a_{i+1}(mod\
## **前言**
$at$终于上黄啦！
希望下周不要掉回来。
## **C**
先对坐标排序，再检查有没有同一行内先出现R再出现L。
## **D**
刚开始看到题时，我想：“欸？这题不直接模拟就好了嘛！”
然后，
### **WA**!
我一看,这题目只保证答案在 $long$ $long$ 范围内，没保证过程中不溢出。又发现，$U$和$L,R$是可以抵消的，这样就不会溢出了。
##
感谢审核大大在百忙之中审核本文，辛苦了！qwq
# 少年陈哲之勇闯洛谷神魔试炼场
最后更新于：2024/3/8 12:00
# 点赞收藏加关注，更新来看不迷路！
### 点赞是免费的，但是可以让作者开心半天，让作者更新的动力更足。
### 收藏也是免费的，但是这也是对作者的肯定，可以让作者作品质量稳步提高。
### 关注同样是免费的，但是关注作者可以收到作者更新时发的犇犇，最先追更作者小
洛谷P3413 SAC#1-萌数 题解
前言
本题并不难，同为数位DP板子题，可细节较多，需耐心分析，所以子标题也会分得较细（有些与上题重复，将不再赘述）
题目分析
我们首先看一眼数据范围，就会发现r最大能取到$n^{1000}$，这显然是暴力无法承受的，这是我们又发现这题是按位分析的，所以考虑数位```DP```（跟上题差不多）
输入
我们注意到这题的```r```的范围，显然即使是
真服了入门赛测试点全是UKE
## 题意
有一个珠子序列，你可以在任意位置插入任意颜色的珠子。每当连续 $\ge 3$ 个相同颜色的珠子相邻时，它们会消失，并可能引发连锁反应。求至少需要插入几个珠子使所有珠子都被消除。
## 思路
很显然，这是一道区间 DP 题，我们设 `f[l][r]` 表示消除 `[l,r]` 里的珠子需要的最少发射次数。唯一一个难点就是会发生连锁反应。
## 代码
```cpp
#includ
# T1 T640726 落落的去的围栏
二分题哇
**思路：**
涂色 : 从 $1$ 到 $k$ 涂成一种颜色，从 $k+1$ 到 $n$ 涂成另一种颜色。
可以枚举 $k$ 。
- 左边颜色必须满足 $>=k$ 的条件才可以，二分出有多少 $>=k$ 的颜色 $x$ 。
- 右边颜色必须满足 $>=n-k$ 才可以，二分出有多少 $>=n-k$ 的颜色 $y$ 。
即 $ans
[cnblogs地址](https://www.cnblogs.com/ynycoding/p/16972411.html)
### Day0:
试机最后一题元旦激光炮没调出来就润回去了。
### Day1:
开场先看T1，感觉可能需要析合树，被演了1h。结果仔细思考后发现只需要线段树维护单调栈，于是花了1h写+调。
接下来看T2，发现很奇怪，于是看T3。T3想了大概1h，中途有几个假做法，最
从今天开始记录写题时犯的低级错误。
- 7-31
- [ ] [P1541 [NOIP 2010 提高组] 乌龟棋](https://www.luogu.com.cn/problem/P1541)
错误代码：
```cpp
for(int i = 1 ; i <= m ; i ++) {
for(int a = 0 ; a <= t[1] ; a ++) {
for(int
:::success[测试]{open}
```cpp lines=1-1,3-3
测试
测试
测试
```
:::
https://www.luogu.com.cn/paste/zuy6eopx
https://www.luogu.com.cn/paste/1rj3m6z7
***神话**一则*
在 A 星球上有一个名为 B 的谷，在谷的底部生活着无数青蛙：
每月在谷中只能看见月亮掠过谷几个小时，却很难以看到太阳。
谷很深很深，青蛙们世世代代尝试爬到谷外。
谷内的燃料能量非常大，以至于科学家们研发的
https://www.luogu.com.cn/paste/uwvn0ue7，
::::info
符合要求3天内未回关私
```cpp
#include <iostream>
using namespace std;
int a[10005];
int main(){
int n = 100;
for(int i=1;i<=n;i++){
a[i] = 1;
}
for(int j=2;j<=n;j++){
for(int i=1;i<=n;i++){
if(i % j == 0 && a[i]
## 时间线
- 13\:38 开题！看 T1，脑残以为只要对左端点做最长上升子段，成功浪费 10min。
- T1 秒题失败使我心态下降，先看了一遍题，wc 怎么 T2 在第一次考试神秘换题的过程中出现过？？？T3 看起来很乱搞，T4 神秘期望 dp 决定直接弃了。
- 回来看 T1，想到了一个超级做法：维护一个线段树表示当前所有温度能达到的最长维持长度，每次做**区间加 $1$、区间求 $\
T638414 营养达标
错误代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[105],x[105][105];
int main(){
cin >> n >> m;
for(int i = 1;i <= m;i++){
cin >> a[i];
}
for(int i = 1;i <
巅峰见证虚假的拥护，黄昏见证真正的信徒
（不知道有什么意义，但就是要说一下）
T643658 落落的去的数学题1
额，脚滑的老师居然挖坑给我跳，那我算了半天算什么啊（恼）
数学特性分析：
当a>b>c时，2^a + 2^b - 2^c = 2^c(2^{a-c} + 2^{b-c} - 1)
二进制中1的个数取决于高位1的分布情况
关键发现：
结果中1的个数等于(b-c+1)
题目说 $0\le A_i,B_i <M$，有两种情况。
1. $A_i+B_i <M$，对答案贡献为 $A_i+B_i$。
2. $A_i+B_i\ge M$，即 $M\le A_i+B_i<2M$，对答案贡献为 $A_i+B_i-M$。
所以对答案的贡献不是 $A_i+B_i$ 就是 $A_i+B_i-M$。
答案的柿子就变成了这样：
$$(\sum_{i=1}^N(A_i+B_i))
# 思路
这是一道简单的 dp。
- 需要定义动态规划的数组 $dp1$ 和 $dp2$，$dp1$ 表示当前状态，$dp2$ 表示下一个状态。
- 对每个 $a_i$ 作取模处理，防止这个 $a_i$ 大于 $m$。
- 计算答案。
- 每次循环，把 $dp2$ 里的元素初始化为 $0$，这很重要！
- 如果当前余数 $j$ 的概率为 $0$，跳过这次循环。
- 选择当前题目
已知 $H,O$ 分别是 $\triangle ABC$ 的垂心和外心，$E$ 为弧 $BC$ 的中点，$OD//AE$ 交 $BC$ 于 $D$，$EH$ 交圆 $O$ 于 $F \neq E$
证明：$F,O,D,E$ 共圆
[我是答案](https://www
## 四边形不等式
### 1.四边形不等式
对于 $a\le b\le c\le d$ 和定义域为整数域的二元函数 $w$，若有
$$w(a,d)+w(b,c)\ge w(a,c)+w(b,d)$$
则称 $w$ 满足四边形不等式
### 2.拓展形式
对于 $a\le b$ 和定义域为整数域的二元函数 $w$，若有
$$w(a,b+1)+w(a+1,b)\ge w(a,b)+w(a+1,b
T1
# 思路
$n$ 个字符串，求两两最长公共前缀的长度。
很简单可以想到，直接暴力肯定不行，所以想到用字典树来优化，将每个字符串插入字典树，求答案即可。
# 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
const int N = 3e5 +
从本节开始，我们将进入数学的海洋（~~希望不会溺水~~），那就从质数开始我们的数学知识之旅吧！
# 1、定义
> 若一个**正整数无法被除了$1$和它自身以外的任何自然数整除**，则称该数为质数（或素数），否则称该数为合数。
> --《算法竞赛进阶指南》
在整个自然数集合中，质数的分布比较稀松，大约**每$lnN$个数中有一个质数**，即对于正整数$N$，不超过其的质数大约有$\frac{
# 字符串算法
### 1.[Hash](https://www.luogu.com.cn/blog/wjx307816794/xue-xi-bi-ji-hash)
### 2.[manacher算法](https://www.luogu.com.cn/blog/wjx307816794/xue-xi-bi-ji-manacher-suan-fa)
### 3.[KMP算法](https:/
## 温馨提醒：未满114514岁的人禁止观看本文章
说好再也不写的，但今天我又想写了。
# 进制：
### x 进制转 10 进制：
```cpp
int f(int x,string s){
int t = 1;
int sum = 0;
for (int i = s.size()-1;i >= 0;i--){
if (s[i] >= '0' && s[i] <= '9'){
## Day 1 - 07/18/25
这次联考准备每天都记录一下情况。同步转发与 QQ 空间和洛谷专栏。
今天是第一场模拟赛。
#### T1 - 橙
注意到 $n$ 最大为 2e5，遂考虑枚举其中一个数，统计和他配对的数的个数即可。复杂度 $O(n \lg n)$ ，100pts。
#### T2 - 蓝
对我来说还是太困难。虽然被某些大佬秒了。
先拼一个 $O(k^2nm)$
## 声明
本文非严谨的算法理论研究，仅仅是个人对解题经验的归纳和实验性的系统总结，不保证理论上的完备性与纯粹性。仅对解题实践提供一个较为自洽的解释，作为参考。
本文所有题都不会提供题意和完整包含细节的题解，也就是说您需要先做一遍或看其他题解，因为没有做题经验就无法感受解题思想。您也可以把本文理解成一个归类好的题单。
如果一题包含多项技巧则会放在多处，但如果包含多项思想则只会在一处解说。如果
决定先在typora上写，回头传上来。
# Day1 DP优化和状态定义。
## 知识点：
四边形，斜率，wqs，二分栈/队列，状态定义（判定合法转状态，状态压缩），数据结构。
### 四边形/斜率/wqs
详情请见我的课件，可能重构。
### 二分栈/队列：
常用于 1D DP，转移形如 $f_i=\min f_j+w_{i,j}$ 的形式。
当相对靠后的决策点一定会被前面的决策
**前言**
写这篇题解是为了纪念我做这个黄题时的【数据删除】，我真【数据删除】的【数据删除】。我试图用简单贪心无果，最终恼羞成怒用了我们珂爱的 dp。
**正文**
首先我们显然可以令 $x \leq y$，我们的目的是令 $x$ 等于 $y$，令 $x$ 为 $y-x$。我们把 $x$ 用二进制的形式表达出来，会是一个类似 0100110 形式，我们发现，其实我们只可能使用三种操作：
-
注：这个方法是[犇犇犇犇](https://www.luogu.com.cn/user/35998)大佬教我的，后期又自己摸索了一下，在此感谢。
众所周知，P站被墙了，那么问题来了：
# 它是彻彻底底的被墙了吗？
答案简单粗暴：
# NO!!!
好了，聪明好问的各位就要问了：
# WHY？？？
因为GFW封锁的只是SNI，而使电脑的hosts和DNS集体死光光，但实际上IP本身并没有
本文章同步更新在 [cnblogs](https://www.cnblogs.com/twilight-star/articles/17957377)。
### Update on 2025.5.28
因为这篇文章是初二写的，~~当时心智不熟~~，所以写了很多废话，把一些考前训练的情况写了下来，显得有些偏题。为了不那么啰嗦，我把这一部分放在了最后。
# 正文
这是本蒟蒻第二次参加CSP比赛，
二合一傻逼题。没看到边权一定为正数，以为有 0 边搞 max 部分搞了半天...
事实上 min 部分感觉就是[这题](https://www.luogu.com.cn/problem/P1875)改一改，是一个 dij 基础题。
具体说就是我们设 $f(i)$ 是一只怪物 $i$ 能得到的最少钻石数量，然后转移就是枚举它的拆分方式，设得到怪物集合 $S$ 和 $n$ 颗钻石，那么取 $n+\
点分治之前就学过，最近机房有人让我帮调，曹神又给了道好题，自己又学了点分树，因此简单记录一下。
点分治即每次找到树的重心，并以其为中心分治，处理跨过中心的所有路径，再递归下去处理不经过中心的子树内路径。处理方式为枚举其子树，先处理该子树与之前子树之间的路径，再将该子树内的点记录下来以便之后查询。由于以重心为根时，其子树大小不超过 $\frac{siz}2$，因此每个节点只会被处理 $O(\log
### 原文
```plain
用户在犇犇或公开讨论区中有如下违反 洛谷讨论区规范，扰乱社区讨论秩序的行为，视情节严重性，可处以警告或禁言的处罚：
在公开讨论区中发表较多无意义内容；
在公开讨论区中使用夺人眼球、哗众取宠、或不知所谓的标题；
短时间内发表大量帖子，或在帖子、回复、或犇犇中刷屏；
发表对其他用户的辱骂、歧视、人身攻击等不友善内容；
发表泄露其他用户个人隐私的内容；
在公开讨论区中发表
final standings:4 517,Cu。
感谢二号队员的发力和三号队员的义务劳力（？），以及志愿者的义务劳力。
Day -1
热身赛，赛前没配置监考环境，然后发现准备是六点半开始，于是急急去舍友宿舍偷了个摄像头回来。
然后就是录制，因为不检查作弊所以相当顺利，我唐了两次，一次是电脑摄像头不知道怎么开，一次是没给管理员权限。
于是坐牢等热身赛，期间紧急把志愿者叫过来了。然后热身赛
个人感觉这题更像一个构造题。听说这个构造很典？反正我赛时没想出来。
我们大家肯定都做过一道题叫做[序列合并](https://www.luogu.com.cn/problem/P1631)。这道题就是把那题拓展到数列个数很大的加强版。
如果没做的话，建议做了这题之后再来写这题。如果做了，建议回去看一下那题的做法，因为我是直接基于那题解法继续写的。
首先不难想到一个暴力思路是，直接把原来削弱版
（本篇题解使用C++）
# P1001 A + B Problem
## 题目大意
输入两个整数 $a,b$，输出它们的和（ $|a|, |b|≤ 10^9$ ）
## 题目分析
这个题目要求我们通过输入两个数字 $a, b$ 来求他们的和。那么我们就要首先输入两个数字，这时我们可以使用 ```cin```来输入，它的使用方式如下：
```cpp
cin >> 变量1 >> 变量2
# 思路
首先，对于增速的 $a_i \ge 0$ 先扔在一边。对于 $a_i < 0$ 先求出他最后是在哪一个检测器被检测为超速的，检测器的位置记为 $p_i$。 对于一队二元组 $i,j$，如果 $p_i < p_j$，只要车 $j$ 的起始位置 $d_j \le p_i$，就也会被检测。贪心一下，对于 $p$ 按从小到大的顺序排一个序，考虑完在排序下的 $p_1$ 到 $p_{i -1}$
# 安装 Smart - Luogu:
- 打开你的浏览器扩展管理页面。对于 Edge 或 **Chrome**，你可以通过地址栏输入 [edge://extensions/](edge://extensions/) 或 [chrome://extensions](chrome://extensions)/ 来访问。
- 打开开发者模式。在扩展管理页面的右上角，你会看到一个 **“开发者模式
[题面](https://www.lydsy.com/JudgeOnline/problem.php?id=5312)
线段树，势能分析法。
然而我不会势能分析。所以只能口胡一个啦。我们找规律会发现，基本上，区间$and$和区间$or$多了，到了后面这两种操作基本上对答案的影响是差不多的。所以，当区间影响是一样的时候，这两种操作就等价于区间加和区间减，这样就可以做了。然后好像这个复杂度可以通过
## 刘谦 2024 春晚魔术原理证明
### 魔术内容
### 程序证明
根据魔术内容可以写出以下 $\textit{C++}$ 程序，运行程序，如果按照正确格式输入且电脑运行处于正常状态，那么输出的最后一行一定是 `魔术成功！`。
```cpp
#inclu
**~~cz大大不要打我~~**
原文：
```
用户可能有以下违规行为
I类违反（轻微规则违反）：
犇犇或讨论发送无意义内容
用私信骚扰辱骂他人而被举报，或私信骚扰管理员
提交不符合要求的题解或题目，或者剽窃他人成果而不注明出处
提交无意义评测代码或在评测时抄袭他人代码
恶意进行评分
在洛谷站内发送未经许可的洛谷站外广告
在洛谷站内宣传不符合规定的比赛、团队
其他的轻度不合理行为（包括但不限于发
很有意思的计数题！观察！注意！启示！
观察给出的四个字符串，注意到这四个串的 B 都在结尾，C 都在开头，这启示我们把 C 当成左括号，B当成右括号进行括号匹配，因为给出的字符串是 CCB，所以 B 要当成两个右括号。
接下来观察 A，注意到 A 出现在 CA、AB 中，这启示我们把 A 当成一个可以成为单右括号或双左括号的通配符。代入发现这同样能凑出 AAA。
继续观察，注意如果你将前面的
C++ 是许多信息学竞赛选手最熟悉的编程语言。日常训练中，我们可能只用到循环、数组这些基础功能，但这位朝夕相处的"老朋友"，其实藏着更多值得探索的奥秘。
也许你曾见过题解中神奇的语法"黑科技"，也许你被未定义行为导致的"玄学问题"困扰过，也许你面对突如其来的编译错误百思不得其解...
掌握这些知识，不会让你在赛场多拿几分，但能让你更加了解这个朝夕相处的代码伙伴。它们或许能帮你理解那些精妙的语言
$$\color{darkblue}\colorbox{CAEBFB}{\large\boxed{\texttt{洛谷经典名言}}}$$
$$
\def{\c}{\color{000000}}
\def{\l}{\Large\c\text{\raisebox{3pt}『\kern{12pt}}}
\def{\r}{\Large\c\text{\kern{12pt}\raisebox{-3pt}』
# 卡常小技巧
- i++ --> ++i
- a=b --> a(b)
- 读入输出优化:
```cpp
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
```
- 能不用变量就不用，转而用常量。
- 在类型前加register,在函数前加inline。
- 尽量用位运算,相反数:`~n+1`:
a%2 --> a&1
a*2 --> a<<
**题目大意**：
给定 $n$ 个人各自的 $m$ 种特征，问第 $i$ 个人至少要询问多少个特征才能知道这个人。
**题目思路**：
蒟蒻一开始看到这道题感觉要崩了，感觉是一道 DP。
可当我看到这个我就开心了：$1\le n,m\le 20$。
数据竟然这么水！
那我们便可以使用深搜来解决。
在深搜中我用了一个动态数组来储存需要询问哪些特征（下文所说的遍历的特征均是这个动态数组
# B4206[常州市赛2021]数字翻转题解
这是本蒟蒻第一篇题解，求管理员通过；
~~我是看这题可以写题解才来做的~~
原本我只是想用暴力~~水~~一下，没想到
我立刻觉得这是一个好~~骗~~的方向，便去修改我的代码；
根据题目所说的，$0$，$2$，
### 前言
先讲讲我自己是谁吧，虽然我并不喜欢下定义，但是我希望大家对我也能有初步的了解。
我是一名OI老龄选手，即将高二，坐标SD，~~学了两年半~~但是CSP2024 只拿到了 6 级钩，NOIP2024 寄。当时感觉自己的 OI 前途已经一片黑暗了，但在家人老师朋友们的帮助下精神状态一直没出什么问题，可能只是学习成绩上出了点波动~~但你一个竞赛生管学习成绩干什么~~。
另外强调非常重要
2024年11月4日，离CCF出分还有最后的20min。
---
那个蒟蒻却丝毫不知道他的命运。
---
还有15min。
---
再见了，蒟蒻想。凭自己的实力，一定是0+0+0+0。
---
还有10min。
---
蒟蒻愤怒地想，为什么会有万恶的CSP？
---
还有8min。
---
蒟蒻说，他命不久矣。再见了，同学们，虽然你们都是唐诗。
---
还有6mi
##
**Update：优化了 std，将运行时间控制在 $1$ 秒以内。**
# Part 0
由 $h_i=i \times s_i$，可以发现 $W=h_1\times h_2\times \ldots\times h_n=1 \times s_1 \times 2 \times s_2 \times \ldots \times n \times s_n=(1 \times 2 \times
哈哈
## MCKC Round 1 赛后总结
### 只是效仿公开赛答疑帖
- 比赛结束前和结束后，可以在评论中适当灌水
- 禁止在评论中讨论题目，若发现，取消奖品资格并踢出共和国。
- 欢迎举报作弊者。
作弊者名单：
```
无
```
### 正经的
比赛还没开始我总结个什么啊
**说句闲话：**
- 出题人这题做了半年。
- 当 $m \le 500$ 时，贪心上界是 $13853793$（$n=13853793=57 \times 493^2$，$m=494$）。
# Part 0
显然，无解是不可能的，因为 $n$ 个 $1^2$ 的和就是 $n$，而 $m \ge 1$，因此这一定是合法的方案。
# Part 1
> 设答案为 $k$，求证：$p \le
**42粉**提前发出来了
50呢是个整十数，而我的第一个粉福也在此发布。
你可以询问我的身高、体重、年龄和坐标，我会一一私信回复(**私**)
（其他的就等**100粉粉福**再发吧（提示：有真实姓名与更精细1级的坐标等））
因为最近灰名都私信加我，~~我好像没有一点的橙名的样子~~
正题
##### 条件
### 必要(全要满足)
##### 1.比赛等级分>0~~至少也要>=0吧~~;
##### 2.粉丝>0
##### 3.不是灰，棕，封
##### 4.做对至少一道黄题，十道橙题
### 选要(满足两项即可)
##### 1.加了[csm团](https://www.luogu.com.cn/tea
# 桶の桶解法
我们考虑特殊性质 A。
开两个桶 $row, col$，其中 $row_i$ 表示第 $i$ 行被涂色了多少次，$col_i$ 表示第 $i$ 列被涂色了多少次。
这样，由于只涂行，只需判断每个 $row_i$ 是否满足 $row_i \bmod k$ 不为 $0$ 即可。如果满足条件，则将结果加上 $m$。
如下所示：
```cpp
int main() {
read
# 0.前言
这个方法是数学老师讲的。笔者所写是为了解释这个方法的本质。
~~马上要月考了，写文章 rp++~~
# 1. 推导
## 1.1 引入
在**初二数学**中，有时会用到直角三角形中锐角与三边比的关系。但是三角函数还没有引入，于是我们需要找到替代方法。
下面将直角三角形中较小的锐角，记作 $\angle A$；将直角三角形中较大的锐角，记作 $\angle B$。直角记作
# 前言
上次月考写了两篇博客，rp += inf 拿到年级 rk1。周二期末考，写一篇，加 rp。
# 问题
如图，在平面直角坐标系内，$A(4,0), B(0,3), C(4,3)$，将 $\triangle CAO$ 沿 $CO$ 翻折到 $\triangle CA'O$。求点 $A'$ 的坐标。
, B(x_2,y_2)$，则 $AB$ 长为
$$
\sqrt{(x_1-x_2)^2+(y_1-y^2)^2}
$$
# 点到直线距离公式
$(x,y)$ 到 $y=kx+b$ 的距离为
$$
\dfrac{|kx+b-y|}{\sqrt{k
# 前言
昨天写了一篇博客加 rp，今天 Thupc2024 烧鸡了，明天月考，再写一篇，rp++。
# 引入
这是一道折叠的模板题。
如图所示，$AC=3, BC=4, \angle CAB=90\degree$。点 $D$ 是线段 $AC$ 上的一个动点，将 $\triangle ADB$ 沿 $AD$ 折叠到 $\triangle A'DB$，使 $A'$ 落在 $BC$ 边上。求 $
应同学要求，写篇总结。
# 题目
如图，将 $\triangle ABC$ 绕点 $A$ 逆时针旋转 $\alpha$ 度到 $\triangle AB'C'$，延长 $C'B'$ 和 $CB$ 交于点 $D$，连接 $AD$。若 $\angle ABC > 90 \degree$，求 $\angle C'DA$。
这不一眼树直径模版吗？？
三个点，连接两条边权为 $a$ 和 $b$ 的边，跑一下就好了。
是不是很简单？
小学奥数题。
考点：
- 行程问题的灵活运用。
- 整体思想。
- 高精度加法，乘法，除法。
解析：
易见 $T_{zhangxun6315}=T_{chenjunyv1123}$。
相遇时间 $T=\frac{n}{v_1+v_2}$
因此，$S_{chenjunyv1123}=Tv_3$。
高精度即可。
问：$n$ 很大，$v_1,v_2$ 也很大，高精度除以高精度不会怎么办？
## Day 1
参加入营测试，搞了154分，rk1，虽然一题没做对。
T1 我写了暴力24tps。正解其实就是预处理质数，然后枚举每个质因数的个数，顺便处理答案。值得注意的是：要想数尽量小且因数多，质因数的指数一定是降序的。小技巧：注意两数相乘大于另一个数的判断中可能会出现爆long long的情况，所以尽量换成除法。
T2 模拟而已，虽然正解是并查集，我少考虑了一种组合方式，所以90p
刷 [NFLSOJ](http://www.nfls.com.cn:20035/) 上的比赛，打算每次刷完写个总结
（话说 nfls 都有总结功能了，这个是不是没用了）
1. [20220808练习赛-普及](https://www.luogu.com.cn/paste/yjbfxzhl)
2. [20220808练习赛-提高](https://konyakest.blog.luogu.or
（前言：今天怎么又5道题啊！！！）
# 错题一
# 分析题目
题目要求计算 \( 2^a + 2^b - 2^c \) 的二进制表示中1的个数。直接计算这个表达式对于大的a、b、c（比如1e9）是不现实的，因为这会得到一个极其巨大的数。因此，我们需要找到一个数学规律或模式，避免直接计算这个巨大的数。
## 关键观察
1. 当a、b、c都是不同的数时（题目保证c < b < a），我们可以考虑
## 骗分
- 那么，骗分是什么呢？骗分就是用简单的程序（比标准算法简单很多，保证蒟蒻能轻松搞定的程序），尽可能多得骗取分数。
- 让我们走进这本《骗分导论》，来学习骗分的技巧，来挑战神牛吧！
### 第1章 绪论
- 在Oier中，有一句话广为流传：
任何蒟蒻必须经过大量的刷题练习才能成为大牛乃至于神牛。
- 这就是著名的lzn定理。然而，我们这些蒟蒻们，没有经过那么多历练，却要
# 线段树
## 线段树简述
> ### 线段树是数据结构中的常用算法，常用于解决序列修改与查询问题
> by OI wiki
>
> > 线段树的思路在于，将数组 $a[]$ 分为一个树\
> > 这个树就是线段树\
> > 本质是将数组中 $[1, N]$ 分为 $\displaystyle {[1, \frac{N}{2}] }$ 和
$\displaystyle {[\frac
你们说。能力范围内的尽量
```cpp
#include<bits/stdc++.h>
using namespace std;
#define _ ;
#define __ ,
#define ___ int
#define ____ main
#define _____ {
#define ______ }
#define _______ +
#define ________ (
#define _________ )
练不死，就往死里练。
[图论 Atcoder](https://www.luogu.com.cn/problem/list?type=AT&tag=6,68,79,155,158,159,160,166,172,173,174,175,176,177,179,180,181,182,185,186,187,189,197,198,204,350,364,450,476&orderBy=diffi
# 这个人很懒，什么也没写......
###### （纯属搞笑无实际意义）
不得不说，这题太水了。
直接上代码：
```cpp
#include<bits/stdc++.h>//万能头
using namespace std;
struct poin{
float d,p;
}sz[100005];
float dd,c,lc,p,sum,zdlc,oil;
int n;
int main(){
cin>>dd>>c>>lc>>p>>n;
for
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=205;
int p[N];
long long dp[N][N];
int f[N],mn[N];
int MOD=1e9+7;
int oo=1e9;
long long C[N][N];
int main(){
freopen("c.in","r",stdin);
~~一道二分水题。~~
## 思路
容易发现，答案具有单调性。
我们假设答案为 $x$。
那么，$x - 1$ 肯定不能到达 $L$ 的位置，但 $x + 1$ 肯定能到达 $L$ 的位置。
**所以，我们考虑二分。**
我们确定好二分的边界：$l = 1,r = 2 \times 10 ^ 9$。
然后，我们如何判断答案合不合法？
显然，我们充 $x$ 的电，最多能到达 $\lf
哇啊哦，原来是神秘诈骗题。
我们考虑当前经过一系列异或操作之后的序列的形式 $a_1\oplus k,a_2\oplus k\cdots a_n\oplus k$，此时如果我们再异或上某一个位置的数，也就是 $a_i\oplus k$，可以得到 $a_1\oplus a_i,a_2\oplus a_i\cdots 0\cdots a_n\oplus a_i$，也就是说，无论操作多少次，达到的效果
# 数学杂项
$1:{\Large a+a+a+a+...+a=a \times b}$ ( $b$ 为 $a$ 的个数）
$2:{\Large a \times a \times a \times a \times ... \times a=a^b}$ ( $b$ 为 $a$ 的个数）
## 快速幂！
${\Large Fristway} $
## 二分治
${\Large a^
### 闲话
终于能稳切 $D$ 题了！发个题解纪念纪念。
## 题意
题目意思简单来讲就是有两个序列，其中第一个序列可以任意排序，第二个序列不能动，然后，我们将第一个数组排好序后，然后两个数组相同的位置的数相加取模题目的模数，要使得结果最小。
## 思路
首先，我们发现，其实我们可以任意移动第二个数组，为什么呢？
因为呀，第一个数组可以移到任意一个位置，所以，我们移动第二个数组其实等
0[^1]
[^1]: 迷你世界
:::info
1
:::
:::warning
2
:::
:::error
3
:::
:::info[感觉不如迷你世界]
4
:::
:::align{center}
5
:::
源码
```
0[^1]
[^1]: 迷你世界
:::info
1
:::
:::warning
2
:::
:::error
3
:::
:::info[感觉
热学学不会了，我要来这里背公式了嘻嘻。
1. *热力学第零定律:温度的相等是一种等价关系.
2. *玻尔兹曼常数$k=\frac{R}{N_A}=R\frac{m_0}{M}$,其中$m_0$是单个分子的质量,$M$是分子的摩尔质量.
3. *理想气体标准方程:$pV=\frac{m}{M}TR$.
4. *理想气体标准方程的变式:$p=nkT$,这里的$n$指的是单位体积内的分子数,也即$n=
此题考察的是动态规划（DP）问题。这种问题通常分为三步：状态定义，数组初始化以及状态转移。
### 状态定义
令 $dp_{i,j}$ 表示覆盖 Hankook 前 $i$ 天和 Jeong-ul 前 $j$ 天观光的最小费用。
### 数组初始化
如果 Jeong-ul 没有参观，即 $dp_{i,0}$，则此时其值应该为买一日票，三日票，五日票的最小值，不需要考虑组合票。
同理可以得到
# 请加入[这个团](https://www.luogu.com.cn/team/74972)
## 引子
“别！“在这宽阔的平原上，突然想起了孤零零的一声呐喊……
“为什么？在这里的生活还有什么意思？朋友的背叛，那帮理应断子绝孙的小人的离间计看来是奏效了……“另一个声音也同样孤零零的回响着。
“可是……“还是最开始的声音
“可是什么可是？吾意已决，不必多言！别了，我的朋友！“接着，本在
# 斜率优化
## 简单介绍
斜率优化是一种优化dp的方法，形如单调队列，但针对的方程不同。
单调队列优化形如$f[i]=max(f[j]+a[i])$的方程，而斜率优化可以将形如$f[i]=max(f[j]*a[i]+b[i])$的方程从$O(n^2)$优化到$O(n)$
## 做法
### step1：列出暴力dp的状态转移方程
### step2：将方程转移为$j$比$k$更优时$\frac
## Day 0
从合肥坐火车到芜湖。
试机是 NOIWC2025。
## Day 1
>我常常追忆过去。
>
>生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。
>
>云朵之间亦有分别：积云厚重，而卷云飘渺。生命里震撼的场景掠过我的思绪便一生无法忘怀，而更为普通平常的记忆在时间的冲刷下只留下些许残骸。追忆宛如入梦，太过清楚则无法愉悦自己的幻想，过分模糊却又坠入虚无
来记些完成的任务计划中的一些题。
### 20250716
P6775 [NOI2020] 制作菜品：Zzzcr 给的题，$m=n-1$ 是好做的，直接贪心即可，必然有解，$m=n-2$ 就直接通过背包划分成两个 $m=n-1$ 的情况即可，用 bitset 优化。
### 20250718
P11364 [NOIP2024] 树上查询：区间 lca 深度为相邻 lca 深度之区间 min，二分
`static const unsigned int wS=1<<24` 处调成最大输出文件大小
```cpp
#include<bits/stdc++.h>
using namespace std;
/*
chenbs
mmap 究极读写，快到起飞
*/
#ifdef __linux__
#include<sys/mman.h>
#include<sys/stat.h>
#endif
#if
纯属队列训练题
这题其实说的很明白，就是让你在 $n$ 个数里拿出第一个数，若这个数减 $1$ 不为零就将其放到队尾，否则将其弹出去，在 $k$ 次操作后输出剩下所有数的编号，若操作次数大于 $k$ 次，则输出 $-1$。
### 你们最爱的代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
long long n,k,x,s;
q
有才的家长：
⑴
“隔壁小明玩游戏吗？” “玩！”
“他成绩好吗？” “好！”
“你知道他为啥玩游戏吗？因为他学习好！”
⑵
“隔壁小明玩游戏吗？” “玩！”
“他成绩好吗？” “不好！”
“你知道他为啥成绩差吗？因为他打游戏！”
⑶
“隔壁小明玩游戏吗？” “不玩！”
“他成绩好吗？” “好！”
“你知道他为啥成绩好吗？因为他不打游戏！”
⑷
“隔壁小明玩游戏吗？”
# Solution#1
对于 $5\%$ 的数据，if else 特判即可。
# Solution#2
考虑分别 $O(2^n)$ 枚举排列，直接爆算即可。
得分 $20$
# Solution#3
设计 $dp$ ，令 $f_{i,j}$ 为 $A$ 排列中做到第 $i$ 个值， $B$ 中做到第 $j$ 个值。
$if \ \ \ \ \ A_i=B_j \ \ \ \ \
## P1746 离开中山路
### 题意简化
> 给定一个 $n \times m$ 的地图，地图中的每个格子要么是一个障碍物 $1$ ，要么是一个空地 $0$ 。你需要从起点 $(x_1,y_1)$ 移动到终点 $(x_2,y_2)$ ，移动时只能上下左右四个方向移动，且不能穿过障碍物。请问最少需要多少步才能到达终点 B。
### 思路
> 这道题可以使用广度优先搜索（BFS）来解决。我
我们先抽象，令 $\Huge b_{i,j}$ 为用第 $\Huge i$ 种烹饪方法，第 $\Huge j$ 种主要食材的做饭的做菜数量 $\Huge \circ$
显然：
$\Huge \forall o\in N^+,1\le o\le n ,\sum b_{o,j}\le1(\mathbb{A})$
$\Huge \forall o\in N^+,1\le o\le m ,\sum
### 第1章 绪论
在Oier中，有一句话广为流传：
任何蒟蒻必须经过大量的刷题练习才能成为大牛乃至于神牛。
这就是著名的lzn定理。然而，我们这些蒟蒻们，没有经过那么多历练，却要和大牛们同场竞技，我们该怎么以弱胜强呢？
答案就是：
## 骗分
那么，骗分是什么呢？骗分就是用简单的程序（比标准算法简单很多，保证蒟蒻能轻松搞定的程序），尽可能多得骗取分数。
让我们走进这本
## [题目传送门](https://www.luogu.com.cn/problem/CF83B)
## 题意
给定一个包含 $n$ 个数的序列 $a_1,a_2,\dots,a_n$，$a_i$ 的编号为 $i$，注意编号不会因为数字的移动而改变。
现在请你执行 $k$ 次操作，每次操作为取出序列的第一个数并将其值减一，若其值大于 $0$，则将其放到序列的最尾端，否则将其删除。
求最后的
这是 Markdown 源码：
```plain
你的代码仍然存在 **WA（Wrong Answer）** 的问题，主要原因在于 **树状数组（Fenwick Tree）的实现方式不适合维护前缀最大值**。
### 问题分析
1. **树状数组的局限性**：
- 树状数组通常用于维护 **前缀和** 或 **单点更新 + 区间查询**，但 **不能直接用于维护前缀最大值**。
- 你的 `u
### 一、递推及转移方程
>读题之后，考虑使用类似 递推 的方法，设 $f_i$ 表示走到 $i$ 坐标所需的最少移动次数。所以就可以得出没有障碍物的转移方程：
>$$
>f_{i+1} = f_{i-1} + 1
>$$
>这个转移方程的原因是：从一个点到另外一个点用跳两步的移动方法一定比走一步的移动方法要更优。
### 二、特殊情况：
>1. 两个障碍物紧挨在一起，也就是 $ x_i ==
风带来了故事的种子，时间使之发芽。
[第二届鲜花魔怔杯](https://www.luogu.com/paste/1ospopvc)参赛作品：
[参赛版](https://www.luogu.com.cn/paste/ji4h2k64)
[一些解释](https://www.luogu.com.cn/paste/4ma63tq5)
## $5$ 个未完成的故事
注意：可能存在**改编**和
## 7.28 dijkstra （Dijkstra's Algorithm）
时间复杂度$O(mlogm)$
### dijkstra 模版
```cpp
void dijkstra(int bg)
{
priority_queue<P, vector<P>, greater<P>> heap;
memset (dist, 0x3f, sizeof(dist));
heap.push({0
# Ynoi总结
做的不是很多，主要是熟悉根号复杂度算法及其数据结构，提升一点DS水平。
### [P7446 [Ynoi2007] rfplca](https://www.luogu.com.cn/problem/P7446)
考虑分块，然后对每个点维护父亲 $f_i$ 和跳出块外的第一个祖先 $p_i$。
注意到一个块如果被整体修改 $\sqrt n$ 次，那么里面所有点的$
不太懂数学，有错请指出/kel
首先认为 $\log$ 是小项。有一个比较 trival 的想法。提取模数中 $\le m$ 的素因数，在乘除的时候都把先这些素因数提完。这部分的素因数只有 $O(\log p/\log \log p)$ 个，因此复杂度是 $O(m\log\log\log p)$。
可以发现这里的小素因子提取是很慢的。只需要对不超过 $O(\sqrt{\log p})$ 的质因
# update（10.21）：更新$Part$ $3$和$Part$ $4$。
## 前言
写于$2020$生日前。这次生日是初中生涯最后一个生日。谨以此文总结初中的三年。
## 目录
$Part$ $1$ 对初中部分教过我的老师的评价。
$Part$ $2$ 班级里各种梗。
$Part$ $3$ 印象较深的同学。
$Part$ $4$ 日后要改进的地方。
$Part$ $5$
# 前言
教练的任务。本来想写线段树来着，被人占了，那就写平衡树罢。
# BST
BST，全称 Binary Search Tree，即二叉搜索树，其定义为：
1. 空树是 BST；
2. 左子树的权值小于根节点；
3. 右子树的权值大于根节点；
4. 左右子树均为 BST。
可以发现 BST 具有一些良好性质，比如中序遍历有序。
## 操作
### 定义节点
```cpp
tem
[原题传送门](https://www.luogu.com.cn/problem/P10954)
---
## 思路分析
dp。
先考虑设 $f_{i,j}$ 表示 $a$ 的前 $i$ 个数和 $b$ 的前 $j$ 个数的 LCIS 的长度，但发现这样不好转移，我们可以考虑设 $f_{i,j}$ 表示 $a$ 的前 $i$ 个数且以 $b_j$ 结尾的 LCIS 的长度。
考虑状态转移
## 前言
[二进制警报器](https://www.cnblogs.com/zkyJuruo/p/18668862)是 zky 在 WC2025 前不久提出的一个掀起了巨大波澜的算法，该算法使得一道来自于四年前的经典折半警报器大时限题目[鬼街](https://www.luogu.com.cn/problem/P7603)的限时可以被压制到 1s 以下。
对于该算法，zky 本人已经在他的博
## 前情提要
因为第二天的比赛，晚上提前放学，所以晚半个小时下课，要说也是真巧，晚半个小时就能赶上大堵车、超大暴雨，我也是真的服了。
## 正片
### 赛前-1h
早上一到就听别人说今天是$3h$，6道题，那不是更贴近AT了吗？但是难度未知，这就很慌了呀！
### 赛前-0.5h
进入考场，诶，yjx，wtc跟我一个考场，那不慌了呀！不对，我的座位怎么在最前面，这就不好搞了呀。没事
## 前言
本文又名：《回文树：从入门到入土》。
## 回文树
咕
## 回文子串
咕
## 回文划分
### 周期
对于字符串 $S$，若其是某个字符串不断反复组成的，假设该字符串长度为 $p$，则称 $p$ 是 $S$ 的一个周期。
形式化的表达为 $\forall i\in[1,|S|-p],s_i=s_{i+p}$。这里我们定义总是有 $p<|S|$。
> 弱周期引理：
[N1](https://benben.sbs/feed/5596003)
然而小朋友不知道，他面前的就是 7wny，不过是改名了，语文真好！
[N2](https://benben.sbs/feed/5592894)
神评：“一看你这个等级分就一言难尽啊。”
诶别人不打比赛怎么你了呢。
[N3](https://benben.sbs/feed/5592329)
[更好的阅读体验](https://www.cnblogs.com/LaoMang-no-blog/p/16427416.html)
---
考场一直在想神仙构造方法，实际上连最浅显的结论都没有发现。
首先关注到数据规模不大，想到通过某种方法构造完一棵树后暴力 $\mathcal O\left(n^3\right)$ 判断是否满足要求的可行性。
这题还是比较需要思想火花的，如果想不到第一步
我不到啊
雾.jpg
## 【CCPC-桂林 2022】Problem H. Hysteretic Racing 线段树-LogUpdate
### 问题分析
https://codeforces.com/gym/104008/problem/H
#### 【题意】
给出一个长度为 $n$ 的环，标号为 $0,1,2\cdots n-1$，第 $i$ 号单元的下一个位置是 $i+1\mod n$ 。
第 $i
[题目传送门](https://www.luogu.com.cn/problem/P13511)
呃呃（感觉）相当清新的做法（
令 $maxh$ 表示 $N$ 个点中最大的纵坐标， $minh$ 表示最小的纵坐标。
观察样例可以发现，底边上的点的纵坐标要么是 $maxh$ ，要么是 $minh$ 。
还可以发现，其斜边是**系数为 $\pm 1$ 的一次函数上的一条线段**（因为是45度角
树上背包，在合并俩子树时需要做 (max, +) 卷积，但这是 $O(m^2)$ 的，下面介绍一些规避 (max, +) 卷积的方法。核心思想是改变考虑 dp 的方式。
#### 以 dfs 序的角度考虑 dp
例题：$n$ 个点的一个有根树，点有点权，给定 $m$，对每个点 $x$，求出包含根以及 $x$ 的大小 $m$ 的点权和最大的连通块。 $n\le 5000$。
这个正常 dp 不
看完题明显是LCT~~从题目知道的~~
同时是个动态树问题~~废话~~
### 什么是动态树问题
维护一个 森林，支持删除某条边，加入某条边，并保证加边，删边之后仍是森林。我们要维护这个森林的一些信息。
一般的操作有两点连通性，两点路径权值和，连接两点和切断某条边、修改信息等。
### 什么是LCT
LCT的核心思想基于实链剖分与Splay树的结合。我们可以简单的把 LCT 理
# 这是正常一级标题
## 这是正常二级标题
### 这是正常三级标题
:::align{center}
# 这是居中一级标题
## 这是居中二级标题
### 这是居中三级标题
:::
:::align{right}
# 这是右居中一级标题
## 这是右居中一级标题
### 这是右居中三级标题
:::
## 代码守则
- 数据结构类型题，并列或是嵌套的数据结构使用 **命名空间** 区别，对于各类树形数据结构，使用全局变量 **tr** 视为一棵树，数据结构内部树的编号使用 **r** 代替
- 对于计数变量，全局使用 **tot**，余下的格式统一为 **n+统计元素名称**，如 nson 为儿子的数量，释义为“The number of ...”。
- 链式前向星循环变量使用 **e*
省流：D1T1 $100\to 20$。
upd：官方出了，是 $100\to 50$。
_**# NOI 账号被清除了是正常的？**_ _**[CCF_NOI](noi.cn)**_
```
wmr成神记：Accepted
Wmr参加洛谷月赛，提交代码后意外触发全站公告：“隐藏
挑战激活”。
管理员“差分机”紧急会议：“他解开了初代管理员的思维
锁！”
三重试炼开启：底层题库Bug潮、社区被篡改的求助帖、同
时响应百万用户需求。
当Wmr代码在虚拟洛谷城市点亮万家灯火时，管理员后台权
限列表悄然新增了一个ID。
键盘的敲击声在狭小的房间里连成一片细
思想很简单，就是线段树上的每一个点都维护的都不在是一个区间，而是一棵平衡树。
具体地，每一个点都维护那一个点上平衡树的根。
但是代码实在是难写，常数巨大，洛谷还卡常，卡了老久才过。
细节超多，在代码中了。
时间复杂度：
区间查一个数的排名：$\mathcal{O}(\log ^2n)$。
区间查对应排名的数：$\mathcal{O}(\log
语文老师告诉我们游记要写时间人物地点
### 时间:2023年10月21日
### 地点:华中师范大学
### 人物:我
# 审题环节
开始考试了,我们老师告诉我们先审题30分钟
先看**时间和内存限制**
| 题目名称 | 时间限制 | 内存限制 |
| :------: | :-----------: | :--------------: |
| 小苹果 | 1.0秒 |
$$
\lceil \text{学前班} \rfloor \hspace{0.2 cm} \text{线性代数基础}
$$
### 矩阵的定义
### 矩阵的基本运算
### 矩阵的变换
d定义n个变元，$ x_1,x_2,x_3...x_n$ 的线性方程。
$$
\begin{cases}
a_{11}x_1+a_{12}x_2+...a_{1n}x_n\\
a_{21}x
物理，太困难。
我似乎都忘记了什么叫动量守恒，这下学到选必二的时候就输麻了！
大输特输。
每次比赛前都想着要复习 tarjan，所以直接写一篇之后就不用找了。
### 强连通分量
有向图。即这个分量的每个点都能到达其它点。
判断方式是 $low_x\ge dfn_x$ 代表连不出去，然后跳栈直到跳到 $x$，因为 $x$ 是这个分量中 $dfn$ 最小的了。
细节是注意跳栈时要把 $vis$（是否在栈内）设成 $0$，防止重复访问已经更新的点。所以必须先判断在栈内再 $low_
## FHQ-Treap
即**无旋转** Treap，代码长度短，好写好调，同时支持维护序列和可持久化。
首先在它是建立在 Treap 的基础上的，需要同时满足以下性质：
* 是二叉搜索树，是平衡树所有操作的基础。
* 是一个堆，这里堆的权值是一个一开始确定的随机权值 $rnd$，在后面的代码中是按大根堆的方式实现的。
由于权值是随机的，可以证明同时满足这两个性质的树的树高一
### 费马小定理
$$
a^{p-1}\bmod p=1
$$
用处是乘法逆元，$a^{-1}\bmod p=a^{p-2}\bmod p$。
### 欧拉定理 / 欧拉函数
欧拉函数性质：
* $\varphi(x)=\sum_{i=1}^n[\gcd(i,x)=1]$
* $x\in P$ 时有 $\varphi(x)=x-1$
* 是积性函数
* $n=\sum
洛谷新手村外，一个 OIer 开设的机房里，程序员 kkksc03 端坐在桌后。他头也不抬，冷冷地问：“你叫什么名字？”
“chen_she。”
“年龄？”
“**岁。”
“什么错误？”
“TLE。”
kkksc03 程序员站起身熟练地打开病人的代码。他愣住了，蓝色的眼睛里闪出惊疑的神情。他重新审视着眼前这个人，冷冷地问：“你的洛谷名是什么颜色的？”
## 试题 A
找规律。模拟斐波那契数列，每次都对 $10$ 取模，取个位输出。
:::info[代码]
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
i
为了方便，所有的分数默认下取整
$$\sum_{i=0}^{n}\binom{n}{i}p^i\times \frac{i}{k}$$
$$n,p\leq [0,998244353)\quad k=2^t(t\in[0,20])$$
$$=\sum_{i=0}^{n}\binom{n}{i}p^i\times \frac{i-i\bmod k}{k}$$
$$=\frac{1}{k}\su
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <conio.h>
#include <windows.h>
using namespace std;
const int WORLD_WIDTH = 40;
const int WORLD_HEIGHT = 20;
const
#include <iostream>//用C++写一个简易版我的世界的代码，只用C++内部库。要有较多的功能，不要那么卡
#include <conio.h>
#include <windows.h>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <map>
using namespace std;
// 游戏常
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <conio.h>
#include <windows.h>
using namespace std;
const int WIDTH = 20;
const int HEIGHT = 5;
class GameObject {
```
金牌祭坛下的孤王座
Jiyu AK了IOI，全球瞩目。
记者问他：“最想感谢谁？”
他盯着镜头，眼神淡漠：“感谢对手太弱。”
教室沸腾，hhr颤抖着递来写满问题的笔记本：“能…能讲讲思路吗？”
dyq把Jiyu的解题截图设成手机壁纸：“你代码太美了…”
Jiyu接过笔记本，指尖在颤抖的纸页上划过，突然轻笑：“美？”
他抬眼，目光扫过狂热的脸庞，像扫过一行行无法
### 算法一、DFS一号
```cpp
#include <bits/stdc++.h>
using namespace std;
int n = 2, a[5], s;
int dfs(int x, int sum) {
if (x > n) return sum;
int i = dfs(x + 1, sum);
int j = dfs(x + 1, sum + a[
[
注：根号暴力算法指一些时间复杂度为 $O(n\sqrt n)$ 的较为暴力的算法，通常情况下在 $n\le 10^5$ 级别时可以通过。
# 1. 普通莫队
其基本思想基于分块的性质，主要解决线段树等其他较为优秀的数据结构较难实现的**离线区间**问题。
首先这个问题需要满足：对于区间 $[l,r]$ 的维护是可以以 $O(1)$ 的时间复杂度将左 $/$ 右端点向左 $/$ 右移一格的，移
[题目传送门](https://www.luogu.com.cn/problem/P13492)
## 题目大意
这道题目要求我们找到最小的正整数 $k$，使得给定的排列 $p$ 可以通过将其划分为 $k$ 个可空子段，然后反转这些子段的顺序，最终得到一个升序排列。操作可以执行任意多次。
## 思路
这道题的核心在于观察排列的结构，并找到关键的断点（也就是相邻元素不连续递增的位置）。通过分
[题目传送门](https://www.luogu.com.cn/problem/P13422)
## 题目大意
有 $N$ 个玻璃杯，每个杯子有当前液体量 $T_i$ 和容量 $Z_i$。通过在杯子间倒液体（每次可倒任意整数升，但是不能溢出），问最多能让多少个杯子变空，并输出一种可行的最终液体分布方案。
## 题目思路
想要让空杯子的数量尽量多，就要让尽可能多的液体聚集到尽可能少的杯子里。
## 一道简单模拟（贪心）题。
------------
## 思路（策略）
1. 如果当前人分数与之前一人一样，那么橘子数相等。
2. 如果比之前一人分数高（**递增**），那么橘子数为之前一人的橘子数加一。
3. 由于分数可能出现**长度大于$2$的递减序列**，所以最后还要反过来扫一遍数组，把橘子数加上去。（~~卡了我一次~~）
# 注意：要开$long long$!（值域最大为$1e
### 题目不难，就是有几个注意点
1. 取模时先减$1$再加$1$，是为了避免$0$的出现
2. ~~有个小坑~~，如果第一条狗暴躁但是第二条狗安静，那么答案为$one$而不是$both$
**下面上代码（注释都在里面）**
```
#include <bits/stdc++.h>
#define R register
#define gc() getchar()
using namesp
[旧版备份](https://www.luogu.com.cn/paste/80bmmxj4)
## 声明
本文主观性较强，可能含有口嗨，请谨慎对待其正确性。
本文针对于联赛，因为省选并不在我经验范围内。
这是[之前的版本](https://www.luogu.com.cn/blog/vegetable-MLE/ru-he-zai-lian-sai-hu-xing-xuan-zhong-j
$2025$年$7$月$18$日做题数：$17$
$\hspace{2.1cm}$前缀和：$17$
$2025$年$7$月$19$日做题数：$23$
$\hspace{2.1cm}$前缀和：$40$
$2025$年$7$月$20$日做题数：$22$
$\hspace{2.1cm}$前缀和：$62$
$2025$年$7$月$21$日做题数：$21$
$\hspace{2.
## 前记
SPOJ - GSS系列 on : 2022.10.27 总用时 $ 4 $ 天
P5073 on : 2023.02.15 总用时 $ 1 $ 天
P5693 on : 2023.02.15 总用时 $ 1 $ 天
P4118 on : 2023.07.29 总用时 $ 1 $ 天 ( 拉了P5073的代码 )
## Part 1 SPOJ - GSS 系列 Easy V
### Day -35
怀着初赛**再**不过就退役的心态再次来到 pyyz
~为什么上午普及组的题怎么简单！~
下午的提高组前面 $15$ 道选择并不难，但后面程序的马蜂实在是难看（当然，我没看懂几道）
返程时，看到最后 $10$ 道选择居然有 $9$ 个 A，早知道就全蒙 A 了。
### Day -34
发现身份证和铅笔盒都丢了，祭！
### Day -30
我居然还能过初赛
$${\large \color{Red}重要的不是你做了多少题，而是你放了多少心思进去。}$$
目前整理：3.3至7.31，[链接](https://www.luogu.me/article/vu3wcowr)
# 搜索
## 深度优先搜索
### [P1731](https://www.luogu.com.cn/problem/P1731)
题意：构造一个蛋糕，每一层都比上一层薄且小，给定总
在计算机科学领域，排序算法一直是基础研究的核心方向。从经典的冒泡排序、快速排序到现代的 Timsort，每一次算法的革新都推动着数据处理效率的提升。本文将探讨两种独特的排序算法 —— 珠排序（Bead Sort）与玄学排序（Metaphysical Sort），并分析它们在特定场景下的应用潜力。
## 珠排序：物理启发的 O (n) 奇迹
珠排序是一种基于物理现象的排序算法，其灵感来源于算盘珠
# 问题
掏出一个包含且仅包含一个字符串 $S$ 所有字串的自动机。
# 原理
显然，有一种 $n^2$ 级别的构图方法：trie 树上存储所有后缀。
然而，可以考虑增量式地去构造。
# Part 1
首先，把原来 $S$ 中的所有字串全部分类，按照**在原串出现位置（末字符）的集合**来划分。它有一些很好的性质。
- 1.一个集合内的字串是最长的那一个串的连续后缀。
- 2.对于
# 空间优化
1. 滚动数组。
2. 离散化。
3. 二进制（状态压缩）。
4. 对称剪枝。
# 转移优化
1. 单调性（单调队列或二分）。
2. 斜率优化。
3. 可行性剪枝。
4. 最优性剪枝。
# 递推加速与分治
1. CDQ分治。
2. 矩阵快速幂。
1.和几项有关，矩阵就是几*几
2.含有常数项就
# 斐波那契堆详解+摊还分析(附 带注释C代码)
斐波那契堆是一种可合并堆，支持以下5中操作：
MAKE-HEAP() : 创建和返回一个新的不含任何元素的堆
INSERT(H, x) : 将一个已填入关键字的元素 x 插入堆 H 中
MINIMUM(H) : 返回一个指向堆 H 中具有最小关键字元素的指针
EXTRACT-MIN(H) : 从堆 H 中删除最
更新时间：2025/5/18 01:38:06
# 第一周
## NOIP2018
### 提高组
- [ ] [P5023 [NOIP 2018 提高组] 填数游戏](https://www.luogu.com.cn/problem/P5023)
- [ ] [P5024 [NOIP 2018 提高组] 保卫王国](https://www.luogu.com.cn/problem/P50
## 生山纪念中学纪念山中学生
### ——纪念三位同学
:warning:文章纯属**虚构**，本文和中山纪念中学**没有任何关系**。
### 前言
上周下着倾盆大雨，把风雨连廊靠近食堂的最后一块玻璃压裂了。现场只有小Z同学一位死者——他中午为红烧牛腩盖浇饭抢跑而遭此飞来横祸。不过大家对小Z的死无动于衷，只是继续看着手上的复习资料，到食堂排队就餐。因为山上这个破碎的学校，每天都有人接二
无聊，随便写写，不想看的别看
- 入门（非常水的无脑题目，如 A+B）
- 入门+（有一点思考的无脑题目）
- 普及-（橙）
- 普及（黄）
- 普及+（黄+/绿-）
- 提高-（绿/绿+）
- 提高（蓝-/蓝）
- 提高+（蓝+/紫-）
- 省选-（紫）
- 省选（紫+）
- 省选+/NOI-（黑-）
- NOI（黑）
- NOI+/CTSC（黑+）
## [前情提要](https://www.luogu.com.cn/article/gkf28l3b)
## 又是新的一个学年，鸿运当头666。
## $\text{2024年}$
### $9.1$
今天也是成功的去学校报到了。
感觉我们班上的同学一个一个一个都没怎么长。
现在初二的教学楼一层有6个班，也就意味着5班和6班将会和我们同一层楼。
发了新书，老大还把班上的座位重新排了
> 今年是最后一次J组了，发游记发早一点吧……
拒绝伤感，祝所有人CSP2025 **RP++**
## 去年犯过的错误
### 第一轮（S组纯粹娱乐，实际自己没有那样的水平，在此不予展示）
成功地涂错一道判断题，使总分来到89.5。
### 第二轮
**T1：** 简单的扑克牌，通过遍历得出结果，5分钟解答。
**T2：** 通过大模拟模拟迷宫，遇到障碍就左拐，还是很简单的，20分钟左右。
让我们直入主题吧。
## 压缩 trie
或许这里的压缩 trie 并不是很标准的压缩 trie。
众所周知，假设你要插入 $n$ 个字符串 $s_i$ 到一个 trie 里，假设字符集大小为 $k$， 通常的写法是时空复杂度 $O(k\sum s_i)$ 的，关键在于建立的节点个数是 $O(\sum s_i)$ 的，这样不够好，我们可以考虑这颗字典树每个字符串结尾节点建出的虚树，这样可
## 7.20
高铁一路上网络神神秘秘，好几次刚进云游戏直接断线，给我整无语了。
但是加上最后去广附的一段时间，也将近玩了五个小时，新剧情有点泪崩啊，但是白厄60多抽没出，好吧，有人抽不了了。
一到寝室直接给我看懵了，wc纯狱风大铁门，八人无桌宿舍（但只有四个人一寝），没有插头！！！！！！！
两个卫浴，一个喷头坏了一个没灯，难绷。
差点以为我在广附苟延残喘两周，食堂救了我一命，在XF赤石
是的，这里是一个**FW的日记**（大佬勿入）
7月：
### **刚放假**：
开始在机房里度过余生：
每天早上7：00开始面对学校的~~陈年老电脑~~（像上个世纪的win7）
晚上6:00放学回家，面对ex的whk作业
12：00闭眼，进入每天最快乐的时间
### 总之，暑假作业只写了几笔，还被**某YX**在群里通报了
## 到NOI了：
### 教练们出去打比赛了（**某
为什么要写这篇文章呢？因为教练让我们选一个专题写博客然后交流。
为什么选数学呢？因为线段树分块都被选走了，而数学专题没人选，并且可以把写过的笔记拼起来（
本文章涉及数论 & 组合数学两个部分，还包含一些数学杂项，整体内容比较简单。
本文代码中出现的 `modint` 或 `mint` 是笔者编写的自动取模工具。
# 质数
定义一个正整数 $p$ 为质数，即它不存在 $1$ 和 $p$ 以
[Link](https://www.cnblogs.com/ying-xue/p/17060429.html).
复制过来换行全没了，建议前往 [原文](https://www.cnblogs.com/ying-xue/p/16703279.html) 查看。
赛前占坑。
由于不知是 $Day ?$ 故采用日期方式记录。
文笔所限，闲话较多，略显杂乱。
### 09.??
接到通知，LN 初赛线上。面基环节无了/kk
### 09.17
翘 whk 和数学统练参加多校联测，全程罚坐，状态持续低迷。为明天
[原文食用效果更佳~](https://www.cnblogs.com/ying-xue/p/15468694.html)
#### 题外话
中午十二点半到了考场。没到时间不让进，恰巧发现 lhm 在对面饭店于是去讨论了一下上午 J 组的题，复习了线段树板子（
在考场门口面基了众多大佬（
等到进考场坐好的时候已经两点半了，看考号本来以为我们同机房三个同学会坐一起，结果和去年一样，到我这里正
~~我们不能误导新人~~。
## 思路
我们要算出 $a+b$ 等于几我们肯定首先想到的是线段树，但线段树不够新颖，我们可以把它扩展到二维。一维和二位的区别就在于一个线段求和一个是矩阵求和，修改。
在一个矩阵里我们分别把 $(1,1)$ 改为 $a$ 和 $(2,2)$ 改为 $b$ 求出 $(1,1)$ 到 $(2,2)$ 的和就行了，十分简单。
## code
拿出我今天刚写的二维线
### 今天！！
**某个人给我比了个赛（（**
这是赛时第3[题](https://www.luogu.com.cn/problem/P5427)，也是我想出来的唯一一个思维题。。。
当时只有一个点$哇$了，原来有一个情况没考虑到。。。。。解决之后就过了
↓ 给你们分享一下我的英雄事迹（？
我发现了，假如有一个字符串作为《标准》，这时如果所有的字符串都等于标准，或者跟标准反着来，就可以
## 前言
写这篇文章还是因为猜交互题应该怎么配置，一个下午没弄出来红温了写的。
感觉洛谷帮助文档讲自制题目、SPJ、交互不是很详细。
而且举例仅有代码，没有别的（例如放置位置，注意事项等）详细说明。
所以这篇文章就来详细讲讲。
---
## 正文
### Part 1 自制题目
大部分人都自制过题目吧。这里仅为基础内容介绍。
少部分第一次自制题目没有经验的，建议看这里。
##
# [L·篮球队招新](https://183.250.108.194:500/OnlineJudge/problem_show.php?id=2714)
## 题意简述
给定一个非负整数列，每次操作可以将任意相邻两项合并为其差的绝对值。求最后剩余元素的最值。
## 思路简述
典型的区间 DP，若设 $f_{l,r}$ 表示区间最大值，则不满足最优子结构的性质，因此考虑增加一维，即设 $f_{l,
$$\textit{prologue}$$
为手写信的电子版。
有稍大篇幅的改动。
为 2025.7.12 后写的第二版。
没想到第一版废得如此果断，第二版写的如此顺畅。
---
$$\textit{Chapter 1}$$
五月二第一次见面后，我就知道我们彻底不可能分开了。
见面了之后就不是网恋了，是异地！
我预想了无数多次的场面在现实中并未上演，倒是不出意外。
其实当天早上
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10, mod = 1e9 + 7;
int n, p[maxn], x[maxn], h[maxn], e[maxn * 2], ne[maxn * 2], idx;
long long dp[maxn][2];
void add(int a,
[2023/1/8 上午]初步理解分块方法的主要思想，开始写代码
[2023/1/8 11:09]完成第一版代码，写代码&调样例时发现三个错误
[2023/1/8 下午]发现代码里面只处理了块内贡献，经过思考加入了lst和pre两个数组用来处理块间贡献
[2023/1/8 下午&晚上]对拍并检查出多个错误
[2023/1/8 20:02]完成第一版正确性没有问题的代码，提交获得8pts
# A
注意到总人数极小，直接枚举三个不同的人判断即可
注意有两种判断正确的可能
```cpp
#include<bits/stdc++.h>
using namespace std;
int m , f;
bool g[10][10];
int main(){
cin >> m;
for( int i = 1 ; i <= m ; i++ ){
int a ,
我之前写的是什么玩意啊。。
主要还是为了证明 Matrix-tree 定理和之后的东西所以没用到的就不写了。
## 矩阵之前
先证明几个小引理吧：
定义：$\lambda(p)$ 为排列 $p$ 中的逆序对数，$p'$ 为一个排列，且满足对于任意 $i\in[1,n]$ ，有 $p'_{p_i}=i$ 。
**Lamma 0.1**
$\lambda (p')=\lambda (p)$
### 一篇写了将近一年的略制代码：
```cpp
#include<bits/stdc++.h>
#include<windows.h>
#include<conio.h>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#inclu
### $重载cin\&cout（自动快读机）\textcolor{red}{\Large{V}\normalsize{2.0}}$
```cpp
/*
重载cin&cout（自动快读机）
*/
#include<stdio.h>
#include<type_traits>
#include<algorithm>
#include<array>
#include<atomic>
#include<
# Matrix-Tree (矩阵树) 定理
**：一个算生成树个数的东西**
## 思想
1. 设 $D$ 为度数矩阵 $A$ 为邻接矩阵
2. 令 $K = D - A$ , $K^{'}$为 $K$ 去掉 $i$ 行 $i$ 列后得到的矩阵
3. $|K^{'}|$ 即为所求
证明~~不会~~略
## 实现方式
### 有向图
设当前加入边为$<x,y>$
## ひかり(hikari)
### $O(n^3)$
将所有灯塔按 $x_i$排序
枚举两个灯塔 $i,j$ 再枚举 $i,j$ 之间的灯塔 $k$ ,判断 $i,j$ 连线是否会穿过 $k$ 灯塔，若 $(i,j)$ 合法，概率增加 $ p_i * p_j * ny(n*(n-1))$
### $O(n^2)$
凸包思想
将所有灯塔按 $x_i$排序
枚举一个个灯塔 $i$ 再枚举
比较牛的一个题目。
考虑如果在某一个位置放置了一个物品，那么剩余的空间就会变成 $2$ 个没有关系的单独区间。
注意到 $n\le 14$，那么我们显然可以枚举一个子集 $S$，然后判断是否有一种方案可以把 $S$ 中的元素恰好放进去。
有一个性质，如果 $S$ 确定了，那么在 $[\sum\limits_{i\in S} a_i,+\infty)$ 是具有单调性的，即如果 $x$ 可以做到
# Day -1
下午去佛山市南海中学报道。
回来的时候打了一辆车牌号含 `DS` 的车（笑。
回来 3 点多发现自己前几天熬夜熬脱了，非常头痛。于是在床上躺着试图睡觉，于是 1h 过去了，尝试失败，于是下楼打乒乓球。回来终于有了困意，成功睡着。结果晚上 12:00 鼻炎发力了，直接给我弄醒，费了好大劲才睡着。
# Day 1
早上起来头疼欲裂，~~幸亏我是体验~~。
浑浑噩噩到了考场，考试
# ひかり(hikari)
## 题目背景
$$小杰...你就像光一样$$
$$但有时太过刺眼，使我无法直视你$$
$$即使这样，你还是肯跟我在一起吗？$$
## 题目描述
在「光の境」中，定义地平线高度为 $0$，天际线高度为 $z$，一切建筑基于地平
[题目传送门](https://www.luogu.com.cn/problem/P5076)
---
## Part.-1(?). 闲话
看了一下很多大佬们的题解啊，都很多都用了
`BST multiset 树堆`
之类的高级玩意儿，但是我过于蒟蒻，因此看不懂那些题解。感谢老师和
~~（陪我打CS1.6的）~~
同学，我最终还是用了一种较为野鸡的方法
$AC$
了这道题，就来分享一下自
[题目传送门](https://www.luogu.com.cn/problem/P2712)
## Part.0. 闲话
没错，又是我 [^1]。在上次的 [P5076的一点小理解](https://www.luogu.com.cn/article/266l6yoh) 中说我真的是个 $\color{cyan}{蒟蒻}$ ，事实上也确实如此，在9.16的考试中也是轻松 $AK$ 了20分啊，
[提交记录信息](https://www.luogu.com.cn/record/104003469) / [官方数据集](https://github.com/THUSAAC/THUPC2023-Pre/tree/master/day0/I) / [原题传送](https://www.luogu.com.cn/problem/P9141)
不得不说，这道题目扔到一个 4.5 小时的 ACM 竞
# rui_er 的代码记忆法
## 0x0 阅读前提示与声明
本文只是我梳理我背板子方法的一篇随笔，请不要过度解读。如果你有耐心且有时间读完本文，你会发现这确实就是一篇正常的随笔。
本文的代码记忆法一般只适用于板子，毕竟不可能把每道题都背下来，也猜不到会考什么类型的题，主要是掌握算法的思想。
## 0x1 第一次学习
第一次学习至少要大致掌握算法的用途以及流程，原理要有感性的理解，但不
# min-max 容斥
对于一个长度为 $n$ 数列 $\left \{ a_i \right \}$，有如下式子：
$$
\max_{i=1}^{n} \left \{ a_i \right \}=\sum_{T \subseteq \left \{ 1,2,\cdots,n\right \}}(-1)^{\left | T \right | -1} \min_{j \in T} \left
### 1. 题意解释
给出一个 $H$ 行 $W$ 列的迷宫，你可以往上下左右移动一格或喝魔药移动 $D$ 行 $W$ 列，求最少需要多少次才能逃出迷宫。
### 2. 思路
怎么其他人都写 BFS，就我一个分层图最短路是吧……
由于魔药只能喝一次，所以我们建两次图，对于两个相同的点，我们用边权为 $0$ 的边将其相连。
如果我们在同一层跑最短路，也就是不喝魔药时所需的最短路径。
问
> **笔者注**
>
> 本文原标题为《中考求生指南：能活到中考已经很厉害了！》，为笔者高考后回到初中，给即将面临中考的同学作演讲时的演讲稿。但演讲后意识到，本文似乎可以是全年龄向的，于是稍作修改，并在此公开。
>
> 文中出现了一些无法过审的敏感词汇，我将用对应的英文词汇代替。
>
> 以及，你也可以前往我的个人博客阅读修改前的[原文](https://blog.ryanli.top/inde
P11451
瞅了一眼都是随机化的做法，这来个不随机的。
注意到，先在开头
`1 1`
\
`1`
就让错解 $x=3,y=2$ 了。
让自己的正解取 $x=1,y=3$ 就可以在第三列 `1 100 100` 从而使错解厉害地WA了。
而这样会让错解与正解落点重合了。所以第三列第三个数只能取 $99$。
第四列，`100 100 100 1`。这样选让错解继续选中 $100$。
第五列，`100
## 本质
对于函数 $f$ 和 $g$，构造两个二元函数 $a$ 和 $b$，使得满足
$$
f(n)=\sum_{i=0}^{n}a(n,i)g(i)\\
g(n)=\sum_{i=0}^{n}b(n,i)f(i)
$$
已知 $f$ 求 $g$ 的过程称为反演。
---
将 $g$ 带入得到
$$
\begin{aligned}
f(n)&=\sum_{i=0}^{n}a(n,i)\
有一个朴素的 dp 是直接设 $dp_i$ 表示把 $i$ 删到 $0$ 的最小次数，可以转移：$dp_i=\min(dp_{i-d})+1$，其中 $d$ 存在于 $i$ 的数位中。
进一步观察性质发现，dp 数组是递增的，简单说明一下：设 $q(i)$ 为 $i$ 的最大数位的数，那么有 $q(i-1)\ge q(i)-1$（可以自己举几个例子验证），所以可以数学归纳法证明原式。
也就是说
# 前言：
伟大的教练昨天讲了这个算法，所以来写一写，这段话绝对没有复制粘贴……
# 正文：
## 定义：
一个数的欧拉函数是指这个数字前面（不包含这个数字）有多少数字与他互质，如：2的欧拉函数就是1，3的欧拉函数就是2,4的欧拉函数就是2……
## 计算：
那么一个数的欧拉函数就是这个数所有质因数被一减掉的乘积在乘上这个数本身。（这里我们可以用到容斥原理去证明，但对于我来说貌似证明没有什么实际作
当 $\rm 24$ 小时后再次坐上这班列车，是以 $\rm oier$ 的身份继续走下去，还是滚回去学 $\rm whk$，就看明天上午的四个半小时了。无论结果如何，与大家在一起的一年大概是我高中生活里最快乐的一年，很高兴遇见你们。
从最近的模拟赛数据以及自己 $\rm vp$ 的 $\rm noip 2021$ 来看，尽快切掉 $\rm T1$ 是上上策。但毕竟这次是取消联合省选的第一次 $
建议重写题面
# 题意:
长度为 $N$ 的序列,从左向右每 $k$ 个位置切一刀分割成 $\frac{n}{k}$ 个区间,保证 $k|n$
第一类操作为每个子序列左/右移 $k$ 位
第二类操作为所有位置左/右移 $k$ 位
然后两类操作均为循环移位,即1234左移后变为2341
给出 $Q$ 次操作后的序列,求操作前的序列
$N,Q,k\leq 100000$
## Part1
文化课的日子果然繁忙，断断续续三周才算真正写完了这篇退役记。
由于相当多的 html 标签无法在洛谷渲染，就不搬到洛谷上了，大家可以去个人博客里看：[一场持续 502 天的梦](https://grainrain.site/oi_dream/)。
whk 的闲暇之余可能会写一些文化课周记：《十字路口处》，[知乎](https://zhuanlan.zhihu.com/p/671222984)
本文章基本不包含**数学**公式（我不保证**完全**不包含），若想查看数学公式请出门左转[LaTeX数学公式大全](https://www.luogu.com.cn/blog/IowaBattleship/latex-gong-shi-tai-quan)。
开始说正经的：
将LaTeX写在`$...$`之间，为行内公式：
$abc$
```
$abc$
```
写在`$$...$$`之间，
## Description
x教授是位德高望重的教授 , 他的课以受学生欢迎而著称 .
然而 , 有这么一个熊孩子 , 他上谁的课都不听 , x教授也不例外 . 最让人不能忍受的是 , 他有时还会在上最后一节课时偷偷溜走 , 提前回家 .
有一次 , x教授的课在最后一节 , 然而这并不妨碍熊孩子偷偷回家 . 不巧的是 , 他刚出校 , 正讲得酣畅淋漓的x教授往他的座位瞟了一眼 ,
开始提问！
一共回答20个问题，每人至多问2个
1. 在洛谷上有没有npy 提问者：huangzhaoyuan0318
~~嗯好吧确实有，是Fiona_qiu~~
2. 几年级在哪里上学 提问者：RNtianbowen
可以说是初二，但我是5年级的年龄，在北京八中少儿班上学
3. 你是sb吗 提问者：fuxiao
不是，~~顺便提醒一下你骂街可不成~~
4. 你是社恐还是社牛
我也在想此题如何用$O(n)$解决，然后看到了这个题，就有了这个题解。
由于我比较懒，以下的函数均省略$(x)$
---
引理：设连续可导函数$F_1,F_2,G$满足$G^2+F_1G+F_2=0$，那么$G$也满足$(4F_2-F_1^2)G'+(F_1F_1'-2F_2')G+2F_1'F_2-F_1F_2'=0$。
证明（懒得看就算）：原式对$x$求导得
$$2GG'+F_1
想挂的回复就行
下面我们定义 $1\sim n$ 上的位置集合为主干道，其他位置为岔路。我们没必要把快递搬出主干道，证明考虑我们把物品搬到了从【主干道一位置 $u$ 分出的岔路】上的一位置 $v$。那么 $u$ 肯定是可达的，且相比 $v$ 更靠近 $n$，所以比 $v$ 更优。
所以每个机器人的有效覆盖范围是主干道上的一段区间，直接转化为链的情况。设机器人物流中心到主干道距离为 $d$，离 $1$ 点距离为
机房。
一年过得还真是快啊。
没有普及一等，提高一等，省一，校赛似乎还要寄了。
想要说些什么，却又该从何说起？
不知道是应该失望，悲伤，亦或是愤怒？
喜悦也不是不行。
无言
**Update On 2020.3.6：修复了一些细节问题**
---
“子矩阵最大值等于 $v$ ”的方案数等于“子矩阵最大值小于等于$v$的方案数”减去“子矩阵最大值小于 $v$ 的方案数”，考虑容斥。$2^n$ 地枚举哪些子矩阵满足最大值小于 $v$，那么我们可以得到矩阵中每一个位置能够取到的最大值，设 $x_{i,j}$ 表示 $(i,j)$ 的最大取值，那么方案数就是 $\prod
### 题目大意
接竹竿游戏规则为按顺序依次加入一个牌堆，如果发现牌堆中有一对相同的牌，则将两张牌中间的牌（包含两张牌）全部拿出，求最终牌堆有多少牌。
有一个序列 $a$，有 $q$ 次询问，每次询问给出 $l,r$，求出 $[l,r]$ 的接竹竿结果。
### 题目分析
考虑直接模拟。我们先预处理出每个 $a_i$ 的后面最近出现相同值的下标，定为 $z$。
对于每次询问：
- 如果
### $7$ 月 $20$ 日
由于作者是四川人，所以直接开车。
早上 5 点，我们开车沿着 G93，成渝环线高速跑到了重庆绕城高速上。
不得不提以前夏天热极了，那天居然下暴雨，26 摄氏度， 比我们那边凉快多了。
走匝道又开到 G93，成渝环线高速上，雨就很小了，但还有。
在重庆开了 3 小时左右，还是很大啊。
而且去贵州的路上经过了很多隧道（共计20000多米）和桥（多的算不清）
其实，看似坚强是因为没人关心，看似沉默是因为自卑，看似高冷（只不过熟人面前不会）是因为孤独，看似俭朴是因为压抑。
或许我讲课的时候，看起来非常不近人情，非常着急。我知道你们都讨厌我。其实，我也不喜欢你们。当你们用我的账号给封禁用户随机发私信时，我并没有太多的表现，但是其实我很难过。我一定很失败吧，我的课没有得到严肃的对待。对于我来说，挫败感远大于你们说我进度太快，向我询问课上的知识点。
我知道
再见啦诸位~
其实我只是擅长逞强而已……
想说的话有很多吧，但是一句话也挤不出来啊
其实我以前对于退役的人的博客还有游记一直是抱着一种嘲讽的心态看的,毕竟站着说话不腰疼嘛，感觉那些游记里的感情纯粹是在矫情,有些时候也会抱着一种毕竟你弱你活该的心理在看吧……
出了day2的考场之后发现自己可能明白了一点东西？（笑）
>或许那些博客的背后都是真实发生的故事吧
>但最后的游记我也不想写的那么
## 1. 题目大意
给定一个斐波那契数列，求第n项 %1000000007。
## 2.60分思路
递推，时间复杂度 $O(n)$ ，~~（肯定过不了，别抄啊）~~
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
long long a[93];
long long mod=1000000007;
int main
~~为什么全世界都说这是个物理题，不应该是一个数学题吗~，神犇的势能完全看不懂~
我们直接来看题，对于一个点，在计算时候横坐标和纵坐标互不影响，所以我们分开考虑。
我们记两个点假如横坐标相同，分别记纵坐标为a,b
于是，收益就是$b-a-1$
然后用 ~~当年写大视野鬼畜的思想~~ 来化一下式子，我们可以得到
$$b-a-1=(2*b-2*a-2)/2$$
$$~~
考虑$f[i]$表示状态为$i$的连边方案数，$g[i]$表示状态为$i$的能使得联通的连边方案数，$t[i]$表示状态为$i$使得不连通的方案数。
首先$f[i]$是比较好求的，就是$f[i]=\prod_{(u<v)\in k}(c[u][v]+1)$。
关于求$t[i]$，我们首先固定$i$中的一个点$p$，那么剩余的点要么与$p$联通，要么与$p$不连通。
假设和$p$联通的点集为$
[粉福](https://www.luogu.com.cn/problem/U590086)
:::info
谢谢
> [%%% 陈丹琦](https://www.sohu.com/a/454907115_629135)
普通分治中，从大问题划分出来的所有子问题都是互不相关的，每个子问题只解决它自己。而 cdq 分治主要解决那些前一个子问题对后一个子问题有一定影响的问题。
举个例子：现在有若干个操作，每个操作是查询或者修改。每个修改操作都独立对询问产生影响。
如果直接对于每个询问分别处理，我们对于每个询问
# 前置芝士： ST表，随机化
蒟蒻实在太菜，只能提供一种 ~~非正解~~ 的简单做法，通俗易懂，不用晦涩难懂的数学公式。
没看过题目的点[这里](https://www.luogu.com.cn/problem/P7164)。
巨佬的线段树维护凸包我不会，那就只好上骚操作了。
一看这道题目要求最值，我就感觉是st表了。
st表是很好维护的:
```
void init(){
for(
# A+B Problem c++题解
[这道题](https://www.luogu.com.cn/problem/P1001)主要考察对编程语言的了解。实际上不用学太多知识，只要是有一个良好的编程环境，加上一点点语法知识，这道题就能AC（通过）。
## 思路
**先说说这道题的思路**
题目意思就是说让我们写一个程序，计算两数相加的和并输出。所以我们要用到输入输出的东西：cin和cout。其
喜欢卡卡卡的小朋友你好啊，我是你的父亲。
你别一天到晚抬手放手就交交交交，死循环死循环，你是付费用户还是提供服务器啊这么会卡。
你好歹去外地再卡啊，像【删除数据】* 一样早点退役很难吗？还是你觉得洛谷评测及算变卡就显得你很牛逼？开小号就卡，在学校就卡，你咋不把洛谷收购了每天随便卡呢？
哥你是不是真的你卡卡评测及让我们学校 ip 被封就很有优越感是吧？
该交的就该交，这没问题，但你别一天到晚
### 题目描述
给你一个 $N\times N$ 的矩阵 $A$，其中每一项只会是 $0$ 或 $1$。
请找出有多少种不同的 $N$ 个点的树 $G$，使得：
$\forall 1\le i,j\le N,A_{i,j}=1$，当且仅当 $i=j$，或以结点 $1$ 为根时，$i$ 是 $j$ 的祖先或 $j$ 是 $i$ 的祖先。
两棵树不同，当且仅当存在两个结点 $i,j$，在其中
巨大[细节](https://www.luogu.com.cn/discuss/1118423)题！
---
考虑倒着做变成加边，有经典结论：
> 合并后新树的任意直径端点，必然是合并前某棵树中某条直径的端点。
:::::info[证明]
合并一定会增加一条边 $(u,v)$。
如果新的直径不过这条边，那么直径仍然是某棵树原本的直径，原命题必然成立。
如果经过这条边，那么就变成要证明
**7.19:**
下午2：00~4：00，坐高铁来到贵阳，租了辆车，开车前往酒店，开了个房间。
~~咕咕咕，肚子好饿~~
晚上5：00，开车去吃饭，和[dzl](https://www.luogu.com.cn/user/1638023)一起吃了贵阳的特色烧烤，没吃饱。~~dzl拍我丑照~~
**7.20:**
一觉睡到自然醒，下午1点开车前去报道，签到，领完衣服、书包，把东西都搬进宿
# 算法介绍
孙子定理是中国古代求解一次同余式方程组的方法。是数论中一个重要定理。又称中国余数定理。一元线性同余方程组问题最早可见于中国南北朝时期的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上
呵呵，我赌老师不会看
# P2827 [NOIP2016 提高组] 蚯蚓
[https://www.luogu.com.cn/problem/P2827](题目链接)
## 前言
太有意思的一道题目了！
虽然看上去十分简单，只需要模拟+单调队列维护，但这样效率太低，时间复杂度$O(mlog_2n)$，明显会爆炸（也不至于是一道蓝题）
## 基本思路
其实这题的还有隐藏的单调性，那就是对于一条蚯蚓来说：
*
# [新博客](https://www.cnblogs.com/BigSmall-En/)
目前很多功能还不完善，随笔也不是很多，会慢慢更新的。
要退役了，还是留点东西吧。
------------
已经退役了
>如果我们 几经转折 结局一样不动
>也才算 无愧这 分合
其实很早就想写了，但一直不知怎么起笔。这次新冠算是因祸得福吧，有足够多的时间，也是两百天前后。或许，是时候了？把我们的篇章展开，也算是某人所谓的【宣示主权】。那么，做好准备了么？迎接一个超长的，横跨数月的故事。
我们的故事。
---
还是叠甲。文笔很流水。抱歉无法将爱意全透过文字展示，那就交给时间和行动吧。
本文以时间顺序为主，
- 本文章历史些许久远， KaTeX 的错误不可避免。
### 首先，线段树是什么？
这！~~就是线段树~~！
### 这是正文
咳咳……线段树 是一种将 区间查询、区间修改、单点修改 的时间复杂度优化到 **log 级别**的 数据结构。
…… 别看我把
[菜鸡的 cnblogs](https://www.cnblogs.com/adam01)
受害者视角写一篇，从【数据删除】每一天干的抽象事迹开始描述，以下为了保护当事人隐私，名字用【数据删除】代替。
### 本人目前仍然没收到工资，预计是 600r/day，最晚期限是8.1（从 7.26 开始五个工作日内），发了之后删掉这句话。
7.13
抛开我坐了四个小时的无座来不谈，下来就给我安排活干，去讲评模拟赛，我午饭都还没吃，我还得谢谢他，你人还怪好的嘞。
不过当时我还觉得无所谓，毕
开坑。
7.12
因为在山东高密干了五天的苦力，喜提免费住酒店一晚上，然后创玩节，买到武陆逊。
在山东营白干了一天苦力之后，这是 12 号八点左右发生的一连串事情：
七点去超市买了个晚饭，然后准备去接水泡，结果弄完之后发现还没有水卡，然后 ABC 快开了，想着打完再去泡。结果大概七点四十左右开宿管大会，虽然没我事但是我还是去了，然后反手接到电话，说北京营临时缺人，让我连夜启程，然后我打 A
前置知识：[斜率优化（一）](https://www.luogu.com.cn/blog/bladrrxy/xie-lv-you-hua-yi-post), [CDQ分治](https://www.luogu.com.cn/blog/bladrrxy/cdq-fen-zhi)
斜率优化（一）中的斜率优化要求状态转移方程形如 $dp_i = \min/\max{y(j) - k(i) \times
### 刷表法
用刷表法求书上背包复杂度是正确的，具体来说是这个式子：
$$$
\sum_{i=1}^n \sum_{j=1}^{|son_i|} (\sum_{k=1}^{j-1} size_{son_{i,k}}) \times size_{son_{i,j}}
$$$
如何证明这个式子的答案是 $\Theta(n^2)$ 呢？
可以这么想，令 $p_i = \sum_{j=1}^{|
先看一道题：[P2365](https://www.luogu.com.cn/problem/P2365 "标题")
显然是DP。
设 $dp_i$ 表示做完前 $i$ 个任务的最短用时，则状态转移方程是：
$dp_i = \min_{0 \le j < i} \{dp_j + (\sum_{k = 1}^i t_k) \times (\sum_{k = j + 1}^i c_k) + S
[也许有更好的阅读体验](https://www.cnblogs.com/zheyuanxie/p/noip2022.html)
## 考前
给大家说一下我糟糕的模拟赛成绩：
$\operatorname{rk}29$
（总人数 $32$）
感觉 NOIP2022 无望了。
（最后再说一句，我的 CSP/S 太菜了，才 $165$ 分，无缘 NOIP 正式名额，只能去下午补题了）
#
暴力枚举激光的预期得分为$0$。
观察发现每个点$(x,y)$的价值是$gcd(x,y)^2$
其实要求的就是这个:
$\sum ^{N}_{i=1} \sum^{N}_{j=1} \varphi(gcd(i,j)^2)$
直接暴力求期望得分$30$分。
考虑反演：
$\sum ^{N}_{i=1} \sum^{N}_{j=1} \varphi(gcd(i,j)^2)$
$=\su
因为博客不支持回复，所以答疑帖牵走了。
大约比赛开始前$1.5$小时开帖
赛后可以点开的题解地址：
[分析矿洞](https://www.luogu.org/blog/zhoutb2333/luogu17691-yi-dao-shuo-xue-ti)
[洞穴遇险](https://www.luogu.org/blog/zhoutb2333/dong-xue-yu-xian-ti-xie)
# Part 1 前置芝士
## 1.1 数论函数
数论函数：对于函数 $f$，若满足定义域为正整数，则称这个函数为 **数论函数**。
加性函数：对于函数 $f$ 若满足 $\gcd(p,q)=1(p,q \in \mathbb N^+)$ 时 $f(pq)=f(p)+f(q)$，则称函数 $f$ 为 **加性函数。**
积性函数：对于函数 $f$ 若满足 $\gcd(p,q)=1(p,
更新：2022.9.21 修正代码。
前置知识：[割边](https://www.cnblogs.com/ljy-endl/p/11595161.html)
# 边双连通分量
### 概念
若一张无向连通图不存在桥（割边），则称它为“边双连通图”。
无向图的极大边双联通子图被称为“边双联通分量”，简记为“e-DCC”。
在上面的定义中，我们称一个双连通子图 $G'=(V',E')$ “极大
# 位运算
我们常见的进制有10进制，2进制，8进制等
而计算机用的进制是2进制
### 什么是2进制
逢二进一，只有0和1
而位运算是按2进制的每一项进行计算
有以下几种位运算符：
## 按位与： &
两个二进制按位与，那么会按位进行与操作
假设我们有2个二进制数字
| 1 | 0| 0 | 1 | 1 | 0 |
|:-:|:-:|:-:|:-:|:-:|:-:|
| 1
# B3846 [GESP样题 一级] 闰年求和
## 错误原因
把起点和终点算进去了
## 解题思路
把是闰年的年份累加，不用算起终点
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
long long n,m,sum=0;
cin>>n>>m;
for(int i=n+1;i<m;i++){
i
# 位运算
## 按位与
两个二进制数进行与运算（ & ），对应位上都为1则为1，否则为0
假设有两个二进制数进行与运算：
1 0 1 0 1 0
1 1 0 0 1 0
得到的结果为：1 0 0 0 1 0
## 按位或
两个二进制数进行或运算（ | ），对应位上只要有一个数为1则为1，只有都为0时才为0
假设有两个二进制数进行或运算：
1 0 1 0 1 0
1 1 0 0 1 0
得到
# 神奇的幻方
## 错因
没看清楚题目内容。
## 思路
先输入二维数组，再枚举每个条件并按条件来录入另一个
二维数组，最后输出另一个二维数组。
```
#include<bits/stdc++.h>
using namespace std;
long long n,f,a[10001],b[10001],ab[10001][10001],s=0;
int main(){
cin>>n;
Last updated at around 23:20(16:40) Jul 30(Jun 21) 2025.\
All characters: 11366(11403)
# Preface
[](好了，又来写小说了。这本小说将会按照**广度优先搜索**进行编写。文章的语言不仅限于中文。越往高维就越烧脑，请大家保管好脑子。)可能有人看到我在一些项之后标了一些括号。那些是将特殊文字更改成图片之后
> # Lead in
> 你睁开了眼，四周一片漆黑，前方可以看见隐约的光。\
你向前走去，前方的光变成了小点，接着逐渐放大，直到你看清上面的字你才停下。\
映入眼帘的是 `1+1=2`。\
你来不及看更多的信息，身体突然抽了一下，那串字符突然消失了。\
随后，你被吐出了这片空间。
# Article 1
你躺在床上，身体突然抽搐了一下。\
随后，你便茫然醒来。\
你坐起来，环顾四周，觉得家里好
### 这是一个即将 $A.F.O.$ 的蒟蒻将要写下的他的OI生涯
~~(虽然但是他要鸽了~~
# **P1847 轰炸II**
### 轰炸！！！
###
### **思路**
二维数组不能开，一维就够了
**解析代码**
```cpp
#include<bits/stdc++.h>
using namespace std;
int m,n,xa[2001],ya[2001],ans[2001];//用结构体也可以，只不过我认为数组更方便😁
int xb[2001],yb[200
## 按位与(&)
### 运算规则
两个二进制的数字(当然不用刻意将十进制转为二进制，因为电脑中存数时都会将十进制转为二进制)，按照对应的位置进行与运算，必须两个数字都为1，结果才为1，否则为0
### 举例
1100100 & 1010110=1000100
## 按位或(|)
### 运算规则
两个二进制的数字(同样不用人工转成二进制)，按照对应的位置进行或运算，如果存在1个及以上个1，结果
2022.7.28 更新：改正一处笔误。
# Tarjan 算法与割点
### 概念
给定无向图 $G=(V,E)$：
若对于 $x\in V$，从图中删去节点 $x$ 以及所有与 $x$ 关联的边之后，$G$ 分裂成两个或两个以上不相连的子图，则称 $x$ 为 $G$ 的**割点**。
一般无向图（不一定连通）的割点就是它的各个连通块的割点。
而由著名计算机科学家 Robert Ta
## B3846 [GESP样题 一级] 闰年求和
这道题就是判断一下一个数到另一个数中闰年的年份合，也就是for循环判断一下是否能被4整除并且不能被100整除或者能被400整除，然后cum+=i，最后输出sum。要注意不包含起始年份和终止年份。
```cpp
#include<bits/stdc++.h>
using namespace std;
long long n,m,sum;
int
# 警示：文章情节纯属虚构，所有出现的名字（无论是人名还是机构名、地名）均为情节需要编造，且仅为艺术创作，禁止私自转载、在现实生活中对号入座、造谣、模仿自伤自残行为、模仿欺凌及家暴行为等不当操作。若因上述行为造成任何不良影响，后果自行承担。
## 阅读提示：该内容含直接暴力描写，危险心理描写，可能引人不适，请谨慎选择观看。全文两万一千余字，请耐心观看！若感受到痛苦（无论是心理层面还是生理层面），