10月日志

26-10-1

梦熊公开模拟赛。

All Counting Round.

不好吃。

T1 题意: 已知个环形排列的盒子经过一次“非空盒子向顺时针下一盒子传递一颗珠子（注意初始情况中允许有空盒子，但是空盒子不传珠）”的操作后的状态，求满足条件的初始非负珠子分布方案数。

T1 Sol: DP 数数，设计表示考虑前个位置，第个位置是/否向后面传球时的方案数，结合题目分讨一下就可以知道合法的状态和转移。

T2 题意：给定一棵个节点的树，求遍历所有节点恰好一次的最小总路径长度，以及达到该最小值的遍历顺序方案数。

T2 Sol：巨大恐怖树形 DP + 树论，第一问是结论，发现答案的上界是，又发现其中可以不重复的走一条路径，为了最优这条路径就是直径，所以答案是。

T3 是 DP 但是暴力加性质可以在水货数据中获得 80 pts，结合单调栈性质加线段树可以优化 DP。

T4 有关拓扑学，直接放弃。

26-10-3

T1 题意：给定和，在所有的 01 矩阵中，满足（全零矩阵）的前提下，求矩阵中 1 的最大数量。

T1 Sol：等价于构造最长路径的 DAG，把个点尽量均匀分入层（不能整除部分均匀放在高层以最大化贡献）并连所有低层到高层的边，答案即总点对数减去各层内部点对数。

T2 题意：初始有个节点、无边。依次加入条无向边，每次加边后检查：若节点到的最短路长度，则清空图中所有边。求清空次数，以及每次清空发生在加入第几条边之后。

T2 Sol：显然可以二分判定，用倍增缩小二分范围定位每段第一次满足条件的位置，配合时间戳 Dijkstra 与记录邻接表开始遍历的位置，时间复杂度。

T3 题意：
给定一个的网格，每个格子涂有红色（#）或蓝色（.）。定义子矩形的“复杂度”如下：

若子矩形内所有格子颜色完全一致，复杂度为 0。
否则，可以沿平行于边的方向切一刀，将其分为两个部分，设两部分的复杂度分别为。该子矩形的复杂度为所有切法中的最小值 +1。

根据输入的网格，计算并输出整个矩形的复杂度。

T3 Sol：题解。注意“我们将，视为两个分别不降和不增的函数”一句应为“我们将，视为两个分别不增和不降的函数”。

T4 放了。

26-10-4

补总结，改模拟赛。

26-10-5

颓。

听课效率低完了，而且没有专门做题的时间，只有一点印象怎么做嘛。

26-10-6

~~根据提供的题面和对应的 std.cpp 代码，以下是四道题的题意简述和做法简述：~~

T1 游戏（game）

题意：给定一棵个节点的树，边权为 0 或 1。每次询问给定一个根节点，女生先手，双方轮流操作：选择一条非根节点且边权为 1 的边，将该节点到根的路径上所有边权翻转。无法操作者败。需支持单条边权修改操作，回答每次询问的胜者。
Sol：：维护每个节点的相邻边权之和（即与该点直接相连的边权总和）。对于每次询问，若的相邻边权和为奇数，则先手必胜（Girls win!），否则后手必胜（Boys win!）。
博弈结论证明：
1. 终局状态：若树中所有边权均为 0，游戏结束。此时根节点的相邻边权和为 0（偶数），先手无路可走，为必败态。
2. 奇偶态转移：假设当前根节点的相邻边权和为。
  - 若为奇数：此时必定至少有一条相邻边权为 1。先手可以直接选择该边的子节点进行操作，此时路径只包含这一条边，翻转后该边变为 0，其余相邻边不变。因此变为偶数。先手将必败态留给了对手，故当前为必胜态。
  - 若为偶数：
    - 若，无操作可做，为必败态。
    - 若，先手无论选择哪条满足条件的边进行翻转，其路径中，只有与根节点直接相连的那一条边（设为）被翻转。因此，必然发生改变（边权或），奇偶性必从偶数变为奇数。即先手无论怎么走，都会把必胜态留给对手。故当前为必败态。
      由以上推导可知，局面为必胜态当且仅当根节点的相邻边权和为奇数。

