p_b_p_b的博客

博客

Tags
None

Public Round #12 题解

2024-02-25 16:08:26 By p_b_p_b
  • 搬题人
    • 电塔：Wu_Ren
    • 并查集：p_b_p_b, Lynkcat
    • 划分序列：Crysfly
  • 组题人
    • p_b_p_b
  • 题解：部分题解可以见验题人题解。

电塔

来源：

首先把 $x_i$ 从小到大排序，不妨假设 $x_i$ 相对大小关系不变，那么只需满足 $x^\prime_{i+1}-x^\prime_i\ge d$。

设 $y_i=x_i-id$，那么只需保证最终 $y_{i+1}\ge y_i$。同时，在这个过程中我们需要保证 $y_i\ge -id$。

由于我们需要保证 $y_i\ge y_1\ge -d$，所以我们先把比 $-d$ 小的 $y_i$ 先提升到 $-d$，然后就不需要考虑下界的限制了。

那么接下来就是有一个数组，每次给某个数加减一，使得最终单调不降，求最小操作数。

考虑设 $f_{i,j}$ 为 $y^\prime_i\le j$ 且前 $i$ 个数已经单调不降的最小花费，$g_{i,j}$ 为 $y^\prime_i=j$ 且前 $i$ 个数已经单调不降的最小花费，那么有 $g_{i,j}=f_{i-1,j}+|y_i-j|$，容易发现我们的 $j$ 只需要取在 $\{y_i\}$ 里出现过的即可，复杂度 $O(n^2)$。

然后发现假如 $(j,g_{i-1,j})$ 这些点是下凸的，$f\leftarrow g$ 相当于前缀最小值，所以 $(j,f_{i-1,j})$ 这些点也是下凸的，然后 $(j,|y_i-j|)$ 也是下凸的，所以 $(j,g_{i,j})$ 也是下凸的。

同时 $(j,f_{i,j})$ 是呈现分段线性函数的样式，具体的，存在 $0=a_0\le a_1\le a_2\le \dots\le a_i$，使得 $f(x)=f_{i,x}$ 在 $[a_j,a_{j+1}]$ 上斜率为 $j-i$，且 $\forall x\ge a_i,f(x)=f(a_i)$。我们尝试用堆维护 $a_1,a_2,\dots,a_i$ 以及 $w=f_{i,a_i}$。那么从 $f_{i-1}$ 转移到 $f_{i}$ 时，假如 $y_i \ge a_{i-1}$，那么直接令 $a_i=y_i$ 即可；假如 $y_i < a_{i-1}$，那么令 $w:=w+a_{i-1}-y_i$，并设置 $a_{i-1}:=y_i,a_i=y_i$ 即可。

复杂度 $O(n\log n)$。

并查集

来源：

考虑每条边对答案的贡献。合并 $A_i,B_i$ 时，如果令 $A_i$ 为 $B_i$ 的父亲，则这条边被走的次数是 $B_i$ 当前连通块向外连的边数。

因此只要确定了边的顺序，那么一定是让度数小的连通块成为度数大的连通块的父亲。

进一步可以发现，如果 $B_i$ 的连通块度数非零，那么把加边的顺序修改为先合并 $B_i$ 的连通块，再连接 $(A_i,B_i)$ ，再按照原顺序合并 $A_i$ 的连通块，一定不劣。

因此不难证明，最优加边顺序一定满足加入的边在任意时刻都是连通的。即存在一个根，每次加边是把儿子和父亲合并，且父亲此时一定已经与根连通。

感性理解一下，最优加边顺序里，儿子的度数应该不会比上面一整个连通块的度数要大。事实上，如若不然，把儿子选为根一定更优。

于是加入一个儿子就是给答案加上总度数，然后给总度数加上儿子的度数减一。

最后只需要把加入儿子的顺序定下来，满足父亲比儿子早加入。这是一个经典的贪心题，可以用并查集加优先队列实现。

复杂度 $O(n^2\log n)$ 。

划分序列

来源：

咕了，见验题人题解。

Public Round #12 公告

2024-02-18 10:32:11 By p_b_p_b

省选即将来临，Public Round #12 将在 2024 年 2 月 25 日的早上 8:30 举行！比赛将进行 4.5 小时，共 3 道题，OI 赛制。

本次比赛的题目难度可能略低于省选，方便选手整理状态，提振信心。所有题目都有部分分。

本次模拟赛的搬题人为 Wu_Ren, Crysfly, p_b_p_b, Lynkcat ，组题人为 p_b_p_b ，验题人为 znstz, flower, yzc2005, Lynkcat 。

赛后会公开原题链接和题解链接。

特别提醒：本次比赛的题目均为原题，但为了比赛的公平性，请勿在比赛时尝试查找原题地址。如不幸见过原题，请向管理员报告。

Public NOIP Round #6 题解

2023-10-15 13:04:18 By p_b_p_b
  • 搬题人
    • 倒腾：p_b_p_b
    • 探索：p_b_p_b
    • 抉择：feecle6418
    • 重生：p_b_p_b
    • 遍历：Crysfly
    • 排序：Wu_Ren
  • 组题人
    • p_b_p_b
  • 题解：部分题解可以见验题人题解。

倒腾

来源：

直接模拟即可。

探索

来源：

深度优先搜索每一步是否有碰到障碍，并且不能与之前已经定下来的状态冲突，即可 $O(2^n)$ 搜出所有可能的路径。

抉择

来源：

算法一

设 $dp(i)$ 表示 $a[1\dots i]$，其中 $i$ 必须处于子序列中，的答案。转移为 $dp(i)=\max_{j\lt i}dp(j)+(a_j\&a_i)$，时间复杂度 $O(n^2)$，期望得分 $45$。

算法二

对于 $a_i\le 511$ 的数据，可以设 $f(i,j)$ 表示 $a[1\dots i]$，选择一个子序列，子序列最后一个数是 $j$ 的答案。转移为 $f(i,j)=f(i-1,j),f(i,a_i)=\max_{j}f(i-1,j)+(a_i\&j)$。期望得分 $20$。

算法三

如果 $a_i$ 随机，大部分 $a_i$ 肯定都要选。在算法一中强制 $j\ge i-500$ 就可以了。

算法四

考虑如何用类似算法三的思路（大部分时候多选都比少选优）优化算法一。

注意到如果 $i$ 之前选的最后一个数是 $a_x=y$，而存在 $x\lt j\lt i$ 满足 $a_{j}$ 和 $a_x$ 的最高位都是 $2^w$，但是最优解在 $i$ 之前没有选 $j$ 而是选了 $x$，则 $(a_x\&a_i)\ge (a_x\&a_j)\ge 2^w$，说明 $a_i$ 也有 $2^w$ 这一位。那 $(a_x,a_j,a_i)$ 一定比 $(a_x,a_i)$ 优，矛盾了（前者权值至少是 $2^w\times 2$，后者权值至多是 $a_x\lt 2^{w}\times 2$）。

所以可能转移到 $i$ 的 $x$ 只可能是每种最高位出现的最后一个位置。

时间复杂度 $O(n\log V)$。期望得分 $100$。

解法不唯一，本题还有很多形式类似的结论都是对的。

重生

来源：

在路上了！

遍历

来源：

在路上了！

排序

来源：

solution by Wu_Ren

考虑操作变成，把序列 $A$ 划分成 $D_1+D_2+\dots+D_m$，把 $A$ 变为 $rev(rev(D_1)+rev(D_2)+\dots+rev(D_n))$。

因为可以用两步进行一次相邻元素的交换，有一个 $n(n-1)$ 的做法。同时有很多简单的 $n-1$ 的做法。

还有一个分治排序的做法，归并两段有序的 $a_{1,\dots,p},b_{1,\dots,q}$ 时，找到这些数的中位数 $w$，进行一次 reverse 把比 $w$ 小的数放在左边，大的放在右边，显然两个部分还是分别能分成两个有序的段，可以分治并行，总操作数精细实现可以做到 $1+\sum\limits_{j=1} \lceil\log_2(\lceil\frac{n}{2^j}\rceil)\rceil$。当然，也有很多其他 $O(\log n)$ 归并的方法。

正解考虑排序 01 序列，那么把相邻的 0 和相邻的 1 合并，最后有 ...0101...，那么我们划分为 ...|01|0|10|1|01|0 或者 ...01|0|10|1|01，那么操作一次后，段数都会变为原来的 $1/3$ 上取整。

我们从高到低考虑每个位，假设我们对于高的位都排序完了，那对于这一位我们把高位相同的数看作一个序列，相当于对若干个序列进行上面的过程，可以并行，所以对于每个位我们的操作数都是 $\lceil\log_3n\rceil$。

