view in Push_Y’s blog

view in 博客园

view in 洛谷博客

2021.01.26 来WZHS了有望复出

2021.01.31 发现东西都忘光了，得从基础的基础开始复习了。。。

2021.03.10 发现真正做题之后根本不会记得来这里记录，很能拖更啊。。。

2021.05.10 月赛后涨了30左右，第一次红名 QwQ

2021.05.12 搭建了新的博客

2021.06.24 中考阅卷占用的机房回归了，由于在机房，只能在洛谷博客上更了。

2021.07.12 正式拿到了WZHS的录取通知书。

2021.08.21 明天新生报道了，要正式开启高中生涯了。

2021.09.24 晚上20:21野狐5段了

2021.10.06 将目标中的 p 改回了 t 。

2021.10.16 第一次尝试咖啡，准备在一周后的csp考场上使用。

2021.10.19 传6个参数的merge函数会编译错误！！！

2021.11.03 夜聊讨论概率问题被宿管抓住，次日在班主任眼皮底下罚跑10圈QwQ

专题

以下专题按 Push_Y 复出后接触的时间先后排列

基础dp

状压dp

  • 2021.02 写了一些比较简单的状压，就不放上来了

  • 2021.06.29 [WZOI]奶牛的食物 从02.04的50分一直咕到今天闲着没事干才改

  • 状压难起来还是挺难的QwQ

  • 2021.06.29 [WZOI]简单签到题

    • 我的代码上题解了！其实近似于抄的

    • 一个f[i]存子树状态为i的有根树方案数，一个sum[i]存含状态i的森林方案数

  • 2021.06.29 UVA12235 Help Bubu ATue秒掉的黑题，但我觉得挺难的

  • 2021.06.29 Sgu P131铺地板 有时状压用递归的形式来写很方便

  • 2021.06.30 P3204 [HNOI2010]公交线路

    • 题意比较难理解吧。晚上做的这题，那个转移让我心态崩了，浑身无力直接瘫电脑前了。

树形dp

分治

基环树

仙人掌

树链剖分

长链剖分

cdq分治

数位dp

数据结构优化dp

  • 某月某日 基站选址

  • 2021.06.28 ABC207E

    • 赛时只想到 $O(n^3)$ ，原来异或也能前缀和，前缀和优化一下就能 $O(n^2)$ 过了

  • 2021.07.09 [十一集训A班day2]计

    • 去年十一的时候考的题。当时可能并没有完全理解。

    • 前缀和不一定是 $sum_i=a_1+a_2+…+a_n$ ，像这题就是 $sum_i=sum_{i-2}+a_i$ 。

  • 2021.07.12 [ABC209F] Deforestation 还是前缀和优化。近阶段其实很多dp优化都是用前缀和优化。

  • 2021.07.28 [CE2003] Minimizing maximizer 经典线段树维护dp，写法跟线段树维护最长上升子序列很像。

bitset优化！

决策单调性/单调队列/斜率优化dp

  • 疑难点：推柿子；单调队列里 $l$ 与 $r$ 的关系（是 $＜$ 还是$≤$），以后习惯 l=r=1;q[1]=0; 并且维护队列部分用 l<r。

  • 2021.4.12 P3648 [APIO2014]序列分割 看着题解写完了一些斜率优化题之后，这题开始尝试自己推柿子

  • 2021.4.14 CF311B Cats Transport

    • 题目给的信息过多，难想到先按“每只猫子所需出发时间”排序再斜率优化。
    • 粗略一看题解区绝逼互抄的，既然大家都想到开一个 $g[]$ 存上一轮状态了为什么 $f[]$ 不用滚动？

  • 2021.05.30 [NOI2007] 货币兑换

    • 笔记
    • 2021.06.29 周神今天讲了下决策单调性和斜率优化，准备写篇笔记记下心得

  • 2021.06.29 P4544 [USACO10NOV]Buying Feed G 单调队列

  • 2021.06.30 P2900 [USACO08MAR]Land Acquisition G/土地购买 很好的联系推式子的题了，但预处理折腾了我好久。。。

强连通分量 和 2-SAT

左偏树

矩阵

  • 2021.04.24 P2151 [SDOI2009]HH去散步 点边转换处理不能走重边

  • 2021.04.24 P2886 [USACO07NOV]Cow Relays G 定义新的矩阵乘法规则

    • 2021.06.25 听周神讲了才知道，原来min/max(a[i][k]+b[k][j])也可以当做不规则的矩乘，ATue表示其实就是说符合结合律的运算都可以套矩乘。

