Skip to content

Latest commit

 

History

History
212 lines (134 loc) · 14.6 KB

2021.4.18 - 4.24 一周小结.md

File metadata and controls

212 lines (134 loc) · 14.6 KB
Raw

2021.4.18 - 4.24 一周小结

这周做的题目，难度总体都挺高的，集中在 CF 上 3000 左右。并且在通过之前没有看任何一题的题解！（得瑟一下！）其实，有些难题，多想想，还是能艹过去的！Try a Try, AC is OK.（bushi）至于为什么看这些 CF 评级比较高的题呢？因为感觉评分高一些的题，在题目风格上更加 OI 一些，也更是我所擅长的。

CF1408I. Bitwise Magic

题意：

给定 $n,k,c$，以及长度为 $n$ 的序列 $a$（保证元素互不相同）。

操作 $k$ 次，每次随机选择一个 $a_i$，然后将其 $-1$。对于 $x=0,1~...~2^c-1$ 输出最后序列的异或和为 $x$ 的概率，答案对 $998244353$ 取模。

$k,c\le 16,a_i\in [k,2^c),n\le 2^c-k$

题解：

洛谷题解区里的做法充斥着生成函数，的确看到这题想到的第一个想法就是二元生成函数：设 $x^ay^b\times x^cy^d=x^{a+c}y^{b\wedge d}$，答案的 PGF 是 $\sum\sum \frac 1{a!}x^ay^b$：于是问题就可以转化成快速求多个二元多项式的乘积。但是这么想是没有必要的，我有一个更加巧妙而简洁的做法：

设一种最终局面中，第 $i$ 个数被操作了 $d_i$ 次；那么对于一个可能的局面 $d{}$，它出现的可能性可以用可重排列计算： $$ P(d{})=k!\cdot\left(\prod_{i=1}^nd_i!\right)^{-1}\cdot \left(\frac 1n\right)^k $$ 于是，设 $f_{i,j,S}$ 表示前 $i$ 个数、操作了 $j$ 次、影响为 $S$ 的所有方案的当前阶乘倒数乘积的和，其中 $S=\sum\limits_{p=1}^ia_i\wedge(a_i-d_i)$。于是我们就有了一个 $2^c\times 2^c\times k^2$ 的做法。考虑如何加速。

我们注意到两个事情：1.复杂度实际上是 $n\times |S|\times k^2$；2.每个数等价，所以不按顺序统计不影响答案。

所以我们可以把东西序列分成若干段，在每个段内 $S$ 的值域很小，段内可以快速 DP；最后再想办法拼起来。

由于 $k\le 16$，所以几乎只会影响到最后的 4 位；考虑到减法退位的情况，最多再将前面的某一位开始全部取反；所以我们可以按照它影响的是前面的哪一位分段，每一段内的 DP 数组中，$S$ 的取值个数都只有 $15\times 2$ 个，可以快速地 DP，这一部分的总复杂度就是 $2k\times n\times k^2$。

然后考虑如何把这 $9$ 个 DP 数组拼起来，第一维暴力卷积，第二维 fwt 即可，复杂度 $(c-k)\times 2^c\times c\times k^2$。

**评测链接：AC submission：https://codeforces.ml/contest/1408/submission/113971716. **

UPD：事后 zc_li 强神告诉我说直接对第二维 fwt 一下就行了，我傻了。

CF1474F 1 2 3 4 ...

题意：

给定一个序列，求其中最长严格上升子序列长度及其个数。

序列按如下方式给出：给定 $n(1\leq n\leq 50)$ 和序列中的第一个数 $x(-10^9\leq x\leq 10^9)$，接下来 $n$ 个数 $d_i(-10^9\leq d_i\leq 10^9)$，若 $d_i\ge 0$，则重复 $d_i$ 次，在序列末尾加上当前序列最后一个数 $+1$ 的值，若 $d_i<0$，重复 $-d_i$ 次，在序列末尾加上当前序列最后一个数 $-1$ 的值。

题解：

