妈的，做的题怎么这么少

2.26

[JOI 2020 Final] 火事 - 洛谷

想法：

前三档部分分小孩子不懂事出着玩的。

第四档部分分所有点只会经历一次 \(1\) 到 \(2\) 的过程，询问排序后线段树维护更改即可。由于每个点更改只有一次，所以复杂度是 \(O(n\log n)\) 的。

这启发我们建出包含所有点的矩阵，然后瞪眼观察

9 3 2 6 5
9 9 3 6 6
9 9 9 6 6
9 9 9 9 6
9 9 9 9 9

以 \(6\) 为例，所有值为 \(6\) 的点于其上构成了一个平行四边形。

不会了

题解：

把平行四边形拆成三个三角形，再把询问拆成查分然后丢到三角形底部查询即可。

不想写了。

广义串并联图学习笔记

我更愿意称之为拓扑排序 pro，用着同样的思想，干着差不多的事情。

核心思想就一句话：“柿子先挑软的捏”，在拓扑排序中，“软柿子”是无出度的点，在删一缩二叠重边中，“软柿子”是度数小于等于二的点，叠合重边只是为了让我们捏软柿子产生的必要步骤。

[SNOI2020] 生成树 - 洛谷

想法：

学完上面那东西直接出来了

题解：

删掉一条边以后是仙人掌，说明这个图是个广义串并联图，换句话说，用删一缩二叠重边的操作可以将整个图变成一个点。

这有更兴奋的地方，我们如果可以在删一缩二叠重边的过程中转移 dp，最终的答案肯定就是我们要的（因为所有状态都被转移到了）

设 \(f_i\) 为 i 号边在生成树的生成树个数，\(g_i\) 为 \(i\) 不在生成树里的生成树个数，转移不难推导。

[JOI Open 2022] 放学路（School Road） - 洛谷

想法：

构建出以下缩点方式

删一：直接删

缩二：将新边变为两边之和

叠重边：如果相同就不用操作，否则赋为 \(-1\)。

tips：无论 \(1\) 与 \(n\) 度数为几都不参与上面操作，原因显然。

根据直觉，用删一缩二叠重边缩完图后如果 \(1\) 存在且仅存在一条通向 \(n\) 的边权不为 \(-1\) 的路径，则无解，否则有解。

过了？

题解：

直觉对了大半，证明明天再写。

这是能被 hack 的，但是 JOI 数据太水把我放过去了。

有可能有一个以 \(1\) 为其中一个节点却不包含 \(n\) 的点双联通分量，就连出了一条没用却会阻碍判重的边，于是寄了。

解决方案是在 \(1\) 与 \(n\) 之间加入一条长度为最短路的边。然后只跑在 \(1\) 和 \(n\) 点双里的点。

2.27

白天是开心的文化课生活，晚上为了备战 THUPC VP 了一场 ICPC。但题目质量不高。。。

2.28

上午是开心的文化课生活，下午补完了 ICPC。

[JOISC2020] 最古の遺跡 3 - 洛谷

神仙计数，可以看我的草稿P7213 [JOISC2020] 最古の遺跡 3 乱写 - _maze - 博客园

2.29

我在疑惑我 2 月 29 号为什么没写过题，然后觉得自己应该进弱智吧溜一圈。

3.1

开心的文化课生活~

[JOI2018] Snake Escaping - 洛谷

神秘题，有三种不同的暴力：

  1. 把每个问号暴力枚举修改成啥，复杂度为指数，与问号个数相关。

  2. 把 0 修改成 ? 减去 1，然后用高维后缀和快速求出只包含 1 与 ? 的答案，由于两边都要如此处理，因此复杂度为指数，与 0 个数相关

  3. 把 1 修改成 ? 减去 0,之后类似于 0 的做法，复杂度为指数，与 1 个数相关。

这三种暴力都不能过，但是把三个字符出现次数最小值拿出来，用对应的暴力就能过了。

3.2

开心的文化课生活~

[JOI 2021 Final] ロボット - 洛谷

每条边如果要被更改，就有两种可能：

  1. 更改自己

  2. 更改除自己以外的所有边

于是我们对于每个节点的每种颜色的边建个虚点，按如下方法建立：

  1. 原点向虚点连边权为 0 的单向边

  2. 虚点向原点连向的点连边权为 该颜色所有边边权 - 这条边边权的边

  3. 虚点向原点连向的点连边权为 这条边边权 的边

  4. 原点连向的点向虚点连边权为 0 的边

注意第 4 步，这涵盖了一种情况：此时路径为 \(u\) 到 \(f\) 到 \(v\)，其中 \(f\) 是原点，并且我们已经钦定 \(f\) 到 \(v\) 这条边不会改变颜色（即要改变其他边的颜色）。既然其他边的颜色发生了改变，那么 \(u\) 到 \(f\) 的路径颜色也会发生改变。因此我们无需再在开始时将改变 \(u\) 到 \(f\) 边的代价计入答案中。

然后跑最短路即可。

3.3

开心的文化课生活~

[POI2006]MIS-Teddies - 洛谷

dirty 题。

设 \(f_{ia1,ia2,ib1,ib2,A,B}\) 表示当前 A1 泰迪熊用了 \(ia1\) 个，。。。倒数第二个泰迪熊型号为 \(A\)，倒数第一个泰迪熊型号为 \(B\) 的方案数。利用滚动数组优化后大力转移即可。

3.4

对着错题做了一上午，我是天才。

下午 vp 春测，出题人是天才。

晚上写组合数学博客没写完，来写这个东西