第一次复出后的记录

Push_Y · 2021-01-31 16:23:26 · 个人记录

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的录取通知书。

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

基础dp

• 2021.01.31 UVA437 The Tower of Babylon

状压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

• 2021.01.31 [POI2014]FAR-FarmCraft 中间遍历子树顺序不能换

• 2021.04.15 [WZOI]粉兔找妹子 从2.13的60分（暴力）一直咕到今天才补。今天重写了个换根dp。好难改

分治

• 2021.02.17 平面最近点对（加强版） 平面分治，关键在合并

• 2021.03.10 摆放L

  • 好巧妙的构造！
  • 每次把棋盘分割成4份进行分治，使得每份各有一黑格

• 2021.07.05 [十一集训A班day1]奖杯

基环树

• 2021.04.19 P5022 [NOIP2018 提高组] 旅行 拓扑排序找环，O(n^2) 暴力断边dp

仙人掌

树链剖分

• 2021.07.18 [POJ3728]The merchant 树剖写的话要转好几下

长链剖分

cdq分治

• 2021.05.30 [NOI2007] 货币兑换

  • 笔记

数位dp

• 2021.03.30 P4127 [AHOI2009]同类分布 枚举模数这里有点难懂

• 2021.03.30 P3413 SAC#1 - 萌数 转移方程里的 k 有点难懂

• 2021.03.30 准考证 适合作为板子题之后自己写的第一题

数据结构优化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优化都是用前缀和优化。

决策单调性/单调队列/斜率优化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

• 2020.10.04 写了2-SAT模板题题解

• 2021.04.21 写了题解 [POI2001] 和平委员会

左偏树

• 学习笔记

矩阵

• 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表示其实就是说符合结合律的运算都可以套矩乘。

平衡树

• Splay学习笔记

• 2021.06.24 维护数列 好板子

• 2021.06.25 [bzoj3678]/[wzoi] wangxz与OJ

  • 开始看似就是维护数列那题的子问题，结果T飞了。

  • 此题插入区间时不直接插入完，而是插入一个结点并保留区间信息，用到时再下传。

• 2021.06.25 P3960 [NOIP2017 提高组] 列队

  • 笔记

• 2021.07.12 P3215 [HNOI2011]括号修复 / [JSOI2011]括号序列 请来麻大师改了半天，错误居然出现在k-=sz[ch[x][0]]+1;老黄油手了。

• 2021.07.12 P4036 [JSOI2008]火星人 初始化忘记rt=1了????

整体二分

• 2021.05.01 AC了板子 P3834 【模板】可持久化线段树 2（主席树） 和 P2617 Dynamic Rankings

• 2021.05.03 P3527 [POI2011]MET-Meteors

  • 感觉每个询问的id都是它序号本身，所以ans[q[i].id]=l写成了ans[i]=l，不知道为什么错。

• 2021.05.04 P3242 [HNOI2015] 接水果 这题主要难在树上路径覆盖条件的转化

• 2021.05.04 P3332 [ZJOI2013]K大数查询

  • 区间询问区间查询，数据结构选择线段树

  • 之前的板子和例题都是第k小，这题要q1和q2反过来

点分治

• 2021.05.05 P4178 Tree 经典题

• 2021.05.05 P3806 【模板】点分治1

• 2021.05.08 [bzoj3648]寝室管理/[wzoi]点分治2

  • 吐了，改了一晚上，最终是 ATue 神佬找到了错误QwQ。。。

  • upd:05.09 bzoj上还过不了，可能像 ATue 说的那样环编号得是在环上连续的吧，懒得改了

• 2021.05.09 [hdu4812]D Tree/[wzoi]点分治3

  • 这时候才学习了逆元，这题用 O(p) 递推求出 1 到 p-1 每个数的逆元

  • 个别数组要开到 p 那么大

分块

• 2021.05.10 P4168 [Violet]蒲公英

启发式合并

• 2021.06.24 P3201 [HNOI2009] 梦幻布丁

• 2021.07.01 [bzoj4919][Lydsy1706月赛]大根堆

主席树/可持久化线段树

• 2021.06.26 P3834 【模板】可持久化线段树 2（主席树） 这回不是用整体二分做的了

• 2021.06.26 SP1487 Query on a tree III 求下dfs序就可以套上一题板子了。注意点是点的编号和主席树结点序号不同。。。

• 2021.06.28 P4197 Peaks

• 2021.06.28 P3402 可持久化并查集 主席树维护历史版本的并查集数组 fa[] ，不路径压缩

• 2021.06.30 P2839 [国家集训队]middle

• 2021.07.01 Travel To The Ugly 链接先不放了，但ac出的题是真的强

线段树合并

• 2021.06.28 P3521 [POI2011]ROT-Tree Rotations

• 2021.06.28 P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并

三分

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

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

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.07.09 POJ3292 Semi-prime H-numbers UVA11105 H-半素数 Semi-prime H-numbers 素数、同余

• 2021.07.09 POJ1061 青蛙的约会 P1516 青蛙的约会 扩展欧几里得算法

• 2021.07.09 POJ1845 Sumdiv P1593 因子和

  • 挺综合的一道数论题。

  • 运用了唯一分解定理、约束和公式、递归二分求等比数列、快速幂。

• 2021.07.09 P1495 【模板】中国剩余定理(CRT)/曹冲养猪 CRT 板子

• 2021.07.10 POJ1006 Biorhythms 运用了CRT

• 2021.07.11 POJ2115 C Looooops 扩欧。long long类型的要用1ll<<k，而不是1<<k。

• 2021.07.12 CF1543A Exciting Bets gcd的一个很trivial但不常用的性质吧，gcd(a,b)=gcd(a-b,b)

「实时更新」查漏补缺

• 2021.03.05 离散化

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

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