假如这个像过山车一样的序列总长只有 $10^5$ 该怎么做？考虑增量构造，设 $f_i$ 表示当前序列中，结尾是 $i$ 的最长上升子序列个数；那么增加一个数 $x$ 也就等价于执行 $f_{x}+=\max(f_{x-1},1)$；依次加入数就行了，最后的答案只要统计那些 $\sum\limits_{j=1}^i d_j-\min\limits_{k=1}^{i-1}{\sum_{j=1}^kd_j}=max$ 的 $i$ 位置的值的和就行了（注意这个 $f$ 是在 $i$ 位置时的 $f$）；注意每次到达新的最低点时要将 $f$ 数组清空。

现在考虑序列可能很长的情况。我们发现：下降操作，大致相当于把 $[pos_i,pos_{i-1}]$ 这一段平移一下加到自己身上；上升操作，相当于把区间的第一个数加上一个数，然后把这个区间前缀和一下。

有没有合适的结构可以用来维护这个 DP 数组呢？有，那就是多项式！先给出一个结论：任一时刻的 $f$ 数组皆可以被分成 $O(n)$ 段，每一段内的 $f_x$ 均可以用次数小于 $O(n)$ 的多项式 $f(x)$ 表示。下面大致口胡一下：

  1. 序列 1,1,1,... 可以用 $f(x)=1$ 表示。
  2. 它的前缀和可以用 $f(x)=\frac{(1+x)x}2$ 表示，它的前缀和的前缀和可以用 $f(x)=\frac{(2x+1)(x+1)x}6$ 表示。...... 它的任意一阶前缀和都可以用多项式表示。
  3. 下降操作中，除了区间第一个数之外的 $f$ 可以用 $f(x)+f(x-1)$ 表示；第一个数可以单独拆成一个常数多项式。
  4. 上升操作中，前缀和操作可以用多项式表示；而第一个数加上一个数，相当于在这个多项式上加上一个常数；而这些使得这段的 $f$ 可以看作是序列 1,1,1,... 的多阶前缀和的多项式的和。

于是我们可以大力用多项式维护这个 $f$ 数组，每次操作直接算出这一段 $f$ 的前 $n$ 项，前缀和/偏移一下，然后把新的 $f$ 直接拉格朗日插值插出来。

有一些细节，比如在下降操作中，第一个位置需要单独新建一个多项式；上升操作中，如果有一段的 $f$ 已经超出了原来的范围，那么就需要新建一个常数多项式来表示这一段。

**评测链接：AC submission：https://codeforces.ml/problemset/submission/1474/113669336. **

CF1476F. Lanterns

题意：

有 $n$ 个灯笼拍成一排，第 $i$ 个灯笼具有 $p_i$ 的亮度。每个灯笼要么朝向左，照亮左边编号为 $[i - p_i,i - 1]$ 的灯笼，要么朝向右，照亮右边编号为 $[i + 1, i + p_i]$ 的灯笼。

寻找一种方案，为所有的灯笼确定朝向，使得每一个灯笼被至少一个其他灯笼照亮。$n\le 3\times 10^5$。

题解：

Try a try，AC is OK！这里是 $n^2\log n$ 过 $n=300000$。

首先有一个 $O(n^3)$ 的 DP：设 $f_{i,l,r}$ 表示使用了前 $i$ 个灯笼、最左边需要点亮的灯笼是 $l$、最右边已经照亮了灯笼 $r$ 的一个状态，然后就可以快乐地 DP 了。

然后我们可以发现：同样的 $l$，只有最大的 $r$ 是有用的，于是状态数和复杂度就可以减小到 $O(n^2)$。

但是还不能过，我们发现，对于同一个 $i$，合法的 $l$ 应该是很少的——因为只有当前的灯笼的威力可以到达 $l$ 我才会使它朝左，所以我们从左往右只保留这些合法状态来 DP，大致代码如下：

