Edu 20 ~ 24

CF Edu 20 / CF803

A Maximal Binary Matrix

贪心填数,每次先填 $(i,i)$ ,然后两个两个填 $(i,i+k),(i+k,i)$ ,如果只能填一次就放到 $(i+1,i+1)$ 上。不难发现每步都最优了,满足最大字典序。

罚时是代码在 $k = 0$ 的时候会放个 $1$ 进去。

B Distances to Zero

$L[i],R[i]$ 分别表示左右最近的 $0$ ,然后转移显然讨论下这个位置是否为 $0$ 即可。

C Maximal GCD

如果最终整个序列的 $\gcd$ 是 $x$ ,那么显然必须有 $x | n$ 。而且使得和最小的构造必然是 $x,2x,3x,\dots ,kx$ 。如果想要和是 $n$ ,只需要 $a_k = n - (x+2x+\cdots +(k-1)x)$ 。

然后我们分解质因数一下,找一下满足 $\frac{k(k+1)}{2} x \le n$ 的最大 $x$ 。

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

罚时的那一发是没发现这个东西乘起来会炸 long long ,或者说是开始发现了后来觉得不会炸,结果实际上是会炸的。

D Magazine Ad

我们按照空格和 hyphen 来切开这个字符串,假设每段的长度是 $a_i$ ,那么问题就是分成 $k$ 组使得每组的和尽量小。

我们可以二分一下这个尽量小的和,不难发现在和没超过二分的值的时候尽量拿的贪心是对的。

所以二分后贪心一下即可,复杂度 $O(n\log n)$ 。

E Roma and Poker

考虑设 $W = -1, L = 1 , D = 0$ 。

考虑 $dp[i][j]$ 表示前 $i$ 个数,到现在的和是 $j$ 是否存在一种方案,如果存在那么 $pr[i][j]$ 就是这个位置填的是什么。

这个 $dp$ 的转移是很显然的,考虑一个位置如果不是 ? 就直接转移,否则转移的时候可以往三个方向转移。然后如果一个位置不是 $n$ 那么 $|j| < k$ ,否则 $|j| = k$ 。这些都很容易在转移的时候限制。

复杂度 $O(nk)$ 。

F Coprime Subsequences

套路题。

后面的条件就是,这个子序列必须全部被 $t$ 整除。显然选择的方案数就是 $2^{cnt_t}-1$ ,其中 $cnt_t$ 表示 $t$ 的倍数个数。

于是复杂度就是 $O(n\ln n)$ 了。

G Periodic RMQ Problem

感觉也很套路,场上由于耽搁了些时间没来得及写,口胡一下。

维护一个平衡树即可,每次找到第一个 $\ge l$ ,第一个 $\ge r$ 的位置,然后分别转上去,然后就是丢掉一个子树,往子树插入一个点的问题,再维护一下子树的最小值即可。复杂度是 $O(n\log n)$ 。感觉还要讨论一下 $[l,r]$ 在一个块里的情况,反正讨论一下即可。

后来看了看题解,其实有一些比这个好做很多的做法。首先可以离线一下,然后合并一下询问,于是就没有修改了。或者可以开一棵动态开点线段树,最开始只有 $[1,nk]$ 这一个位置。然后修改的时候,修改一个节点后就把它的两个儿子都建出来,这些儿子的值整成 $k$ 轮复制后 $b$ 在这些区间的最小值,这个可以通过 RMQ 做到 $O(1)$ 查询。

感觉主要是注意到,如果初始都是 $0$ 就可以直接拿动态开点线段树做,这个题初始数组不是 $0$ 但是也可以直接用 RMQ 来 $O(1)$ 询问初值。

然后大概就做完了。复杂度 $O(q\log(nk) + n\log n)$ 。

CF Edu 21 / CF808

D Array Division

相当于是对于一段前缀,和为 $s$ ,判一下前缀中是否存在 $\frac{S - 2s} 2$ 这个数,如果有就可以,后缀同理。

