本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-15 17:48:26

lxn 要求写笔记，所以就写笔记了。

学习了一些新的 tricks。

• P2371 [国家集训队] 墨墨的等式
  本质上和跳楼机相同。
  另外，可以通过差分忽略 $l$ 的限制。
  可以看成初始在 $0$，每次可以上升 $a_i$ 格，或者回到 $0$，问 $r$ 以下的格子有多少能到达。
  这里注意，如果一个层数 $x$ 可以被到达，那么 $x - k \cdot a_i$ 也可以被到达。
  也就是说，我们可以在模意义下执行操作！！！
  事实上选择任何一个 $a_i$ 进行取模都可以，但是为了更快的计算，这里选择 $\min_{1 \le i \le n}a_i$。
  然后没然后了。
• P5304 [GXOI/GZOI2019] 旅行者
  首先，如果是两个点集，求在两个集合各选一个点使得最短路长度最小，只需要建立一个超级源点，一个超级汇点，源点到汇点的最短路就是最小值。
  假设 $x,y$ 在原图中最短路最小，则试图把他们分成两个集合。
  想一想以什么为依据划分，使得他们一定包含在不同的集合中。
  注意到 $x,y$ 至少有一位二进制不同，所以可以依此枚举 $i$，编号第 $i$ 位为 $0$ 放入第一个集合，否则放入第二个集合，然后反过来跑一遍。
• Complete The Graph
  两种做法。
  首先，假设不确定的边全是最小值 $1$，共有 $c$ 个边不确定，然后依此将 第 $1,2,3,\cdots,c,1,2,3,\cdots,c,1,2,3,\cdots$ 加 $1$，这样每次最短路最多加 $1$。
  只需要二分就行。
  第二种，不确定的边按照最小值 $1$ 跑 dijkstra，记录 $dif = L-dis_t$，第二次 dijkstra 大概是以动态确定的方式，若 $dis_{to} + dif \gt dis_u + edge[i].val$，那么修改本边的权值使得 $dis_{to} + dif = dis_u + edge[i].val$，这样就能保证最终的最短路加上 $dif$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-10-15 16:03:56

将字母看成 $[0,25]$ 的数字。

每次修改都视为模 $26$ 意义下的区间加法。

对于询问，注意题目要求没有任何回文子串，这等价于 ${\forall i} \in [1,n], s_i \neq s_{i+1}, s_i \neq s_{i+2}$，对此维护数据结构标记它们的相等关系。

想一想如何维护区间加法，以及 $s_i$ 是否等于 $s_{i+1}$ 或 $s_{i+2}$。

一次区间加法操作结束后，被修改区间内部相等关系不会有变化，主要考虑边界变化。设加法操作区间为 $[l,r]$，那么我们需要更新 $l-1,l-2,r,r-1$ 位置的相等关系记录。

而查询操作，设区间为 $[l,r]$ 则意味着 $l \le {\forall i} \le {r-1}, s_i \neq s_{i+1}, l \le {\forall i} \le {r-2}, s_i \neq s_{i+2}$。

第一种操作包含区间加法，单点查询（和区间加法共用数据结构，用于修改相等关系），单点修改（相等关系的标记，和区间加法独立）。

第二种操作包含区间查询（和第一种操作的单点修改共用数据结构，查询相等关系）。

显然可以树状数组，但我赛时脑子抽了，写了 250 整行分块，不过也 50min 写完一发 AC 了，反正是打星就图个愉快。

提交记录

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-10-18 21:12:27

感觉是一道水紫，主要考察对级数求和公式的背诵。

不过除了我这个蒟蒻，大佬们应该都有实力在赛时发明公式。

为方便表示，比较长的整体在句子中用括号表示。

Sol

自然而然想到 dp。

考虑如何设计 dp 状态？

• 考虑逐层递推？
• 题目要求的是第 $n$ 层最终透过了多少光。
• 光线会反复弹射，所以第 $i$ 层的最终透光率和（光反射进入前一层然后弹射出来的占比）直接挂钩。

显而易见，可以设 $f_i$ 表示前 $i$ 层的透光率，$g_i$ 表示从 $i$ 层之后的空气中射入前 $i$ 层，不考虑折射，然后反弹出来回到 $i$ 层之后的空气中的光线占最初光纤的占比。