for (int i = 1; i <= n; i++)
{
	sort(dp[i - 1].begin(), dp[i - 1].end(), [](node x, node y) { return x.l == y.l ? x.r > y.r : x.l > y.l; });
	int mx = -1e9;
	for (int j = 0; j < dp[i - 1].size(); j++)
	{
		node u = dp[i - 1][j];
		if (u.r <= mx) continue;
		if (u.l >= i - p[i] && u.l != i) dp[i].push_back({ u.r < i ? i : n + 1, u.r, j, 0 });
		dp[i].push_back({ min(u.l, u.r < i ? i : n + 1), max(u.r, i + p[i]), j, 1 });
		mx = max(mx, u.r);
	}
}

这样写，复杂度其实卡不满的，于是就过了。

**评测链接：AC submission：https://codeforces.ml/problemset/submission/1476/113486661. **

CF1430G. Yet Another DAG Problem

题意：

给定一个有向无环图，每条边都有 $W_i$ 的权重，给每个点分配权值 $A_i$，对于每条连接 $(u,v)$ 的边，定义其权值为 $Bi=Au-Av$，要求：

  1. $Bi&gt;0$

  2. $\sum Wi\cdot Bi$ 最小

请输出一种 $A$ 的分配方案，$n\le 18$。

题解：

一开始可能会以为这个状态甚至可以按照拓扑序来贪心，但是最后一个样例就给出了反例——两条长短不同但是端点相同的链，这是不能直接贪心的。

那么我们考虑怎么 DP：一种朴素的状态设置是直接状压下已经填好的每一个点的权值，记为 $S$；设 $f_{i,S}$ 表示当前填数填到了 $i$、状压为 $S$ 的最小花费。但是这样复杂度几乎等同于爆搜，行不通。

由于 $n=18$，所以我们考虑指状压下当前已经填好的数的集合 $S$，这样复杂度就是 $2^n$ 的，但是怎么转移呢？？？

大开脑洞一下，我们费用提前计算，在 $f_i\to f_j$ 的转移中我们的代价，把其他还没选的状态都算上，也就是代价直接记为 $i$ 集合所有出边的边权之和。这样做有点反直觉，因为代价竟然和 $j$ 无关，甚至不用记录当前 DP 到了第几位；但是这样的确是对的。

复杂度最劣是 $2^{36}$ 的，但是由于状压 DP 常常跑不满，我们相信它能过。

**评测链接：AC submission：https://codeforces.ml/problemset/submission/1430/113711359. **

CF1455G. Forbidden Value

题意：

已知初始值$x=0$，给定下面2种命令：

  1. set $y$ $v$，令$x=y$，或花费$v$元钱删除该命令；
  2. if $y$ ... end，如果$x==y$，执行if...end中的命令，否则跳过该if...end。

你需要使用最少的花费，使得无论运行到哪里，都有$x \neq s$。命令条数 $1e5$。

题解：