因为有效的移动肯定是从前缀移到后缀,或者从后缀移到前缀中。

E Selling Souvenirs

如果 $w_i \le 2$ 就是个人尽皆知的可撤销贪心。

开始想要直接上可撤销贪心,然后 WA 了很多发之后发现这种情况:

1
2
3
4
5
6
5 9
3 6
3 6
2 4
2 4
2 4

根本没法处理,因为性价比相同的可能有很多不同容量,而容量并不是 $1,2$ 。

但是注意到这个题只需要算总容量是 $m$ 的情况,所以可以枚举一下拿多少个 $3$ ,然后问题就成了多次询问一个容量,然后 $w_i \le 2$ 的经典问题了。

具体做法就是之前刷题赛的 硬币 ,由于只有 $1,2$ ,直接可撤销贪心即可。每次如果之后是 $1$ ,那么直接更新。否则有可能从前面选一个丢掉再拿这个 $2$ ,要么选择后面的一个 $1$ 。

复杂度 $O(n)$ 。

F Card Game

很好的套路题。如果不是以前见过 HDU Prime set 这个题很可能想不到。

首先可以想到二分答案一下,然后问题就变成了给你一些 $p_i,c_i$ ,问能否让和超过 $k$ 。

可以考虑给两个和为质数的数之间连一条边,表示不能同时选这两个数,然后问题就变成了这个图的带权最大独立集。

考虑如果两个数和是质数,那么除了 $2 = 1+1$ 的情况,两个数必须是一奇一偶。我们把 $1$ 单独拿出来,剩下的就是一个二分图。

考虑 $1$ 怎么办。不难发现只能拿一个 $1$ ,拿两个 $1$ 就死了。所以我们把除了权值最大的 $1$ 直接丢掉,权值最大的 $1$ 照样连进图里面。

考虑一个二分图如何求最大独立集。相当于是对于一条二分图上的边,它的两边的点不能同时被选。我们建立原点和汇点后,考虑割掉一个边意味着不选择这个点,于是,现在问题就变成了最小割。所以总和减去最小割就是答案了。

复杂度是二分图上网络流的复杂度,$O(n^2\log n)$ ,众所周知网络流是跑不满的。

G Anthem of Berland

我们考虑先求出 $S$ 哪些位置作为开头是可能可以匹配上字符串 $T$ 的。这个可以直接 $O(nm)$ 预处理。

然后考虑做一个 $dp$ 。设 $dp[i]$ 表示钦定一次匹配从 $i$ 开始,往后一直匹配到 $n$ 最多匹配多少次。考虑如何去转移。

由于我们钦定了第一次匹配从 $i$ 开始,所以 $[i,i+m-1]$ 的字符必然是确定了的。所以如果下一次匹配的位置是在 $[i,i+m-1]$ 这一部分开始的话,必然是从一个 $i+m-\text{border}$ 的位置开始。所以转移有:

这个转移的复杂度是 $O(m)$ 的。

然后还有一种转移,如果下一次选取的串并不从 $[i,i+m-1]$ 开始,那么就不与这里的字符有关了,所以就是

这个东西是可以预处理 $f[j] = \max_{k \ge j} dp[j]$ 来做到 $O(1)$ 的。

总复杂度 $O(nm + m)$ 。$\text{border}$ 的预处理参考 $\text{kmp}$ 。

CF Edu 22 / CF813

C The Tag Game

+1 ,开始没考虑第二个人可以先往上跳一段的情况。

显然,第一个人可以随时保证第二个人在子树内。

所以第二个人的最优决策肯定是,先尽量往上跳并且不与第一个人碰面,然后开始往最深的方向跳。

我们预处理出所有点子树的最深深度以及每个点的深度即可。

D Two Melodies

+2 开始 $dp$ 的时候在 $i’ < j$ 的时候直接贪心拿最靠后,这样不具正确性。