然后，分别计算。

• 对于 $f_i$，光纤来源是 $f_{i-1}$，每打中一次第 $i$ 层玻璃，都有 $\frac{a_i}{100}$ 的占比进入下一层，剩余 $\frac{b_i}{100} \cdot g_{i-1}$ 的占比留到下一次打中第 $i$ 层玻璃。
• 所以：$f_i = \sum\limits_{p=0}^{\infty}{f_{i-1} \cdot \frac{a_i}{100} \cdot (\frac{b_i}{100} \cdot g_{i-1})^p}$
• 对于 $g_i$，可以用类似方法简单推导得出以下结论。
• $g_i = \frac{b_i}{100} + \sum\limits_{p=0}^{\infty}{\frac{a_i}{100} \cdot g_{i-1} \cdot (\frac{b_i}{100} \cdot g_{i-1})^p \cdot \frac{a_i}{100}}$

可以发现 $f_i,g_i$ 的计算，只要把多余项提出去，就变成了典型的指数级数，所以：
$f_i = f_{i-1}\cdot \frac{a_i}{100} \cdot \sum\limits_{p=0}^{\infty}{ \cdot (\frac{b_i}{100} \cdot g_{i-1})^p}$

$g_i = \frac{b_i}{100} + \frac{{a_i}^2}{10000} \cdot g_{i-1} \cdot \sum\limits_{p=0}^{\infty}{(\frac{b_i}{100} \cdot g_{i-1})^p}$

带入公式 $\sum\limits_{k=0}^{\infty} x^k = \frac{1}{1-x}$ 直接算就行了。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-10-19 16:45:45

Sol

题目本质是设置一个数值下限，选中数组中数值下限以上的所有数，将连在一起的被选中数视作一个连通块，求连通块数量。

先离散化一遍把数据范围从 $10^9$ 降到 $4 \cdot10^5$。

先预处理能力下限为 $i$ 的答案，并用数据结构维护。

重点是如何维护。

• 设能力下限是 $lim$

• 设一次操作中，操作位置 $pos$，新数是 $d$，原数是 $old$。

• 对于 $d \ge old$：

• 在 $lim = [old+1,d]$ 的所有情况中，原来位置 pos 不会被选中，而现在会被选中。

• 那么这个变化如何对 $lim = [old+1,d]$ 的情况们造成影响呢？

• 情况 1，位置 $pos-1,pos+1$ 都被选中：

• 连通块个数 -1。

• 情况 2，位置 $pos-1,pos+1$ 只有一个被选中：

• 连通块个数不变。

• 情况 3，位置 $pos-1,pos+1$ 都没有被选中：

• 连通块个数 +1.

• 分别计算情况 $1,3$ 对应的 $lim$ 区间，它们与 $[old+1,d]$ 分别的交就分别是 $1,3$ 情况的影响的 $lim$ 区间。

• 然后更新受影响区间的答案。

• 对于 $d \le old$：

• 和 $d \ge old$ 差不多。

可以发现是区间修改单点查询，使用树状数组即可。

Submission

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-10-25 00:17:52

bing 上死活搜不到，搜索能力还是不行。

虽说对于大佬们，都能一眼秒掉，但我太菜曾经很久没推算出来，今天写小蓝本时，搞错了某个步骤，意外找出了解决法案。。。。。。。

设 $\frac{a}{b}+\frac{b}{a} = x$，$x$ 给定。

$\frac{a^2}{ab}+\frac{b^2}{ab} = x$

$a^2+b^2 = xab$

$\frac{a^2+b^2}{a^2} = \frac{xb}{a}$

$1+\frac{b^2}{a^2} = x \cdot \frac{b}{a}$

$(\frac{b}{a})^2 - x \cdot \frac{b}{a} + 1 = 0$

$\frac{b}{a} = \frac{x \pm \sqrt{x^2-4}}{2}$

设 $n = \frac{a}{b}$，原等式变为 $n + \frac{1}{n} = x$。

容易得到，$n = \frac{2}{x \pm \sqrt{x^2 - 4}}$

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-11-02 13:34:47

对我来说的难度: A<B<F<D<<C<E

A

从前向后贪心就好了.

B