平衡树

整体二分

点分治

分块

启发式合并

主席树/可持久化线段树

线段树合并

三分

  • 单峰函数求峰值，可以求导后二分，也可以用三分。

  • 2021.07.05 [十一集训B-day1]tree 形如对于若干条直线 $f_i(x)$，在每个 $x$ 取 $F(i)=\max/\min{f_i(x)}$，则得到的 $F(i)$ 为一个单峰函数。然后三分求解。

1
2
3
4
5
6
7
while(l<=r){
    ll mid=(r-l)/3,lmid=l+mid,rmid=r-mid;
    ll k1=solve(lmid),k2=solve(rmid);
    if(k1<k2) ans1=lmid,r=rmid-1;
    else ans1=rmid,l=lmid+1;
    ans2=min(ans2,min(k1,k2));
}

博弈论

  • 2021.07.07 [ABC206F]Interval Game 2 第一次写博弈论的题居然还是在VP的时候（看了Editorial就AK了）

  • 2021.08.25 CF455B A Lot of Games

    • 开始以为就是个 Trie SBT，原来是 SBT 套 SBT。
    • 给出的 $k$ 自然是有用的，可以故意输掉第 $k-1$ 局来获得后手换来第 $k$ 局的胜利。

数论

计数dp

题单

XJ提高过关

CF455B in 博弈论

BZOJ

#3705 对称的正方形 二维哈希+二分

国家集训队作业

Link

思维题

太巧秒了系列

Problem

  1. [WZOJ#283] 初始在 $0$ 号点，每秒 $\frac{1}{4}$ 概率向左/右移动 $1$ 个单位，$\frac{1}{2}$ 的概率不动。问 $t$ 秒后到达位置 $p$ 的概率。

Toturial

  1. [WZOJ#283] 将 $1$ 秒延续到 $2$ 秒，每秒 $\frac{1}{2}$ 的概率向左/右移动 $1$ 个单位，与原问题等价。于是答案就是 $\frac{\tbinom{2t}{t+p}}{2^{2t}}$。

Level 1

Problem

  1. [WZOJ#400] 对 $n*n$ 矩阵求满足对任意 $1 \le i,j \le n$ 有 $f_{i,j}=\min ( x_i ,x_j )$ 的排列 $x$ 的个数，并输出字典序最小的一个排列。

  2. [WZOJ#403] $n$ 个盘子 $m$ 个柱子的汉诺塔问题，求第 $1$ 个柱子 $n$ 个盘子全移到第 $m$ 个柱子的最小步数。

Toturial

  1. [WZOJ#400] 找到 $f_{i,j}=n-1$ ，则 $x_i$ 与 $x_j$ 一个为 $n-1$ 一个为 $n$，且第 $i$ 行其余的 $x_k$ 都等于 $f_{i,k}$。

  2. [WZOJ#403] 设 $f_{i,j}$ 表示 $i$ 个盘子 $j$ 个柱子的最小步数，显然有 $f_{i,j}=\min { 2 \times f_{k,j} + f_{i-k,j-1} }$

Level 2

Problem

  1. [WZOJ#227] 维护一个长度为 $n$ 的序列，要求：1.单点修改。2.区间查询是否存在区间内三个数构成三角形并求周长最大的可能值。

Toturial

  1. [WZOJ#227] 通过类似斐波那契的数列发现，只用考虑前 $50$ 大的数。数据结构再维护一下。

「实时更新」查漏补缺

  • 2021.03.05 离散化

  • 2021.03.16 准备系统学字符串算法

  • 2021.03.17 老惨了发现虚树已经忘了无数遍了。。。板子集合

成就

  • 2021.10.06 由于 ss 催更，更一发吧。

第一次拿榜1也挺惊喜的其实。

  • 2021.10.17

第二次拿榜一也挺惊喜的其实。

  • 2021.10.18

惊喜的发现：

然而：

一些题

2020tg10

day1

A. 把 $n$ 划分成尽量少的数字之和，每个数都形如 $3k^3 - 3k +1 (k\ge 1)$。

B. 求给定字符串中 $AA^rA$ 串的数量（其中 $A^r$ 表示 $A$ 的反串）。

Tutorial

A. mod 3 之后是结论题。

B. 先 Manacher，再在树状数组中找满足 $i-man_i \le j$ 的 $j$ 的数量，再把 $i$ 加入到树状数组中。