## Background
[去年省选](https://www.luogu.com.cn/article/r2gku3ia)标志着我 OI 新生涯的开始。今年省选标志着什么？
赛前思考：NOIP 二等奖如何在省选中翻盘？
答案：不需要翻盘，翻了也进不了。天哪这实在是太有道理了。
省选前一个月学习了网络流（是的你没看错这个时候才学的），封装了自己的 `mf_graph` 与 `mcf_gr
最近更新
**置顶公告：<http://8.136.99.126/contest/67ea76027aadac7b413b5258> 已经开赛，欢迎参加！**
---
欢迎来到 Sleeping Cup！这是一个以 Hydro 做框架搭建的网站，但又又不只是一个以 Hydro 做框架搭建的网站。在这里，我们将打破你对 OI 的传统认知：
- 与众不同的体验，从[试机题目](http://8.136.9
~~连E都挂掉的蒟蒻来水一波C题解~~
### 做法
#### $O(qk)$ 做法
直接用队列模拟。
#### $O(qn)$ 做法
先想到 $k$ 太大，又想到每移动 $n$ 次，序列是不会变得，所以可以用 $k$ 先对 $n$ 取模，即可优化到 $O(qn)$ 的时间复杂度，但依旧无法通过。
#### $O(q)$ 做法
容易想到操作 $3$ 是瓶颈，如果我们可以不去修改整个序列，而只用修改
## 目录
1. 简介
2. 浅析倍增
3. $ST$表算法
4. 题目
4.1. 1615 -- 【RMQ练习】奶牛排队（USACO 2007 January Gold）2591
## $1$ 简介
RMQ问题($Range\space Mininum/Maxinum\space Query$)，就是求一系列区间的最大/最小值(静态)，我们应该首选ST表算法，但在此之前，我们应该
寄
## 大事记
--------
### 鸦片战争（1840~1842）
--------
#### 背景
- 1838年底，道光帝派林则徐为钦差大臣，前往广东查禁鸦片
- 1839年6月3日至25日，收缴的鸦片在虎门海滩被当众销毁。虎门销烟是中国人民禁烟斗争的伟大胜利，显示了中华民族反抗外来侵略的坚强意志
#### 主要概括
- 1840年6月，鸦片战争爆发。英军于1841年强占香港岛。
匆匆的学了一下ST表，勉强算是跟上了
牧dalao喊我一起写去年CSP-S的T1
读题：
第一遍：没看懂
第二遍：还是没看懂
第三遍：哦哦哦转密码锁这下看懂了
再看数据范围，区区n=8直接暴力枚举
在只转一个的时候 针对第i个位置上的密码，可以转1~9，然后直接记录当前状态打个桶记录状态出现次数秒了
```cpp
zhuan1(int n){
for(int wei=1;wei
大概是个临时博客。到机房把这个放到 Github 博客里。
## CCPC 吉林站 游记
队员：日记 推车 HMY
天气很不错。昨天晚上大致计划了一下流程，反正开场和封榜期必然是我的，中间让队友分了吧。
大约 7:55 到的校门。碰到了 HMY 家长并被送到了目的地。/bx
接下来 20 分钟人就陆续来了。8:15 签了 rp++，顺便给推车签了一下。
推车出发晚，8:25 左右才到。
# 小狗让我写的
upd：2025-1-22（还有 5 天一周年）
以下用「🗡🖊」代指 ojs。
讲一下事情起因：🗡🖊 看不起 Pentiment 然后 Pentiment 揍了 🗡🖊，后面就是 🗡🖊 的父亲利用不知名因素威胁学校报复 Pentiment。不管 Pentiment 以前犯了什么事，对于这件事我的看法就是 🗡🖊 及其父亲的行为令人气愤，今天因为 🗡🖊 又
- Dilworth 定理：偏序集的最小链数等于反链的最长长度（DP）
- $d(ij)=\sum_{x \mid i}\sum_{y \mid j}[\gcd(x,y)=1]$（莫比乌斯反演）
- 平均值相关题目同时减去平均值
- 整除相关题目考虑作模意义下的运算
- C++ 实型数组 `memset` 结果与整型有别
- 若某个点双连通分量中存在一个奇环，则这个点双连通分量里的任意一个点都被包
谨以此纪念我的OI生涯。
# 前言
本来不想写游记的，但心里挺憋屈的，还是写了。
估计就是100pts了，八九不离十又是省二。
杨队依旧很稳，大家差不多都能1=。怎么说呢，虽然已经说服自己不要在意结果，但还是够我难受上一阵。
# -? Days
看了眼比赛文件夹，大概是从期中考试12号开始连着打模拟赛打到24号。除了一次炸了之外其他的还能看得过去。
18号中午去了济南。当时济南是整个
```cpp
从农民手中买来的破旧草帽，
已经过持有者的反复修补，
但依然无法拭去经年使用带来的磨损。
流浪生活并不容易，
好在它总会适时给予你一点儿无足轻重的惊喜。
```
费用提前计算 dp：似乎没什么好记的？
长剖优化 dp：当状态与深度有关且树边长为 $1$ 时可以使用。时空复杂度 $O(n^2) \rightarrow O(n)$。
重剖优化 dp：当 dp 状态设置为 $f_{i,j}$ 时且只需要记录部分状态时，先遍历重儿子，再遍历轻儿子，在用到的时候分配内存，合并完后释放内存。有值的 dp 数组一定全在 $rt -u$ 的链上，发现只会在走轻边时贡献
[喵。](https://www.wxmp3.com/mp3/a51344d512b0c8c40c899a202fa9ca8e.html)
---
[Top Cluster](https://qoj.ac/problem/8235?locale=zh-cn)
> * 题意：多次查询邻域点权 mex，其中**点权两两不同**。
>
> 二分答案，每次问 $\max_{i=0}^{mid}\ma
做法是概况标记队列。
举个例：两种标记，一种区间加，一种记历史和标记。
若标记队列为 $q=\{t_1,t_2,t_3,\mathsf{upd},t_4,\mathsf{upd},\mathsf{upd},\cdots\}$。设 $sum_i$ 表示前 $i$ 个标记中 $t$ 的和，设执行了前 $i$ 个标记后得到的区间和和历史和为 $s_i,hs_i$。
* $s_i=s_0+len\t
**【已经收入文章《[每日一技](/article/8xv5xva5)》。】**
**UPD 20241120: 添加了一道习题。**
前言：这篇文章包含两道题的题解，以及相同的一个 trick（我称其为“数值倍增法”）但是只投到了 CF1844G 上面。既然 1844 里有 844 作为子串，那么我是不是也要学习一下 844 的卷批精神呢。
## HDU 多校 2024 R10 1010
[更好的阅读体验](https://www.cnblogs.com/Tomori0505/p/18895696)
### 前言
以下均为流水账。
都说文章开头放个一言比较好，所以：
### Day -0x7f
去完重庆 CCPC 接着六月份又是四川 CCPC，
# CF208E 题解
这里提供一个比较劣的做法。
对于每次询问，求出 $x$ 的 $p$ 级表亲 $t$，则答案为 $t$ 的子树内与 $x$ 同深度的节点个数 $-1$。我们知道，一棵子树内的 dfs 序是连续的，考虑把询问拍成序列，用莫队处理。
时间复杂度：$\Theta(m\sqrt{n})$。
代码：
```cpp
#include<bits/stdc++.h>
using na
[CF1849E Max to the Right of Min](https://www.luogu.com.cn/problem/CF1849E)
套路的枚举区间最大值的位置，记为 $i$，预处理 $i$ 左边第一个比它大的位置 $l$、右边第一个比它大的位置 $r$。先处理有一个端点是 $i$（一定是右端点）的区间，有 $i - l - 1$ 个。
考虑一种方法：枚举左端点 $j$，$l
没有想到机房大佬再一个月前就卷过这个科技：[Youwike 大佬的博客](https://www.cnblogs.com/i209M/p/16335551.html)。
[载谭 Binomial Sum：多项式复合、插值与泰勒展开](https://www.luogu.com.cn/blog/EntropyIncreaser/zai-tan-binomial-sum-duo-xiang-shi-
```cpp
继承了来自父亲的神秘术，她能看破一切遮蔽。
在这双眼睛前，隐匿与伪装都是徒劳的。
借助这双眼睛，她寻回了失踪的小凯拉，
在农场雇工的惊呼中获得了“阿尔古斯”的名字——
就像那位传说中的百眼巨人，双眼明察秋毫。
然而，这种力量却带来了名为“夜盲症”的副作用。
但阿尔古斯毫不在意，甚至过度使用，
直到一阵辉光带来一道横亘眼上的伤疤。
从此，阿尔古斯可视物的眼睛仅剩一只。
```
c++自动化、病毒、游戏教程！
# 学前基础
在学习这几项非常牛的东西前，我们先要了解一些很重要的东西：
## 项目
这里，我用 Dev-c++ 编译器表示，首先，我们电击我们经常点击的“文件”，位于编译器左上角，电击整个目录最上面的“新建”，我们
[](https://badges.toozhao.com/stats/01JSX52ETYZ46SGGDCRPA4ZZZP "点击查看访问量统计 - badges.toozhao.com")
## 2025 江苏高
顺道推几个以前写的东西。
[一些（可能？）有用的东西 & 思想和二级结论](https://www.luogu.com.cn/article/xz8gvlhk)（还在更）
[【洛谷日报 #427】浅谈网络流的各种建模技巧](https://www.luogu.com/article/k2hh2bok)
### 一些没用的话
树树题感觉是做起来最舒服的题啊！
树结构无论在 OI 中还是在现
## 前情提要
我的 `rp` 被 xixiyan 吃光了， `CSP-J2` 狂挂 `0+30+70+[0,60]pts`，`CSP-S2` 狂挂 `0+100+[20,50]+0pts`。
## Day ?
蔬菜拿上手机，登录了机房电脑。
## Day -2
蔬菜又摸鱼。
打 S- 赛，但没有任何大样例。
T1 签到题。**+100pts.**
T3 先猜结论，开始对拍。
拍
`#define Frielen CuSO4`
前几天都学文化课去了，没啥东西，可以从中间开始。
### Day 1（1.13）
文化课还在肆虐，啥都没干。
### Day 2
文化课还在肆虐，啥都没干。
### Day 3
碰到了牢 JK。%%%。%%%。%%%。\
`cccccccccccccccccccccccccccccccccccccorz`。
然后中午就碰到了这个：
!
### [$\color{red}{T157981 比赛【2020-11-29NOIP模拟赛】}$](https://www.luogu.com.cn/problem/T157981)
不得不说，这题真的恶心。
主要恶心在$3$个方面，一是读入，二是大模拟$+$搜索，三是纯模拟$+$搜索会$\color{red}{TLE}$
主要思路如下：
因为题总共才$1
如果你会二维单调队列（不知道为啥要叫这个名字，见 P2216），它的思想对本题很有帮助。
## 思路
最外层枚举箱子的行数 $o$，处理出 $b$ 数组：
$$
b[i][j]=\min\limits_{k=0}^{o-1}a[i+k][j]
$$
你应当预处理出数组 $maxn$，$maxn[j]$ 表示 $o\times j$ 的矩形中的最小值最大是多少，即不考虑水面上涨时 $o\ti
C++ 是许多信息学竞赛选手最熟悉的编程语言。日常训练中，我们可能只用到循环、数组这些基础功能，但这位朝夕相处的"老朋友"，其实藏着更多值得探索的奥秘。
也许你曾见过题解中神奇的语法"黑科技"，也许你被未定义行为导致的"玄学问题"困扰过，也许你面对突如其来的编译错误百思不得其解...
掌握这些知识，不会让你在赛场多拿几分，但能让你更加了解这个朝夕相处的代码伙伴。它们或许能帮你理解那些精妙的语言
https://b23.tv/BV1ZC411z7Sb
https://v.douyin.com/iNjE1nD4/
很巧妙的一道题，做法是 dp 套 dp，why？
很容易可以想到这样的状态设计，```f[i][j][p]```代表走到格子 $(i,j)$，并且已经后退了 $p$ 步。
直接前进很好说：
```
f[i][j][p]=f[i-1][j][p]+f[i][j-1][p]
```
同样的做法可以构造出来后退的转移方程：
```
f[i][j][p]=f[i+1][j][k+1]+f[i][j+1
[ikrvxt's blog](https://blog.csdn.net/Emm_Titan/article/details/114750814)
设普通矩阵乘法的 op1 是乘法，op2 是加法。
因为 op1 对 op2 满足分配律，所以整个矩阵乘法具有结合律。
比如 P6021：
我们把矩阵乘法的 op1 转化为加法，op2 转化为取min。
为了赶时间有亿些证明没写，需要的话查看下面的链接
<https://blog.csdn.net/zxyoi_dreamer/article/details/85195819>
<https://www.luogu.com.cn/blog/wengweijie/solution-p5668>
## 目录
1. 0 次同余
2. 1 次同余
3. 2 次同余 / 剩余
1. $ax^2+
~~vp 时写出来的抽象东西，大家当乐子看就好。~~
## 思路
容易想到
```cpp
memset(f,-1,sizeof f);
f[h][m]=0;
rep(i,1,n){
cin>>a>>b;
dep(j,h,0) dep(k,m,0){
if(f[j][k]==i-1&&(j>=a||k>=b)){
# Day -?
初赛 J 96,S 89。
停课。在停课的过程中，经过艰苦训练，提升了自己的麻将水平和军事指挥能力。
# Day 0
## CSP-J
开局顺利在前两题卡了。T2 想了一个复杂的贪心，从前往后扫，如果当前位置的费用是最小的，就把上一个买油的位置撤销一部分。调了接近 1h。
T3 大模拟，果断跳了。
T4 很快写了一个改造 Dijkstra 的做法，简单证了一下。
线段树，是一种可以在 $O(\log n)$ 的时间复杂度内处理可合并性信息的区间修改与区间查询的数据结构。
> [P3372](https://www.luogu.com.cn/problem/P3372)：有一个长度为 $n$ 的数列 $a$，要支持将一段区间的每一个数加上 $k$，或者查询一段区间的和。$n \le 10^5$。
### 基本结构
以模板为例，线段树是一种二叉树的结构，
```
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int b[100005];
int dp[3][100005];
signed main()
{
int n=0;
while(cin>>a[++n]);n--;
for(int i=1;i<=n;i++) b[i]=a[i];
对于给定**两**个字符串 $a$ 和 $b$，得到 $a,b$ 的扩展串为 $A,B$（扩展串即题目中的定义），那么我们很容易想到若 $A,B$ 的第 $i$ 个位置上有空格，则意味着这一位置上的字符将作废，从而变成添加空格的费用。
$a:\verb!cmc!$
$b:\verb!snmn!$
扩展后可以得到 （$?$ 表示空格）
$A :\verb!?cmc!$
$B :\ver
[$\color{#64B431}\texttt{T1 立夏 Author:Syadouhayami}$](https://www.luogu.com.cn/blog/blog10086001/glr-r4-li-xia-sol)
[$\color{#81B13A}\texttt{T2 小满 Author:Azazel}$](https://www.luogu.com.cn/blog/1-2
在中考前应该会记录很多内容，应该会类似于日记吧。
## Day -111(2025.03.01)
省选Day1
## Day -110(2025.03.02)
省选Day2
为了省选旷了好几节课，这导致下一周处于水深火热之中
似乎考了100+20+28+56+12+0=216分，但是后来发现挂飞了，可能只有190分甚至更低。似乎d2t1和d2t2暴力全都挂了。d2t1挂到了$[36,4
# CSP2021 游记
### CSP-S1 Day -1
星期五，第一次到师大附中机房讲课。
在之前一周了解了一下现役师附 OIer 的情况，决定从 DP 开始讲。讲了[数字三角形](https://www.luogu.com.cn/problem/P1216)和[乌龟棋](https://www.luogu.com.cn/problem/P1541)两道经典题，但忘了讲代码实现，下次课
### Description
Alice 和 Bob 手中各有 $n$ 张牌 $1,2,...,n$，从 Alice 开始轮流出牌，如果一个人出牌后场上所有的牌之和能被 $m$ 整除，则出牌者输；如果两人牌都出完后双方都未输，则 Alice 胜。问当双方都以最优策略出牌时，谁能获胜。
### Solution
显然地，当 Alice 和 Bob 手中的牌都 $\ge 2$ 时，牌局并不会结
[我的博客](https://www.yijan.co/scoi-2020-you-ji/)。可能下次发博客得等到很久之后的联赛了。
## Day 0
Day 0 居然放假。。在家里打了下各种多项式板子认真背了下 ppt 上的经典套路。。
据说要考多项式，字符串和计算几何？
考到计算几何就放弃吧（？）大概写了下凸包和半平面交。。反正几何算是知识盲区了。。不过按照前几年的惯例SC出几何多半全
不难发现那个 $\sum_{i=1}^{m-1} c_i$ 就等于序列长度。所以考虑对于每种元素单独计算答案。
因为非 $1$ 的元素还会有一个奇怪的“出现时间”，即第一次在序列里出现的位置，不好算，所以考虑先算 $1$ 的答案。
设 $f_i$ 表示序列长度为 $i$ 的时候，$1$ 的期望出现次数。则：
$$
f_{i+1}=\dfrac{p}{100}f_i+\dfrac{100-p}
# UOJ216 Jakarta Skyscrapers
### 思考
每个数肯定能写成若干数加起来，再减去若干数
凑二进制？余数？
### 题解
真是二进制，不过有更重要的部分，哎，$\gcd$ 啊
$c$ 不是 $\gcd(a,b)$ 的倍数肯定无解了。考虑先凑出 $g=\gcd(a,b)$
耻辱性的大败
越学越菜是吧？
不好评价我自己
我要你永远记住这种无力感
###### 前前前前前前前前前前前前前前前前前前前前前前前前前前前前前前前前前前前前前前排提示：适龄-18岁+，本文更新速度为SPD字每天，那么有：
$$
SPD=\lim_{n→0}/\lim_{n→∞}
$$
对于我这样一位弱省弱校的选手，往年的学习和比赛都基本是一个人。
**或许我想要的并不是金牌，而只是与同学一起学习，比赛的快乐时光**
**或许每一次的落选，每一次试图翻盘，每一次别离，都是选拔中的另一重考验**
**我想把这其中的快乐，继续传递下去**
**离别终会相见**
时间按胸牌上的计算（即2024-1-29为Day1，2-5为Day8，之前没有Day0直接调至Day-1）
部分
**做题策略**：先水平移动到足够大的半径 $r$，使得目标点 $(233,666)$ 位于圆周上；
然后沿圆周移动所需角度 $\theta=\operatorname{atan}2(666,233)$；
总距离=水平移动距离 $(r)+$ 圆周移动距离 $(r\theta)$；
最优解出现在 $r=\sqrt{233²+666²}$ 时。
**计算**：半径 $r=\sqrt{233²+
喵喵喵~
---
### abc355
[](https://atcoder.jp/contests/abc355/standings?watching=little__bug)
A 水，判断是否出现加上一坨 if，过。
B 水，但是题意看了好几遍，才看懂是求 $i$，使得 $c_i
### Meaning
在二维平面内，有位置不同且不存在三点共线的 $R$ 个红点和 $B$ 个黑点，判断是否能用一些互不相交的线段连接每一个点，使得每条线段的两端都分别是黑点和白点。
### Solution
当 $R\ne{B}$ 时，显然无法实现红点与黑点的两两组合，故题干所述的情况一定不存在。
当 $R=B$ 时，我们考虑一种连线的方式（事先给所有红点带上 $1$ 的权值，给
以下这份数学笔记是笔者从 2023 年 7 月开始记录至现在的，`.md` 源文件达到了 $232$ KB（ 比上次更新增加了 $80$ KB ）。目前笔者高二，所学知识尚未完善，部分知识点未齐全，请读者见谅。
以下内容可能加载时间较长，请耐心等待。并且大约消耗 $1\sim 2$ GB 的内存。~~可以当作电脑性能测试了哈哈哈~~
可能存在图片加载不出来的情况或者其他意见建议，请私聊告知我，
[设定集](https://www.luogu.com.cn/article/zpnyawlz)
**经过协商，我与歌者决定各自运营一本章二**
-------------------------------
无边无际的黑暗中，身着红衣的女孩睁开了双眼。她看了看四周，没有任何有异常的地方。“我是谁？这里是哪里？我该做什么？”，她努力的回想着，但却想不起任何事情，似乎回想本身也只是一个习惯性的
### NOIP2022
简记：秒了T1，被T2橄榄，会T3但是没时间仔细查错了。
简评：情理之中，意料之外。
### WC2023
简记：没写文件。
简评：没有评价。
### 省选2023
简记：D1没想出来T2，D2没想出来T1，D2T2会了但写不动，D2还挂没了。
简评：面对强于自己水平的考试在战术选择和风险把控上没有熟练。
### THUSC2023
简记：算法场被T2
打得依托钩十。
### Day1
T1.平方显然是秒了，然后因为我三次方优化到平方是使用的记录左右端点最小 P 状态长度，所以就一直在想如何用数据结构维护这个东西。四十五分钟时胡了一个 类 dijkstra 式松弛的做法，花了一个小时写了这玩意，。。然后发现假了。于是赶紧写了个 73 跑路了。
剩余时间只有一个半小时了。先写了个 T2 高斯消元，。。。发现有自由元会
如你所见，当你看到这条专栏时，我正在被挂上“作弊者”的标签。
事情是这样的：上周时，洛谷举办了一场6月的基础赛，而YL中学机房的全体OIer几乎全数参加，~~唯一一名年仅初三的我也不例外~~。而悲剧则出现在[T7](https://www.luogu.com.cn/problem/T618284?contestId=251050)这道题上，当时在考场上我们机房里的~~大牛~~们都在想方设法地做出
1.
2.
3.
参考了 maspy 的题解。
感觉这个容斥非常厉害，所以写篇题解记录一下。
先转化为若干个点，分成三类，求把它们连成若干个环，不存在只有第一或二类点的环的方案数。
假设这三类点分别有 $N_1,N_2,N_3$ 个，考虑容斥。
我们先钦定一些不合法的环，假设全 $1$ 的环钦定了 $k_1$ 个，全 $2$ 的钦定了 $k_2$ 个，先考虑容斥系数，为 $(-1)^{k_1+k_2}$。
## Day -1
大家 RP++！
自从春测 T3 RE 调不出来后整个人都不好了。
解决方法：首先，使用 noilinux2！（本省 windows 没有 C++14/fn）。IDE 推荐使用 Geany。（优点：开箱即用。缺点：~~虚拟机慢~~，warning 和 error 颜色一样，无一键编译运行（推荐把 compile 的指令改成 build 中的内容））
编译选项加入设为 `
你还知道你在做工业垃圾啊？———题记
## 2025.6 做题记录
但是从 $\text{2025.5.22}$ 开始记录的。
### 326 uoj889（坐标变换，猫树）
贪心，无可救药。考虑强制钦定每一步的 $y\to y+1$，那么对于第 $i$ 行整体平移 $i-1$ 个单位，也就是做 $(x,y)\to (x,x+y-1)$，此时每一步就是向右或者向右下走一步。此时步数就是 $
首先只有把一个数二进制表示下某一位的 $0$ 补成 $1$ 才对答案有贡献。假设这一位是第 $i$ 位（钦定最低位是第 $0$ 位），那么要把这一位补成 $1$，$k$ 需要减掉 $2^i$。 我们贪心地考虑，肯定是先让从低位向高位看，第一个有 $0$ 的位置最低的这个数进行操作才是更优的。根据这个建立一个优先队列，按照每个数最低位的 $0$ 的所在位子升序排序。
考场上看到要求每个数最低位的
# Day -7
听到了大湾区编程比赛进复赛的消息，好开心！
# Day -6
搞了场SGOI2025小学组模拟赛。（已结束）
# Day -2
妈妈说我可以带电脑去，开心！😊可以参加abc410了!
# Day -1
今日洛谷打卡大吉。
老师给我免了点作业，还鼓励了我，开心😊！活力满满，奔赴比赛！（不过听说台风“蝴蝶”要登陆了……）
本文将用 ``[dollar]`` 代替美元符号
省流：寄了，但没有完全寄
## Day -?? ~ Day -2
停课，但没有完全停
每天没有上午模拟赛的时间，只有下午改题的时间
这几天有好几道题由于能力限制没改出来
感觉自己越来越菜了，怎么办？
10.15 vp 了去年 luogu 的 CSP 模拟赛，得到了 260pts 的成绩
（鲜花：以为 CSP 是 4.5h，所以将比赛
# 专业MC！！！，支持互注~~
------------
------------
MC~~十年~~八年老玩家
~~关于我不讨厌迷你这件事~~
_支持一起玩MC……_
## 一起玩私聊。。
### 微信互加私聊😊
# 就这些了，~~我手懒，不想写了~~
# 蓝名了！
## 哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈
~~我很不开心~~
upd in 2025/1/11：真太监了
世界观架空，可能会坑。
---
慕贤中学，坐落在幻城某个偏僻的角落，但却是幻城中人人都想要进入的“天堂”。高居不下的升学率、强大的师资力量、丰富多样的社团……就算只拿出其中一样，也足够令人憧憬了。
他们的“故事”，便从此处开始……
10月1日，星期五，慕贤中学高一（1）班。
李羽柯坐在教室靠后的位置，趁着午练的空档，似是玩世不恭般的看着学校明令
发在灌水区
736073已经发了（七八遍）
祝你们成功（滑稽）
___
好了搞正事。~~虽然也不是~~
大概昨天下午（1.24)，在wfyz的机房翻帖子的时候看到一篇标题是“水友小队（做题用的）可以加入了”的帖子，点进去一看就是个宣团。
当时~~闲的没事干~~觉得这样做影响洛谷社区风气，所以就直接举报了，也删除了。
没想到那个家伙又连续发了好几遍。
标题如下（并不是全部的帖子，有些可
# 十年OI一场空，
# 不开long long见祖宗。
#### 缺省源
```cpp
#define g(i,j,k) for(int i=j;i<=k;--i)
```
#### 虚树
我不排序。
```cpp
for(int x:p[o])v[a[++s]=x]=1;
a[++s]=b[l=1]=r[t=1]=1;
f(i,1,s){
c=T.lca(a[i],b[l]);
if(c!=b[l]){
for
# 思路
其实这一道题可以利用一个小结论：
**如果出现最长下降子序列长度超过 2 的，一定不能分成两个严格递增的子序列。**
其实这一个小结论的证明方法很简单，就是小学学过的**鸽巢原理（即抽屉原理）**。这个原理告诉我们 **3 个下降的数字，放到两个盒子之中一定会有一个盒子是一定下降。**
~~虽然听起来有点绕哈，但多读几遍就看懂了。~~
# 实现
由上面的小结论可以知道，我们只需
### 地点：东莞中学松山湖学校
## Day 0
在高中部集合，在校门口被乱停车堵了半个小时 (emmm)
出门后经过两个半小时车程终于到了，在酒店开了房以后就去比赛的中学蹭晚饭
回酒店后就一直和同学看电视到11点，随后就上床睡觉了。
希望明天的题不要太难......
## Day 1
一觉起来下楼吃酒店的早餐，可比学校的好吃多了。
来到学校，上午是讲座，讲构造，开始还挺认真的，到后
## 一、踩到 TNT
```cpp
#include<iostream>
#include<bits/stdc++.h>
#include<windows.h>
using namespace std;
int main()
{
system("mode con cols=200 lines=25");
while(1)
for(int i=1;i<=30;i++)
{
for(i
爆照了兄弟们
哇哈哈哈哈哈哈，开一瓶汽水庆祝一下
写在前面：本文都是实话，评论区的[大神不要批了](https://www.luogu.me/article/ta19adre#)。
这个赛季真得摆烂了，初赛估分 $61$ 分，本以为能够稳过初赛的，结果实际 $59$ 分，分数线 $58$ 分，卡线过。
复赛之前，状态一直很差，感觉学的东西都忘光了，大部分时间都在摆烂，只能靠临时抱佛脚了。
复赛那一天上午，整个人昏昏沉沉，吃完午饭才打起了精神
# Day 0
zxz和lqs迟到了20min我妈把我背包里的电脑拿出来了我的手机忘记充电只有30%车在学校前门和后门都被堵着卡了30min还有奇怪的女人给我们拍照照车上zxz和我互相拍照晚上到酒店半天没有一个人下来集合safari插件用不了登不了florr大号只能玩小号7点多去shh中学报道并吃饭回去酒店发现小号练度极低于是开始找可以打开开发者工具的手机浏览器找到的没有一个能用的我直接
怎么你
Z-function (因该首先想到的不是它吧)
```cpp
#include<bits/stdc++.h>
using namespace std;
char s[111111];
int l,r,i,j,k,cnt,n,z[111111],ans[111111];
pair<int,int> res[111111];
int main(){
scanf("%s",s);
由费马小定理可得 $a$ 在模 $m$ 意义下的逆元为 $a^{m-2} \bmod m$。写个暴力即可。
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=2146516019;
ll qpow(ll n,ll m){
ll res=1;
while(m)
# 总结：全是细节
## T618144 迷宫之输出最短步数
### 错误原因
1. 在找不到路时没有输出-1
2. 没有将起点标记为走过
## T618146 统计线路
### 错误原因
1. 没有在找到宝藏后撤回标记
2. 没有将起点标记为走过
## T618168 全排列问题
### 错误原因
1. 数组开小了
## T619294 二分查找左侧边界
### 错误原因
1. 数组开小了
##
六年级小蒟蒻参加 $2025$ 年的粤港澳大湾区小学组比赛的游记。
# 初赛
## 初赛 Day $\bf-3$
拿去年 CSP-J 的初赛题目来练习，因为难度差不多，考的内容也差不多。
拿了个 $78.5$ 分。（小数点前的数怎么这么那个㖏）
今天做完这些题，突
大家好，我是 CQ-C2024 蒟蒻 CJH。
## 题意
“幸运号码”是十进制表示中只包含数字 $6$ 和 $8$ 的那些号码。
求：在 $[l,r]$ 中有多少个数能被“幸运号码”整除。
## 分析思路
**注意：此题解非正解，如果要寻求正解请查看其他题解。**
我这里提供另外一种相对于题解区中唯一一篇分块打标中不那么优雅的一种方法（空间换时间），事实证明，此方法和我其他同学（正解
傻逼 sxz 给志愿者发凳子都不给我们寝室发凳子？我们寝室周围几乎没有寝室有 $>2$ 个凳子。大家只能在床上或奇怪物体上坐着。
傻逼组题人怎么敢 T1 限制那么紧 T3 限制那么松的，界的松紧取决于屁眼子的松紧吗？
压线 Au。喜提 Au 的相对原子质量。
[原题](https://atcoder.jp/contests/abc410/tasks/abc410_e)
读完题目之后还以为是贪心，但是这么简单放到 e 题又不是太合适，所以重新思考一下：击败怪物有两种方式（消耗体力或者魔力），并且要让击败的怪物数量最大化，那不就是 dp 吗？
定义数组 $dp$，那么 $dp[i]$ 表示剩余体力为 $i$ 时消耗的最小魔力，由于我们的 $dp$ 数组
嗨嗨嗨，飞竹小课堂限时回归！第 $18$ 课！
今天我们学船新算法-线段树！
首先，我们要知道一个点：
树状数组能实现的，线段树一定能实现。
线段树能实现的，树状数组不一定能实现。
但是，既然他比树状数组更优，那么代码复杂度......
比如炖肉松花了一个小时调线段树还没调出来。
话不多说，进入正题：
树状数组的原理是通过二进制拆解，而线段树是分治的思想。
我
### 统计
共计1923词（typora显示）
### Day -??
初赛日
一大早看见了zxy、zkx、ycy、zjs等熟悉的面孔
8:30考试，8:00就进了考场
由于姓氏优势，来到了离出入口最近的考场
照例先上个厕所
话说 j 组考牛顿迭代？
提前交了卷，发现zkx、ycy也在讨论
>ycy：那道判断题算出来是448，题目是44
## P1868题意概述
从 $n$ 个 $[l_i,r_i]$ 的区间中任取若干个互不相交区间
使得这些区间的长度之和最大
## 初步思路分析
很显然：这是一道动态规划的题目
双倍经验：[P2439](https://www.luogu.com.cn/problem/P2439)
### 状态定义及其转移
定义 $f_i$ 为前 $i$ 个格子最多能吃到的牧草
显然 $f$ 序
## generals.io
排序方式：优先完美 FFA，然后根据幽默程度。
- https://generals.io/replays/bfJ4Wmhss?p=Catgirls **七杀**，完美 FFA。
- https://generals.io/replays/iYLsaOwiB?p=Catgirls **七杀**
- https://generals.io/replays/r1Y
# 游记
## 前言
- 或许题目可以叫 (其他 and THUSC 游记 and WC 游记) with 鲜花？
- ~~这什么人啊，咕这么久才写游记~~
## 01/20
发现 (THU) WC 快到了，自己还在耽误这上午的模拟赛
~~再加上实在不想周练和写 whk 作业~~
于是。。。
写在前面：本文都是实话，评论区的大神不要批了。
这个赛季真得摆烂了，初赛估分 $61$ 分，本以为能够稳过初赛的，结果实际 $59$ 分，分数线 $58$ 分，卡线过。
复赛之前，状态一直很差，感觉学的东西都忘光了，大部分时间都在摆烂，只能靠临时抱佛脚了。
复赛那一天上午，整个人昏昏沉沉，吃完午饭才打起了精神，吃了点零食压压惊。
进了考场，希望这次考的不要太烂吧。
看了第一题，感觉像是神
## 形式化题意
给定一个网格，其中有 $n$ 个点（点不会重合），可以移动其中一个点到任意不与其它点重合的位置，使得满足包含这 $n$ 个点的矩形面积最小。
可以维护两个 `multiset`（注意不能是 `set`），枚举删掉每一条边时的横纵坐标极差的乘积，求其最小值。
```cpp
#include <bits/stdc++.h>
#define int long long
using n
浪费我时间。
13:30 左右来到考场，坐在座位上摆烂。
14:00 开考，先看 T1，一眼 bfs，秒了。
14:10 看 T2，发现是更水的数组计数，发现不对劲了。
14:15 看 T3，居然是树上路径的长度奇偶性，甚至直接 $O(n)$ 就行了，不是，都是什么题目呀！
14:25 看 T4，有点难度，但不多，想几下之后发现线段树可以乱做，秒了。
15:00 写完 T4 没事干了。
感觉烂完了。但是还没有完全烂完。
出分了，兄弟。为什么我赢完了。
---
第一天语文。文言文是能会的东西吗。蒙了一下。好像是全对了。红楼梦没看。现代文阅读。鲁迅。感觉两个六分大题能一共给我六分就挺不错的。后面忘了。作文不会写，写了一坨石，用比较好看的字掩盖一下我是个文盲的事实。
生物感觉还不差啊，和生竞同学对了一下问题不大。但是 19 全是概念背诵题我怎么写。感觉仍有上 80 希望。
英
坐标JS，第一次参加CSP。
作为一名优秀的，只学了一年C++的蒟蒻，J组应当以冲击200分的目标为主，T3和T4可以随缘处置。
在大巴车上一群巨佬四散开来的金色光芒之中，我显得那么不起眼，突然感觉一切努力都是虚无......
### 于是摸鱼就这样开始了。
来到南京的路上：狂玩游戏。
住在酒店的时间里：打羽毛球 $+$ 狂玩游戏 $+$ 下棋。
比赛前：带了一包饿货架 $+$ 准考证
# 排列DP
$a_1$到$a_n$，n个数，写下来，就是排列
一般问的是：所有排列中，满足某个要求的排列个数。
## 题
### 题面
1~n所有排列中，逆序对个数为偶数的有多少个？
### 一般思路
把n个数按从小到大或从大到小插入。
### 此题思路
按从小到大插入。
${f_i}_j$代表当前已经把$1$~$i$插入了，逆序对个数为j的方案数为多少。
已插入到$i$，
AD和空格移动，E打开商店，Q退出商店。
Z使用技能炸弹，X使用道具炸弹（需要购买）
OP对应左右普攻。
```cpp
#include<bits/stdc++.h>
#include<windows.h>
#define RESET "\033[0m"
#define BLACK "\033[30m"
#define RED "\033[31m"
#define GREEN "\03
### 前三周
直接被封在学校，还变成了低贱尖。
### 赛前三天
跑路去酒店，服了一天。
### 赛前两天
火题场，在本校 OJ 上交题被诅咒了再次痛失阿克.
### 赛前一天
失去信心赛，直接白蓝。
发现被诈骗了。
睡了一天。
### 开赛
发现 T1 是我之前出的[某题](https://www.luogu.com.cn/problem/U216743)的弱化版，当时憋
- 出题人题解，写于出题后两个月。
不知道出题的时候发了什么电弄出来了这道题。可能是水电吧。
- 但说实话[黯洃銫](https://backrooms-wiki-cn.wikidot.com/th3-sh4dy-gr3y)这篇文真的好看。
- 本题数据很水，但是懒得动了。
---
其实是一个很显然的分层图最短路。观察到 $1 \le d \le 10$，于是分层。
分完层以后正常跑
- 出题人题解。
- 听 Rubia 的时候想出来的一道题，本来是一道自以为有一点点难度的图论题，然后被 [yuruilin2026](https://www.luogu.com.cn/user/1294410) 一眼了。
- 还有，能请[某位出数据的同学](https://www.luogu.com.cn/user/1275540)解释一下你的测试点 #47 是怎么回事吗？谢谢~
---
观察
### 通知
暂无
### 第一回 梦的开始
落叶村的广场上，村长正在宣布着事情：“今年，盟自一宗的招生将在一个星期后举行，前几年，我们村子一个能选上的人都没有，但是今年我们村出了一个金细菌，他用了一年时间，修炼到了武者六星，已经超过了武者五星的标准！”
台下响起一阵掌声，一个金发少年站在人群中，下巴微微仰起，双手环抱在胸前，嘴角不经意间向上翘起，随后他挑衅般地望向身后一位黑发白色瞳孔的
临时去年级部报名，年级部表示不知情 /kx。
时间：$5.15$ 下午，一试 $1:30$ ~ $2:50$，二试 $3:10$ ~ $6:00$。
反正是退役选手去别的竞赛玩一玩，也没报什么进高联的希望。
upd：竟然给到高联名额了 /kx
看以往一试卷子一堆圆锥曲线解析几何，发现我题都读不懂，周六晚上拿选必一数学恶补了一阵。周日上午按照 zyb 的说法恶补了椭圆、双曲线、抛物线标准方程
# $\color{red}{First :}$并查集个人简介
并查集，字Union-Find，数据结构，简单，代表作[【模板】并查集](https://www.luogu.com.cn/problem/P3367), [亲戚](https://www.luogu.com.cn/problem/P1551)等
# $\color{blue}{Second:}$并查集之中文代码
```cpp
#in
[原题传送门](https://dmoj.ca/problem/ccc15s4)
## 题意简述
题目非常清楚。
船从 $A$ 到 $B$，船体厚 $K$ 厘米。群岛有 $N$ 岛 $M$ 航线，每条航线连两岛，耗时 $t_i$、磨损 $h_i$。要找总磨损小于 $K$ 的最短耗时路线，到不了就输出 - 1。
即有 $N$ 个点，$M$ 条无向边，每条边都有权值 $t_i$ 和 $h_i$，
这篇文章主要介绍**拓展域并查集**。
拓展域并查集，主要用于一种状态表示无法解决问题的题目。例如本题，一个开关有两种状态，用和不用。
本文主要介绍二倍拓展域的拓展域并查集。
## 什么是拓展域并查集？
拓展域并查集是一种数据结构，用于解决具有多个相互关系集合的问题。它是传统并查集的扩展，能够处理集合间的不同关系，如相互排斥或相互独立的关系。
## 拓展域并查集有什么用？
只看定义是不可
```cpp
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <map>
#include <limits>
#include <memory>
using namespace std;
// 卡牌基
$$
\dfrac{cx+d}{(x-a)(x-b)}=\dfrac{(ac+d)/(a-b)}{x-a}+\dfrac{(bc+d)/(b-a)}{x-b}
$$
考虑如何计算 $\dfrac{P}{Q}=\sum \dfrac{P_i}{Q_i}$，其中 $|P|<|Q|,Q_i=(1-a_ix)^{k_i},Q=\prod Q_i,a_i$ 两两不同。
考虑 CRT 的过程，$P_i=\
[题目传送门](https://www.luogu.com.cn/problem/P8816)
这道题很有意思，做法还蛮多的。
## 深搜（无优化）
我们可以先回归朴素，直接按题意去对每一个起点深搜，找到所有合法的点列路径。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define N 505
int n,p,ans;
bits
发现bug请在此博客下回复。
[下载链接](https://www.luogu.com.cn/blog/581015/you-xi-gong-kai-xia-zai)
尚未完工。
## 游戏性质
##### upd: 24/7/3 13:21
这是由 CYC 开发的一款回合制的游戏。其原型为校内/外有所流传的“波波拳”（BBQ），或更加广为人知的“西部牛仔”。
然而作为电脑版，你的交互速度显然会显著下降。为了弥补这一不可避免的改变带来的游戏体验的下降，我将会以多种方式来增强其可玩性。包括但不限于引用部分允许二创的游戏中的元素（例如 Genshin Imp
# 闲话
我在学校跟同桌声称我已经会了这类题的通用解法。
某同学听到之后说：你敢不敢跟我举行构造大战？
我当然敢！
感谢这位同学提供的若干题目。
# 前言
在高中数学中，有这么一类题目，它给出 $f
(x)$ 与其导数 $f'(x)$ 之间的不等关系（如 $f(x)>f'(x)$），我们需要把这个不等式改写成 $g'(x)>0$ 或 $g'(x)<0$ 的形式，然后解决一些问题。
在
[备份1](https://www.luogu.com.cn/article/k8ma4kn4)
[备份2](https://www.luogu.com.cn/article/jcz9w07g)
# ABC409 赛后
## 排行榜
## 输赢
- 1 组：lw（
写std前：就是黄题的难度嘛
写std后：就是 上位~~绿~~黄嘛QWQ
虽然题目说有100个变量，但其实最多只有26个。
## 正片
>0.输入
>先把数字输进`in[]`，并定义`zhii`为它的指针，每执行一次`cin`就把它+1，代表抛弃这个数。
>
>```cpp
>cin>>n;
> for(int i=1;i<=n;i++) cin>>in[i];
>int zhii=1
## Day -1
先把游记放这。
其实这是第一次打NOIP。
前年没报提高，去年变成了春测。
要寄了，一堆板子不太会敲。
## Day 0
自由复习日，但我在做蓝题分享。
摆了。
其实已经都无所谓了。
## Day 1
机房垫底人。
拿到题先扫了下题面，发现似乎题面都不是很简洁的样子，还是先正序开题。
上来看T1，发现是个弱智题，随便判一下最大最小字母就完了。不
~~找几个人玩原神~~
君不见，紫黑之题天上来，各个蒟蒻“爆0”题
本题可以使用 STL 中的 `set` 完成。
使用一个 set 储存空的停机位，每一次来飞机时，寻找编号最大的小于等于 $g$ 的空位，如果空位存在，就把飞机安置进去（从集合中删除这个空位）；否则机场关闭。
set 用法提示：
* 使用 `s.upper_bound(x)` 寻找 `s` 中编号最小的严格大于 $x$ 的元素；使用 `--s.upper_bound(x)` 获取其前一个元素
似乎很长一段时间内我都没有太大的兴趣看番，re0 也是太过无聊才启动的，没想到哭的如此惨烈。
看 白鲸攻略 一集直接从头哭到了尾，为何能够爱一个人到这样的程度，也许威尔海姆在斩断白鲸时终究还是向剑圣作出了告别吧。
当然，雷姆线也是必须品尝的一环，我看到了真昼小姐的影子（
## 赛时
A还是照样的水~~差点吃一发罚时~~\
B有可能爆``long long``，那就先将乘法变成除法看看会不会爆1e18，然后算就行了\
C...在纸上画了一下：↗↘↗或↘↗↘~~（我当时读错题了）~~\
也就是说对每个点，要找后面两个“高峰”到三个“高峰”中间的距离\
等会，怎么样例3过不了？哦，有A1<A2，成joker了\
最终T3吃一发罚时，完成了在ABCD中吃罚时的成就\
D，
简单的 if 嵌套，如：
```cpp
if (表达式) 执行内容;
else 执行内容;
```
按照这个格式我们进行**堆叠**，可得出：
```cpp
if (n % 3 == 0 && n % 5 == 0 && n % 7 == 0) cout << "3 5 7";
else if (n % 3 == 0 && n % 5 == 0) cout << "3 5";
else if
T1花了2小时，本来可以二维数组A过的，结果我嫌时间复杂度太低了，开个map，加了个log，T飞了。
```cpp
map<pair<int,int>,int> mp;
```
乐，100pts -> 76pts，好活！
T2也是花了2小时。然后……RE了。
https://www.luogu.com.cn/record/96694145
乐，100pts -> 15pts 。
别
## 分析
看到了 $\oplus$ 符号，基本上往 01Trie 上面去想是没有问题的。
一开始想到的是离线做法，由于 $b_i$ 都不相同，但是对于单个 $i$ 是相同的，所以把所有 $i$ 拆分开来，录入所有的 $k$，然后用 01Trie 计算答案。但是**本题部分测试点强制在线**打破了我所有念想。
之后推了一下，发现可以成对将 $a_i$ 和 $b_i$ 压入 01Trie，和我们
# 最小生成树
## 概念
我们先画一张连通图：
我们将图中的点标出来：
然后保证这些点能够两两之间互相连通的情况下，我们选择性的删
# T226001 【排序】桶排序
### 赛时代码
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,a[10000];
int main()
{
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
sort(a+1,a+n+1);
for(int i=1;i<=n;
~~部分~~海报选自[奥奇传说精灵大全](http://aoqi.100bt.com/jingling/daquan_list.html)
如发现本人未更新的情况，可私信提醒。
# 神盾
[逆时空·黄金神女](https://i0.hdslb.com/bfs/ar
## Source & Knowledge
2024 年 01 月语言月赛，由洛谷网校入门计划/基础计划提供。
考察二维数组。
---
## 文字题解
假设字符数组 $s[i][j]$ 存储了原字符画第 $i$ 行第 $j$ 列的字符。
将原字符画扩大 $k$ 倍，本质上就是将一个字符，横向重复 $k$ 次，纵向重复 $k$ 次，将一个字符重复 $k^2$ 次。
人物背景：[主线同名](https://www.luogu.com.cn/article/x578tdzh)
S：Styx A：Acheron
剧情讨论：
A：欸，你读过《烧》了吗？
S：（点头）
A：感觉如何？
S：人物名字怪怪的。
A：怎么个说法？
S：首先蓝山嘛，coffee 没问题吧；肖舟，挺容易让人联想到小丑的。
A：（笑出了声）事实也如此。蓝山是一个让肖舟痛苦又爱的人
这题其实这么说吧，分几个步骤
1 找树的直径，要得到直径长度之余，还要用一个bool数组把树的直径上的点都标记起来。
2 最后要输出的m值的数量等于ans.size()+k*2，ans是存放直径的点的vector，并且k=min(k,n-ans.size());也就是说，k要先比小，防止点没k多的情况
3 然后就可以用一个for循环+dfs方法，去输出这条最终路径
这部分倒是很简单
**题意** : 给出一棵树形迷宫,叶节点是出入口。
现在有一个人闯入了迷宫深处,如果他达到出口就可以逃离。
可以在出入口放置守卫,守卫的移动速度和闯入者相同,若闯入者和守卫相遇则被抓住。
守卫和闯入者在移动过程中均可以观察到对方的位置,而后决策。
对于闯入者可能的每个起点,问至少需要多少个守卫才能确保闯入者无法逃脱?
$n\leq 7\times 10^4$ ,时限$\texttt{1
注册了一个号 0x3b800001，结果密码丢了。
然后注册了一个 666，看了一眼题，结果胡了一个 100+77+25，这个时候一看榜发现垫底了就没写。
睡了一觉起来一看榜发现各种 T3 大于 50 分的都来了，然后再想了 20 分钟结果是链并且编号相同都不会大于 25% 的分数。，
感觉完美模拟了 APIO 的惨案，NOI 遇到就搞笑了。感觉场上遇到这个 T2 说不定 77 都写不出。、
# 目录
- [0.前言](#0)
- [1.附题单](#1)
- [2.KMP](#2)
- [2.1.前缀函数](#21)
- [2.1.1.定义](#211)
- [2.1.2.计算](#212)
- [2.2.KMP 算法](#22)
- [2.2.1.模板](#221)
- [2.2.2.Password 模板+思维](#222)
- [
# 基础算法
- [二分](https://www.luogu.com.cn/blog/719978/fu-xi-bi-ji-er-fen)
- 倍增 $\ done$.
# 动态规划
### dp
- 状压 dp $\ done$.
- 树 dp（树上背包、换根 dp） [普通](https://www.luogu.com.cn/blog/719978/suan-fa-bi-ji-shu-dp
#### Written by @Areka6219 @PrefixAMS
### 对 $2021/6/6$ 高等数学的总结
1. 代数基本定理 ：对于方程 $\Sigma _ {i = 0} ^ n a _ i * x^i = 0$ 一定有`n` 个根。
2. 数列极限：对于数列 $\{a_1,a_2, a_3, \cdots ,a_n\}$ 若对于 $\forall \varepsilo
## 题意：
给定长度为 $n$ 的序列 $a,b$。
一共 $q$ 次询问，每次询问给定 $k$，你需要输出有多少 $i$ 满足 $a_i \oplus k\le b_i$。
## 题解：
对于异或问题，考虑字典树。
我们把关于 $a_i$ 和 $b_i$ 的 $k$ 放到字典树上，考虑 $k$ 在什么情况下会使得满足条件。
从高到低枚举位，
- 前 $j-1$ 位都一样，并且第 $j
一觉醒来，cqfcbb2015感觉浑身充满了OI之气。
ta打开电脑一看——诶，昨天才刚把ta CPU搞爆的线段树居然真会了！那个 `fread` 也难不住他了！
cqfcbb2015非常高兴，兴高采烈地尝试绿题。
诶，这道题目吗我怎么最优解？
诶，区间DP我怎么会了？
诶，我怎么会大模拟了？
诶，我怎么会 exgcd、CRT 了？
…………一下感叹略。
一上午，cqfcbb
- 2022-06-03 初入洛谷
- 2023 蓝名
- 2024-03-29 第一次参加官方比赛
- 2024-05-01前 绿名
- 2024-05-01 第一次发布文章
- 2024-05-17 拥有等级分
- 2024-05-31 第一次发消息
- 2024-06-24 第一次提交题解，但是未通过
- 2024-10-07 橙名
- 2024-10-07 排名突破10k
- 2024-1
时间：2025.1.18——2025.1.23
### 一月18日
上午先做了[4道题](http://39.99.183.126:8888/contest/6789fddffff7c5acf9a2ecce)，是戚朗瑞出的，T1想难了，T2优化WA了~~本来也不会~~，T3T4数据太大了。
下午来讲题讲课，讲的平衡树，是省选的难度，根本听不懂。
### 一月19日
今天是北大的鞠曜徽来讲，
NOIP 之前最后一场模拟赛。
---
啥都不说就说说心路历程吧。
---
摸到了题，没有把三道题都看完就直接莽了 T1。
花了 20 min 左右把 T1 搞完就再也没动，虽然最后的确是切了。
然后又毛毛躁躁的去看 T2，woc 这不 Lucas 板题吗！不对，一看模数 1e8，woc 这不 exLucas 板题嘛！歘歘歘（念 chua，一声，但改成啪啪啪是不是更合适？）写完就又扔一
已经退役好久了！无所谓了。赛前一个多月没碰 oi/fad
来到了六中！
## Day 1
进场 3 道 998244353 让我感觉这把直接寄掉。
先看 T1，不会是个论文题吧。不会做，考虑乱搞，假如说数据的 $C$ 是由 $A*B$ 之后随机交换一些元素生成的，那直接判行列和就很好了，写了个行列和直接丢了。
T2 发现自己不会推错排了，然后随便二项式反演了一下写了 40 分，发现我不会
### 2024/7/7
8:30，来到了[威海职业学院](https://baike.baidu.com/item/%E5%A8%81%E6%B5%B7%E8%81%8C%E4%B8%9A%E5%AD%A6%E9%99%A2/389410?fr=ge_ala)......
大学校园真大啊！
教室离宿舍好远，还好有空调。
宿舍只有我和[张睿渊](https://www.luogu.com.
## 前言
祝审核和看见这篇题解的人事事顺心！ヽ(≧∀≦)ﾉ(≧ω≦)/
## 题目描述
题目传送门（https://www.luogu.com.cn/problem/B3755 ）
## 题目简要
我们需要在一个 n×n 的矩形上放置最多的 1×2 的小矩形 （只可以水平或垂直放置），对角线上的 k 个连续障碍物不可放置。 而且如有多种最优方案，输出任意一种即可。
## 解题思路
- 首先
前两个点直接按照题意和给出的函数模拟，可以拿到 $20$ 分。
第三个点直接将 $a$ 与 $0$ 用比较节点进行比较可以获得 $6$ 分。
但我们发现 $S$ 函数的出现必然是有意义的。因为 $x\rightarrow +\infty$ 时 $S(x)=1$，$x\rightarrow -\infty$ 时 $S(x)=0$，$x=0$ 时 $S(x)=0.5$，并且题目允许一定的精度误差，
上接[夏令营日记2024上](https://www.luogu.com.cn/article/1ruoud6c)。
### 2024/7/10
夏令营的下半段开始了，第四天来了。
今天起床竟然比闹钟响的还早。
早餐又喝了**椰奶**~~原来那是椰奶~~，还有肉饼、油条 and so on。
上午考试，做**戚朗瑞**大佬出的题，好激动。
3小时后......一共180分，
## 目录
### 第一章：来到真正的世界
### 第二章：荒野大战
### 第三章：队伍壮大
### 第四章：死里求生
### 第五章：宝剑锋从磨砺出
### 第六章：五行修行巅峰者
## 第七章：五行精兵
## 第八章：杀死狼皇
## 人物简介：一到五章
```
姓名：MMR
特点：头脑十分聪明，让XZL十分崇拜。
但攻击力、防御力等其他技能都没有
```
```
姓名：XZL
特点：
### 十三、狼皇之怒：荒兽源血
#### 狼皇：
#### 等级： SSP+
#### 技能： 荒兽源血（SSP+） - 融合十二荒兽本源之力，可短暂模拟或强化其部分核心能力，生命力与恢复力恐怖。裂空爪（SSP） - 利爪蕴含撕裂空间之力，攻击范围广，穿透力极强。噬魂咆哮（SSP） - 蕴含灵魂攻击的咆哮，震慑心神，瓦解意志，范围巨大。不灭战躯（SSP） - 体表暗金鳞甲防御无双，融合源血后恢复
## 人物简介：六到十章
```
姓名：LYL
特点：金系,可以发射出金针,金针可以使射中的一切物体化为金相或
控制住敌人。拥有金珠眼,直视人可使人死。是MMR五行精兵的五大头领之一。
```
```
姓名：ZC
特点：木系,可以使一片区域化为异植森林，花园中有傀儡异植兵
和许多能力各异的异植。是MMR五行精兵的五大头领之一。
```
```
姓名：MZN
特点：水系,可以变出水，踏浪而上，快
2024/3/17 俄罗斯是五常？爱尔兰不是五常吗？
2024/3/17 四毛子 $\mathcal O (1)$ 预处理！（注：该算法被一致通过命名为 AC400 算法）
# 未完待续
# 题解： [P6418](https://www.luogu.com.cn/problem/P6418) [COCI2014-2015#1] ZABAVA
### 题目理解
我们需要计算公寓中所有楼栋的吵闹指数之和的最小值。 每个学生搬入某栋楼后，该楼的吵闹指数会增加 （等于当前人数）。 我们可以进行最多 `k` 次操作，每次操作可以清空一栋楼的所有学生，从而重置该楼的吵闹指数增长。
##
很好的题。
首先条件可以转化为 $a_{y_i}=a_{x_i}\oplus z_i$，因此 $a_{x_i}$ 一旦确定了，那么 $a_{y_i}$ 同样也就确定了。
我们考虑连边：对于每条限制 $(x_i,y_i,z_i)$，我们在 $x_i,y_i$ 间连双向边，边权为 $z_i$。
那么对于一个连通块，只要一个数确定了，所有数就都确定了。只需要计算每个连通块的答案然后乘起来就行了。
因为luogu.me会把图片圆角，所以请将圆角视而不见，避免识别错误。\
另外，请随时更新文章，以查看最新版本。
# 第一章 版本、版权及颜色
## 1.版本
本版本为**迷宫3.3版本**。
## 2.版权
版权如果没有标注即归于@Martin0310，**严禁模仿，如果想要模仿请私信申请**。
## 3.颜色
|编号|颜色名称|十六进制RGB/$\LaTeX$ 颜色名称|
|:-|:-|:-|
[this](https://www.cnblogs.com/lnyx/p/17517893.html)
密码去问 @耳朵龙_
## 线段树
线段树是一种数据结构，支持区间、单点修改，区间查询。
线段树是用一个段一个段的答案拼起来的，也就是说线段树是一个分治模型，每一个段表示一个区间：
这里每一个格子都会向下拆分，直到长度只有 $1$ 的时候才会停止拆分，此时的答案就是当前的节点（随题目变
# Day -2
今天是开学考。
看着挺有趣的，紫题刷不动，然后就来放松了（
显然对子和单牌是用来清空剩余手牌的，所以不需要在第一步考虑。
那么还剩下两种牌型:三带一和炸弹。
但是如果分开考虑有些繁琐，发现炸弹其实也是一种三带一,只是带的牌和前三张一样而已。
那么此时就只剩下了三带一这一种牌型，并且可以带任何牌。
贪心地想，想让步数尽可能少，就要多出三带，因此可以先计算出最多可能有多少个三带，同时算出这时能出多少张牌。
> 只因刘谦一上台，去年魔术来研究。
## 魔术步骤
Step 1：首先选取四张牌，然后将这四张牌对折后撕开，得到八个小张牌，这时撕开我们会得到两组牌，我们将牌放在一起。
Step 2：根据每个人的名字字数，将牌叠最上面的牌放到最下面，重复名字字数的次数。例如，如果名字有两个字，就放两张牌到最下面。
Step 3：从牌顶拿三张牌插进中间位置，然后藏起一张牌。
Step 4：南方人拿走 1
使用ctime库中的clock()方法，可以计算某段程序代码运行时花费的时间，这里以分解质因数算法为例，在main函数中，调用分解质因数算法之前记录了一次clock()的时间值，调用算法结束后又记录了一次clock()，用两次差值除以 CLOCKS_PER_SEC（时间滴答常数）得到秒数，乘以1000得到毫秒数。
```cpp
#include <iostream>
#include <vect
公开下载本人实现游戏：
[dino](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/bf8bpku8)
[扫雷](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/viet0sdd)
[BBQ(1.3)](https://wwhy.lanzouq.com
|周次|标题|主要内容|
|:-:|:-:|:-:|
|1|《一丈青和简爱为何走向不同人生》|名著读后感：《水浒传》《简爱》|
|3|《辩论复盘》|如题|
|5|《如何为周记作评论》|如题|
|7|《浅谈选位：我们正在舍本逐末》|对部分组长选位行为发起犀利的攻击|
|9|《无体育，不附中》|谈体育及锻炼|
|11|《期中成绩总结》|如题|
|13|《沿河镇》|批判项目部量化分制度|
|15|《魔头
我要被拿去献祭了。
我被绑在祭台上。刽子手走过来，她是真好看啊。她没有拿刀，因为今天处决我的方法太劲爆，人类完成不了。
她是真好看啊。她按下按钮，一把铡刀缓缓升起。我看着她咬着自己的嘴唇。
刀落下，瞬间斩断我的大腿。
她是真好看啊。
血如泉涌。她点燃我的血液，天蓝色的火焰包裹了我的全身，让人不禁好奇我来自哪个星球。
但是我只好奇她为什么这么好看。
本题我的基本思路是：依次读入这些名字，一个一个转化为数字判断是否与读入的数字相等。
```
#include<bits/stdc++.h>
using namespace std;
int i;
bool f=false;
long long m;//12位int不够
string st;
long long name(string s)
{
long long n=0;
for
基本思路：
首先，如果魔法足够，用闪烁，因为更快。
其次，如果魔法不够：
若魔法值为6至9，回复1秒即可再次使用魔法，而1秒可以跑17米，因此如果剩余时间大于一秒并且剩余距离大于17米，就休息1秒再使用闪烁法术，否则跑步
魔法值为2至5同理，需要回复2秒，因此如果剩余时间大于2秒并且剩余距离大于34米，就休息，否则跑步
若魔法值为0或1，需要回复3秒加上使用魔法1秒，而四秒能跑
基本思路：
首先，如果魔法足够，用闪烁，因为更快。
其次，如果魔法不够：
若魔法值为6至9，回复1秒即可再次使用魔法，而1秒可以跑17米，因此如果剩余时间大于一秒并且剩余距离大于17米，就休息1秒再使用闪烁法术，否则跑步
魔法值为2至5同理，需要回复2秒，因此如果剩余时间大于2秒并且剩余距离大于34米，就休息，否则跑步
若魔法值为0或1，需要回复3秒加上使用魔法1秒，而四秒能跑
好说好久没写树形dp了，今天切掉三道水题，干脆就把以前写的总结搬过来吧
## 1.子树和类
### CF767C Garland
[http://codeforces.com/problemset/problem/767/C](题目)
很神的一道题，题目大意是把一棵树切成三份，使每一份的子树和相等
结果就瞎写一气在cf上面向数据编程
到了几个数据点大到无法显示的时候，怎么魔改也是wa
# 前言
###### ~~（为什么现在才来写斜率优化的总结我也不知道）~~
斜率优化 DP 是动态规划中十分重要的一类优化方法，难度约为省选，洛谷上的很多板子题也都是紫的。但其难度并不算大，模板都一样，只需要会根据题目的条件推一些简单式子，那么基础的斜率优化DP就掌握得差不多了。~~（至于进阶的，显然我是个蒟蒻根本不会）~~
# 引入
对于状态转移方程 $f_i=\min(w_i+w_j+
# 基础
树状数组的原理是二进制，而线段树的原理是分治。并且都是现存区间答案，再合并进行分析。
树状数组能完成的，线段树都能完成；线段树能完成的，树状数组不一定能完成。
线段树因为需要传参，所以需要带一个大常数。
普通线段树可以解决的事有：
1. 区间和
2. 区间 $\gcd$
3. 区间最值
4. 区间异或和
## 单点修改+区间查询
这是很基础的线段树，步骤是：
1. 建树
2.
```cpp
阿尔古斯对活儿总是来者不拒。
无论是捉奸、讨债还是解救人质，
阿尔古斯都能令雇主满意，绝不拖泥带水。
锐利的眼睛为她追溯蛛丝马迹，
有力的拳头和精准的枪法使她无往不胜。
最重要的是，
她心甘情愿地接下一切委托，从不抱怨。
很显然，
完成工作已经不只是必要的生存手段，
而是某种秘而不宣的执念。
```
首先，Accepted_100 是一个优秀的 OIer。他刚学 OI 半年，就已经熟练地掌握了各种代码编辑器的名称。而编译器和编译选项显然有点刁难他了，暂且不提。
为什么说他是千年不遇优秀的 OIer 呢？以下就是几点原因：
### 优秀的独立思考能力
作为一名足够优秀的 OIer，他有着出色的独立思考能力。
无论是在别人讲好题分享、老师讲课，还是在别人讲专题时，他总是不像别人一样听课，而
当你访问一个数组的时候，通常人会用a[i]来访问。
但是，你用i[a]访问也可以，例如，你要访问a数组的第100个
元素，正常人都用
```cpp
#include<bits/stdc++.h>
using namespace std;
int a[1001];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
cou
# 题目简述：
有 $N$ 个人，第 $i$ 个人的值为 $A_i$ 。同时有 $M$ 个寿司，第 $i$ 个寿司的值为 $B_i$ 。
如果一个人的值小于等于这个寿司的值，这个人就会吃掉它，并且后面的人不会再见到这个寿司。求第 $1,2 \dots M$ 个寿司分别会被谁拿走？
# 暴力（ $40$ pts 左右）：
简单分析，$N$ 个人， $M$ 个寿司，$O(NM)$ 的时间复杂度，简单实
## Day -1
待更
## Day 0
待更
## Day 1
待更
### T1
这个题是一个我相对擅长的模拟题，可能是大家做思维题做多了，这种非常考察细节的题目似乎发挥都不太好
我把时间轴分为了三个部分：
公元前 | 公元 1.1.1 到 公元 1582.10.4 | 公元 1582.10.15 之后
简单做了数学题之后，把时间轴分割为三个部分，中间还是算错了一次
## 前言
https://www.luogu.com.cn/discuss/1092310
## 方法一：修改 hosts 文件
### 性能
推荐值：$3$ 星。
使用难度：$1$ 星。
访问速度：快。
稳定性：过几天就不管用了。
### How？
路径：`C:\Windows\System32\drivers\etc`。
这道题的思路是比较显然的，但实现上就会有些细节，
我们知道，一个数异或其本身为0，而任何数异或0还是自身，
就可以用异或前缀和$s[ 0..n ]$来表示区间异或和了。（学术文章本来是该打实心句号的，这里懒得调成英文模式了）
------------
有了异或前缀和，我们对于1~n中的每个i，
求以第i的数结尾的区间异或和大于等于k的有多少，
即$s[ 0..i-1 ]$中有多少个与$
### 战役意图
最高统帅部决定，于 11 月 18 日在伏尔加河沿岸发动一场大规模进攻战役。战役主要目的是摧毁南线德军的进攻矛头，打击补给系统，收复失地。作为部队实力更为庞大的北线方面军，我们将重点进攻四个目标：首先，以最快速度突破罗马尼亚军队负责的防线。第二，调集部分部队南下，于顿河畔卡拉奇和高加索方面军会师，歼灭其中的第六集团军。在完成第二个目标后，集中兵力向入海口城市罗斯托夫发动进攻，
# [P1040 [NOIP 2003 提高组] 加分二叉树](https://www.luogu.com.cn/problem/P1040)
我们定义:$dp_{i,j}$ 表示选取是下标为区间 $[i,j]$ 的加分最高的二叉树。那么初始的时候 $dp_{i,j} = a_i$ 首先，要中序遍历是 $(1,2,3......n)$ ，然后，我们知道中序遍历是左根右。
那么我们在一串序列 $[
非常容易就能想到 01trie 的做法，首先建立一颗字符集只有 $0$ 和 $1$ 的 trie，然后把所有的数按位拆开插入进去。考虑树形 dp，记 $f_i$ 为树上节点 $i$ 子树上的最小异或值最大的数。
记两个儿子节点的编号分别为 $x$，$y$，当前位位权为 $w$，那么转移方程就是：
$$f_i=\begin{cases}
1 &i \text{ 无子结点}\\
f_x &i \t
## 颜色说明
* $\colorbox{gray}{\color{white}灰色}$：未达成
* $\colorbox{green}{\color{white}绿色}$：已达成，可以游玩
## $100$ 粉
有限 Q&A，每个**粉丝**可以问我一个问题，但是我可以选择不回答。私信即可提问。加上前缀：`100 粉福 Q：`。
$\colorbox{green}{\color{white}达
变量名可能比较奇怪？大写的是函数，小写的是常数。
假设有
$$F'=\dfrac{P}{G'(F)}+Q$$
记 $H$ 为 $G$ 的反函数。那么
$$G'(F)F'=QG'(F)+P$$
$$G(F)=C+\int P$$
$$F=H(C+\int P)$$
带入回原式，解出 $C$ 即可。
如果 $H$ 的形式不是很好的话，还是只能用一般的办法：
$$F'=G(F)$$
1. 首先，你要保证你并不是抄袭对方题解，否则是会被封禁专栏的！
2. 你已经通过了这道题目，而不是听取别人的一面之言。
3. 并非套取数据点以来达到 AC 的小丑行为，也非打表卡常的不正当行为。
4. 尽量不要滥用标题，`\text` 和 `\texttt`，否则你可能不会通过，尽量使用 `- 主题`解决。
5. `对于按钮 A`，这类很容易错，建议使用 `对于第一个按钮` 之类的话术。
粥鱼汤一到机房，所有写题的人便都看着他笑，有的叫道，“粥鱼汤，你的 $n\log^2n$ 又被卡常了！”他不回答，对肚子的说，“出一道乱搞，要两道贪心。”便排出九个 $\log$。他们又故意的高声嚷道，“你一定又挂了分了！”粥鱼汤睁大眼睛说，“你怎么这样凭空污人清白……”“什么清白？我前天亲眼见你写了 $\text{cerr}$，挂 $40$。”粥鱼汤便涨红了脸，额上的青筋条条绽出，争辩道，“卡常
# 一. 什么是状压DP
状压DP是一种利用位运算来高效表示和转移状态的动态规划方法。它特别适用于状态可以用二进制位表示的问题，通常处理的是"选或不选"、"存在或不存在"这类的二元状态。
## 为什么需要状态压缩？
• 常规DP在表示某些状态时需要大量空间
• 状态压缩可以极大减少内存使用
• 位运算操作非常高效，能提升算法速度(其实就是因为这个)
# 二. 常用的一些技巧（位运算）
## Part 1.基础部分
这种题目最显著的特征：dp 不知道开几维，数据范围很小，这种题十有八九是状压 DP。而状态压缩即为用一个数的二进制去记录这个状态，因此数组需要开 $2^n$。
## Part 2.模版
```cpp
//前面全部初始化为很大的数，每种状态的第一种情况为0
//f[S][i]：S集合中的前i-1个已经处理过，且当前处理到i的最小总代价
//计算f[S][i]时，枚举
这题可以看做[洛谷P2016 战略游戏](https://www.luogu.com.cn/problem/P2016)的进阶版，多了一个价值
~~如果一道题不够难，那就把它放到树上。~~
**题意**
给出一棵树，每个结点都可以看守与其连接的点。在每个点上安排看守需要花费一定的代价，每个点的代价各不相同。求在能够看守到每一个点的情况下的最少花费。
**思路**
树状dp。设 $f[i]
# **数论**
### **①**素数&素数筛法：
筛法有欧拉筛与埃氏筛两种，在时间复杂度上前者更优
代码：
欧拉筛(线性筛)
```cpp
void gp(ll r){
cnt=0;
ll i,j;
for(i=2;i<=r;i++){
c[i]=c[i-1];
a[i]=a[i-1];
if(!p[i]){
z[++cnt]=i;
c[i]++;
a
...
根据上述材料，给将要离任的小粉兔写一篇小作文。
ChatGPT
亲爱的小粉兔：
时光荏苒，眨眼间，你即将离开我们了。在这个告别的时刻，我想表达我对你的深深感激和最诚挚的祝福。
回首我们一起度过的时光，你那魔怔而又独特的个性总是给我们带来无尽的乐趣。你的笑容、你的言行举止，总是让人忍俊不禁。无论是在工作中还是生活中，你总是能够以自己独特的方式照亮周围的一切。
虽然有时你会显得有些
目前在打：核能
---
~~灵光沙海 （5.0/5.2）^~~✓
~~百变圣诞夜（5.0/5.3）~~✓
~~时间（5.1/5.3）~~✓
~~街头篮球（5.1/5.4）~~✓
~~机甲（5.1/5.4）~~✓
~~工业时代 （5.0/5.4）^~~✓
~~神灯（5.1/5.5）~~✓
~~天空之城（5.5/5.6）~~✓
旋律大都市（5.1/5.6）^
核能 （5.1/5.
# 状态压缩
用一个**整数**来记录状态：
整数的每个二进制位对应一个物品，0未选，1已选
# 例题
## [传球游戏(模板)](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3311&tid=J)
通过题目得知每个人传给其他人的消耗都**不一样**，所以使用**状态压缩DP**
使用f[i][j]数组，表示在i状态下（i的**二进制*
看看会不会咕/cf
除非极度不可做题，否则一般都是会写的。
每个题限时思考 $30\min$，如果有想法可以延长；然后自己写/看题解。
## BJOI2019
### P5322 排兵布阵
比较水的，略。
### P5323 光线
考虑记 $f_i$ 为直接穿过第 $i$ 面镜子的光有多少，记 $g_i$ 为从第 $i$ 面镜子反射回来的光有多少。
易得：
$$
\begin{a
我们知道, 在某些背包问题中, 我们需要解决一些零和问题, 也即: 物品有正有负且都不是特别大 ($|w_i| \leq W$), 我们需要找到一个具有某种性质的子集 $S$, 满足 $\sum_S w_i = 0$.
对容量这一维进行 DP 的话, 体积是有可能达到 $\pm nW$ 量级的, 但如果问题只需要和答案有关的某一个 instance 被 DP 过程命中的话 (更具体地说就是比如
## 3.31
学了一个月 whk 后感觉脑子变傻了，AT 和 CF 都打得奇烂无比。
今天到了 MX 线下，XZQ 大哥哥走了后，我现在一个熟人都没有了。PengAo 在 XYD，WTR2007 和 Lopzith 在 TYZ。
刚来第一天刚好就有模拟赛，不过听对面老哥说不用打。看了看题，怎么感觉 100+100+eps 并不困难。赛后看榜发现 JX 红太阳 hz 老师 100+100+4
# Solution 【模板】单调栈
## 题面
### https://www.luogu.com.cn/problem/P5788
如给出项数为 $n$ 的整数数列 $a_1 \to a_n$。定义函数 $f_i$ 代表数列中第i个元素之后第一个大于 $a_i$ 的元素的下标，即 $f_i=[min (i,j≤n,a_j \ge a_i)]{j}$。若不存在，则 $f_i=0$。试求出 $f
定理：相似矩阵特征多项式相同。
证明：$|\rm PAP^{-1}-\lambda E|$
$=|\rm PAP^{-1}-\lambda PP^{-1}|$
$=|\rm (PA-\lambda P)P^{-1}|$
$=|\rm P(A-P^{-1}\lambda P)P^{-1}|$
$=|\rm P(A-\lambda E)P^{-1}|$
$=|\rm P|\tim
比赛的时候看到这题，想起了上次被[这题](https://www.luogu.com.cn/problem/CF1270C)支配的恐惧，不断提醒自己绝对不能想复杂，这是CFdiv2，不会考数据结构！代码一定很短！
然后yy出分治之后以为时间复杂度是错的。。。于是就又浪费了十分钟想到了01tire的做法。
思路：首先，我们可以通过构造$X$使任意的$a_i$成为整个序列中最大的$a_i \ \t
_省流：_ 作者在一堆 _精彩极了_ 的梗中写出了一篇 _糟糕透了_ 的文章。
_初 见 端 倪_
最近~闲的没事干~，浅浅的估算了一下圆周率，最终取得了$6\sqrt{2-\sqrt3}$（“约”3.1058285412302491481867860514885799401888268158391661657680384877806836969856239630684156963309959
# 星际战争：觉醒的星辰 4
## 第二十二章：新纪元的挑战
和平的新纪元带来了前所未有的繁荣和发展，但同时也带来了新的挑战。随着星际旅行和探索的普及，不同星球和种族之间的文化冲突开始显现。凯尔作为银河系的守护者，必须找到平衡各方利益的方法。
## 第二十三章：文化交流
为了促进不同文化之间的理解和尊重，凯尔提议建立一个星际文化交流中心。这个中心将成为不同种族和文化展示自己特色、交流思想的平
# 星际战争：觉醒的星辰 3
## 第十二章：重建与和解
战争的尘埃落定，艾瑞斯星球和联盟的成员开始着手重建家园。凯尔利用他的领导力和影响力，推动了一个全面的和解计划，旨在修复战争带来的创伤，促进不同星球和种族之间的理解和合作。
## 第十三章：新的力量
随着和平的到来，凯尔和其他星辰之子开始更深入地探索他们的力量。他们发现，除了与星球共鸣外，他们还能够与宇宙中的其他能量源建立联系。这种新发
# 星际战争：觉醒的星辰 2
## 第六章：联盟的裂痕
随着战争的持续，星际联盟内部出现了裂痕。一些成员星球开始质疑这场战争的意义，他们担心长期的冲突会耗尽他们的资源，甚至可能导致联盟的瓦解。
凯尔意识到，要想真正赢得战争，不仅需要在战场上取得胜利，更需要在联盟内部巩固团结。他开始秘密地与其他星球的领袖进行沟通，分享艾瑞斯的能源矿石，并承诺在战争结束后，将这种能源用于整个联盟的共同发展。
#
望周知。
此题为单调队列模板题，其实楼下把单调队列与优先队列混为一谈本人并不赞同。
# 单调队列有两个性质
1. 队列中的元素其对应在原来的列表中的顺序必须是单调递增的。
1. 队列中元素的大小必须是单调递\*(增/减/甚至是自定义也可以)
# 单调队列与普通队列不一样的地方就在于单调队列既可以从队首出队，也可以从队尾出队。
# 那么我们应该怎样实现单调队列呢?
就拿样例来谈谈，设以最小的为
[往期](https://www.luogu.com.cn/paste/fl60t7zi)
# luogu
[闻兔队左前棕名遥有此寄](https://www.luogu.com.cn/discuss/950047)
[悼念小粪土（诗兴大发）](https://www.luogu.com.cn/discuss/949996)
[发现程序员经常熬夜有三个弊端：](https://www.lu
**投票:你诗人吗**(点击选项进行投票):
[bushi](https://vote.saobby.com/v/c2438JnP/0) 
[shide](https://vote.saobby.com/v/c2438JnP/1) 
## 长链剖分
将重链剖分中的重儿子（siz最大的儿子）变为长儿子（dep最
大的儿子），来将树划分成一条条不交的链。常常用于优化与深度有关的树上 dp/计数 问题。
### 基本性质：
- 任意不同长链不交（都是树链剖分了）。
- 从任意一点出发到根的路径上经过的短边不超过 $O(\sqrt n)$。证明考虑每次跳短边后子树内所有点的siz和，卡得最满就是 $1+2+3+4+5+ \dot
【三体Ⅲ死神永生】
序·心事浩渺连广宇
严 锋
复旦大学中文系副教授
《新发现》杂志主编
多年以后，我还回记得看完《三体》的那个秋夜，我走出家门，在小区里盘桓。铅灰色的上海夜空几乎看不到几颗星星，但是我的心中却仿佛有无限的星光在涌动。
这是一种奇异的感受，我的视觉、听觉和思维好像都被放大、重组和牵引，指向一个浩瀚的所在。
即使没有光污染，身在北半球中纬度
## T619145 质数筛
### 赛时代码
错误原因：
1.思路错误：自己的思路是什么，为什么错误，一定要把错误原因找出来！！！
2.细节错误1，输入。。。。。
3.细节错误2，。。。。
```cpp
#include<cstdio>
using namespace std;
int n,a[105];
bool fp(int x){
if(x<2)return fals
## 置顶内容
这个人很菜，快嘲讽他。
### 我不曾忘记
***【迪娜泽黛】***
我的破木箱
装满枯萎的花
放不下 光与壤
和新鲜的愿望
如果能飞翔
去高高的地方
撒一张 梦的网
收集爱的回响
***【纳西妲】***
你也在听吗
落单的孩
### 思路
显然答案就是最长的区间 $[1,r]$，使得从 $1$ 到 $r$ 的串等于从 $n-r+1$ 到 $n$ 的串，就是 KMP 中的 $n-nxt_n$。
### 代码
```cpp
#include<bits/stdc++.h>
#define Maxn 1000005
using namespace std;
int nxt2[Maxn];
void KMP(int n,st
一滴，两滴，窗上开始出现雨的痕迹，我知道，雨又悄悄地来了。周围的环境安静下来，伴随着树叶窸窸窣窣的摩擦声，雨渐渐地大了，零零碎碎的雨声如同不规则的鼓点一般荡漾在我的耳边，牵动起我的回忆。
小时候，雨是我快乐的源泉，每当听到雨声，我总要笨手笨脚地穿上雨靴和雨衣，兴冲冲地跑下楼，窜入那片灰蒙蒙的世界。雨幕遮掩下的小区几乎没有其他的人，我只听见雨滴落在雨衣上发出的“啪嗒”声。我总喜欢在雨中飞奔，肆意地
## 题目大意
有一个无限大的二维网格，$(0,0)$ 处有一个篝火。
在时间 $t = 0$ 时，烟雾只存在于坐标 $(0, 0)$ 处。
给定一个长度为 $N$ 的字符串 $S$，由字母 `N`, `W`, `S`, `E` 组成。在时间 $t = 1, 2, \dots, N$ 时，按顺序发生以下事件：
- 风开始吹动，当前时刻所有的烟雾按照如下规则移动：
- 如果 $S_t$
## 题目大意
给定一个字符串 $S$，请你在 $S$ 后面追加最少的字符，使得 $S$ 是一个回文串。
## 解题思路
定义 $|S|$ 为字符串 $S$ 的长度。
首先我们考虑找到一个最靠前的下标 $i$（$0 \leq i < |S|$），使得以 $S_i$ 为回文中点可以构成一个回文串，由于题目让我们把 $S$ 补全成一个回文串，我们在找回文中点的时候只需要满足以 $|S| - i$ 为
### 题目大意
给你一堆字符串 $S_i$，然后让你统计满足以下条件的字符串 $T$ 的数量：
- 只由 $\texttt a$ 和 $\texttt b$ 组成。
- 不包含任意一个 $S_i$。
### 解题思路
考虑 AC 自动机，dp，矩阵快速幂。
由于字符串长度在 $6$ 以内，所以自动机的节点数小于 $2^7$。
首先设 $dp_{i, c}$ 为 $T$ 的长度为 $i$
## 前言
最近几场可以切 A~E 了，所以赛时没切掉 F。而且最最令人开心的是只 WA 了一个点的快感，可惜 Atcoder 不给部分分。
### 小细节
代码中可能出现的错误就放这里了，作者是用的数组和 `vector`，所以对使用 `map` 的家人们可能帮助不大。下文无特殊说明默认通过了样例（如果没过可以留言让我帮你调）：
- 样例 RE 了。
- 可能是数组下标访问到负数了，需要
### 在迷茫的时候不妨听听牢朱的话
资料来源于 2025.6.15 0:00-3:08
牢朱说胡琦到更年期了脾气很不好。
牢朱说二班不要去全年级最菜。
牢朱说四班很多91哥。
牢朱说四班人很拘谨很有礼貌。
牢朱说九班大多都是弯的。
牢朱说文化课适合不喜欢睡觉的人。
牢朱说她和炮姐和孔令初一坐一组的时候三个人内向完了。
牢朱说她每天都很饿。
牢朱说柯南是她二次元启蒙。
牢朱给
这种~~鬼畜~~奇怪的剪枝是我在做P1120小木棍时发现的，当时发现前只有78分。
```cpp
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
int a[70],n,len,t,vl[70]
这道题十分简单，谢谢大家了！
---
**我是一个新手，请多包涵**
---
如下方法 very good.
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
int z=1,n,a[1000005];
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(
这个人莫名其妙从66粉长成了88粉
今天模拟赛中出现了一个题，需要对一个 $n$ 个点，$m$ 条边的图做边覆盖计数，边覆盖是一个边集 $S\subseteq E$ 使得任意一个点 $i$ 都存在一条边 $(u,v)\in E$ 满足 $u=i$ 或 $v=i$，即覆盖所有的点。
$n\leq 40,m\leq 60$，1s 512M。
然后被我使用神秘做法冲过去了（然后莫名其妙登顶？）求叉 & 求证明。
这是一个 NPC 问
# 挂大分了，我是shaber，晚点再写
咕了两周。
### Day -1
复习图论
### Day 0
复习数据结构 + 字符串
### Day 1
带的吃的不够，饿死在考场上了
20 min 码完 T1，一遍过大样例
看 T2 想不出正解，只好先把 20pts 打了
随后发现我大脑好痒，觉得要长脑子了
然后写了 T2 的另外 20pts 的计数
看了 T3T4 的题面发
首先容易看出一个性质，这个Hx(0)
是一个具有斐波那契性质的串，然后就一直在想合并的做法，然后直接GG
1h后点开题解，只能大喊妙妙妙（得出结论，我又在混吃等死）
首先看性质，我们来具体地统计一下：
斐波那契性质：Hx=Hx−1+Hx−2
当2|x
时以0
结尾，否则以1
结尾
定义H−1(x)
为H1(x)
的逆操作，不难发现当s′
为s
字串时，H−1(s′)
仍为s
字串
再考虑一
## P9335
双倍经验 P8421。
发现三个都最多改变 $\log n$ 次。
所以 P8421 离线扫描线搞搞就好了。
但是 Ynoi 题一定要卡常滴。
这边把 vector 换成了链表，然后装上了 @Min_25 的超级快读。
## P5356
简单的分块。
考虑只有询问怎么做：二分第 $k$ 小值，查询有多少个数比它小即可。散块暴力做，大块内数组重新复制一份，提前排序好
在之前，我这个号被我们班的同学机惨，之后发了很多不该发的东西。对此，我表示深深的歉意。今天，我终于找回了这个号，我在这里立下坚定的誓言：从今天开始，我将不再抄题解、刷黑题，不再发我是AKIOI的大佬。我会让大家看到，我正义的一面。我将努力学习，争取早日橙名。对于那些机惨了这个号的同学，我也表示感谢，感谢你们帮我绿名。
过去的路还有很长，我们仍在路上。希望诸位信竞生不要乱机惨他人，让洛谷不再是万恶
# DP
## 如果你的亲戚没学过计算机
### A：dp是个啥？
### Q：是动态规划。
### A：由什么推来的？
### Q：递归。
### A：用什么优化？
### Q：记忆化递归。
### 此时你应该得心应手，临危不惧
## 但......
### A：它有什么优缺点，要有什么步骤，什么前提......
### 局势发展到这就不可控了
## 所以今天就带大家了解一下
## 递归 记忆化
### 题意简述
- 输入三个整数 $n$，$m$，$len$，表示 $n$ 个人参加计划，每个人基因长度为 $len$。
- 接下来 $n$ 行，每行 $len$ 个字符，表示每个人的基因。
- 当两个人同一位置的基因成功配对，主人公将会收到一条消息，且这两个位置的基因不再与任何人配对。
- 求主人公可以收到多少条配对成功消息。
### 样例分析
样例输入：
```
省流：我的手机坏了，彻底坏了。
请重点关注加粗部分。
### 赛前小事
#### Date 2025/4/18
开坑。
难绷，机房里有人没过 APIO 的审核，我不说是谁。
#### Date 2025/4/24
THUSC & PKUSC 似乎已经确定噶了，节哀。
#### Date 2025/5/11
打了一场 APIO 模拟赛，拜谢 HEZ。
#### Date 2025/5
这里的题是真的水……
| 难度 | 数量 |
| :----------: | :----------: |
| 蓝 | 3 |
| 紫 | 5 |
| 黑 | 2 |
- [$\color{#9D3DCF}{CF5E}$](https://www.luogu.com.cn/problem/CF5E)
单调栈优化DP，没了
- [$\color{#3498DB}{CF6E}$](http
- 这题对我来说可以说尤其地困难啊！
- 感谢[奆佬](https://www.luogu.com.cn/user/58543)对我探究性学习的指导和帮助，我也要尽力避免思维的死胡同，寻求契机。
**[题意](https://ww
跟着成外“旅行团”来南京“旅游”了（7.30 ~ 8.14）。
附：2023 南京游记集合：
[2023南京号家军集训游记](https://www.luogu.com.cn/blog/574916/post-2023-na-jing-hao-jia-jun-ji-xun-you-ji) by gjy
[2023NJ旅游记](https://www.luogu.com.cn/blog/lis
以下是我自己弄的几道题目，当然已经全部贡献给JL了。。。
有些没考的我暂时不放。。。
如果撞题了请无视，毕竟我很菜。。。
欢迎各位大佬前来$AK$：
[U21609 公主的花](https://www.luogu.org/problemnew/show/U21609)
[U21643 公主的花加强版](https://www.luogu.org/problemnew/show/U2164
感谢MicDZ自动化脚本的提供： https://github.com/MicDZ/luogu-problem-difficulty-blog
也用于总结自身吧..
* 
[](h
爆 零 人（年年都有系列）
C C F 人
考场感叹人
# 声明（也就是废话）
- 一审打回，感谢一审管理员[Jiyuu_no_Tsubasa](https://www.luogu.com.cn/user/261981)的审核。
- 二审打回，感谢二审管理员[swiftc](https://www.luogu.com.cn/user/183154)的审核。
- 这是本蒟蒻的第一篇题解，激动不已。三审管理员求过~
- 代码请需要的同学谨慎使用。切
谨以此文纪念2025.01关服，本人肝了一年，陪伴本人走出MCJE萌新的服务器。
版权归Luogu UID 1053192所有，任何人未经允许不得抄袭、转载、复制。
如果小说的哪里让你感到不好，那么对不起，请你及时跟我说，我尽量修改。
小说中没有映射任何服务器中的玩家和组织，所以不要喷qwq
内容纯属虚构，~~危险动作，请勿模仿~~
对剧情及文章内容有任何建议的欢迎留言awa（目前看来只
国宴！来自我校六年级选手！虽然我知道尊重，但真的很好笑
```cpp
#include <bits/stdc++.h>
using namespace std;
struct node {
int ez[2];//儿子
int sjz, sz, zhi;//随机值，size(少有正常的）,值
} treap[1000010];
int len/*最新结点的下标*/, n, r11
欢迎报名[洛谷网校](https://class.luogu.com.cn/)，期待和大家一起进步！
本题考察结构体，排序。
我们用一个结构体 `Stu` 来存储每个学生的信息，包括名字 `nm`（字符串）和成绩 `sc`（整数）：
```cpp
struct Stu {
string nm;
int sc;
}a[105];
```
这样，我们可以直接使用 `a[i].n
## 状压 DP
状压 dp，说白了就是把dp状态转移的一些状态通过二进制压缩进一个集合里（不然十多维的数组写着不累吗）。如表示第 $a_1,a_2,a_3…a_i$ 这几个节点去过没有，可以用 $f_{a_1,a_2,a_3,…,a_i}=1$ 表示，也可以把这些节点变成一个二进制集合，即 $f_{2^{a_1-1}+2^{a_2-1}+2^{a_3-1}+…+2^{a_i-1}}=1$
##
摆
按 lxl 讲课的顺序来。
写了的题我打个 $\color{green}\surd $。
## 倍增值域分块
#### 引入：CF702F $\color{green}\surd $
按 $q$ 为第一关键字、$c$ 为第二关键字排序后，这相当于对于维护若干个二元组 $(a_i, b_i)$， $a_{i}\ge q$ 的二元组 $a_{i}-q, b_{i}+c$。
对于 $[0
与点分治类似，边分治也是用来处理树上链问题的一种方法。只不过点分治是找到重心，考虑经过重心的路径；边分治是找到“重心边”（两边子树大小的最大值最小的那条边），考虑经过这条边的路径。通常情况下用边分治解题会更好想，复杂度也与点度数无关；而点分树常常需要担心点度数的问题。
## 三度化
直接找“重心边”的复杂度是错的，可以被菊花图卡成 $O(n^2)$。所以需要进行三度化。这通常也是最难的部分之一
一块烤肉要么被不被带走，要么被带走但没有被吃，要么被带走又被吃了。因为只有最后一种情况对答案有影响，所以我们只需要求出每一块烤肉被哪个人吃了再更新他的美味值总和就可以了。
我们先对 $a,b$ 数组排序，二分找到最小的大于等于 $s_i$ 的 $a_{j_1}$ 和最大的小于 $e_i$ 的 $a_{j_2}$，可以发现处于 $[a_{j_1},a_{j_2}]$ 区间内的 $a_j$ 均满足
##### 著作时间：11/5
CSP-S大游祭
---
- 回到赛前20分钟，我走进了XXXX中学校，望着树上拉着的横幅2024年CSP-J/S指定认证考点，我第一次参加CSP-S（初赛48.5）心中莫名的紧张起来，但我也满怀期待的走进了~~祭墓场~~
- 考试前1分钟，我坐在考场上，旁边全是初高中，因为我才X年级，十分的紧张。随着铃声的响起，考试开始了。
- 有个十分~~奇
# 本文面向广大Florr.io玩家提供~~准确~~的最值(欢迎反馈)
## ${\color{red} 伤害之最}$
### 单发之神：
${\color{00ff99} TOP 1}$(图片缺失)
感觉大家都写得挺长啊，蒟蒻放一个稍微短点的代码供大家评赏（可在评论里尽情喷）
缩短思路：很多dalao用二维数组模拟3×3的方格，我用一维模拟：
设dalao们用的是a[x][y]，在我这里就变成了a[(x-1)×3+y]
例子：a[1][1]→a[1] a[2][3]→a[6] a[3][2]→a[8]
还有一个就是大家判定一条线时，很多人是如果全0，就是小a赢，全1就是uim赢，我觉得
主包手搓代码被识成AI了，大概是因为图灵测试人类相似度14%罢。
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
怎么不写矩阵乘法？
首先我们需要知道矩阵乘法，两个矩阵 $A$ 和 $B$ 相乘的结果是 $C$。
我们设 $A_{i,j}$ 表示 $A$ 矩阵的第 $i$ 行第 $j$ 个元素，$B_{i,j}$ 表示 $B$ 矩阵的第 $i$ 行第 $j$ 个元素，那么有公式 $C_{i,j}=\sum_k A_{i,k} \times B_{k,j}$。
好的，相信聪明的你已经学会了矩阵乘法，再来看
神题，模拟赛考到，不会，遂题解诞生。
读完题目，发现等价于给出若干 $[l_i,r_i],c_i$，需要将 $c_i$ 分为 $k,c_i-k$ 两部分加到 $[l_i,r_i]$ 亦或 $[1,l_i)\cup (r_i,n]$，要求最小化最后每个位置的值的最大值。
可以考虑一个调整法的思路，我们先假定全部分给 $[l_i,r_i]$，得到当前的解 $p_i$，同时将 $c_i$ 拆分为 $
|1|2|3|4|5|6|7|8|9|10|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|disc|tas/cutter|tas|tas|tas|tas|tas|soil|relic|sponge|
|basil|basil|basil|yucca|yucca|yucca|yucca|amulet|amulet|bandage/yucca|
如果没有 b
这是一个程序员用来测试编译环境是否正常的代码。
首先我们来简单介绍一下输出。
常用的有`cout`，`printf`，`puts`这三种。
`cout`所属的库为`iostream`。
剩下两个都属于`cstdio`库。
对于库的调用，我们要在程序开始时输入`#include<库名>`，并独自占据一行。
我会在下面的程序中加上注释，就是`//`之后的文字，不影响程序的运行。
我们现在
考虑维护每一行的和。
然后交换的时候考虑一个套路，就是交换两行时不真交换，只交换编号，然后对应 $i$ 就是 $id_i$。
这样对于一行 $+a$ 就是 $sum_{id_i}+a$。
```cpp
#include <iostream>
using namespace std;
int a[1001][1001];
int tagl[1001], tagr[1001];
int sum[
# floyd
## Part1
### 1. 算法介绍
Floyd 算法是一种用于解决**所有顶点对之间最短路径问题**的算法。可用于计算任意两点的最短路径及长度。时间复杂度为 $O(n^3)$ 。
### 2.核心思想
- 通过一个二维数组 $d[ ][ ]$ 来记录最短路径及长度。
- 通过三层for循环枚举 $k,i,j$ ,考虑以 $k$ 为中转点时，点 $i$ 到 $j$ 的
首先定义两个$\mathbb F$-线性空间$U,V$的张量积$U\otimes V$。我们说，以下三个线性空间是同构的:
- 所有$U,V$到$\mathbb F$的双线性函数。
- $U\times V$张成的空间，其中加法和数乘满足$(u_1,v)+(u_2,v)=(u_1+u_2,v),(u,v_1)+(u,v_2)=(u,v_1+v_2),\lambda(u,v)=(\lambd
## A
题意:给定 $n$ 个区间，问交集是否为空
```cpp
void solve() {
int n = read(),l = 0 ,r = 1e9;
for(int i =1; i <= n;i ++){
int L=read(),R=read();
l = max(L,l);
r = min(R,r);
}
### A
考虑先构造一个 $2\times \frac{2n}{\operatorname{lowbit}(n)}$ 的矩阵 $a$，第一行前一半放 $1$，后一半放 $0$，第二行全放 $0$。
接下来进行 $\log_2(\operatorname{lowbit}(n))$ 次如下操作：
- 设矩阵 $a$ 有 $n'$ 行 $m'$ 列，则将其扩展到 $2n'$ 行 $2m'$ 列。
私藏了好多，嘿嘿。
![](https://cdn.luogu.com.cn/upload/image_hosting/g5a6k27m.