T2 小伙伴（friends）

题意：有个人围成一圈，每个人属于对小伙伴中的某一对。每次可以交换相邻的两个人，求最少需要多少次相邻交换，能让每一对小伙伴都相邻。
Sol：将圆环上的每对小伙伴看作连接它们的一条弧（区间）。由于选哪一边不影响区间之间的相交性，我们直接取每对小伙伴“较近”的那条边，初始答案为所有点对较近弧的长度之和。接下来要使所有点对相邻，只需通过操作消除区间之间的交叉。可以发现，每存在一对交叉的区间（即对于两个区间和，满足），就可以在一次操作中对两个区间做贡献，节省一次操作（答案减 1）。将区间按左端点排序，用树状数组维护右端点，统计有多少个已有区间的右端点落在当前区间的左右端点之间即可。时间复杂度。

T3 奇怪的树（strtree）

题意：给定一棵个节点的树，点有“奇怪”和“正常”两种状态（初始给定）。有次操作，每次操作形如：
1. 1 u：对于所有当前状态为奇怪的节点，给它们的最近公共祖先加上的编号。
2. 2 u：翻转节点的奇怪状态。
  求所有操作结束后每个点的最终权值。
Sol：直接在处加不好维护，但转化为对到根节点的路径加则是容易的。
利用树链剖分和线段树进行路径加操作：
操作 1：对到根路径上的节点加上 1。
操作 2 修改状态：对到根路径上的节点加上（或减去）的编号；
这样每个节点累积的值，实际上是其子树内所有“奇怪点”和“操作节点”产生的贡献（即该节点作为它们公共祖先的累积）。为了得到准确在 LCA 处的答案，只需在最后将每个点的累积值答案减去其子树答案：（每个点）。
线段树维护两组标记的乘积交叉项即可，时间复杂度。

T4 三元组计数（count）

题意：给定一棵个节点的树，统计满足条件的三元组数量：互不相同，且到与到的两条路径没有公共边。之后有次操作，每次向树中添加一条新边（可能产生重边或自环），每次加边后都需输出当前的三元组数量。
Sol：不会。

本场关键题 T2，然而没想到可以取不同方向的弧，更加没法观察到相交与点对取哪条弧无关，寄掉了。

26-10-7

CQBerZ Counting and DP Round。

仅写会了的题的做法。

A：容易写出状态数时间 DP，然后将转移式子拆开，发现内层转移是可以斜率优化的形式，然而无序，不好做，但是我们发现，需要斜率优化的部分可以提前做，没必要按 DP 顺序来，因此可以提前排序，然后就有单调性了，容易斜率优化。
A 还有的 Slope Trick 做法，这个就很脑残，就是把内层转移拆开后扔进李超树里然后每次查询即可，但这题开到了所以很难卡过去。

B：为个有标号部门分配长度为的互异二进制串，第个串必须包含给定的长为的标记。
。

看到互异我们想到什么？对，集合划分容斥。

所以就要计算包含一个部门子集的二进制串数量，这个是 AC 自动机上 DP。

令部门集合为。
构建 AC 自动机，其状态（节点）集合为，根节点为。
令为 AC 自动机的转移函数。
令为节点输出函数，表示到达状态时匹配的模式串下标集合。

定义表示当前构造的串长度为，在 AC 自动机上处于节点，且已匹配的模式串下标集合为的方案数。

初始状态为，状态转移方程。

经过次转移后，累加所有 AC 自动机节点，得到恰好匹配集合中所有模式串的合法串数量。

还需要扩展，因为当一个串包含了一个部门子集的超集时，此时选择它也是对这个子集中的所有部门都合法的，因此，我们还要做一遍 SOS DP 算超集和，得到 .

设函数为容斥系数：

令为包含容斥系数的匹配方案数有。

