Edu 20 ~ 24

CF Edu 20 / CF803

A Maximal Binary Matrix

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

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

B Distances to Zero

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

C Maximal GCD

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

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

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

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

D Magazine Ad

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

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

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

E Roma and Poker

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

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

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

复杂度 O(nk)O(nk)

F Coprime Subsequences

套路题。

{ak}A[gcd{ak}=1]={ak}Atgcd{ak}μ(t)=t1μ(t){ak}A,tgcd{ak}1\begin{aligned} & \sum_{\{a_k\} \in A}[ \gcd\{a_k\} = 1 ]\\ &= \sum_{\{a_k\} \in A} \sum_{t | \gcd\{a_k\}}\mu(t)\\ &= \sum_{t\ge 1} \mu(t) \sum_{\{a_k\} \in A,t | \gcd\{a_k\}} 1\\ \end{aligned}

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

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

G Periodic RMQ Problem

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

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

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

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

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

CF Edu 21 / CF808

D Array Division

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

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

E Selling Souvenirs

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

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

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

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

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

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

复杂度 O(n)O(n)

F Card Game

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

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

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

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

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

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

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

G Anthem of Berland

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

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

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

dp[i]=maxjborder{dp[i+mj]+1}dp[i] = \max_{j \in \text{border}} \{dp[i+m-j] + 1\}

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

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

dp[i]=maxji+mdp[j]dp[i] = \max_{j \ge i+m} dp[j]

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

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

CF Edu 22 / CF813

C The Tag Game

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

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

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

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

D Two Melodies

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

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

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

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

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

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

E Army Creation

1A

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

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

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

复杂度 O((n+q)logn)O((n + q)\log n)

F Bipartite Checking

+1 某个地方并查集修改 uu 写成 vv 了。

老套路题了。

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

CF Edu 23 / CF817

D Imbalanced Array

1A

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

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

E Choosing The Commander

1A

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

F MEX Queries

1A

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

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

复杂度 O(nlogn)O(n\log n)

CF Edu24 / CF818

D Multicolored Cars

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

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

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

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;
}

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

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

E Card Game Again

1A

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

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

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

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

F Level Generation

1A

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

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

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

G Four Melodies

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

真就两场后的加强呗。

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

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

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

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

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

\