NOIP 2023 退役记
前几次: NOIP2022游寄 CSP-S 2023 复赛
博客 (Obsidian)
按更新时间排序
按年份归档
按标签归档
Recent Posts
CSP-S 2023 复赛
考场上 T1, T3 做出来了 T2, T4 CF 上有原题 这里就记录一下 T2 正解 T2 原题 做法1：dp 令 $f_i$ 从 $i$ 开头的可消去子串的数量 $nxt_i$ 是使得 $\left[i,j\right]$ 可消去的最小的 $j$ 那么 $f_i=f_{nxt_i+1}+1$ 如果 $nxt...
幻影坦克
所谓的幻影坦克是一类图片，在预览和点开的时候显示不一样的图
不动点法求数列通项
今天复习数列，碰到了这个东西。
最小费用最大流
一个重要的定理(Negative Cycle Optimality Conditions)：一个流的费用是最小的(在大小相同的流之中)，当且仅当它对应的残量网络中不存在负环。
集合DP
我们想要知道的是：对于某个集合$S$, $\sum\limits_{R\subseteq S}{x(R)}$ (子集dp) 或者 $\sum\limits_{U\supseteq R\supseteq S}{x(R)}$ (超集dp)，$x$表示集合的某个性质
Dev C++ 翻新
Dev C++ 是一个很常用的 C++ IDE，但是它的年代有点太老了，所以它现在用它可能有一些问题，所以我们需要翻新它。
wqs二分
原始论文
两道有意思的微积分题目
第一题
2维DP四边形不等式优化（决策单调性优化）
对于区间DP问题，都可以列出转移方程： $$ f[i][j] = \smash{\displaystyle\min_{i \le k \le j-1}} F(i, j, k) $$
1维DP四边形不等式优化（决策单调性优化）
对序列切割问题，令 $f[i]=\smash{\displaystyle\min_{0 \le j \le i-1}} F(j, i)$，即 $1$ 到 $i$ 的最优解
VSCode 配置
推荐OI类拓展 Github Theme Material Icon Theme Competitive Programming Helper (cph) TabOut C/C++ Code Runner Error Lens
快读模板
// orz laofudasuan // modified
毒瘤题，纪念一下
题目
图床炸了
云图床好像在进行维护工作，虽然上面说“请过几分钟回来”，但是它已经维护了好几天了...
变质量系统中力与动量的关系
由牛顿第二定律可以得出$m$不变时 $$\vec{F}=m\vec{a}=m\frac{d\vec{v}}{dt}=\frac{d\vec{p}}{dt}$$
Konig定理和匈牙利算法(其实是增广路算法)
Konig定理
网络流入门
注：本文只考虑整数容量、整数流，但一部分论证可以直接推广到非整数流的问题上
写数学公式太难受了
Jekyll有时候会把latex公式里的一些符号当成markdown的符号处理掉，然后mathjax就不能正常渲染数学公式了，需要在一些地方用反斜杠escape掉那些字符才行，但是这么做我的这些latex就不能在其他地方正常渲染了...
再看 OSU 拓展
书接上文
树状数组BIT的正确性的证明
出处1 出处2
OSU 拓展
题面 B 君并不喜欢 OSU，但是 B 君觉得 OSU 这个题不错。
洛谷 P1654 OSU
定义
NOIP2022游寄
T1 (25/100) 简单题，但是我错误得估计了复杂度 $ O(Tn^2m) $ 不够过1000，其实我只要再做个前缀和应该就能100了
线段树技巧：处理负数端点值
如果线段树端点值可以取负数，那么应该用$ mid = \left[ \frac{l+r-1}{2} \right] $计算中点（除法向0取整，可以直接用c++的整数除法）
memset和整数数据范围
memset 初值
Floyd和倍增Floyd
1.Floyd
Dijkstra最短路算法
算法过程 假设我们用数据结构 $f$ 维护每个点的 $dis$ 初始化 $dis_S=0$ 并加入 $f$, 其余点的 $dis$ 设为无限大, 所有点标记为未访问 重复3-5，直到没有未访问的点，算法结束 从 $f$ 中选出 $dis$ 最小且未访问的点，记为 $u$（$f$中查询） 把 $u$ 标记为已访问...