日寄 of November,2024

Week 11.18 to 11.23#

11.19#

今日模拟赛

T1#

用了半个多小时推了个错误的结论（但是还 骗 拿了 20pts）。

看了题解，感觉写的不是人话，不改了

T2#

赛时想到正解了，但是码力不行，赛后改的时候也没打出来

敲的字典树的尸体

全是指针谁tm敢运行啊

T3#

一眼 DP，不会，过

upd: 赛后一看，这方程不是板吗？我连这都推不出来？该复习 DP 了。

T4#

$\color{White}\sout{\text{OIer to 数竞生：信竞题都不会做还学什么数竞（}}$

纯数竞题，做法挺神奇的：

先将 $xOy$ 平面旋转 $45 \degree$。然后移动的向量就从 $\begin{bmatrix} 0 \pm 1 \end{bmatrix} , \begin{bmatrix} \pm 1 0\end{bmatrix}$ 映射到了 $\begin{bmatrix} \pm 1 \pm 1 \end{bmatrix}$

然后就升维打击，通过上面的转化， $x,y$ 两维就可以分别考虑，每一维方案数为 $[(n + x) \bmod 2 = 1] \times C _ {n} ^ {\frac{n + x}{2}}$。

扩展到三维，设 $x,y$ 用了 $i$ 步，剩下的 $n-i$ 步就是在 $yOz$ 平面内用的，令 $F_k$ 为用了 $X + Y + 2k$ 步走 $x,y$ 方向，恰好到达 $(X,Y)$ 的方案数，所以总方案数为：

然后ctj可得 $F _ k = C _ {x + y + 2k} ^ {x + k} C _ {x + y + 2k} ^ {k}$

然后就可以去做强连通分量 $\Omicron(n)$ 求出答案了

赛后#

终于当上牢人了兄弟们555555（祝老的绿茶挺好喝的）

讲 T4 的时候甚至 数学老师 来了，活久见。

11.20#

$\bmod ^ {-1} \sin Again$

省流：寄

T1#

分治，然后炸成30pts了，正解区间 DP，没复习，寄

T2#

树上背包，并且昨晚复习了背包。爽 $\ldots$ 个 damn，只复习了背包没复习树上背包，寄。就打了链的情况。事实上是二分答案，但我实在看不出来 $qwq$.

upd: 真tm服了，二分答案板中板，套在树上就不会了，基础算法都烂成这样了，晚自习就拿来好好复习吧

T3#

线性 DP，方程错了，寄

但赛场上敲线段树也没错，反正要用线段树维护（

T4#

计数图论题，不会，寄

最后也是拿到 rank 2 了啊，反方向的。 $\textcolor{white}{\text{ctmd}}$

赛后#

光速改出 T1,T2 就不想改了，写了字典树板子，然后就去改博客了

还有

谁家电脑一天黑屏五次啊

11.21 & 11.22#

11.21去出题了忘写了，11.22补的

21日没有 $\bmod ^ {-1} \sin$，但是去出题了，导致一天就没写几道题。出了个下位橙 T1，中上黄 T2。

下午去拍一等照了，乐。下周三还要 NOIP 团建，爽！

22日 $\bmod ^ {-1} \sin$。感觉比之前简单些。

T1#

周期+逆序对，但是归并没想起来，就直接用了 pbds 的平衡树 A 掉。

T2#

感觉是计算几何，但又感觉是 Kruskal。

upd: 就是 MST，但是要写 Prim，因为是稠密图，Prim 优于 Kruskal，但是考场上不会，寄。赛后有人想用 Kruskal 艹过去，但是被卡掉了。

T3#

一眼 DP，不会，过。

upd: 打了个 75pts 的暴力，然后题解写的优化根本不会，寄。

T4#

本来觉得是组合数学题，推了个公式成功骗了10 pts

赛后一看，状压 DP，写不来寄。

下午#

学了学珂朵莉树啊

珂朵莉真的好可爱啊，我要去看末日三问 awa。

然后用珂朵莉树在随机数据赋值题里暴打线段树

upd 11.25：《致敬传奇耐卡王 ybz》：

但是我用 ODT 只用了 671ms

$\LARGE{\text{awa}}$

11.23#

$\bmod ^ {-1} \sin$，但是联考。

T1#

不会正解，赛后一看正解就是大模拟，看不懂，写了个暴力模拟骗了 30pts，过。

T2#

推了 nmb 两个多小时的结论，然后数据结构写错了，qnmd。

upd: 赛时算错复杂度了，$\Omega(n \log n)$ 算成 $\Omicron(n \log n)$ 了，导致 T 飞，只有 10pts。

其实是动态开点线段树上二分，好题。（多加个数据结构练习得了

T3#

一眼 DP，不会，过。（这句话好像都写了 3 遍了来着）

T4#

也是 DP，看不懂。

最后成功把 CW 的脸面丢光了

P.S. 感谢 qcz dalao 的提交记录

Weekend#

周末是绝不可能补题的

周天下午打了场 ICPC，3A 大作，双方都是。

题目：AI 绘图，AI 绘图，还 tm 是 AI 绘图。

我们：只 A 了 3 道。

然后晚上就没回学校，玩了亿会战地和图灵完备，只能说搞不懂为什么逻辑门的基础都是 NAND 和 NOT。

Week 11.25 to 11.30#

11.25#

无 $\bmod ^ {-1} \sin$，补了一道 Trie 树的题，然后就开始爆切珂朵莉树的题。

末日三问豪堪，珂朵莉珂爱😊。

电脑配置低，一写代码就死机，我要换成老年机（编不动了，但是 Bad Apple 确实好听）

11.26#

$\bmod ^ {-1} \sin AAAAAgain$

T1#

水题，秒了。

T2#

没什么思路，线段树骗 30pts 得了。

赛后一看，auv，您猜怎么着，线段树的常数给我卡到 10pts 去了，宝贝的。而且这还是个原题的变式，寄。

赛时有人用 ST 表，也被出题人的《精心构造》的数据卡掉了。

T3#

暴力骗了 10pts。

《T3难于T4》

T4#

发现特殊性质保证路径无交，所以可以用组合数学骗 25pts。

赛后一看，容斥原理，但是还是挺好想的，就是不咋好实现。

下午#

改了两道题，然后就把这个站主页那个每日歌单功能写完了（还有 JS 为什么没有 STL(雾) ）

fzh 还 3 抽出金，qtmd，明天真人 CS 真实他。

晚上#

复（xue）习（xi） ST 表。

11.27#

今日团建，太长了，见此。

11.28#

今日 $\bmod ^ {-1} \sin AAAAAAgain$，但是和高一高二学长考 NOIP，4.5h 打下来了 10 分，寄。

T1#

不会，寄

赛时想的是求逆序对，后来一看还真是，只能说思维雀食几乎没有。

T2#

本来觉得 Tarjan 求一下边双就好了，但是转念一想，边双不只是环，还有可能是环套环，点双同理。然后就没啥思路了，去开 T4 了。

最后 1h T4 实在调不动了，就回来看看 T2，有个特殊性质，这个图是一个基环森林，可以用边双，所以就打了 10pts 的性质分，也是唯一的 10 分 $\ldots$

T3#

不会，赛后题解也没看懂，寄。

T4#

一眼树剖，然后就开始码力展开，40min 敲了 5kb，200 行，键盘都快干出火星子了，然后一分没得，不得不说青轴确实有点吵。

然后子树操作的 dfn[x] + sz[x] + 1 打成了 dfn[x] + sz[x] - 1，调了 1h+ 才找到，虽然说改了也是 0pts。

本来想的是暴力维护操作 4，能骗一点是一点，但是也没骗到 qwq。

但是，还是那句话

我打 NOIP ？真的假的？

11.29#

今日无模拟赛，但是下周还有三场

不是说考完 NOIP 频率就会降下来吗？

今天主要在补 DP 专题，但也是不怎么会补，第一道是个紫的，要用矩阵快速幂优化。

今天还搓了一个 Modint 的板子，以后打线上比赛就好用了 awa。

下午下课以后，要打 NOIP 的就回家了，就剩我们几个孤寡劳蒟蒻在机房 qwq。

吃完饭和 wgc,ybz,yzp 等一众 dalao 交流了 OI 的生平，感觉对未来有了点期望？可能本来就有吧

睡前写的，github 真的太 tm 慢了，调了半天仓库。

不知不觉，日记已经写了半个多月了呢，这个文件也已经要有 8kb 了。

11.30#

11 月最后一篇日记了呢。早上先在补 DP 专题，因为 2000-2400 做不动就去做 1600-2000 的了，但是还是要看题解才能过。

可能还是得写一下 DP 方法总结吧，不能只记方程。

下午#

做上 NOIP 真题了

T1#

一眼想不到正解，然后打了 40pts 的性质分。

T2#

因为中午 wbh 在群里发了一个结论，我就觉得是结论题。事实上真是，因为 $n \in [1,10 ^ 9]$，要么 $\Omicron(\log n)$ 或者直接 $\Omicron(1)$，然后这个题怎么看怎么不像 $\Omicron(\log n)$ 解法，并且还忘了结论，也是直接写了个乱搞做法上去。

T3#

计数题不会。

祝老说是树上容斥，但是没学过，不会。

T4#

维护原树上的区间信息的题也是第一次见。

刚开始在推 $LCA$ 的性质。我就在想，如果直接将 $LCA$ 视为一种运算，然后它天然的满足交换律和结合律，那么 $G(V,LCA$) 是不是一个幺半群呢？

然后成功将自己的结论证伪了，因为找不到 $LCA$ 的单位元，然后就放弃了用线段树维护的想法。

然后就打了个暴力，我也不知道骗了多少分。

赛后一想，$LCA(a,a) = a$，所以满足可重复贡献，可以用 ST 表维护。

如果早点想起来还能多骗几分

End of Diery of November,2024#