停课记录

· · 个人记录

开个坑记录一下难得的停课生活，监督一下自己

Day 1

学习期望相关

P1654 OSU!

P1365 WJMZBMR打osu!

CF235B Let's Play Osu!

比较常见的期望 dp，实际上这三题区别不大，有点类似于三倍经验（

P4316 绿豆蛙的归宿

图上 dp，跟期望相关

待填：

CF280C Game on Tree （2020.10.20）

T147584 深海少女与胖头鱼 （2020.10.22）

P3232 [HNOI2013]游走 （2020.10.21）

Day 2

CF280C Game on Tree （填坑）

树上期望，学到了

P4206 [NOI2005]聪聪与可可

图上动点期望

P3802 小魔女帕琪

排列相关期望？只想到了等概率性，离正解还缺点想法

CF1428F Fruit Sequences （修锅）

将前几天写的代码调了下，发现是long long（

复习：

高斯消元

并顺便学习：高斯-约旦消元

感觉跟普通的高斯消元区别不大，大概就是确定系数后从 i+1 开始消元和从 1 开始消元的区别

P3389 【模板】高斯消元法

写了遍板子，计划明天做几题然后和图上期望一起做题

Day 3

今日不行，做题效率有点低（

一天三题我是屑（

P4035 [JSOI2008]球形空间产生器

高斯消元练手，构造一个答案矩阵作为等式右边每次进行加减即可

P3232 [HNOI2013]游走 （填坑）

高斯消元求期望的套路，等号右边构造一个状态矩阵记录每个点的权重，最后用每个点去统计每条边的权重，按照边权的大小往里放就可得到答案，还是挺有意思的

CF802L Send the Fool Further! (hard)

树上消元，好像也是线性高斯消元，新的黑科技，明天看看证明

待填：

P5516 [MtOI2019]小铃的烦恼 （2020.10.22）

看了一半题解没看完（，不知道后半部分那很套路的想法为啥行不通，明天顺便看一下线性消元的思想

P5643 [PKUWC2018]随机游走

Day 4

屑（

P5516 [MtOI2019]小铃的烦恼 （填坑）

对条件期望理解更深了一些，列式子应为总期望

P6858 深海少女与胖头鱼 （填坑）

转移其实没错，只是细节出了点问题，改完就过了

P4284 [SHOI2014]概率充电器

挺有意思，先要想到根节点只求子树的正确性，然后再用换根dp做

屑屑屑（

明天开线性基（？）

Day 5

nmd想了一下上午随机游走发现自己是sb

下午+回家路上看了看线性基，感觉还行

P3812 【模板】线性基

板子题，贪心搞一波就行

P3265 [JLOI2015]装备购买

正版线性基/jk，按花费排序之后每次消元

P3857 [TJOI2008]彩灯

每次消元，最后解出来的就是线性无关的元，答案为 2^{\left\vert B\right\vert}

P4570 [BJWC2011]元素

按魔力值排序，消元

待填：

P3211 [HNOI2011]XOR和路径

Day 6

P4301 [CQOI2013] 新Nim游戏

由 nim 游戏知道异或和维持让对面是 0 的情况必赢，而对面有可能在整堆操作后让我们变成 0，而异或和变成 0 说明这是线性有关的，所以我们第一次只要将他取成线性无关的就可以避免这种情况

P3211 [HNOI2011]XOR和路径

由于异或二进制下两两无关，所以按位考虑概率算贡献，乘上 2^k 就是第 k 位的期望

打了 cf 1436 div2 赛时 4 题

Day 7

回了家状态确实不太行，自己水平还不够扎实，这两天打的 cf 状态差距有点大，多vp一下以前的 cf div2吧

P4151 [WC2011]最大XOR和路径

很巧妙的一道题，非常适合异或和与图论的结合，由于异或两两相消，所以一条路径 k 走两遍贡献为 0，然后就可以用图中的所有环去增广想走的路径，所以把环都扔进线性基里。然后路径其实可以任选，因为当前路径与最优路径肯定形成环（起点终点都想同），然后把当前路径和这个环异或一下就得到了最优路径。

打了 cf 1435 div2 赛时 2 题

明天争取搞完线性基，然后去练 dp （？）

Day 8

CF1436E Complicated Computations

想了一上午就补了一道题（

本题其实并不难，只是赛时思想和赛后思想都只想到了一部分，拼起来就过了

P4839 P哥的桶

线性基合并板子，套个线段树随机数据就跑过去了

P4869 albus就是要第一个出场

有个结论是线性空间里出现的每一个数的次数都是相同的，具体证明看题。用这个结论映射到线性基上求出比他小的数的个数再乘上 2^{|V|-|B|} 即可

虽然说线性基还是没写完，但还是跳了（

Day 9

早上做题效率越来越低了（

P4127 [AHOI2009]同类分布

数位dp，列出式子后发现可以枚举每一位上的和，然后记忆化dfs一波就切了

P1156 垃圾陷阱

