202411 测试笔记兼停课记录

最近 UPD 于：$2024/11/27$ $19:57$

$2024/11/6$ Wed

考完二检，通知明天开始去，但是校长不给去。

$2024/11/7$ Thu

经过一番斡旋三个人能去了，但是没我份。

$2024/11/8$ Fri

学校约家长，成功跑路，下午来到发现石中正在体艺节，各路 coser 遍地跑，氛围比我们学校的好太多。晚上看文艺晚会，看到了群青轻音少女京吹 etc。

$2024/11/9$ Sat

星期六上飞鹰班，早上测试下午 wzr 讲题。

T1

简要题意：对于一个长度为 $k$ 的序列 $a$，定义 $\mathrm{sort}(a)$ 表示将序列a排序后形成的新虚列，定义 $f(a)=\sum _{i=1}^k[a_i=i]$。给定一个长为 $n$ 的序列 $A$，求 $A$ 的所有非空子序列 $f(\mathrm{sort}(S))$ 之和。

解析：先 $A\leftarrow \mathrm{sort}(A)$，考虑 $A_i$ 对答案的贡献，那么就可以在 $A_1\sim A_{i-1}$ 中选择 $A_i-1$ 个数，方案数为 $C_{i-1}^{A_i-1}$，在 $A_i$ 后面可以任意的选或不选，方案数为 $2^{n-i}$，乘起来就行了。

T2

简要题意：给定一个 $n$ 个数且互不相同的序列 $a$，求它的一个子序列 $b$ 的最长长度，满足 $\mathrm{\forall }i,\mathrm{\forall }j\in [1,i],b_i>b_j$ 或 $b_i<b_j$。

解析：考场突然想到的奇怪做法。

令 $cn{t}_{a_i}=i$，随便写个样例就能发现，只要是合法的 $b$，呈现在 $cnt$ 数组上都是一个 V 字形，那就是在 $cnt$ 上做一个 合唱队形，V 字形取负值转换成倒 V 就可以简单的树状数组维护。

但是人机 gj 数据不保证互不相同，直接爆挂 ${40}^{\prime }$，我也不会改，直接一个一个一个特判吧。

T3

简要题意：$n$ 行 $m$ 列，每一行和每一列至少单独选一个点，代价为 $a_{i,j}$，求最小代价。第 $i$ 行和第 $j$ 列都选择点 $(i,j)$ 是非法的。

解析：套路地行向列连边，$a_{i,j}$ 为边权，发现合法的选择方案是一棵基环树，求最小生成基环树即可。

怎么求？跑最小生成树，用一个 $vi{s}_x$ 表示 $x$ 这个连通块是否构成环，如果 $vi{s}_x=1$ 且 $vi{s}_y=1$，根据基环树的定义这两个块不能连，如果 $\mathrm{getfa}(x)=\mathrm{getfa}(y)$，那么成环了，$vi{s}_x\leftarrow 1$。合并两个连通块的时候把 $vis$ 也合并一下即可。

int fu = gf(u), fv = gf(v);
if (vis[fu] and vis[fv])
    continue;
if (fu == fv) {
    vis[fu] = true;
    ans += w;
    continue;
}
f[fu] = fv;
vis[fv] |= vis[fu];
ans += w;

T4

简要题意：有 $n\le 5\times {10}^5$ 个点，经过 $i$ 号点时，如果分数 $>a_i$，则分数增加 $b_i$，$q\le 2\times {10}^5$ 次询问，每次询问最初有分数 $x$，依次经过 $[l,r]$ 号点，最终的分数是多少？

解析：用线段树维护，维护 $[l,r]$ 的点中存当它以 $x$ 的分数经过 $[l,r]$ 时，最终增加多少分，发现增加的得分中，不同的连续段只有 $r-l+1$ 个，所以可以只存一个连续段的起点和增加的值，查询的时候，把查询的区间放在线段树上从左到右依次查询，找这个分数属于的连续段二分即可。

由于合并左右儿子的连续段的操作过于**，两个钟写不出来，直接写成屎山，跑路了。

T5 AT_agc043_d [AGC043D] Merge Triplets

解析：考虑对于一个块 $(a_1,a_2,a_3)$，如果 $a_1>a_2>a_3$，那么 $a_1$ 一被放到 $P$ 的末尾 $a_2,a_3$ 就会被跟着放进去，下一个再放进 $P$ 的数一定比 $a_1$ 大，因此，在生成的序列 $P$ 中，最多只会有连续 $3$ 个下降的数。如果 $a_1<a_2$，等价于有两个块 $(a_1),(a_2,a_3)$。

于是问题变成求长度为 $3n$ 的排列，这个排列满足单调下降的块的长度不超过 $3$，且长度为 $1$ 的块的个数 $c_1$ 大于等于长度为 $2$ 的块的个数 $c_2。

排列 DP，设 $f_{i,j}$ 表示前 $i$ 个数中，$c_1-c_2=j$ 的方案数。

• 长度为 $1$ 的块，$f_{i,j}\leftarrow f_{i-1,j-1}$。

• 长度为 $2$ 的块，$f_{i,j}\leftarrow f_{i-1,j+1}(i-1)$。

• 长度为 $3$ 的块，$f_{i,j}\leftarrow f_{i-3,j}(i-1)(i-2)$

T6 AT_agc007_e [AGC007E] Shik and Travel

待补。

$2024/11/10$ Sun

赛博朋克 2077，爽！谁能想到五公里路程，六点出门，也难逃迟到的命运。

晚上为了斜率优化学了个 李超线段树，const int eps = 1e-7; 虚空调试一小时。

此外 GJ 又把我们拉过去交代了一遍 CSP 集训交代过的事情。

$2024/11/11$ Mon

早上补斜率优化题，下午写题写不出来，晚上测试但是一题不会。

T1 P2755 洗牌问题

但是 $n\le {10}^{14}$，且是 $1,n+1,2,n+2,\dots ,n,2n$ 的放法。

解析：观察一个数动一步的状况，对于 $i\le n$，$i^{\prime }\leftarrow 2i-1$，对于 $i>mid$，$i^{\prime }\leftarrow (2i-1)mod(2n-1)$。

那么，对于一个原本在 $x$ 的数，它动若干（假设是 $p$）步就是：

$$2(2(2(2x-1)-1)-1)\cdots mod(2n-1)$$

拆左边的式子找规律，发现是 $x\times 2^p-2^p+1$。

继续观察，除了第一个数和最后一个数以外，如果某个数第一次回到自己本来的位置，那么整个序列就变回原来的样子了，所以挑最简单的 $2$ 代进 $x$，就变成了

$$(2^p+1)\equiv 2(\mathrm{mod}2n-1)$$

当 $n>1$ 时，显然可以左右两边同时减去 $1$，否则直接特判输出 $1$ 即可，问题变成求最小的 $p$，满足：

$$2^p\equiv 1(\mathrm{mod}2n-1)$$

根据欧拉定理：

若 $gcd(a,b)=1$，则 $a^{\phi (b)}\equiv 1(\mathrm{mod}b)$。

显然 $2$ 和 $2n-1$ 互质，但是 $\phi (n)$ 只是可行解，并不是最小解，大胆猜想枚举 $\phi (n)$ 的约数，再用快速幂判断一下，就可以找到最小解。

总时间复杂度 $O(\sqrt{n}+\sqrt{\phi (n)}\log \phi (n))$。

T2 AT_agc016_d [AGC016D] XOR Replace

解析：研究样例发现就是 $a$ 序列的数和 $a$ 序列的原异或和之间在变来变去。所以如果 $a$ 序列和它的异或和 $w_a$ 组成的序列，和 $b$ 序列和它的异或和 $w_b$ 组成的序列不一一对应，就是无解。

如果 $\mathrm{\forall }i,a_i=b_i$，直接输出 $0$。

考虑对于 $a_i\ne b_i$ 的 $a_i$ 和 $b_i$ 之间连边，$w_a$ 和 $w_b$ 之间也要连，相同权值的看作一个点。发现动一步就相当于从 $a$ 序列的异或和的点开始向前走一步（或者跳到下一个连通块），而每个连通块都存在欧拉路，当整个图都被遍历一次时就可以组成答案序列。