精细实现的话总操作数为 $1+\sum\limits_{j=0} \lceil\log_3(\lceil\frac{n}{2^j}\rceil)\rceil$，在 $n=20000$ 时为 $78$，能过。

Public NOIP Round #6 公告

2023-10-14 23:12:13 By p_b_p_b

Public NOIP Round #6 将在 2023 年 10 月 15 日 8:30 举行！

比赛分为普及组和提高组，普及组进行 3.5 小时，提高组进行 4 小时。普及和提高分别有 4 道题，OI 赛制，组别之间可能存在题目重合。

本次比赛将与 MarsOJ 合作。pjudge 上仍然会有常规模式的比赛，而 MarsOJ 则可以提供仿真 csp / noip 考场环境的云电脑，具体可以加入用户群（915426363）。

选手可以根据训练需求自由选择在 pjudge 或 MarsOJ 参赛。两边都是免费的。

本次比赛的题目难度约为 CSP-J/S ，所有题目都有部分分。

本次模拟赛的组题人为 p_b_p_b ，搬题人为 Wu_Ren, p_b_p_b, feecle6418, Rainbow 。验题人 znstz, namespace_std, Lynkcat 。

赛后会公开原题链接和题解链接。

特别提醒：本次比赛的题目均为原题，但为了比赛的公平性，请勿在比赛时尝试查找原题地址。如不幸见过原题，请向管理员报告。

Public Round #10, #11 公告

2023-07-15 10:03:53 By p_b_p_b

Public Judge 也来蹭 NOI 热度了！

为了帮大家备战 NOI ，Public Round #10, #11 将分别在 2023 年 7 月 18 日和 7 月 19 日的早上 8:00 举行！比赛将进行 5 小时，共 3 道题，OI 赛制。

本次比赛的题目难度分别为 NOI Day1 Day2，所有题目都有部分分。

本次模拟赛的搬题人为 Qingyu, Wu_Ren, feecle6418, p_b_p_b ，组题人为 p_b_p_b ，验题人为 znstz, TBD 。

赛后会公开原题链接和题解链接。

特别提醒：本次比赛的题目均为原题，但为了比赛的公平性，请勿在比赛时尝试查找原题地址。如不幸见过原题，请向管理员报告。

Public Round #9 题解

2023-05-14 17:03:33 By p_b_p_b
  • 搬题人
    • 比赛：feecle6418
    • 排列：cdw
    • 选择：p_b_p_b
  • 组题人
    • p_b_p_b
  • 题解：别急

比赛

来源：

考虑怎么算单次答案。可以发现比赛规则等价于，建一棵 $n+1$ 层满二叉树，第 $i$ 轮让从叶子开始数第 $i$ 层两两对战，然后把胜者传到第 $i-1$ 层。那设 $f(x,i)$ 表示这棵二叉树的结点 $x$ 胜者为 $i$ 的概率，算一次答案是 $O(n^2)$ 的（复杂度分析同树形背包）。

注意到，除了与主角有关的结点外，二叉树的每个结点内的选手对应了 $a$ 序列的一个区间。如果说我们知道所有合法区间 $[l,r]$ 对应的 $f$ 数组，那单次算答案是 $O(n)$ 的（只需要主角每次都赢，而每次打的区间之间是独立的，把概率相乘即可）。而哪些区间可能被对应呢？实际上只有 $O(n)$ 种 $[l,r]$ 可能被对应：只有 $[X\times 2^Y+1,(X+1)\times 2^Y]$，或者 $[X\times 2^Y,(X+1)\times 2^Y-1]$ 两种区间可能被对应（分别是主角在其之后和之前的情况）。则对这些 $[l,r]$ 预处理出对应的 dp 数组的值即可，复杂度还是 $O(n^2)$。

排列

来源：

算法 1：随机调整，使得冲突的对数最小化，期望得分 $0\sim 100$ 分 因为我忘了所以没给这档分，想尝试的同学可以试试

算法 2：根据题解的第 $67$ 和 $70\sim 73$ 页, 若已有长为 $n$ 的排列, 可以构造长为 $3n+1$, $3n+5$, $3n+9$ 的排列, 那么从长为 $1,5,9$ 的排列即可构造长度任意的排列.

算法 3：分 $n\equiv 0\pmod 4$ 和 $n\equiv 1\pmod 4$ 两种情况, 见题解的第 $74\sim 75$ 页.

选择

来源：

Tutorial by p_b_p_b.

本题的证明有一些问题，在下面用黑体标出。

无脑 $O(n^2)$ 的 dp 非常显然，可惜没什么优化空间。

不难发现一个简单的性质：对于任意一个 $k$ 的最优方案，选择的每个位置 $i$ 一定是 $i$ 所在的区间里 $p_i$ 最大的位置。

那么从简单的情况开始考虑

  • $k=1$ 时显然只会选择最大值 $p_{m_1}$ 。
  • $k=2$ 时会选择最大值以及 $[1,m-1]$ 的最大值 $p_{m_2}$ 或是 $[m+1,n]$ 的最大值 $p_{m_3}$ ，不妨假设选择的是 $p_{m_2}$ 。
  • $k=3$ 时就会发生有趣的事情——假设 $[m+1,n]$ 的次大值是 $p_{m_4},m_4>m_3$ ，那么虽然 $p_{m_1},p_{m_3},p_{m_4}$ 也满足“选择的每个位置 $i$ 一定是 $i$ 所在的区间里 $p_i$ 最大的位置”的限制，但它一定不会优于 $p_{m_2},p_{m_1},p_{m_4}$ ，更不会优于 $p_{m_2},p_{m_1},p_{m_3}$ 。
    • 这是因为，$p_{m_2},p_{m_1}$ 的组合优于 $p_{m_1},p_{m_3}$ ，而 $p_{m_4}$ 在两边的贡献相同。

简单拓展一下（打表），可以发现第二个性质：对任意一个 $k$ 和一组大小为 $k$ 的最优方案 $S$ ，存在一个大小为 $k+1$ 的最优方案 $T$ ，使得 $S\subset T$ 。证明用类似的调整法即可不会证，肯定需要用到 $x^2+ax+b$ 的性质，但不知道怎么用。

因此我们只需要在每一步贪心加入贡献最大的位置，就已经对每个 $k$ 都是最优的了。

可惜，直接实现仍然是 $O(n^2)$ 的，并且搬题人并没有想到如何把它和最朴素的暴力区分开。

因此我们需要最后一个性质：对任意 $i$ ，$1,2,\cdots,i$ 的加入顺序与 $i+1,\cdots,n$ 无关。这是因为无论是加入 $x$ 还是加入 $y$ 对 $\max(x,y)+1,\cdots,n$ 造成的影响都是相同的，因此 $\max(x,y)+1,\cdots,n$ 对 $x,y$ 的相对顺序没有影响。

于是我们可以从左往右扫，维护当前见到的前缀的加入顺序。设当前做到了第 $i$ 个元素，那么 $1,\cdots,i-1$ 的顺序已经确定为 $p_1,\cdots,p_{i-1}$ ，然后求出 $i$ 应该在什么时候加入即可。

具体地，二分一个 $k$ ，判断已经加入了 $p_1,\cdots,p_k$ 的情况下，加入 $p_{k+1}$ 和 $i$ 哪个更优。但是并不知道为什么这有可二分性。这可以用平衡树维护，复杂度 $O(n\log n)$ 。

Public Round #9 公告

2023-05-08 11:40:05 By p_b_p_b

Public Round #9 将在 2023 年 5 月 14 日 8:00 举行！

比赛将进行 5 小时，共 3 道题，OI 赛制。

本次比赛的题目难度约为省选，所有题目都有部分分。

本次模拟赛的搬题人为 feecle6418, cdw, p_b_p_b ，组题人为 p_b_p_b ，验题人为 ZSH_ZSH, namespace_std, 以及待定。

赛后会公开原题链接和题解链接。

特别提醒：本次比赛的题目均为原题，但为了比赛的公平性，请勿在比赛时尝试查找原题地址。如不幸见过原题，请向管理员报告。

Public Round #8 题解

2023-03-19 23:43:33 By p_b_p_b
  • 搬题人
    • 饼干：Wu_Ren
    • 消愁：hehezhou
    • 养鸡：flower
  • 组题人：p_b_p_b
  • 题解：Wu_Ren，ChatGPT，flower

饼干

来源：

Tutorial by Wu_Ren.

考虑如果仍然需要补魔，那么先施法再补魔一定比先补魔再施法更劣。

那么我们每次一定是，先施法然后补满，直到某次我们施法完之后，把魔补到剩下消耗的总和，然后依次施完。

那么这个过程就相当于我们每个魔咒变成 $a_i$ 个物品，第 $j$ 个物品权值是 $j$，然后我们有 $m$ 次机会把某个魔咒里权值最小的那个物品删去，我们称这个为操作一。

我们要求最后权值和最小。

然后吃饼干就是有 $k$ 次机会把某个魔咒里权值最大的那个物品删去，我们称这个为操作二。

仔细分析一下，我们就是每次对最大的 $a_i$，使用 $a_i$ 次操作一（不足就全用了）。等所有操作一用完后，贪心地使用操作二即可。

复杂度 $O(n\log n+m)$ 或 $O(n\log n)$。

消愁

来源：

由于出题人鸽没了，下面是一个 ChatGPT 翻译的题解。

你好！以下是将LaTeX文档翻译成中文的内容：

首先，$f(p, q)$显然只依赖于对$(p_i, q_i)$的顺序，所以我们可以假设初始时$p_i = i$。

引理。$f((1, 2, \ldots, n), q)$ = $q$的递增子序列的个数。

证明。让我们首先分析字符串$s$何时满足$p$，$q$。基本上，我们有$n$个节点对应上行，$n$个节点对应下行，以及它们之间的一些有向边$(u, v)$，表示单元格$u$中的数字必须小于单元格$v$中的数字。要将1到$2n$之间的数字放入这些节点中，以便满足所有关系的必要和充分条件是：\textbf{不能有有向环}。我们将证明在我们的图中，这等价于以下条件：\textbf{不存在大小为$4$的有向环}。

的确，考虑最小长度的有向环，假设其大小大于$4$。它必须包含来自两个不同行的节点之间的边，因为单行内不能有任何环。不失一般性地，从单元格$(1, i)$到$(2, i)$的边。现在必须有一条从$(2, i)$到某个地方的边，不失一般性地到$(2, j)$。最后，如果从$(2, j)$的边到$(2, k)$，我们可以通过从中移除$(2, j)$获得一个更短的环，因为有一条$((2, i), (2, k))$的边，所以它的边到$(1, j)$。现在，如果$p_i < p_j$，那么我们可以将路径$((1, i), (2, i), (2, j), (1, j))$替换为$((1, i), (1, j))$，否则我们得到一个大小为$4$的环。

因此，只需确保没有大小为$4$的有向环。让我们找到满足此条件的字符串$s$的数量。考虑使$q_i=n$的$i$。如果我们将$s_i$设置为\t{0}，我们可以忘记对$(p_i, q_i)$，因为它不能参与任何长度为$4$的环。否则，我们得到矩阵中$(1, i)$单元格的数字大于第二行中的最大数字，因此对于每个$j > i$，$(1, j)$单元格中的数字也大于$(2, j)$单元格中的数字。因此，如果我们将$s_i$设置为\t{1}，我们还必须将所有$j > i$的$s_j$设置为\t{1}。在此之后，我们可以丢弃所有$j \ge i$的对$(p_j, q_j)$，因为它们无法参与任何环。

因此，我们有一个数组$q$和两个操作：

  • 删除最大元素
  • 删除最大元素及其右侧的所有元素。

很容易证明，通过按某种顺序应用这些操作删除整个$q$的方法数等于$q$的递增子序列的数量。事实上，每个这样的操作序列对应于我们在它们是最大的时候将应用第二个操作的数字子序列。

引理得证

现在，我们有以下问题：

  • 给定$q$的某些元素的排列，其他元素缺失。找到所有有效排列$q$（意味着它们在正确的位置上有给定的元素）的$f(q)$之和。

对于$n \le 100$，这是一个简单的问题。设置$q_0 = 0$和$q_{n+1} = n+1$，现在$f(q)$是从$q_0$开始到$q_{n+1}$结束的递增子序列的个数。对于已经设置的每个元素，比如$q_i$，计算$dp[i][k]$ --- 从$q_0$开始到$q_i$结束的递增子序列的数量，其中恰好包含$k$个\textbf{未设置}的元素。

以下是转移：对于每个$j < i$使得$q_j$也设置了且$q_j < q_i$，我们计算第$j$个和第$i$个之间的“自由”位置的数量，以及“允许”的元素的数量 —— 即 $[q_j+1, q_i-1]$ 中的元素，它们不是已经设置的元素。然后，对于不超过$max(free, allowed)$的每个$choose$和每个$chosen$，将$dp[j][chosen] \times (\binom{choose}{allowed} \times \binom{choose}{free})$添加到$dp[i][chosen+choose]$。

问题的答案就是$dp[n+1][x] \times (n-set-x)!$之和，其中$x$是已设置元素的数量。

养鸡

来源：

Tutorial by flower.

显然是个二分图最大流的模型，接下来用用流的语言的来描述问题。

首先有个贪心做法。每次从 $n$ 扫到 $1$ 遇到一个区间的 $r$ 就加入这个区间，然后对于每个点尽量流 $l$ 最大的。

当 $l, r$ 递增的时候。可以发现上述贪心做的事情是，先加入的区间尽量先流，与 $l$ 具体啥样无关。如果从$n$担心到$p$，再从 $1$ 贪心到$p-1$。两侧的用到的区间是一个前缀和一个后缀。如果总和不爆那就不会冲突，也就是说答案是 $\min(lmaxflow + rmaxflow, \sum_{l_i \le p \le r_i} f_i)$。其中 $f$ 是区间的流量

计算 $rmaxflow$ 可以用 hall 定理，令 $s_i = \sum_{l_j \le p \le r_j \le i} f_j - \sum_{j = p}^{i} a_p $，其中 $a$ 是右侧一个点的流量。

那么答案就是所有区间流量和减去 $\max s_i$，用线段树维护即可。

考虑贪心在做的事情是保证右侧为最大流的情况下，尽量的选 $l$ 最大的，只要我们求出了每个点右侧的情况，那么把每个区间的剩余流量扔左侧跑个最大流即可。

考虑一个 $s_i$ 的含义是：$p$ 到 $i$里至少要浪费 $s_i$ 的区间的流量扔到左侧。把$s$的前缀最大值位置拎出来是 $i_1, i_2, \cdots, i_k$。

考虑 $p$ 到$i_k$ 里优先级最小（$l$ 最小）的区间假设在位置 $x$。令 $i_t \le x$ 且$t$最大，那么这个前缀要浪费$s_{i_t}$而总共要浪费$s_{i_k}$，那么就直接给这个区间的左侧部分增加 $\min(f, s_{i_k} - s_{i_t})$ 的流量，因为这些一定是被浪费的。

考虑直接线段树暴力维护上述过程，下面证明操作次数不超过$O(n\log n)$。

需要对于$s$ 数组做的事情是后缀加和把最大值和降低为非严格最大值。

考虑在线段树的结构，势能为有多少个节点的区间最大值来自右子树（如果相等认为在左子树）

那么每次操作都会使得使能少$1$（$i_k$, $i_t$ 在线段树的 lca），后缀加只会影响$\log n$个区间的相对顺序。 算上线段树操作的时间复杂度是 $O(n\log^2 n)$。

Public Round #8 公告

2023-03-15 11:49:06 By p_b_p_b

Public Round #8 将在 2023 年 3 月 19 日 8:00 举行！咕咕咕了大半年之后， PR 又回来了！

比赛将进行 5 小时，共 3 道题，OI 赛制。

本次比赛的题目难度约为省选，所有题目都有部分分。

本次模拟赛的搬题人为 Wu_Ren, hehezhou, flower ，组题人为 p_b_p_b ，验题人待定。

赛后会公开原题链接和题解链接。

特别提醒：本次比赛的题目均为原题，但为了比赛的公平性，请勿在比赛时尝试查找原题地址。如不幸见过原题，请向管理员报告。

Public NOIP Round #5 题解

2023-02-25 16:00:21 By p_b_p_b
  • 搬题人
    • 青鱼和序列：p_b_p_b
    • 青鱼和怪兽：Qingyu
    • 青鱼和区间：alpha1022
    • 青鱼和游戏：ShanLunjiaJian
  • 组题人：Qingyu
  • 题解：alpha1022, Qingyu, ShanLunjiaJian, p_b_p_b

青鱼和序列

来源：

Tutorial by p_b_p_b.

注意到使用操作二会使得序列变成回文串，于是接下来使用操作一和操作二就没有任何区别了。

因此直接枚举第一次使用操作二是在第几轮，以及特判每次都用操作一的情况，即可得到答案。

事实上还可以注意到，只要用过操作二，无论操作序列如何，最终答案都相等，所以枚举也可以省去。

复杂度 $O(n+\log m)$ 。

青鱼和怪兽