给人的直接感觉就是类似树形 DP，考虑设 $f_{x}$ 表示当前的值为 $x$ 的最小开销；于是在添加一个操作，就等价于： $$ \min_{i=1}^n{f_i} \to f_x,\ \ \ f_{i} =f_{i}+v\ \ (i\neq x) $$ 若是在最后添加一个 if，我们递归计算出这一个 if 内部的 $f$，合并就是： $$ nf_i=\min(f_x+f'_i,f_i) $$ 用线段树维护即可，整体 DP 的 2900 的题也就直接秒掉了，也就是难写而已。

**评测链接：AC submission：https://codeforces.ml/problemset/submission/1455/113822202. **

CF1446D2. Frequency Problem (Hard Version)

题意：

给出$n(1 \le n \le 200000)$个元素组成的序列$a_1,a_2,……,a_n$，求最长的子段使得其中有至少两个出现次数最多的元素。

题解：

假设每个元素的出现次数都比较少，我们可以枚举这个出现次数的上限 $f$，对于每一个 $f$，我们都对原数列从右到左进行一次双指针，每一次操作左移一次右端点，然后尽可能地在满足 $f$ 的限制条件的情况下左移左端点。依次判断每个满足 $f$ 限制的极大区间是否最少两个众数。

这样做为什么是对的？1. 这个最后选出的区间的 $f$ 一定会被枚举到；2. 对于同一个右端点，在同样 $f$ 的限制下，越往左移左端点越能满足至少有两个众数的条件。

假设元素的取值范围很小怎么做呢？我们发现原数列的众数一定是这个子段的众数之一，证明使用反证法，设它不是，那么左移左端点，然后右移右端点，大众数和区间众数的出现次数会是两个相交的分段函数，也就意味着我总可以通过扩大区间使得众数包括大众数，并同时最优化答案；所以不为大众数的情况不存在。

我们枚举另一个众数是哪一个，我们只要找到这个数和大众数出现次数相同的极大区间即可，因为答案中的众数一定包括大众数，于是一旦与大众数相同，便一定是这个答案区间的众数；加入不是，那么它一定不是答案区间，并且存在长度更长的答案区间（证明同上）。

这时惊世骇俗的一步来了！我们分出现次数小于 $\sqrt n$ 和出现次数大于 $\sqrt n$ 分治一下，分别使用上述两种方法，就能实现 $O(n\sqrt n)$。

这一题我想到了小于 $O(n\sqrt n)$, Zenislt 大佬想到了大于 $O(\sqrt n)$，合作一下就过了。

**评测链接：AC submission：https://codeforces.ml/problemset/submission/1446/113452417. **

CF1487G. String Counting

题解：

你有 $26$ 个不同的字符，第 $i$ 个字符有 $c_i$ 个（$\frac{n}{3} \leq c_i \leq n$）。

你希望用这些字符，构造出一个字符串（每个字符在字符串中出现的个数不超过 $c_i$），使得这个字符串上不存在长度为奇数且大于 $1$ 的回文串。求出方案数对 $998244353$ 取模的结果。

题解：

这题是在补之前的题，所以有参考题解。

$c_i\ge \frac 3n$ 意味着什么呢？意味着最多有两个字母非法，我们不妨设它们是 a 和 b,于是设 $f_{i,j,k,u,v}$ 表示有前 $i$ 个字母有 $j$ 个 a 和 $k$ 个 b、前两位是不是 a 或 b（0/1/2）、前一位是不是 a 或 b（0/1/2）。

于是就可以快乐 $n^3$ 地 DP，设 $g_{j,k}=\sum f_{n,j,k,0/1/2,0/1/2}$，$h_{a,b}=\sum\limits_{i=a}^n\sum\limits_{j=b}^n g_{i,j}$，于是答案可以表示为： $$ g_{0,0}-\sum_{i=1}^{26}g_{c_i+1}+\sum_{i=1}^{26}\sum_{j=i+1}^{26}g_{c_i+1,c_j+1} $$ **评测链接：AC submission：https://codeforces.ml/problemset/submission/1487/113459203. **

CF963D. D. Frequency of String

题意：

给你一个字符串 $s \pod {|S| \le 10^5}$，有 $n \pod {n \le 10^5}$ 个询问，第 $i$ 个询问包含一个整数 $k_i$ 和一个字符串 $m_i \pod {\sum_i |m_i| \le 10^5}$。要求找到一个字符串 $t$ ，使得 $t$ 是 $s$ 的子串并且 $m_i$ 至少在 $t$ 中出现了 $k_i$ 次。你只需要求出 $t$ 的最短长度。

保证 $m_i$ 互不相同。

题解：

把询问串建出 ACAM，然后遍历一遍 $s$ ，找到每一个询问串的 Endpos 的集合，判断一下；由于 FJOI 考场上的那个 Trick，这么直接暴力做是 $O(n\sqrt n)$ 的。

主要是十分感慨，感觉 FJOI 考场上写的也几乎是这份代码，只是把 ACAM 换成了 广义 ＳＡＭ，我在想，倘若我没有看错题，那么考场上写的也许有就是这份代码了吧！那也许解决就与现在不同了吧！

写着写着，我感慨万分，但并不后悔或是遗憾；现在的我要做的，是拼搏拼搏再拼搏！

Ｈｅ　Ｗｉｌｌ　ｃｏｍｅ　ｂａｃｋ　ｓｏｏｎ．