所以，答案就是边数加连通块个数，如果 $w_a$ 不是孤立点，就减去一步。

T3 AT_arc108_f [ARC108F] Paint Tree

解析：不难发现答案的上界 $U$ 是直径的长度，下界是 $D=\underset{i=1\wedge i\ne r{t}_1\wedge i\ne r{t}_2}{\overset{n}{max}}\{min(di{s}_{1,i},di{s}_{2,i})\}$。其中 $r{t}_{1/2}$ 是直径的两个端点，$di{s}_{1/2}$ 是分别从 $r{t}_{1/2}$ 出发到每个端点的距离。

枚举答案 $d$，直接计算恰好等于 $d$ 的方案数 $g_d$ 并不好算，因此计算答案小于等于 $d$ 的方案数 $f_d$，离任意一个端点大于 $d$ 的点都只能和那一个点涂不一样的颜色，方案数为 $1$。故统计离任意一个端点的距离都小于等于 $d$ 的个数 $cn{t}_d$，则有 $f_d=2^{cn{t}_d}$，$g_d=f_d-f_{d-1}$。最后的答案是 $ans\leftarrow \sum _{i=D}^{U}i\times g_i$。

但是这种方法不能处理 $d=U$ 的情况，特判一下，$d=U$ 只需要端点涂相同颜色，其它的点可以随便涂，$ans\leftarrow ans+di{s}_{1,r{t}_2}\times 2^{n-2}$。

涂色方案有两种，还需要 $ans\leftarrow 2\times ans$。

T4 AT_arc152_f [ARC152F] Attraction on Tree

数据范围说得对，但是 $0\mathrm{\%}$ 的数据满足 $x_i=1$。

解析：$1\to n$ 的简单路径上的点是必走的，容易发现如果 $n\ne dis(1,n)(\mathrm{mod}2)$，那就无解。

为了方便讨论，令 $i$ 号点表示 $1\to n$ 上第 $i$ 个点的编号，如下图所示：

用 $c_i$ 表示 $i$ 号点除了 $1\to n$ 上的 $i$ 的子树，如上图，$c_1$ 就是蓝色的部分，$c_2$ 就是红色的部分。

当在 $1$ 号点的时候，显然可以按一下红的按一下蓝的来实现在没有走到新的点的前提下左右横跳。

到最后只会有一棵子树 $c_i$ 没有被抵消掉，说明 $|c_i|-i\ge \frac{n-dis(1,n)}{2}$，进入这棵子树的下一层，运用相同的策略，最后只会有一棵子树的子树 $u$ 满足 $|u|-i\ge \frac{n-dis(1,n)}{2}$，即 $|u|\ge \frac{n-dis(1,n)}{2}+i$

由上一段第一条不等式且 $i\le dis(1,n)$，注意到 $|c_i|\le n-dis(1,n)\le 2|u|$，即如果有不会被抵消完的 $u$ 是 $c_i$ 的儿子只有可能它是重儿子。因此如果将每个节点的儿子从重儿子到轻儿子排序（父亲除外），每次只需要取每个节点的第一个儿子即可。

$2024/11/12$ Tue

T1

简要题意：你拿着 $m\le {10}^9$ 块钱从任意城市出发以任意的顺序不重不漏通过 $1\sim n\le 18$ 号城市，最后无需回到起点。从 $i\to j$ 需要 $w_{i,j}\le {10}^6$ 的时间和 $c_{i,j}\le {10}^6$ 的路费，求最小时间，若无法完成输出 $-1$。

解析：神秘爆搜剪枝题。$18$ 很容易想到状压，但是显然不能直接 dp，所以考虑用状压来剪枝。设 $W_{s,i}$ 表示从 $i$ 号点开始走，走完 $s$ 的点集的最小时间，$U$ 是全集，则有：

$$W_{s,i}=\underset{j\in s\oplus U}{min}\{W_{s\oplus U,j}+w_{i,j}\}$$