来源：

  • Petrozavodsk Summer 2014. Day 4. Moscow SU SG Contest, Problem J

TBD

青鱼还在咕，来帮青鱼补一下。

本题难点显然在于打不动了可以重开，因此无脑 dp 会成环。

有环的 dp 的一般解决方案是用未知数把环上的一个点替代掉，然后用未知数把其他所有状态的 dp 值表示出来。

如果设 $dp_{n,m}=x$ ，根据转移方程不难发现，每个状态的 dp 值都可以写成一大堆关于 $x$ 的一次函数取 $\min$ ，且 $x$ 的系数应当都 $\le 1$ 。

一次函数取 $\min$ 会得到一个凸壳，第一条边的斜率 $=1$ ，后续的斜率都 $\le 1$ 。只要暴力维护分段函数，得到 $dp_{n,m}$ 的分段函数 $f(x)$ ，那么答案就是 $x=f(x)$ 的最大的解。之所以要最大是因为 $(n,m)\to (n,m)$ 的转移是不存在的。

直接维护这个分段函数大概是过不去的。但是通过以上的分析不难发现可以二分答案 $x$ ，做一遍 dp ，判断是否有 $dp_{n,m}\le x$ ，如果有就 $ans\le x$ ，否则 $ans>x$ 。这样就做完了。

青鱼和区间

来源：

Tutorial by alpha1022.

题意就是要求用询问区间区分出每道题目。

记覆盖 $i$ 的区间集合为 $S_i$，则所求即 $S_i$ 互不相同，但这并不好直接计算。

接下来我们注意到一个重要性质：对于任意方案，不会存在 $i_1 < i_2 < j_1 < j_2$ 使得 $S_{i_1} = S_{j_1} \ne S_{i_2} = S_{j_2}$。

这个性质使我们联想到括号序列。因此，考虑如下的构造：维护指针 $i$，初始时 $i=1$，每次取 $\max \{ j \mid S_i = S_j \}$，并令 $i=j+1$。注意到，所有区间要么是在某个 $[i+1, j-1]$ 内部，要么是以某个 $i$ 为左端点，某个 $j$ 为右端点。并且，我们至少可以保证可以将每个数区分到某个区间中。

注意到，若确定了分段方案 $[i_1, j_1], [i_2, j_2], \dots, [i_k, j_k]$，则段内的区间可以任意选取，而跨过段的区间选择的方案数就是我们所要求的答案：选择若干 $[1, k]$ 的子区间区分出所有 $k$ 道题的方案数。

因此我们考虑一个容斥：用 $2^{\binom{k+1}2}$ 减去不能区分出所有题目的方案数，同时维护一个背包数组用来计量分段的方案数，由此即可递推得到答案。时间复杂度 $O(n^3)$。

这还是一个生成函数的复合方程，借助拉格朗日反演可以做到 $O(n \log n)$。

青鱼和游戏

来源：

Tutorial by ShanLunjiaJian.

算法0

显然青鱼的每一步都会清空一堆。

我们计算青鱼的步数$x$，那么答案就是$2x-1$。

首先考虑一下这个游戏会如何进行。青鱼一旦操作一堆$(x,y)\rightarrow (x,0)$，缺头鱼必然跟着把这一对摊平成$(\lfloor\frac{x}{2}\rfloor,\lceil\frac{x}{2}\rceil)$。如果一对堆都空了，缺头鱼不得不把一步用到别的某对堆$x^\prime,y^\prime$，那么假设$x^\prime\leq y^\prime$，他必然会把这对堆变成$x^\prime+1,y^\prime-1$。

我们将青鱼把一对中大的拿走这个操作称为拿，缺头鱼把一对中有一个$0$的摊平称为摊，缺头鱼把两堆大小相同的一对搞的不同称为炸。如果只有拿和摊，可以发现答案就是$2\sum\limits_i(\lg a_i+1)-1$。炸可能减少步数，并且可以发现如果减少了只可能是减少一步。

看看二进制，设一对是$a,a$，如果$a$的二进制表示全$1$，那么一轮炸-拿-摊可以把$a$的长度减少$1$，如此一直进行$a$的长度次就能在这一对上减少一步，但一旦中断就不可能再减少一步了。如果$a$中有$0$，那么先使用若干轮拿-摊直到全$1$，此时仍然可能减少一步，因此这样做必然不劣。

