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

套路题。

$\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}$

后面的条件就是，这个子序列必须全部被 $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$ 。

但是注意到这个题只需要算总容量是 $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}$ 的位置开始。所以转移有：

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

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

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

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

这个东西是可以预处理 $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

这个询问就是对区间内每个数的出现次数和 $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

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

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

E Choosing The Commander

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

F MEX Queries

我们考虑能取到 $\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$ 在某个前缀的出现次数。

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

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

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

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

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

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

F Level Generation

会发现通过点去求边不太方便，考虑如果我们确定了有 $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 。