考虑一个 $dp[i][j]$ 表示第一个数列结尾 $i$ ,第二个数列结尾 $j$ ,同时钦定 $i > j$ 。然后每次更新分为两种,要么 $i’ > j$ ,也就是从 $dp[i’][j]$ 转移,那么我们一定会取最靠后的 $A_i\pm1$ 或者最靠后的同余的 $i’$ 。

但是如果 $i’ < j$ ,也就是从 $dp[j][i’]$ 转移,那么取最靠后的就不一定对了。因为可能最靠后的位置被分到第二个数列里面更优秀。我们可以处理出一个 $pp[j][0\sim 6]$ 表示 $\max_{A_{i’} \equiv k} dp[j][i’]$ ,然后从这个转移。再处理一个 $pd[i][j]$ 表示 $\max_{A_k = A_j}\{dp[i][k]\}$ ,然后从上一个 $A_i \pm 1$ 转移即可。

这样做的复杂度是 $O(n^2 \log n)$ 。但是实际上有更好写的 $O(n^2)$ 做法。

可以设 $dp[i][j]$ 表示第一个数列 $i$ 结尾,第二个数列 $j$ 结尾的最优子序列长度。

转移的顺序是直接枚举 $i \in [1,n] , j \in [1,n]$ ,同时处理出 $v[k],t[k]$ 分别表示最大的 $dp[i][j’]$ 满足 $A_{j’} \equiv k$ 以及 $A_{j’} = k$ 。只有在 $j > i$ 的时候,我们才计算 $dp[i][j]$ ,并且算好后去更新 $dp[j][i]$ 的值,因为这两个值肯定是相等的。然后在我们计算 $dp[i][j]$ 的时候,$dp[i][0\sim j-1]$ 肯定已经算好了,而且存到了 $v[k],t[k]$ 里面,所以直接更新即可。

E Army Creation

1A

这个询问就是对区间内每个数的出现次数和 $k$ 取 $\min$ 后加起来。

我们考虑 $k=1$ ,也就是区间不同数个数的做法,是找一个 $last$ ,求 $i\in [L,R], last_i \in [0,L)$ 来做的。所以这个题想一想可以发现只需要把 $last$ 变成上 $k$ 个数做即可。

然后用主席树维护,即可强制在线。

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

F Bipartite Checking

+1 某个地方并查集修改 $u$ 写成 $v$ 了。

老套路题了。

线段树分治变成只有加边。然后加边的时候用种类并查集维护即可。基本上算是之前模拟赛 T4 Candle 的弱化版本。

CF Edu 23 / CF817

D Imbalanced Array

1A

所有区间的最大值的和减去最小值的和。分开做。所有区间最大值的和直接按最大值分治即可。复杂度 $O(n\log n)$ 。

或者也可以单调栈,不难发现在弹掉栈顶的时候栈顶到 $i-1$ 和栈顶到上一个栈顶组成的所有区间的贡献都是栈顶。画一下会发现这样肯定可以考虑完所有区间。复杂度 $O(n)$ 。

E Choosing The Commander

1A

考虑 $< l_i$ 这个东西,可以枚举一下 $\text{LCP}$ 长度,现在问题就是前一段的二进制表示一定,剩下一段二进制表示任意的数的个数。这个东西可以直接拿 $\text{01-Trie}$ 维护。复杂度 $O(n\log v)$ 。

F MEX Queries

1A

我们考虑能取到 $\text{MEX}$ 的位置,显然只能是某个操作的 $l,r+1$ 。所以我们给这些位置离散化一下,然后直接在线段树上操作即可。

操作大概需要考虑一下标记的顺序。在我们维护赋值操作的时候,就直接把翻转标记给删掉了。这样的话只要既存在翻转又存在赋值,就肯定是先赋值在翻转了。

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

CF Edu24 / CF818

D Multicolored Cars