$C_{s,i}$ 同理可以求到，这一部分是 $O(2^n{n}^2)$ 的。

爆搜的时候顺便记录最后经过 $i$，走过的点集状态 $s$ 和当前的时间金钱花费 $w^{\prime }$，$c^{\prime }$，如果当前状态在最优情况下走完剩下的补集，还是不可能达到最优解，即 $\underset{j\in s\oplus U}{min}\{w^{\prime }+W_{s\oplus U,j}+w_{i,j}\}$，或者说钱已经不够用了，就可以直接不搜了。

这样就成功把一个运行 $18\times 18!=115,242,726,703,104,000$ 次的爆搜优化到了最大点 $0.85\mathrm{s}$。

T2

简要题意：给定一棵以 $1$ 为根的 $n\le 2\times {10}^5$ 个点的二叉树，每个点有点权，$q\le 2\times {10}^5$ 次修改，每次修改某个点的点权。求修改后，构成二叉搜索树的子树个数。二叉搜索树是指对于任意一个点，左子树内所有节点点权小于等于该点权，右子树内所有节点点权大于等于该点权的树。

解析：对于暴力的求法很容易想到：如果左右子树均是二叉搜索树并且左子树的 $max$ 不大于该节点点权并且该节点点权不小于右子树的 $min$，这就是一个二叉搜索树，答案加一。$O(qn)$。

容易发现修改一个节点只会影响从根节点到该节点的答案，更新这一条路径即可。

将点权 $a$ 放到中序遍历序列 $a^{\prime }$ 上，发现每个子树都相当于序列上的一个区间 $[l,r]$，如果这个子树是二叉搜索树当且仅当区间 $[l,r]$ 内的权值单调不降。因此如果在序列上出现 $a_i^{\prime }>a_{i+1}^{\prime }$，则在树状数组上 $\mathrm{update}(i,1)$，一个区间 $[l,r]$ 单调不降的条件是 $\mathrm{query}(r-1)-\mathrm{query}(l-1)=0$。

dfs 求中序遍历时顺带求出每一棵子树的 $l\to s{t}_u$ 和 $r\to e{d}_u$ 即可 $O(\log n)$ 查询某一棵子树是否合法。考虑求 $u$ 到根节点这一条链上的答案，如果它父亲的父亲可以合法，那么它父亲和它一定也可以合法，这启示可以倍增。

先跑一次暴力求出原树的答案，更新的时候像莫队一样先减去原来的答案，然后 $\mathrm{update}$ 一下再加上新的答案就行了。$O(n+q{\log }^{2}n)$。

T3

不会。

T4

不会。

？

$2024/11/13$ Wed

T1 AT_agc015_d [AGC015D] A or...or B Problem

？

思路一小时，

oo 不慎开太小，

调题三个钟。

——Garbage_fish 于 2024/11/13 21:41

神秘「找规律」做法。

T2 CF1295F Good Contest

解析：考虑 DP，将左右边界离散化，根据题意单调不降的要求，可以将 $r_i\leftarrow \underset{j\le i}{min}{r}_j$，$l_i\leftarrow \underset{j\ge i}{max}{l}_j$。

离散化后，这 $2n$ 个左右边界会将能取的数分割成 $(2n+1)$ 组，设 $f_{i,j}$ 表示前 $i$ 个数中在第 $j$ 组的方案数，$l_i$ 表示第 $i$ 组离散化前的实际长度，则有：

$$f_{i,j}\leftarrow \sum _{k=1}^{i-1}\sum _{x>j}{f}_{k,x}{C}_{l_i+i-k}^{i-k}$$

后面的组合数表示将 $k+1\sim i$ 都放到第 $j$ 组的方案数，是插板法。显然杨辉三角和根据公式算都不可行，会 TLE+MLE。由于 $i-k\le n$，且这个 $C$ 总是上标下标同时增，可以令 $c_x=C_{l_i+x}^x$，根据组合数的定义，易得 $c_1\leftarrow l_i$，$c_i\leftarrow \frac{c_{i-1}(l_i+i-1)}{i}$，$O(n)$ 预处理即可。