于是青鱼在一开始会把每一对都搞成全$1$的形状，然后两鱼每次都会选择最长的那一对操作，缺头鱼如此选择是因为最长的最不容易产生作用，青鱼则要逼缺头鱼往短的上走，这个还是比较自然的。青鱼一旦先手操作一堆就会操作干净，因为它上面不可能再省下步数了，而缺头鱼先手操作一堆会让这一堆长度减少$1$。最后每一堆长$1$的都能贡献，不过如果青鱼先手则有一堆不行。

此时我们可以对于每个前缀连续$1$个数求出它的出现次数，然后对着这个数组模拟，复杂度$O(q(n+\log v))$。结合两个答案只跟区间长度相关的特殊性质，可以通过前$6$个测试点。

算法1

当然可以用数据结构维护这个出现次数！前缀和可以通过测试点$7,8$，BiT简单卡卡常可以通过测试点$9,10,11$。

这个做法空间是$O(n\log v)$的，为了砍掉这个$\log v$，我们对底层按$\log v$大小分块，维护块间的BiT，时间复杂度不变而空间变为线性，可以通过$12,13,14$，提交记录，卡卡常大概能过$15,16$。使用avx可能可以直接草过去。

算法2

观察模拟的代码。这是搬题人写的一份代码 : 

const int B=40;

inline int query(int l,int r)
{
    int c[B+1]={0},p[B+1]=0,g=0;
    for(int i=l;i<=r;i++) c[__builtin_clzll(~(a[i]<<__builtin_clzll(a[i])))-1]++,g+=(65-__builtin_clzll(a[i]));
    for(int i=B;i>0;i--) c[i-1]+=(c[i]+p[i])/2,p[i-1]=p[i]^(c[i]&1);
    return 2*(g-(c[0]-!p[0]))-1;
}

其中$c_i$表示前缀连续$1$个数为$i-1$的数的个数；$p_i=0/1$表示进行到$c_i$中的对时的青鱼是先/后手，$g$是不考虑炸的答案。可以发现这里如果把循环各轮的$c,p$分别倒过来组成一个二进制数，我们就是计算了$c$和$p$的和，不过$c$的每一位可以$>1$，并且进到$B$位就停止。接下来使用这个定义的$c,p$(也就是说它们都是倒过来的)。

继续考虑$p$是什么，可以发现它就是$c+p$上"经过"每一位的值的奇偶性的前缀和，也就是说如果向第$i$位发生了一次进位，对$p_{j\geq i}$的贡献就是$\operatorname{xor}$上一个$1$。注意到如果$c$的某位值$\geq 2$则必然向下一位进位，考虑一下发现我们在$c$上做完这些进位，做法就是直接加起来，最后再跑一遍上面的模拟即可。用BiT支持单点修改区间求和，复杂度$O(q(\log n+\log v))$。提交记录。

算法2.5

怎么砍$\log v$?下面这个做法由 hehezhou 发现。喝喝粥好闪，拜谢喝喝粥！

考虑扫过某个$c_i=1$的$i$时会发生什么，发生进位当且仅当$p_i=1$，否则这一位保留$1$，$p_{i+1}$变成$1$。如果$p_i=1$，那么$p_{i+1}=0$，于是$c_{i+1}=1$的话它得到$i$的进位而继续进位，否则它必然不会进位。于是我们知道经过连续的一段$1$之后$p$又变回$1$，而类似$1111$这样的东西它的$c+p$是$00001$。也就是说它不会改变第一个$1$，而在经过第一个$1$之后它的效果就是把每个$1$连续段清空并把连续段后一位赋为$1$。

我们只关心$c_B-\operatorname{not}p_B$(不考虑$B$及以上位的初值)。讨论一下 :

  • 如果$c$全$0$，那么$c_B=p_B=0$。

  • 如果$c_{B-1}=0$，那么$c_B=0,p_B=1$。

  • 如果$c_{B-1}=1,p_{B-1}=0$，那么$c_B=0,p_B=1$。

  • 如果$c_{B-1}=1,p_{B-1}=1$，那么$c_B=1,p_B=0$。

只有第一个case的结果是$1$，所以我们知道$c_B-\operatorname{not}p_B=1$当且仅当$c$全$0$。这样就$O(1)$了。提交记录。

共 22 篇博客
  • 1
  • 2
  • 3
English 繁體中文 简体中文

Server Time: 2024-12-04 01:19:59 | OpenSource Project