+1 在 $m$ 不存在于数组中的时候判错了,应该随意输出一个数组中的东西。

自己想了一个比较垃圾的做法,把所有比 $m$ 出现次数多的提出来,然后 $O(cnt_m)$ 算一下所有 $m$ 出现的点(只有这些点可能导致 $cnt_m > cnt_x$ )时间复杂度是 $O(n\log n)$ ,因为需要 lower_bound 去看 $x$ 在某个前缀的出现次数。

其实有一种非常简单的做法:

1
2
3
4
5
6
7
8
9
10
11
int a,b,c,i,j,n,k[1000001];
main (){
cin>>n>>a;
for (i=0;i<n;i++){
cin>>b;
if (k[b]>=k[a]) k[b]++;
if (k[a]>k[c]) {cout<<-1; return 0;}
if (k[b]>k[c]) {c=b;}
}
cout<<c;
}

就是维护当前出现次数最多的东西的出现次数,如果出现次数最多的都不如了 $m$ 显然就没救了。如果某一个时刻某个数的出现次数已经不如 $m$ 了就不管它了,之后都不给这个数的出现次数增加了。

想想会发现显然是对的,复杂度 $O(n)$ 。

E Card Game Again

1A

不难发现只需要考虑所有 $k$ 的质因子,最多 $\max (w(10^9)) = 8$ 个。

所以我们可以对每个数开个 vector 表示这个数在每个 $k$ 的质因子的次数是多少。

然后可以发现,这个左端点关于右端点是单调递增的,同时对于同一个右端点,显然有一个最大的 $l$ 满足 $l’ < l$ 都满足条件。

所以我们可以用双指针扫过去即可。每个数会被加一次,删除一次,复杂度是 $O(nw + \sqrt k)$ 。

F Level Generation

1A

会发现通过点去求边不太方便,考虑如果我们确定了有 $m$ 条边,那么最少可以放多少个点。

一种构造方式是,先给所有 $\lceil \frac m 2 \rceil$ 个桥边加入进去,那么现在我们就有 $\lceil \frac m 2 \rceil + 1$ 个边双。然后发现最优的构造策略肯定是给 $\lceil \frac m 2 \rceil$ 个边双构造成单点,剩下的一个放一个尽量小的边双,使得可以用完剩下的所有边,也就是可以放最小的 $n$ 满足 $\frac{n(n-1)}{2} \ge \lfloor \frac m 2 \rfloor$ 。

可以发现,随着边数增加,其实每个 $n$ 都是可以取到的。所以我们可以直接二分一下最小的边数,使得 $n$ 可以被取到即可。

G Four Melodies

+1 开始连边方式是 $O(n^2)$ 条边,后来考虑优化才过掉了。

真就两场后的加强呗。

显然这个东西不太能 $dp$ 了。考虑一下更加一般的问题,这东西本质上就是给定一个 $\text{DAG}$ ,选出四条点不相交路径使得整个图尽量多的点被覆盖。

如果我们拆点一下,把点拆成入和出,然后入边向出边连费用为 $1$ ,容量为 $1$ 的边,再从所有出点向汇点连边,从入点限制 $4$ 流量后向所有入点连边,就可以跑一次费用流解决这个问题了。

然后写了一下,TLE on test 4 ,$O(n^2)$ 条边暴过去还是不可能的。

怎么优化呢?回归这个题,分别考虑这两个限制。我们对每个点建立两个虚点,第一个虚点连向下一个 $\bmod 7$ 同余的点,第二个虚点连向下一个值相同的点。然后从每个位置的出点同时连向下一个 $\bmod 7$ 相同和值为 $A_i \pm 1$ 的点,从两个虚点都向这个入点连边。然后这样得到的图边数就是 $O(n)$ 的了。

$\text{SPFA}$ 跑费用流即可。最慢的点大概跑了 400ms

文章作者: yijan
文章链接: https://yijan.co/2020/12/28/edu-20-~-24/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog