后记

这段时间，花了不少精力来学习FAST协议，大致梳理下，相关博文： 1、FAST协议解析1 通过输入输出逆解析 https://blog.csdn.net/weixin_40402375/article/details/130479967 2、FAST协议解析2 FIX Fast Tutorial翻译 ......

## [T1](https://www.luogu.com.cn/problem/T372349)  ## ......

 ![img](https://img2023.cnblogs.com/blog/3213829/202308 ......

## [T1](https://www.luogu.com.cn/problem/T372016) 矩快或分治 ## [T2](https://www.luogu.com.cn/problem/T372017) 单条链用优先队列维护一个下凸包，多条链就合并一下 ## [T3](https://www ......

## [T1](https://www.luogu.com.cn/problem/T371500) 先应该想到 $n^2$ 做法，显然连线有交叉是不优的，所以连线不交叉。 ![img](https://img2023.cnblogs.com/blog/3213829/202308/3213829-2 ......

## [T1](https://www.luogu.com.cn/problem/T371084) 烧饼题，char类型最大为127 ## [T2](https://www.luogu.com.cn/problem/T371090) 暴力题，少考半个小时导致的少拿 $100$ 分 ## [T3](h ......

## 关于时间复杂度 ~~原来这么麻烦~~ 有5种符号： $Θ：Θ(𝑔(𝑛))=\{𝑓(𝑛):∃𝑐_1,𝑐_2,𝑛_0:∀𝑛≥𝑛_0:0≤𝑐_1 𝑔(𝑛)≤𝑓(𝑛)≤𝑐_2 𝑔(𝑛)\}$ $O：O(𝑔(𝑛))=\{𝑓(𝑛):∃𝑐_1,Ү ......

## [T1](https://www.luogu.com.cn/problem/T370107) 令 $DP_{i,k}$ 表示当前颜料为 $i$，前两个盘子状态为 $k$ 的最大收益，$O(16\times n)$ 的 DP ## [T2](https://www.luogu.com.cn/pr ......

## T1 dp注意赋初值 每个点记前 &k& 大的和，暴力转移 ## T2 放到一个序列上双指针，覆盖所有国家 ## T3 ![img](https://img2023.cnblogs.com/blog/3213829/202308/3213829-20230819174428515-627651 ......

## [T1](https://www.luogu.com.cn/problem/T369254)  ## [ ......

## [T1](https://www.luogu.com.cn/problem/T368795) 原来组合数有通项公式（~~大雾~~） **线性求逆元**： 显然，$1^{-1}\equiv 1(\operatorname{mod} p)$ 令 $k=\lfloor \frac{p}{i} \rf ......

## T1 简单题，预处理每段线路要走的次数 $cnt_i$，如果 $c_i+b_i\times cnt_i\le a_i\times cnt_i$ 则买票 ## T2 原题，考虑逆向思考 倒叙枚举操作，将待查询的点还原到原序列上 ## T3 好题 对于每个点 $(i,j)$，考虑以这个点为 左上角 ......

## T1 贪心，按 $a$ 递增排序后选择连续一段 对 $b$ 做前缀和 $preb$ 区间 $[l,r]$ 价值为 $preb_r-preb_{l-1}-(a_r-a_l)$ 其中 $preb_{l-1}+a_l$ 可以 $O(n)$ 预处理最小值 枚举 $r$ 即可，复杂度 $O(n)$ ## ......

## T1 简单的最短路 到终点时不用等红灯，不然会挂40pt ## T2 记 $f(i,j)$ 表示跳到 $(i,j)$ 最少使用的体力。 那么转移就是枚举上一个位置然后加上曼哈顿距离求最小值。 考虑优化，我们注意到如果转移都在左上的话坐标正负的贡献是固定的, 所以可以使用数据结构维护。先按照一维 ......

## T1 简单题，全排后中缀转后缀 ## T2 优化1：从 $(n,m)$ 点开搜 优化2：背包预处理能拼出哪些数 ## T3 ![img](https://img2023.cnblogs.com/blog/3213829/202308/3213829-20230801141830586-1932 ......

Day1 被找规律随机区分 $35$ 分。Day2 以我现有的水平已经无力回天了，d2T3 却还挂了 $35$ 分。 连队线的边都没碰到，只混到了 $100$ 多名的 Ag。 我不愿回忆这场考试的任何细节，知道寄了就行了。 分数是从低往高排的。nfls 的众人中，我是第一个上去的。为什么在公布 Ag ......

## T1 被坑了，是树的直径 ## T2 bitset 邪教 二维能开 $5e4$ 没想到吧 ## T3  ......

## T1 倒着推  ## T2 记每个字母上次出现位置 $f_i$，对应的 $f_i$ 都相等时字符串等价， ......

## T1 简单题，筛的时候记点东西 ## T2 筛完预处理下每个数最大质因数，然后暴力找路径就行 ## T3 分段打表可过，每段长 $2\times10^5$ 差不多就过了 正解： 考虑贡献，每个因数 $i$ 出现了 $\frac{n}{i}$ 次 ## T4 ![img](https://img ......

## T1 异或和塞到状态里就不用管路径相交了 式子： $$ f_{i,j,k\operatorname{xor}G_{i,j},0}=f_{i-1,j,k,0}+f_{i,j-1,k,0} $$ $$ f_{i,j,k\operatorname{xor}G_{i,j},1}=f_{i-1,j,k, ......

## T1 简单题，毒瘤数据 ## T2 ~~找规律~~  ## T3 dfs树 啊？ ## T4 dp ![ ......

## T1 不用估价，被骗了 正常bfs即可 ## T2 会爆__int128，不用记 $a+kb$ 的和，一点一点减 ## T3 ![img](https://img2023.cnblogs.com/blog/3213829/202307/3213829-20230726141147223-209 ......

## [T1](https://noip.ac/rs/show_problem/4097) 小模拟 ## [T2](https://noip.ac/rs/show_problem/4099) 考时过了 dp，用树状数组优化就还了 $f_{i,j} = \sum_{k=1}^{i-1}f_{k,j-1 ......

## [T1](https://noip.ac/rs/show_problem/4089) ### 惨案一：80pt代码忘交了 正解： 开个桶 ~~~cpp cnt[0]++; for (int i = 1; i <= n; i++) { for (int j = 1; j <= tot; j++) ......

# 我的图逃走了 ## 考试 T1 瞎搞题（老师认证） T2 矩阵找最大环，可以推出一个只含两个点3个坐标的式子，$O(n^3)$ 找最大值，再枚举剩下一个点 $n*m \le 2e5$，说明 $n$ 或 $m$ 小于400，$O(n*m+400)$ 可以允许 T3 做法好想，但 缩点 + 分数规划 ......

## T1 序列上  树上 ![img](https://img2023.cnblogs.com/blog/3 ......

## 我去，崩原铁  ## [Kuglarz](https://www.luogu.com.cn/proble ......

## [合并果子](https://www.luogu.com.cn/problem/P6033) 桶排序，开两个队列，排序后两个队列取两次较小值，放到另一个队列里 ## [序列合并](https://www.luogu.com.cn/problem/P1631) 取 $(A_i,B_j)$,插入 ......

## P6090 题解 [传送门](https://www.luogu.com.cn/problem/P6090) 神仙题 ## 先考虑 $O(|\Sigma| ^8)$ 做法： $\Sigma$：字符总数，本题为 大写字母 $26$ 个+小写字母 $26$ 个+数字 $10$ 个。 预处理两个字母 ......

听不懂（悲） ## DP知识 [刷表和填表](https://blog.csdn.net/zpf1998/article/details/121279681) ## [Sleeping Cows P](https://www.luogu.com.cn/problem/P7154) 主要难点在提前钦定 ......