显然第二个和号前缀和即可优化掉，总时间复杂度优化到 $O(n^3)$。

类似题目：P3643 [APIO2016] 划艇。

T3 AT_arc173_d [ARC173D] Bracket Walk

解析：观察可得如果能构造出一种 ( 和 ) 个数相同的序列，那么就可以构造。

称 ( 比 ) 严格多的环称为 ( 环，严格少的称为 ) 环。

由于图强连通所以一定有环，如果没有 ( 环和 ) 环，说明 ( 和 ) 个数相同，可以任意构造出答案。

如果有一个环上的 ( 比 ) 多，那么就可以不断增加 ( 的个数，同理，如果有一个环上的 ) 比 ( 多，就可以不断增加 ) 的个数。由于并不关心最后 () 的个数，根据我拙劣的数学知识，可以在两种环上分别走一定次数使得 ( 数和 ) 数平衡。

所以，如果既有 ( 环也有 ) 环，那么也可以构造出答案，否则就是不行。

T4 AT_agc008_f [AGC008F] Black Radius

待补。

$2024/11/14$ Thu

水母 cm 记。

T1

简要题意：给定 $l,r\le {10}^{18}$，定义 $x(i)$ 表示与 $i$ 的差的绝对值最小的完全平方数，求：

$$\sum _{i=l}^r-(-1{)}^{x(i)}i$$

解析：考虑求 $[1,x]$，定义 $r={\lfloor \sqrt{x}\rfloor }^2$。

一目了然，求 $[r,x]$ 即可求出 $[1,x]$，而 $[r,x]$ 算一下哪里负哪里正等差数列求和即可。

求 $[l,r]$ 容斥即可。

T2

简要题意：给定一张 $n$ 点 $m$ 边（${10}^5$ 级）带权有向图，设 $1\to i$ 的最短路有 $n_i$ 条，第 $j$ 条路径经过了 $d_{i,j}$ 条边，求：

$$\sum _{i=1}^n\sum _{j=1}^{n_i}\sum _{k=j+1}^{n_i}{d}_{i,j}{d}_{i,k}$$

解析：数学不好，人机暴力推式子方法。

首先考虑这种情况：

已知 $x$ 的前一个点有 $a,b,c$ 三种长度的合法路径，$x$ 的答案是多少？

$$\begin{array}{rl}& (a+1)(b+1)+(a+1)(c+1)+(b+1)(c+1)\\ & =ab+a+b+ac+a+c+bc+b+c+3\\ & =(ab+ac+bc)+2(a+b+c)+3\end{array}$$

观察，易得设点 $u$ 的答案是 $an{s}_u$，到点 $u$ 的最短路径经过的边数和 $su{m}_u$，路径数 $cn{t}_u$，如果有边 $u\to v$：

$$\begin{gathered} an{s}_v\leftarrow an{s}_u+(cn{t}_u-1)(su{m}_u)+\frac{cn{t}_u(cn{t}_u-1)}{2} \\ su{m}_v\leftarrow su{m}_u+cn{t}_u \\ cn{t}_v\leftarrow cn{t}_u \end{gathered}$$

这时 $x$ 有了 $a^{\prime },b^{\prime },c^{\prime }$ 三种方案，又来了两个 $d,e$ 也是合法的，考虑如何合并。

首先如果只有 $d,e$ 相乘，那么和上面一样，接下来考虑 $a^{\prime },b^{\prime },c^{\prime }$ 和 $d,e$ 交叉相乘这一部分的答案。

$$\begin{array}{rl}& a^{\prime }(d+1)+a^{\prime }(e+1)+b^{\prime }(d+1)+b^{\prime }(e+1)+c^{\prime }(d+1)+c^{\prime }(e+1)\\ & =(a^{\prime }+b^{\prime }+c^{\prime })(d+e+2)\end{array}$$

所以：

$$\begin{gathered} an{s}_v\leftarrow an{s}_v+an{s}_u+(cn{t}_u-1)(su{m}_u)+\frac{cn{t}_u(cn{t}_u-1)}{2} \\ an{s}_v\leftarrow an{s}_v+su{m}_u(su{m}_v+cn{t}_v) \\ su{m}_v\leftarrow su{m}_v+su{m}_u+cn{t}_u \\ cn{t}_v\leftarrow cn{t}_v+cn{t}_u \end{gathered}$$