定义为集合中的部门被分配互不相同的合法二进制串的方案数。为了不重不漏地划分集合，每次强制提取中的最低位元素所在的子集作为独立划分，进行集合划分 DP，初始状态为，状态转移方程为，最终答案。

C：容易写一个背包 DP 状物，发现瓶颈在于枚举操作区间左右端点以满足时刻之差不大于的限制，这时我们想，如果这个背包能回退岂不美哉，这样就是一个双指针维护的东西，只用扫一遍。

但是由于转移的状态要对取模，因此不能直接回退，但是可以列出转移方程，发现这个方程是可以解的。

观察转移方程，有 $f’{j}=f{j-a}+f_{j}+f_{j+a} $，可得$ f_{j+3a}-f_{j} = f’{j+2a} - f’{j+a}$。

设，这就是周期，我们按余数区分，一个周期内的状态可以统一处理。

由于我们可以算出，那么只要知道了周期中的任意一个位置，就可以计算出整个周期内的值。

由于是的次幂，所以，因此这个周期内要么是：

：对于这一种，已知它们的和是转移出来的对应位置之和的，然后依次减去 $f’{j+2a} = f{j+a}+f_{j+2a}+f_{j+3a},f’{j+5a}=f{j+4a}+f_{j+5a}+f_{j+6a},\dots $，然后就可以算出$ f_{j}$ 了。

：。对于这一种，它们的和同样已知，然后依次减去 $f’{j+3a} = f{j+2a}+f_{j+3a}+f_{j+4a},f’{j+6a}=f{j+5a}+f_{j+6a}+f_{j+7a},\dots $，然后可以算出$ f_{j}+f_{j+a} $，用$ f’{j+a} $减去$ f{j}+f_{j+a} $可得$ f_{j+2a}$。

特判一下的情况，因为此时等同于。

26-10-8

T1 翻面消除（erase）

Sol

题意：给定一个长度为的字符串，选择一个非空区间反转，问反转后能否通过消除相邻相同字符使得字符串变为空。

原本就能消除的相邻对直接无视，剩下的串必然需要是一个形如的结构，表示的反串。

用栈处理出消除相邻对后的字符串，判断并输出即可。

26-10-9

To do.

26-10-10

To do.

26-10-12

To do.

26-10-13

To do.

26-10-14

To do.

26-10-15

To do.

26-10-16

To do.

26-10-17

To do.

26-10-18

抄了下 26-10-16 晚练的代码，反贪证明昨天看的。

26-10-19

To do.

26-10-20

To do.

26-10-21

To do.

26-10-22

To do.

26-10-23

To do.

26-10-24

100+100+20+25。

26-10-25

To do.

26-10-26

其实是不是应该有个专门的模拟赛题总结来着，日志记录一下干了什么即可。

唉 11 月再说。

100+100+20+20。

T1 梦境（dream）

原题未找到。

出题人崩铁玩魔怔了。

Sol

简单题，答案的维护使用线段树，单点修改是的，而修改总数势能分析可得次，用一个 set 维护还可能有效的操作即可避免多余操作影响时间复杂度，时间复杂度。

T2 黄金矿工（game）

原题。

Sol

T2 场切但感觉有点运，发现 DP 是一个能够刻画连通块的结构，使用 DP，状态记录上一列是选上/选下/上下都选，不记录不选的状态，因为没有转移的可能，但是每次转移时要考虑当前列是第一列而前面都不选的情况。

发现列选一个、一列两个都选或者列只选其中的的情况交换是对后手无用或不优的，所以不用管直接加上该有的贡献。

但列只选其中的这种情况，前个的贡献为，之后的贡献才是，难以在不扩展状态的情况下准确计算其贡献。我们称这种为风险型，因为这种类型如果没选够个贡献就是负的。

解决方法是直接做两遍 DP，一遍假设选风险型的个数小于，一遍假设选风险型的个数大于等于，这样前者就是每选一个反而给出贡献，后者就是每选一个给出贡献但是初始化时基础值为（前个均被换掉贡献从变为）。