每个数 $a_i$ 最多被操作 $\lfloor \log_2 a_i \rfloor$ 次.
每次操作,$a_i$ 会变成 $2^{x_i - 1}$ 的倍数.
暴力维护就好了.

C

最优方案是技能 1 干掉一半,剩下使用技能 2 解决.
应最小化使用技能 2 的次数.

考虑最少要用多少次,这里可以显然得出一个结论,设将 $a$ 排序从大到小后,第一个前缀和大于等于 $\frac{\sum\limits_{i=1}^{n}a_i}{2}$ 的元素编号为 $pos$,那么这 pos 个元素都是需要使用技能 $2$ 的.
不难的得出,总答案是 $\lceil \frac{\sum\limits_{i=1}^{n}a_i}{2} \rceil + pos$.

D

显而易见 f 的变化次数是 log 级别,而在 f 相等的情况下, g 的变化次数是 log 级别.
二分就行.

E

贪心题。
可以先拆分成一些由前后互质的数组成的数列。
由于 $1$ 是一个特殊的存在，直接操作非 $1$ 的数，若旁边有相邻的 $1$，那么不会改变与 $1$ 的 gcd，所以将所有 $1$ 找出来，记录所有连续 $1$ 的段落，另外如果连续 $1$ 子段的某一端在 $1$ 或 $n$，则按照贪心策略应放到最后操作。

特别地，如果整个数组全是 $1$，答案是 $n-k$。
具体的，将所有不包含 $1$ 互质子段扔进队列 $1$，所有不包含位置 $1,n$ 的连续 $1$ 子段扔进队列 $3$，另外设一个队列 $2$，后面解释。

然后，很明显，有以下贪心过程。

• 首先遍历队列 $1$，对于非 $1$ 互质段落，可以发现每段从第 $2$ 个开始，到第 $len-1$，隔一个数操作一个数，可以做到每次操作，答案 -2。对于操作剩下的数，如果一个数两边都是 $0$，那么可以扔掉不管，如果仍然剩下两个前后互质的数，将这两个数组成的子段扔进队列 $2$。

• 然后按照长度从小到大遍历队列 3 ，对于连续 $1$ 子段，对于每个子段，若能解决掉 $x \le len-1$ 个数，则答案减去 $x$，否则答案减去 $len+1$。

• 然后遍历队列 $2$，每个区间都有 $1$ 的贡献。

• 最后寻找剩下的 $1$，每个数字 $1$ 有 $1$ 的贡献。

Submission

F

为了方便,将询问离线,提前建立最终的树.

• 操作一,建立新点,应当先消除当前点及其子树原有受到的来自祖先影响.

• 操作二,修改子树,直接改最终形态就行.

对于修改子树,可以提前 dfn 标号,这样整个子树的 dfn 是连续的一段区间,随后使用树状数组.

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-11-05 12:29:05

md，D 题想到了 01trie 结果赛时脑子进水，以为会 TLE，E 题大水题结果没做。

A

Greedy.

B

本质上是把原数组按升序或降序后划分成两个长度相等的子序列，答案是两个数组分别的最大值减最小值的绝对值。

暂且按照升序来。

先把原数组排序，并且考虑划分后的第一个序列包含哪些位置。

显然必然是连续 $n$ 个位置。

C

预处理长度为 $i$，总和为 $j$ 的数组数量，然后没啥了。

D

$b_{n-1} = b_n \oplus a_{n-1}$
$b_{n-2} = b_{n-1} \oplus a_{n-2} = b_n \oplus a_{n-1}\oplus a_{n-2}$
$\cdots$
$b_{1} = b_{n} \oplus a_{n-1} \oplus a_{n-2} \cdots a_1$

把 $b_1 \oplus b_n,b_2 \oplus b_n ,\cdots,b_{n-1 }\oplus b_n$ 插入 01trie，然后枚举 $b_n$，由于题目保证有解，所以无论 $b_n$ 取值如何，最终 $b$ 数组一定满足第一条要求；每次枚举 $b_n$ 只需要检查 $b_n$ 和 01trie 里面插入的值的异或最大值是否小于 $n$。

E

容易想到，也容易证明， 当一个人打出一个血量为 $a$，伤害为 $b$ 的牌时，另一个人打出的牌应在伤害大于 $a$ 的基础上，满足血量尽可能高。