求个最短路跑即可。

T3

简要题意：写一个数据结构，支持区间求和，区间求平方和，单点修改，区间向下取整除，支持负数操作。

解析：参考 P4145 上帝造题的七分钟 2 / 花神游历各国，对于区间除，如果除正数，除到 $-1/0$ 再除也没用，如果除负数，除到 $0/1$ 再除也没用。如果区间除的时候发现某个区间满足里面全都是没用的，如果除负数，给他做个取反操作，然后就不管它了，否则直接暴力递归下去一个一个除。当然如果除负一可以直接一个取反求跑路，起到一定的优化作用。

取反操作可以用懒标记维护，记得 しかのこのこのこ push down down（↓）即可（不会有人机忘记 push down 调半天吧）。

T4

待补。

$2024/11/15$ Fri

T1

简要题意：求 $(l,r)$ 的对数满足 $l,r\in [0,n]$ 且 $l\oplus r=l|r$。$n\le 2^{({10}^6)}$。

解析：非常好暴力推式子，使我浪费四小时做一题。

考虑固定 $n$ 的前 $i$ 位不变，若第 $i$ 位是 $1$，则可以钦定这一位为 $0$，接着 $i+1\sim n$ 就可以任意选，具体来说，可以令 $i+1\sim n$ 全部填 $1$，里面填 $j$ 个 $0$，则这一部分的方案数是 $C_{n-i}^j$，假如这个是 $l$，那再选一个 $r$ 就可以先全部填 $0$，然后在 $i+1\sim n$ 中的 $j$ 个 $0$ 和 $1\sim i$ 中的 $c_0$ 个 $0$ 随便选几个变成 $1$，这里的方案数是 $2^{j+c_0}$，故方案数是：

$$\sum _{s_i=1}\sum _{j=0}^{n-i}{C}_{n-i}^j\times 2^{j+c_0}=\sum _{s_i=1}{3}^{n-i}\times 2^{j+c_0}$$

但是这样就漏了所有 $1$ 都取的情况，易得这一种情况就是在上界 $n$ 的二进制中的 $c_0$ 个 $0$ 中取若干个填成 $1$，方案数是：

$$2\times 2^{c_0}$$

T2

待补。

T3

待补。

T4

待补。

$2024/11/16$ Sat

飞鹰班人机场。

晚上回 ss 看校庆，发现「集训时很在意的前桌竟然是我的校友？！」，结果发现全是人机节目，就最后那几千块钱的烟花有点看头。拍了每次上五楼都想拍的日落，但最终幻想还是没有实现。

T1

简要题意：给定一个只有 $1,2$ 的序列，每次交换相邻的两个数，求将所有 $2$ 置于序列的最左边或最右边的方案数。

解析：人机题不写。

T2

人机大模拟不写，用一个 set $s_{i,j}$ 维护状态是 $i-j$ 的队伍即可。

T3

简要题意：给定一张无向图，若断开边 $(u,v)$ 后图连通，则称新图的最小生成树的最大边权为 $f(u,v)$，求所有合法的 $f(u,v)$ 的期望值。

解析：先求出最小生成树，剩下的 $(m-n-1)$ 条边的 $f$ 值都是这个最小生成树的最大边权。接着考虑连上剩下的 $(m-n-1)$ 条边中的某一条，易得原最小生成树上 $u\to v$ 中间有一条边可以不连，方案数就是 $u\to v$ 的边数。但是会发现如下图所示，$1\to 6$ 这条边连上之后，实际有贡献的只有 $1\to 2$ 和 $5\to 6$，$2\to 4$ 中间的两条边已经被 $2\to 4$ 这条边给“占用了”，因此将 $(m-n-1)$ 条边按边权从小到大排序，每次将中间算过的路径打上标记让它不要再算，像我这样的 ** 用树链剖分维护即可。

T4