发现如果 DP 得出的方案不合法，那么另一边的 DP 使用这种方案时答案更大，即错解不优。

时间复杂度。

T3 惊喜（tree）

原题。

Sol

数论+树论。

前置定义：

有引理。

证明

利用欧拉函数通项，代入得：

因为，所以。

将连乘展开成多项式。例如（质因数），展开为。
发现展开后的每一项，恰好对应从的质因数中挑选若干个相乘（即选出了一个无平方因子的约数）：

选 0 个：项为。
选 1 个：项为和。
选 2 个：项为。

第三步：引入莫比乌斯函数。展开式只包含无平方因子的约数，而恰好是“无平方因子”的指示器（无平方因子时为 1，否则为 0）。因此，将所有项写成求和：

证毕。

然后来拆拆拆。

拆距离：。
拆欧拉函数：。
套用引理：将项替换为。

将上述三步合并，单对的贡献为：

交换求和顺序，先枚举约数。将上式展开，提取出与相关的作为主元，把与相关的项分离。定义全局累加数组：

此时，固定节点和 LCA（记为），它对答案的贡献化简为：

使用 DSU on tree 维护：

先递归重儿子并保留其数组。
暴力合并和轻儿子。合并过程中，当前祖先恰好是重儿子中已加入节点与轻儿子中待加入节点的 LCA。所以代入上面的公式时，就是。
先 query 算贡献，再 add 将轻儿子节点并入。

复杂度：每个节点最多被暴力合并次，所有数约数个数和个，总时间复杂度。

T4 行走于真实之道（path）

原题。

Sol

题解链接。

首先从源点向所有 1 连容量的边，所有 1 向汇点连容量的边，从源点向所有 0 连容量的边，所有 0 向汇点连容量的边，所有 1 向右侧 0 连容量为 1 的边。

我们要最大化最终收益。由于本题每个字符都要二选一（选红或选蓝），我们可以套用最小割模型。

具体做法是：先假设把所有的钱 () 都拿到手，即将每个点连接源点和汇点的点都连上，然后找出所有可能让我们损失钱的情况。

同一个点连接了源点和汇点，肯定选其一断掉；如果最优解中源点连接了 1，经过一条 1 → 0 的边，又从 0 连到汇点（这就是均染红色的情况），那么中间这条边就会进入割，要断掉。

所以最小割割掉之后，刚好对应一个每个点恰好选一种颜色，且减去支出了的合法解。

答案就是 $最小割$ 。

由于最大流等于最小割，因此转化为求最大流。

首先每个点显然有的流量。

对于 1 ，还有的从源点来的入流量，对于点，还有到汇点的出流量。

所以我们就要通过 1 → 0 边用上这部分流量。

从左往右扫，遇到 1 就把当作“可用额度”存起来；遇到 0 就消耗前面的额度来增加当前最大流。

贪心地，我们使用优先使用额度最大的元素消耗，因为每个额度价值相同，但是如果先消耗额度小的元素，可用元素数会减少，对于后面的 0 就不优。

动态插入并排序，后缀减，清除额度归零的元素，这可以用平衡树维护。

注意后缀减时导致分裂的两部分相接处不符合 BST 性质的情况，需要多分裂两次，交换逆序部分顺序，然后再合并，以维护平衡树 BST 性质。

时间复杂度。

26-10-27

上午补了昨晚晚练 P9340，回滚莫队写的，然后见 hyc 与 cdo 均补了上场模拟赛 T4 path，被迫补之，发现从最大流最小割的角度是很好理解的，从 DP 角度理解就很困难。

下午在补总结。

26-10-28

100+0+12+0。

注意到 T2 大模拟，T3T4 都是黑，因此除了 jmr 人均不到 200。

T1 跷跷板（seesaw）

原题。

T2 命题演算（logic）

原题未找到。

T3 安检门（security）

原题。

T4 精彩区间（maxsum）

原题。

26-10-29

To do.

26-10-30

To do.