Grandmaster 计划试题乱做 Part 2

CF1498F Christmas Game

瞎扯

对于一个固定的根,显然深度 $\bmod k$ 不同的点是独立的子问题。

对于 $\bmod k$ 的一个同余系,好像是一个阶梯 $\text{nim}$。那现在可以抽象成一个序列,每次选择一堆中一些元素,移到左边一格,移到 $1$ 就不能移了。奇数位置的元素,对答案没有影响,因为后手可以模仿先手移动。

当一个偶数位置挪到奇数位置了,他就对答案也没有影响了。所以只需要把偶数位置拿出来,每次相当于把某一堆中一些元素扔掉。所以是偶数位置的异或和。

哦那是不是可以直接设 $\text{sg}_{i,j,0/1}$ 表示 $i$ 子树内,$\bmod k=j$ 的位置中,在奇数位置/偶数位置的异或和。然后换根就随便推推就行。$\mathcal{O}(nk)$。

正解

好像是对的,代码鸽了


CF1497E Square-free division

瞎扯

先套路地把所有平方因子除掉,然后变成子段中没有数字相同。如果 $k=0$,贪心是对的。

考虑 $\text{dp}$!设 $\text{dp}_{i,k}$ 为前 $i$ 个元素,用了 $k$ 次修改的最小子段个数。然后就不会了

好像可以 $\mathcal{O}(nk^2)$。可以暴力枚举最后一段花费了多少个修改,设 $l_{i,k}$ 为以 $i$ 为右端点,修改了 $k$ 个位置,最左的左端点是谁,然后就行了。$l$ 可以直接双指针。

总结

此问题有一个很简单的 $\mathcal{O}(n^2k)$ 做法,而此处又用到了那个类似于修改枚举项的 $\text{trick}$,改为枚举修改了多少个位置,再根据贪心,得到更为优秀的解法。

以后对于这种枚举维度不太平衡的问题,一般可能枚举量较大的维度更容易想到,但也可以尝试着切换一下枚举的内容。


CF1497D Genius

瞎扯

卡空间,估计要 $\mathcal{O}(n)$ 空间,但是时间可以 $\mathcal{O}(n^2)$。

感觉解决问题的顺序限制有点紧,每次相当于在数轴上跳来跳去,但是每次要比上次跳得远。

如果上次从 $i\rightarrow j$($i < j$),下一次要么去 $j+1$ ~ $n$,要么去 $1$ ~ $i-1$。如果 $i>j$,那就不能往左跳了,只能接着往右边跳,而且要跳到 $i$ 右边。而且贡献恒 $\ge 0$,在两次移动之间,如果能插入一次,答案不会变小。

那一次移动的路径一定是不断右移,在右移的过程中考虑往左边跳一下再回来。

如果往左跳的 $s$ 在前后两个 $s$ 之间,等于没跳。

md 咋每个问题可以解决多遍啊

那显然就是每次往右边跳,然后找左边 $\Delta$ 的 $\max$。

正解

md 好像跟我推的区别挺大的

考虑 $\text{dp}_i$ 表示仅考虑前 $i$ 个元素的答案。当只考虑前 $i$ 个时,他们都可以跳到 $i+1$。$i+1$ 也可以直接跳到他们中的任意一个。

所以直接拿他们相互转移就行了,注意转移顺序的细节。

总结

有时候一些题看起来很贪心,但如果贪心没有很好的做法,也可以考虑 $\text{dp}$。一般来说,贪心题大多数都能用 $\text{dp}$ 求解,但是可能复杂度偏高,需要通过贪心证明的一些细节来优化状态。


CF1495D BFS Trees

瞎扯

考虑 $\mathcal{O}(n^2)$ 枚举一下顶点对,然后数。

首先可以 $\text{Floyd}$ 一下,那一个点 $x$ 的父亲要满足他和 $x$ 之间的边,是两张最短路图上的边。

然后 $\mathcal{O}(n^2m)$ 算算是不是就行了?

正解

差不多了。一个细节是 $x,y$ 之间一定只能恰好有一条最短路,否则这些在最短路上的点、边都要在最后的树上,这样就会成环。这个 $\text{BFS}$ 判一下就行。


CF1572B Xor of 3

瞎扯

显然对三个 $0$ 或 $1$ 操作是没有意义的。异或和不变,可以用来判无解,如果序列里没有 $0$ 也无解。

擦这和 CF1438D Powerful Ksenia 咋这么像,那就也先变得两两一样!

奇数的情况下,如果最后剩的是 $1$ 说明无解,否则每次只要找到 $11$ 状的边界,拿一个 $0$ 把 $11$ 吃掉就行了。

偶数不会了!

正解

奇数好像是对的。

对于偶数的情况,如果能找到一个长度为奇数,且异或和为 $0$ 的前缀,那对这个前缀与相应的后缀分别做一遍奇数的部分就行了。

可以证明,如果不存在这样一个前缀,则无解。如果不存在这样一个前缀,则说明 $a_1=a_n=1$,且每一个偶数 $i$ 满足 $a_i=a_{i+1}$。

每次操作,由于必然会覆盖一个偶数 $i$ 与 $i+1$,所以剩下的一个元素一定是不会改变的。因此,$a_1$ 不可能从 $1$ 变成 $0$,因此无解。想到一模一样的卡人方法 但是还是没想到


CF1494E A-Z Graph

瞎扯

好难啊这为啥只有 2400

如果存在长度为 $2$ 的同色环,则所有询问全部解决了。哦如果存在长度为 $2$ 的环,则点数为奇数的询问都解决了。

哦如果没有环就直接 $\text{GG}$ 了 我是 sb 吧

如果没有长度为 $2$ 的环,奇数怎么搞呢?草如果有 $x\rightarrow y$ 的边,但是没有 $y\rightarrow x$ 的边,直接就挂了,所以 $k$ 是奇数就做完了。

哦对于 $k$ 是偶数,经过的边,所以一定会有一条边恰好正着反着颜色相同,所以就行了。哈哈做完了

正解

过了。


CF1594F Ideal Farm

瞎扯

考虑每一个前缀和,首先 $0$ 和 $s$ 都必须要选,然后每选择一个 $x$,就会 $\text{ban}$ 掉 $x-k$ 和 $x+k$。那如果能选择 $\ge n$ 个前缀和的点,使得他们互相没有 $\text{ban}$ 掉,是不是就是 $\text{NO}$。

哦,那显然贪心从大往小能选就选,那每 $2k$ 个能选 $k$ 个。剩下的 $m=s\bmod {2k}$ 可以讨论出能选择几个,如果 $m\ge k$ 那至多选 $k-1$,否则可以选 $m$ 个。

正解

差不多就这样。

需要特判一个情况:$s=k$,这样实际上 $0$ 和 $s$ 已经被互相 $\text{ban}$ 掉了,所以一定是 $\text{YES}$。

添加新评论