后记
FAST协议详解5 后记
这段时间,花了不少精力来学习FAST协议,大致梳理下,相关博文: 1、FAST协议解析1 通过输入输出逆解析 https://blog.csdn.net/weixin_40402375/article/details/130479967 2、FAST协议解析2 FIX Fast Tutorial翻译 ......
8.25 后记
## [T1](https://www.luogu.com.cn/problem/T372349) ![img](https://img2023.cnblogs.com/blog/3213829/202308/3213829-20230827160907969-1985028821.png) ## ......
8.26 后记
![img](https://img2023.cnblogs.com/blog/3213829/202308/3213829-20230827161222973-186149494.png) ![img](https://img2023.cnblogs.com/blog/3213829/202308 ......
8.24 后记
## [T1](https://www.luogu.com.cn/problem/T372016) 矩快或分治 ## [T2](https://www.luogu.com.cn/problem/T372017) 单条链用优先队列维护一个下凸包,多条链就合并一下 ## [T3](https://www ......
8.23 后记
## [T1](https://www.luogu.com.cn/problem/T371500) 先应该想到 $n^2$ 做法,显然连线有交叉是不优的,所以连线不交叉。 ![img](https://img2023.cnblogs.com/blog/3213829/202308/3213829-2 ......
8.22 后记
## [T1](https://www.luogu.com.cn/problem/T371084) 烧饼题,char类型最大为127 ## [T2](https://www.luogu.com.cn/problem/T371090) 暴力题,少考半个小时导致的少拿 $100$ 分 ## [T3](h ......
8.21 后记
## 关于时间复杂度 ~~原来这么麻烦~~ 有5种符号: $Θ:Θ(𝑔(𝑛))=\{𝑓(𝑛):∃𝑐_1,𝑐_2,𝑛_0:∀𝑛≥𝑛_0:0≤𝑐_1 𝑔(𝑛)≤𝑓(𝑛)≤𝑐_2 𝑔(𝑛)\}$ $O:O(𝑔(𝑛))=\{𝑓(𝑛):∃𝑐_1,Ү ......
8.20 后记
## [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 ......
8.19 后记
## T1 dp注意赋初值 每个点记前 &k& 大的和,暴力转移 ## T2 放到一个序列上双指针,覆盖所有国家 ## T3 ![img](https://img2023.cnblogs.com/blog/3213829/202308/3213829-20230819174428515-627651 ......
8.18 后记
## [T1](https://www.luogu.com.cn/problem/T369254) ![img](https://img2023.cnblogs.com/blog/3213829/202308/3213829-20230818205318087-164231548.png) ## [ ......
8.17 后记
## [T1](https://www.luogu.com.cn/problem/T368795) 原来组合数有通项公式(~~大雾~~) **线性求逆元**: 显然,$1^{-1}\equiv 1(\operatorname{mod} p)$ 令 $k=\lfloor \frac{p}{i} \rf ......
8.4 后记
## T1 简单题,预处理每段线路要走的次数 $cnt_i$,如果 $c_i+b_i\times cnt_i\le a_i\times cnt_i$ 则买票 ## T2 原题,考虑逆向思考 倒叙枚举操作,将待查询的点还原到原序列上 ## T3 好题 对于每个点 $(i,j)$,考虑以这个点为 左上角 ......
8.3 后记
## 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)$ ## ......
8.2 后记
## T1 简单的最短路 到终点时不用等红灯,不然会挂40pt ## T2 记 $f(i,j)$ 表示跳到 $(i,j)$ 最少使用的体力。 那么转移就是枚举上一个位置然后加上曼哈顿距离求最小值。 考虑优化,我们注意到如果转移都在左上的话坐标正负的贡献是固定的, 所以可以使用数据结构维护。先按照一维 ......
8.1 后记
## T1 简单题,全排后中缀转后缀 ## T2 优化1:从 $(n,m)$ 点开搜 优化2:背包预处理能拼出哪些数 ## T3 ![img](https://img2023.cnblogs.com/blog/3213829/202308/3213829-20230801141830586-1932 ......
NOI2023 后记
Day1 被找规律随机区分 $35$ 分。Day2 以我现有的水平已经无力回天了,d2T3 却还挂了 $35$ 分。 连队线的边都没碰到,只混到了 $100$ 多名的 Ag。 我不愿回忆这场考试的任何细节,知道寄了就行了。 分数是从低往高排的。nfls 的众人中,我是第一个上去的。为什么在公布 Ag ......
7.31 后记
## T1 被坑了,是树的直径 ## T2 bitset 邪教 二维能开 $5e4$ 没想到吧 ## T3 ![img](https://img2023.cnblogs.com/blog/3213829/202307/3213829-20230731151002718-2098855936.png) ......
7.30 后记
## T1 倒着推 ![img](https://img2023.cnblogs.com/blog/3213829/202307/3213829-20230730140346193-656588523.png) ## T2 记每个字母上次出现位置 $f_i$,对应的 $f_i$ 都相等时字符串等价, ......
7.29 后记
## T1 简单题,筛的时候记点东西 ## T2 筛完预处理下每个数最大质因数,然后暴力找路径就行 ## T3 分段打表可过,每段长 $2\times10^5$ 差不多就过了 正解: 考虑贡献,每个因数 $i$ 出现了 $\frac{n}{i}$ 次 ## T4 ![img](https://img ......
7.28 后记
## 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, ......
7.27 后记
## T1 简单题,毒瘤数据 ## T2 ~~找规律~~ ![img](https://img2023.cnblogs.com/blog/3213829/202307/3213829-20230727140518357-473535594.png) ## T3 dfs树 啊? ## T4 dp ![ ......
7.26 后记
## T1 不用估价,被骗了 正常bfs即可 ## T2 会爆__int128,不用记 $a+kb$ 的和,一点一点减 ## T3 ![img](https://img2023.cnblogs.com/blog/3213829/202307/3213829-20230726141147223-209 ......
7.25 后记
## [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 ......
7.24 后记
## [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++) ......
7.21 后记
# 我的图逃走了 ## 考试 T1 瞎搞题(老师认证) T2 矩阵找最大环,可以推出一个只含两个点3个坐标的式子,$O(n^3)$ 找最大值,再枚举剩下一个点 $n*m \le 2e5$,说明 $n$ 或 $m$ 小于400,$O(n*m+400)$ 可以允许 T3 做法好想,但 缩点 + 分数规划 ......
7.20 后记
## T1 序列上 ![img](https://img2023.cnblogs.com/blog/3213829/202307/3213829-20230720084539967-292438070.png) 树上 ![img](https://img2023.cnblogs.com/blog/3 ......
7.19 后记
## 我去,崩原铁 ![img](https://img2023.cnblogs.com/blog/3213829/202307/3213829-20230719084926190-308879560.png) ## [Kuglarz](https://www.luogu.com.cn/proble ......
7.18后记
## [合并果子](https://www.luogu.com.cn/problem/P6033) 桶排序,开两个队列,排序后两个队列取两次较小值,放到另一个队列里 ## [序列合并](https://www.luogu.com.cn/problem/P1631) 取 $(A_i,B_j)$,插入 ......
7.17后记
## P6090 题解 [传送门](https://www.luogu.com.cn/problem/P6090) 神仙题 ## 先考虑 $O(|\Sigma| ^8)$ 做法: $\Sigma$:字符总数,本题为 大写字母 $26$ 个+小写字母 $26$ 个+数字 $10$ 个。 预处理两个字母 ......