背包，按时间排序，然后枚举前 i 个叠的高度，里面存饱食度，然后就是背包了

P5322 [BJOI2019]排兵布阵

枚举城堡数，然后求出打赢每个玩家所需的兵力，就变成了m放到n个地方求得分max，记忆化搜索就好了

Day 10

啥题都没写

出模拟赛去了

Day 11

啥题都没写

终于要搞定了

Day 12

咕咕咕

Day 13

月赛 T1 不加特判过不了，找原因的时候顺手 hack 了好多人

找出题人要数据后发现是数据造的有问题，数据范围写小了

待填： [P7044 「MCOI-03」括号](https://www.luogu.com.cn/problem/P7044) （2020.11.4） ## Day 14 nmd 对着这题想了一整天，结果还是没搞出来，弃疗了 晚上的 cf 切完 abc 后不会 de 爬了（ ## Day 15 [CF1406E Deleting Numbers](https://www.luogu.com.cn/problem/CF1406E) 第一次做交互，不太一样的思想 想到 $< \sqrt{N}$ 的因子只有 $\sqrt{N}$ 个，然后这部分就暴力查询幂次，实际上也可以二分优化 然后对于大于 $\sqrt{N}$ 就分块删除，统一查询 [P5665 划分](https://www.luogu.com.cn/problem/P5665) 去年的坑，想到维护最后一段最小之后，就可以用单调队列来分析 对于后面 $12$ 分，可以用两个 $long\ long$ 拼在一起 由于非常卡时空，所以每次只记录路径，最后在统一计算答案 待填： [P3177 [HAOI2015]树上染色](https://www.luogu.com.cn/problem/P3177) (2020.11.3) ## Day 16 今天写了一些基础题 [P3177 [HAOI2015]树上染色](https://www.luogu.com.cn/problem/P3177) （填坑） 按每条边的贡献做 dp，注意不要有不合法的情况 [P5686 [CSP-SJX2019]和积和](https://www.luogu.com.cn/problem/P5686) 感觉自己上一年不一定能做出来 考虑 $a_i$ 和 $b_j$ 产生的贡献，合法情况就是 $[i,j]$ 是他的子区间，然后就有 $i * (N-j+1)$ 种情况 分别做一下 $b$ 乘上方案的前缀和后缀和，就可以算出 $a_i$ 的贡献了 [P6218 [USACO06NOV] Round Numbers S](https://www.luogu.com.cn/problem/P6218) 数位 dp，做好细节就行 [P4828 Nagisa loves Tomoya](https://www.luogu.com.cn/problem/P4828) 考虑 $a_i$ 这个数，然后手动模拟 $x$ 次操作，就可以发现是个杨辉三角一样的东西 如果没有达成环的话就可以直接算能影响到 $y$ 的贡献，暴力算他们的贡献，$O(Qx)$ 完全能跑 然后有环的话说明 $N < x$ ，故 $N < 2000$ ，可以直接一开始 $O(Nx)$ 预处理 [SP22393 KATHTHI - KATHTHI](https://www.luogu.com.cn/problem/SP22393) $bfs$ ，好久没写了 由于有点卡常所以用双端队列 $deque

P1108 低价购买

## Day 17 [P1836 数页码](https://www.luogu.com.cn/problem/P1836) 数位 dp，注意一下细节就行 [P2424 约数和](https://www.luogu.com.cn/problem/P2424) 考虑每个数对总和的贡献，然后发现这个东西可以整除分块 ，$O(\sqrt{N})$ 就过了 [P7044 「MCOI-03」括号](https://www.luogu.com.cn/problem/P7044) （填坑） 考虑每一位的贡献，显然在原串中跟他匹配的字符与他处在一个区间时是不会产生贡献的，因此考虑一下最后有贡献的区间，然后区间的左右端点的取法可以用组合数，$k$ 阶就等价于把 $n$ 拆成 $k$ 个非负整数，隔板法给个保底就算出来了，再维护一下前缀和后缀和算一下方案数就做出来了 [P1533 可怜的狗狗](https://www.luogu.com.cn/problem/P1533) 主席树板子，不过这么久没写却几乎就一A了，多交了一次是因为认为自己会出奇怪的错误所以没一开始就把空间开大。。。。 [SP3946 MKTHNUM - K-th Number](https://www.luogu.com.cn/problem/SP3946) 同上，数据规模缩小了，~~然而从蓝变成了紫~~ 待填： [P2607 [ZJOI2008]骑士](https://www.luogu.com.cn/problem/P2607) ## Day 17 考前刷板子 ## Day 18 调整状态，再看了一下盲点，然后上考场 ## Day 19 恢复了 whk 的学习，至此，本文落下帷幕 ---- 其实后面几天的记录是考完之后顶着学校压力补的，考前几天确实忘记写了 虽然结尾确实有些草率，但，此章已过，迎接新生活吧 [听首歌再走吧~](https://music.163.com/#/song?id=1399335349)