Grandmaster 计划试题乱做 Part 1

CF1550E Stringforces

瞎扯

看不懂题

考虑二分答案。为啥 $k$ 只有 $17$/jk。二分答案之后就只需要每一种字符的最长段都在 $\text{mid}$ 以上就行了?

如果已经出现长度满足条件的连续段,这个字符就行了。

这东西不会是个什么 $2^k$ 吧/jk。或者是 $nk\log n$ 但是这样为啥不出 k=26

考虑 $\text{dp}_S$ 是填好 $S$ 所需要的最小长度是不是就行了(。就枚举一下最后一个是谁就行了?

正解

就这么做(

总结

用时 $\text{25min}$。比 zxy 慢了 20 min/ll/ll/ll

大概看到这种东西直接考虑状压就行了?这种东西一开始可能是一个什么 $\text{dp}_{i,S}$ 表示前 $i$ 个字符能不能表示完 $S$,但是这是个 $\text{bool}$ 所以有点浪费,把 $i$ 换进值里就行。


CF1539E Game with Cards

瞎扯

直接暴力枚举,考虑能否在枚举的地方,切换左右手就行了?

然后二分一下找一找是不是就行了(

正解

就这么做(

实际上有一个 $\mathcal{O}(n)$ 的快乐做法:把问题倒过来做,把状态改成从当前点往后,现在换成左手/右手能不能行。因为这个状态是切换的端点,所以左手右手都可以快速得出状态(比如当前切换为左手,则上一次必然是右手),找下一个切换点的话,必定会找距离自己最近的那个,因为越远越劣。

总结

感觉这种题首先肯定是考虑全局的状态长什么样子,比如此题就是左手右手切换。然后据此进行 $\text{dp}$ 或贪心。

还有一个可以考虑的方向是从终止状态开始倒推,如果能推出初始状态就是合法的。有时候会有神奇的效果。


CF1536F Omkar and Akmar

瞎扯

是 $\text{ICG}$,所以只有必胜和必败。终止状态一定不存在两个相邻的空位,对于每一个空位,一定是左右字符不同的。一段连续的放好的位置肯定是 $\tt{ABABA..}$ 状。

现在要考虑什么样的状态不可能出现。是不是只有初始状态和最终状态胜负不同的局面不会出现?

如果存在两个点,夹在中间的点个数是偶数,且两个点同色,则先手能在中间多放一步;同理,中间点数是奇数,两点异色,没有领先优势。

如果后手在中间放了一个奇怪的地方,是不是能证明不改变胜负啊(

好像可以证明,同色的段一定可以使先手多放 $1$,异色不改变状态?归纳一下是不是就行了。很对啊,哦好像直接会被划分为若干子问题(在出现了两个点被染色之后)。

那好像 $n\ge 4$ 的时候,后手必胜啊。$n=3$ 好像后手也必胜。好惨啊先手

先讨论一下 $n=3$,剩下的是不是 $\text{B}$ 第一步显然会放在一个和之前 $\text{A}$ 放的不相邻的位置,并与 $\text{A}$ 同色啊。

擦好像不用,好像直接放在 $\text{A}$ 边上就行了。然后随便 $\text{A}$ 再放在哪里,一定会出现一侧是同色的,然后就赢了。

划分为子问题之后 $\text{B}$ 是不是死不掉啊(,所以好像任意结束状态都行?

正解

差不多,但不完全差不多

考虑最终状态,肯定是一些连续的 $\tt{ABABA..}$,两个连续段之间有恰好一个空格,且空格两边是一个 $\tt{A}$ 一个 $\tt{B}$。所以可以考虑把他们合起来,这样合并之后还是 $\tt{ABABA..}$ 的形式。

考虑如何从这个角度证明后手必胜。当我们把所有的段都合并起来,则会变成一个环。由于是一个环,所以中间的空格个数应该恰好是偶数!偶数说明先手后手下的一样多,这就可以证明后手必胜了。

所以最后,可以枚举终止状态 $f(n)$,游戏过程就有 $n!\times f(n)$。这个方案可以枚举中间的空格个数:

$$ f(n)=2 \times \sum_{2|i} i!\times (\binom{i}{n-i}+\binom{i-1}{n-i-1}) $$

总结

看一看我的瞎扯里有啥是有用的

终止状态一定不存在两个相邻的空位,对于每一个空位,一定是左右字符不同的。一段连续的放好的位置肯定是 $\tt{ABABA..}$ 状。

这个看起来很有用,这也太有用了。这时候如果直接把空位合并,就可以直接导出所有的结论了。不过之后那个归纳证明好像也能导出一样的结论奥,所以四舍五入做出来了(bushi

这种题还是要从终止状态的性质来考虑,观察什么样的状态是可行的,什么样是不可行的,说不定可以找到一些普遍规律。


CF1527E Partition Game

瞎扯

首先盲猜一手复杂度,感觉是 $\mathcal{O}(nk)$ 之类的。

考虑 $\text{dp}$,设 $\text{dp}_{i,j}$ 表示前 $i$ 个划分成 $j$ 段。显然可以分层转移。是不是有决策单调性啊(

考虑一下 $a<b<c<d$,$w(a,c)+w(b,d)$ 和 $w(a,d)+w(b,c)$ 的关系。好像只需要分别考察每一种数就行了。

哈哈好像交叉 $=$ 包含/hanx。那直接决策单调性!然后就是 $\mathcal{O}(nk\log n)$ 了!很对啊(bushi

欸代价咋算。好像不会,这个 $\text{last}(x)-\text{first}(x)$ 一看就能拆成若干 $\text{pos}(x)-\text{pos}(x-1)$。莫队状指针移动!

正解

就这么做。

莫队状指针移动的复杂度证明可以分指针左端点和右端点分开讨论,可以分析出来指针移动次数就是 $\mathcal{O}(n\log n)$ 级别的。

总结

这种区间划分问题,写个式子就很像决策单调性的式子,其贡献也确实很有可能满足决策单调性。

决策单调性由于在考虑某一个 $\text{mid}$ 处的决策点的时候是近乎暴力的,所以实际上贡献的计算形如指针移动。而莫队状计算也恰好是指针移动,所以决策单调性对莫队状移动是很友好的(


CF1527D MEX Tree

瞎扯

考虑计算 $c(i)$ 表示包括 $0$ $\sim$ $i$ 的路径条数。则 $\text{mex}=i$ 的路径条数是 $c(i-1)-c(i)$。

考虑加入一个点。显然首先 $[0,i-1]$ 需要在一条链上。然后考虑加入 $i$,如果仍然在一条链上,就更新链的端点,否则就无解了。

然后每次的答案就是两个端点的子树大小?(去掉中间路径的部分)感觉很对。

正解

就这么做(

总结

$\text{mex}=x$ 的性质中,$x$ 没出现这一点易于处理,但是 $x$ 是最小的没出现的点不太好处理。但是 $x$ 是最小的没出现的,等价于比 $x$ 小的都出现了。

而且对于本题这种,所有 $c(i)$ 都需要求解,且相邻 $c$ 变化不太大的东西,一般都先考虑增量。


CF1523E Crypto Lights

瞎扯

擦 看错题了

一盏灯被点亮之后不会关掉,不知道有啥用

一个状态没有停止,当且仅当任意亮着的灯之间的距离 $>k$。对于一组方案,点亮了 $x$ 盏灯,对答案的贡献是:

$$ \dfrac{x}{n^{\underline{x}}} $$

这不会还要数据结构维护吧(

一个状态,不存在一个位置使得在这里开灯仍然合法,当且仅当每一个空段的长度都 $\in[k-1,2k-1]$。所以只需要计算这样的所有状态的期望,最后 $+1$ 就行了。

如果不是这个模数,是不是可以直接多项式!

欸但是可以直接把期望换成算概率,就变成:

$$ \sum_{i=1}^n f(i) $$

$f(i)$ 表示开了 $i$ 盏灯还没结束的概率。这能算吗(

欸这就是空段都 $\ge k-1$ 的方案数。那放了 $x$ 个,且空段都 $\ge k-1$ 的方案数是:

$$ \binom{n-(k-1)\times(x-1)}{x} $$

那么概率就是:

$$ \dfrac{\binom{n-(k-1)\times(x-1)}{x}}{\binom{n}{x}} $$

好像就做完了?

正解

就这么做(

总结

先来看看瞎扯里从哪里开始对

好像从把期望换成概率开始就对了。这好像说明对于如下的期望计算方式:

$$ \sum_{i} p_i\times v_i $$

其中 $p_i$ 是概率,$v_i$ 是 $i$ 的贡献,可以考虑变成:

$$ \sum_i p_i\sum_{j=1}^{v_i} 1=\sum_i (v_{i}-v_{i-1})\sum_{j=i} p_j $$

也就是差分一下,然后就可以把“恰好”的概率 $p_i$ 换成“至少”的概率了。这种做法对于一些合法状态好算,终止状态难算,且贡献差好算(比如此题贡献差为 $1$)的东西貌似很友好。


CF1523D Love-Hate

瞎扯

不少于就是 $=\left\lceil\dfrac{n}{2}\right\rceil$。那就是一半的人的按位与的 $\text{popcount}$ 的最大值。

显然这个答案 $\le p$ 而且可以顶到上界,那可能出现在答案里的元素也至多只有 $2p$ 个。

这东西如果有一组解,要怎么 $\text{check}$ 啊。不会了 偷看题解!

正解

好像跟我推的没啥关系的样子(

如果知道一个人喜欢所有的货币,那最后的货币一定是这个人的子集,这可以简单状压 $\text{dp}$。

则现在只需要找到一个在最优答案里的人。因为在最优答案里的人至少有一半,所以可以随机化!

于是就做完了。

总结

感觉这种随机化题有点想不到......

好像自己的瞎扯一直都在朝着 $p$ 很小的方向,希望从这里开始暴力枚举。实际上 $p$ 小的作用是最后在检查的时候做状压......

这题的做法好像是从类似写 $\text{checker}$ 的角度来进行的,大概是利用了按位与优良的性质,从而在暴力枚举了一个人之后,大大减小了枚举量。


CF1510B Button Lock

瞎扯

只有 $2^{10}=1024$ 个点,所以可以乱搞!可以先建一张图,每次从原点走到 $\text{R}$,要求把每个特殊节点都走一遍。

可以把图缩一缩,变得只有原点和特殊节点,特殊节点如果 $T\subset S$,就从 $T$ 到 $S$ 连一条 $\text{popcount}(S-T)$ 的边。

那现在就是要找到一些路径,使得覆盖所有点,且最小化路径长度和。

显然每次要从一个入度为 $0$ 的点开始。

欸,好像网络流就行了?每个数字拆成两个点,中间连流量为 $1$ 就行了。

正解

就这么做(

总结

对这种数据范围看起来有些奇怪的最优化问题,没有很好的 $\text{dp}$ 做法,则可以考虑网络流。

很多奇形怪状的问题,都可以用网络流解决


CF1499F Diameter Cuts

瞎扯

感觉要设 $\text{dp}_{i,k}$ 表示 $i$ 子树内包括根的联通块直径是 $k$ 的方案数。长得有点像个 $\text{dp}$ 套 $\text{dp}$,估计最后是背包状转移。

我好像只会三维状态(,好像要 $\text{dp}_{i,x,y}$ 表示 $i$ 子树内包括 $i$ 的直径是 $x$,连到 $i$ 上的最长链是 $y$ 的方案数。

欸好像不用记直径是 $x$,反正只要 $\le k$ 就行了。然后现在只要求每个子树接在 $i$ 上的最大值次大值加起来 $\le k$ 就行。

哦那好像直接 $\mathcal{O}(nk)$ 力。

正解

哈哈 1A 了


CF1499E Chaotic Merge

瞎扯

擦 看了半天原来范围只有 1000

那就先无脑设 $\text{dp}_{i,j}$ 是 $x$ 最后一个元素到 $i$,$y$ 最后一个元素到 $j$ 的合法方案数。

好像还要一个 $0/1$ 表示现在结尾是 $x$ 还是 $y$。如果当前 $x,y$ 的子串都非空,转移显然。现在只需要考虑有一个从长度为 $0$ 到长度为 $1$ 的情况。

那把 $\text{dp}_{i,0}$ 的位置设成 $y$ 还没填数是不是就行(

正解

1A

添加新评论