简要题意：给定平面上 $n$ 个点，$q$ 次询问，只能斜 ${45}^{\circ }$ 或者和坐标轴平行着移动，每次询问给出 $[l,r]$，求 $\mathrm{\forall }i,j\in [l,r]$，$i\to j$ 移动距离的最大值 $a+b\sqrt{2}$ 中的 $a,b$。

解析：如果有两个点 $(x_1,y_1)$ 和 $(x_2,y_2)$，令 $A=|x_1-x_2|$，$B=|y_1-y_2|$，则它们之间的距离：

$$\begin{array}{rl}& \sqrt{2}\times min(A,B)+|A-B|\\ & =(\sqrt{2}-1)\times min(A,B)+max(A,B)\\ & =max((\sqrt{2}-1)A+B,(\sqrt{2}-1)B+A)\\ & =max((\sqrt{2}-1)\times (max(x_1,x_2)-min(x_1,x_2))+max(y_1,y_2)-min(y_1,y_2),(\sqrt{2}-1)\times (max(y_1,y_2)-min(y_1,y_2))+max(x_1,x_2)-min(x_1,x_2))\end{array}$$

使用 $8$ 个 ST 表维护即可。

$2024/11/17$ Sun

睡觉，爽！

赛博朋克，爽！

PUBG，爽！

《继母的拖油瓶是我的前女友》，好看！

新宿管，**！

晚上和 Shxt_Plus 斗图。

$2024/11/18$ Mon

T1

简要题意：求 $\sum _{i=l}^r\lfloor \frac{2^i}{3}\rfloor$，$l,r\le {10}^{1}8$。

解析：

$x$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$
$\lfloor \frac{2^x}{3}\rfloor$	$0$	$1$	$2$	$5$	$10$	$21$	$42$	$85$	$170$
$\sum _{i=1}^x\lfloor \frac{2^i}{3}\rfloor$	$0$	$1$	$3$	$8$	$18$	$39$	$81$	$166$

观察易得

$$\begin{array}{rl}\sum _{i=1}^x\lfloor \frac{2^i}{3}\rfloor & =\lfloor \frac{2^{x+1}}{3}\rfloor -\lfloor \frac{x+1}{2}\rfloor \\ & =\frac{2^{x+1}-(1+((x+1)mod2))}{3}-\lfloor \frac{x+1}{2}\rfloor \end{array}$$

求 $[l,r]$ 的答案容斥即可。

T2

简要题意：给定长度为 $m\le 100$ 的排列 $b$，求不同的长度为 $n$ 的序列 $a$，经过若干次 $a_i\leftarrow b_{a_i}$ 的操作后，序列 $a$ 变回本身的操作次数的期望值。

解析：将 $b_i$ 向 $i$ 连边，发生产生了若干个环，$a$ 中每一位都可以选一个环，最后的操作次数就是选的所有环的环长的最小公倍数。由于会发现每个连通块都一定是一个环，所以并查集维护即可。

接着考虑算方案数，先算出选 $m$ 个数的排列数，设 $g_i$ 表示这个值，首先可以得到 $g_i\leftarrow i^n$，再容斥减去不合法的：$g_i\leftarrow g_i-g_j\times C_i^j$，这一部分复杂度只有 $O(m^2)$。然后算选 $i$ 个数恰好组成公倍数集合 $s$ 的方案数 $f_{i,s}$。

由于 $m\le 100$，所以不同的环长至多只会有 $13$ 个，故 $s$ 的大小可以压缩到 $2^{13}$。

$$f_{i,s}\leftarrow \sum _{j=1}^m{f}_{i-1,s\oplus 2^{i{d}_j}}$$

这一部分的复杂度是 $O(2^{13}\times m^2)$。

最后答案是：

$$\sum _{i=1}^m\sum _{s=1}^{2^{13}}(g_i\times f_{i,s}\times {\mathrm{lcm}}_{j\in s}{v}_j)$$

T3

待补。

T4

简要题意：给定 $n\le 250$ 个人，每个人有三个属性，你可以任意的给他们排序，或者使用魔法增加某个人的某个属性值 $1$ 点，为了使每个人的三个属性都大于等于编号小于它的三个属性，求出使用魔法的最小次数。

