在讨论《「chaynOI-R2」赛时答疑帖》回复：

QP

1. 在更新合法 $L,R$ 的时候如果 `continue` 要先更新一下： ``` cpp for (int i = m, L = 0, R = INF; i >= l; i--) { if (L > R || i + R r) { L = max(L, a[i]), R = min(R, b[i]); conti…

在讨论《关于 FWT 的问题》回复：

@[zjh114514](luogu://user/773944)@[CaiZi](luogu://user/728853)@[Gary_zhan](luogu://user/768784) /bangbangt

在讨论《关于 FWT 的问题》回复：

@[Jordan_Pan](luogu://user/1002571) https://www.doc88.com/p-9485624205963.html

在讨论《关于 FWT 的问题》回复：

@[Herman526](luogu://user/786834) 哦似乎确实是这样的，因为定义了 $\widehat f_S^{(0)}=f_S$ 而不是 $(-1)^{|S|}f_S$。

在讨论《关于 FWT 的问题》回复：

$U_i$ 是 $\{1,2,...,i\}$，$\in$ 似乎要改成 $\subseteq$。

在讨论《关于 FWT 的问题》回复：

$U_i$ 是 $\{1,2,3,...,i\}$。

在推导递归式的时候：  求问是怎么推出来的，为什么我推出来（第一个式子）是 $\widehat f_{…

在讨论《求问关于大样例强度》回复：

@[CommandSR](luogu://user/844860) 哦对就是这个，不是要判 $a_i>\frac{a_n}{2}$ 吗，那如果 $i<n$ 且 $a_i=a_n$ 的话也是合法的

在讨论《求问关于大样例强度》回复：

@[CommandSR](luogu://user/844860) 等等，让我想想我改了啥

在讨论《求问关于大样例强度》回复：

@[CommandSR](luogu://user/844860) 是，准确来说是只选一个价值为 $1$ 的 $i$

在讨论《求问关于大样例强度》回复：

@[CommandSR](luogu://user/844860) 我没过 2 是少判了只选一个且 $i<n,a_i=a_n$ 的情况

以此篇题解记录我失败的 NOIP。这凭啥有紫啊，还有和范德蒙德等式有啥关系。 考虑不优的情况，一种是可以把最小的两个 $1$ 换成一个更大的 $2$，设可以把 $a_i,a_j$ 换成 $a_k$，那么要求 $a_i+a_j k$ 无论怎样都会被选，$j j$ 的部分才会被选，把一定被选的后 $n-k$ 个数贡献扣掉，…

## $\text{Day -INF}$ 前提简要：CSP 坠机了，脑子正常一点至少能 280+，但还是进 NOIP 了。 开始加训 cf，做了一堆神秘计数和随机选的贪心和 ds。 梦熊炼石连吃了两场放弃了，周赛打了一场直接乱搞出正解，获奖了。 初中生不能申请 Linux，生祺了。三中力行楼网络教室 2 53 号。 #…

在讨论《令人愤慨，没有题解解释为什么答案表示为2max(d1,d2)》回复：

我觉得题解说的不准确的是停在原地的操作最多只有一个，否则可以替换为一个上一个下

在讨论《令人愤慨，没有题解解释为什么答案表示为2max(d1,d2)》回复：

@[MspAInt](luogu://user/736801) 你都是上升下降了时间就是高度啊

好题，分享一下史山做法（）首先将最小化删除转化为最大化保留。 暴力 dp：设 $f_i$ 表示选到父亲的边，子树内的答案，$g_i$ 表示不选到父亲的边的答案，每次转移先全部用 $g$，然后选 $f-g$ 前 $x-1$（转移到 $f$）和 $x$ 大的（转移到 $g$）进行更新，对于每个 $x$ 都做一遍，用优先队列…

在文章《题解：P11455 [USACO24DEC] Cowdepenence G》发表评论：

已更正

在文章《题解：P14522 【MX-S11-T3】空之碎物》发表评论：

两只 log 吧

$nm\le3\times 10^5$，因此可以设 $f_{i,j}$ 表示考虑 $i$ 的前 $i$ 个数 $k=j$ 的最小花费，$g_{i,j}$ 表示方案数。 操作 $1$ 是简单的，$(i,j)$ 就是从 $(i,j-1)$ 转移而来。 对于操作 $2$，容易发现 $j$ 固定的情况下 $f$ 随着 $i$…

没想到按 $a$ 排序怎么办？发现有贡献的一定是 $a$ 最大，$b$ 最大，或者 $a+b$ 最大的，st 表预处理出来，用 set 维护当前所有可以贡献的连续段，每次分裂把两边最优的加进去即可。 时间复杂度 $O(n\log n)$，但是最大点 2.8s。

首先容易想出记录 $h$ 的 dp 做法但无法优化。 手玩一下：先不考虑其他操作，假设 $i-1$ 和 $i+1$ 的高度已经定下来了，那么只有 $h_i\le\min(h_{i-1},h_{i+1})$ 的时候对 $i$ 操作才可能更优。那是否一定只有满足上述条件的才变？ 很可惜，并不是。不妨设 $h_{i-1} #…

在文章《题解：P14522 【MX-S11-T3】空之碎物》发表评论：

写错了都是 logV

在讨论《CF 比赛遇到瓶颈》回复：

@[zjh114514](luogu://user/773944) 多练，多思考，理解透彻

先考虑刻画答案。对于合并和拆分的操作，如果对应都要求涉及的数的和相等。手玩一下，发现相当于将序列划分为若干个新区间，并且对应位置（回文）的区间和相等。答案就是区间长度减新区间个数。 有贪心的做法：对于首尾两个区间，长度越小越好，否则可以继续划分。直接做可以做到 $O(n^3)$。 然后想办法直接计算这个东西。把类似递归…

笑点解析：考场上没仔细想以为是乱搞并写了剪枝，怕 T 于是：```up = (n 0$，否则构造 $x=fi$ 则可保留 $x$ 的最高位。若 $l_2 #define int long long using namespace std; const int N = 2e5 + 5; const int P = 998…

显然答案具有单调性，所以先二分 $p$。 考虑 dp。整个序列可以以 $x$ 为中点拆成前后两半，这两部分是类似的，下面以前半部分为例。 由于是否合法和最终选了多少个数有关，因此设 $f_{i,j}$ 表示前 $i$ 个数，最终选了 $i$ 个数，当前最多能选多少个数。转移：$f_{i,j}=f_{i-1,j}+[a_…

显然一个数有效的出现次数就是两次，一个最前面一个最后面的，设 $x$ 的两者分别为为 $fi_x,se_x$。 最后的答案就是 $\sum_{i=1}^m se_i-fi_i$，其中 $m$ 为有效的数的个数。发现这也能写作 $\sum_{i=1}^m se_i-\sum_{i=1}^m fi_i$，所以实际上我们并不…

当染了 $x$ 之后序列会被划分成贡献互不影响的两段，于是考虑区间 dp。 设 $f_{l,r,x,y}$ 表示只考虑 $[l,r]$ 这个区间，钦定 $l-1$ 和 $r+1$ 已经染色了，对 $l-1$ 的贡献是 $x$，对 $r+1$ 的贡献是 $y$ 的方案数（对于 $l=1$ 或 $r=n$ 的在后面枚举的时…

一次操作相当于 $(x,y)\to (2c_i-x,2c_j-y)$，令 $d=x-y$，则将 $d\leftarrow 2(c_i-c_j)-d$，那么根据裴蜀定理，$d$ 能变为 $0$ 的充要条件是 $2\gcd(c_i,c_j)\mid d$（正负号不用管因为相反一下就行了）。 考虑每次操作一定是操作 $f$…