也就是说可以对于每张牌，预处理出打出它之后另一个人应该选择什么牌，用 set 维护可以轻松解决这一部分。

注：一张牌打出后，如果有多张最优的牌可以应对，那么随便选一张标记上，都一样。

然后每个牌向应对它的牌建边。

一张牌打出后，满足以下条件时打出者获胜：

• 没有可以应对的牌。

一张牌打出后，满足以下条件时打出者平局：

• 对手打出应对的牌之后会陷入平局。
• 对手打出了之前打过的牌。

一张牌打出后，满足以下条件时打出者失败：

• 对手打出了应对的牌之后必胜。

F

首先，如果单单计算满足一种条件的方案数，非常简单。

先计算满足条件 2 情况下的方案数，由此寻找突破口。

剩下计算满足条件 2 时，同时满足条件 1 的方案数，此时考虑总方案数减不合法方案数。

设 $f(l,r)$ 代表满足条件 2，且所有元素分布在 $[l,r]$ 的长度为 $n$ 的数组数量。

不合法方案数即 $f(0,\infty) - f(0,x-1) - f(x+k,\infty)$

这些看上去很难计算，先把它们表示出来。

$\cdots$

然后发现 $f(0,\infty) - f(x+k,\infty)$ 可以直接算出来。

另外 $f(0,x-1)$ 可以设计一个 $O(nx)$ 的 dp（第 $i$ 位填了 $j$ 的方案数）。

发现复杂度炸了，注意 $n \le 10^9$，而 $x$ 极小，而第一维转移过程是从 $1,2$ 一直到 $n$，每次转移整个第二维，可以用矩阵快速幂优化。

未完待续。

G

以后或许会补。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-11-08 01:28:19

任务列表 1 （CF Div.2 补题）进度 6/6
任务列表 2 （CF Div.2 补题）进度 6/7
任务列表 3 （ABC 补题） 进度 6/7
任务列表 4 （CF Div.1+2 补题）进度 2/7
任务列表 5（ Vjudge 补题）进度 -114514/inf
任务列表 6（模拟赛补题）进度 0/inf
还剩好多啊。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-11-14 23:57:25

ABCDE 都是一眼题，不写了。

F 题思维比较简单，赛时 并查集 写挂被罚了两发。

G 题有点思维难度，但也就是个状压板子。

因为 whk 赛时只做了 F 就跑路了。

F

将 $a_i,b_i$ 建边，形成的图，对于每个连通分量只需要规定任意一点为 $0$，其他点权值便可推算出来，并判断出矛盾。

看起来不那么容易整体计算答案，那么考虑加边带来的影响。

• $a_i,b_i$ 均未加入图中
  建立一个新的包含 $a_i,b_i$ 两个点的连通分量，并规定 $a_i = 0,b_i =-d_i$。
• $a_i,b_i$ 有一个已经在图中的
  将尚未在图中的点加入已经在图中的点所在的连通分量，并计算出新加入的这个点的点权。
• $a_i,b_i$ 都已经在图中，且 $a_i$ 和 $b_i$ 处于相同连通分量
  此前由于 $a_i,b_i$ 权值已经确定，现在只需要判定原来权值是否满足新的条件即可。
• $a_i,b_i$ 都已经在图中，且 $a_i$ 和 $b_i$ 不处于相同连通分量 此时应合并两个连通分量，这样，要么是 $a_i$ 所在连通分量的所有数加上一个特定值，要么是 $b_i$ 所在连通分量的所有数加上一个特定值（是什么能根据 $a_i,b_i,d_i$ 推算出来），此时启发式合并。

G

显然操作 $1$ 只会执行最多 $1$ 次。

问题转化成将序列 $a$ 分割成若干个区间，将这些区间重新排列后前后连接形成新的序列 $c$，使得 $\sum\limits_{i=1}^{n} |b_i-c_i|$ 最小化。

我的思路是依次加入区间，并算答案。

所以状态：$dp_s$ 表示已经加入集合的点集为 $s$ 的情况下的最小答案。

转移的话，枚举新加入的区间。

看上去复杂度是 $O(2^n \cdot n^2)$ 的，但实际根本跑不满，通过本题绰绰有余。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-11-17 16:59:19

CSP-S 挂了 65分，最后没资格考。