解析：离散化后直接考虑暴力的 dp，设 $f_{a,b,c}$ 表示考虑的三个能力值的排名分别不大于 $a,b,c$，考虑转移到 $f_{a+1,b,c}$。

先取出排名为 $a+1$ 的人，如果他剩下两个能力值排名大于 $b,c$，他不能成为当前考虑的数，否则最小代价是把这个人的剩下两个能力值提到 $b,c$ 所对应的值，记录一下离散化后的对应数算即可，对于剩下两种转移同理。

$2024/11/19$ Tue

四题不会。

$2024/11/20$ Wed

T1

简要题意：有 $n\le {10}^6$ 个硬币，有的是正面，有的是反面，翻 $i$ 需要 $t_i$ 的时间，但必须把 $[i,r_i]$ 全部翻一次，求翻到正面的最小时间。

解析：易得从左到右有反面必须翻，差分数组维护当前这一个是正是反即可。

T2

简要题意：给定 $n\le {10}^6$ 个长度为 $m\le 20$ 的二进制串 $a_i$ 以及常量 $c$，第 $i$ 个串的代价是：

$$min(c,\underset{j\in [1,i)}{min}\{\mathrm{popcount}(a_i\oplus a_j)+1\})$$

求所有串的最小代价和。

解析：考虑每个数向它异或掉某一位之后的数连一条边权为 $1$ 的边，初始时每个数的点权都是 $\mathrm{\infty }$，当某个数可用于 $min$ 右边的异或操作之后，将它的点权设为 $1$ 跑最短路，由于易得所有数的点权一定会越来越小，所以最短路的距离数组不需要清空，合法的点权最大为 $20$，所以每个点最多被经过 $20$ 次，点数是 $2^m$，这一部分的总时间复杂度是 $O(m{2}^m)$。不带 $\log$ 的原因是边权全为 $1$ 的图使用 bfs 即可实现最短路。

T3

待补。

T4

待补。

$2024/11/21$ Thu

前两题笔记待补，后两题不会。

$2024/11/22$ Fri

四题不会。

有个套路觉得很妙，对于在一串序列中找到相邻两个一正一反的位置，可以先找到最正和最反的位置，然后这两个位置的中点必然和其中一边相同，另一边相反，对于相反的一边继续二分。

$2024/11/23$ Sat

飞鹰班挂分场，笔记待补。

dp 的时候不能存这个状态里到底有些啥，极难或不可能维护，应该思考这个状态存的信息到底是干嘛用的，然后去重新设计状态。

$2024/11/24$ Sun

忘记干啥了。

$2024/11/25$ Mon

又来一批人，早上被拉回石实颁奖，下午初中被嫌太吵全部拉到电脑三室去了，然后我还被 gj 选作班长……

不要轻信 CCF 的样例，最好写对拍。如 NOIP 2022 T1。

需要注意：多组数据清空时，特别要注意 依赖于边界是空信息而计算 的数组的清零。

$2024/11/26$ Tue

测试，但是是暴力场，一个正解加两个 DFS 再加一个 T 飞天际的 KMP 拿下 $281$ 分。

如果注意到范围再小一点就可以实现大暴力 DP（如状压），可以先考虑钦定某些数来缩小范围。如本日 T2。（在 $300$ 个数中选若干个使得 $gcd$ 为 $1$，选不同的数有不同的代价，求最小代价。）

对于一些范围较小的 DP，可以考虑暴力设状态，差什么设什么，要敢于尝试；转移要多观察整体，自己多手画样例研究，或者再考虑优化。如 NOIP 2021 T2，NOIP 2023 T3，NOIP 2023 T4，2024 大湾区 T2，CSPS 2024 T3。

要是范围大就考虑给状态添加限制条件，将状态分成若干类，如 NOIP 2022 T3。

$2024/11/27$ Wed

又是暴力 + 原题场，题面还一堆 Bug。

对于关 long long 卡常，应手造大数据或简要计算以思考必要性，并且对于特别是答案计算的部分，思考是否能构造极限数据以卡爆 int。