A - GCD is Funny

题意:在黑板上写有$n$个数,每次删掉$a,b,c$三个数并把$d$写两遍,$d$可以是$(a,b),(a,c),(b,c)$。在$n-2$次操作后会留下两个相同的数,输出这个数的所有可能情况。
题解:给跪了。。。其实是所有大小超过$1$的子集的$gcd$的集合。。。

注意点:值域限制,说是子集当然不可能直接按子集做,而是利用值域很小这一点标记着做;gcd下降速度,两个不一样的数取$gcd$,最大也只能是大数的一半,即对数级别次就可以到$1$。

B - Square Distance

题意:给一个串$s$,长度为$n$(保证偶数),输出一个串$t$,要满足:$t$由两个相同的串拼接而成;$s$到$t$的汉明距离恰好为$m$;$t$是所有满足条件的串中字典序最小的。$s,t$均只含小写字母,若$t$不存在输出Impossible
题解:后半段放到前半段综合考虑,用dp可以求出前$i$个字符产生$j$个距离可不可行。因为要输出字典序最小,所以最终的贪心一定是从前往后从小往大,若是直接在这种dp上贪心,会导致最后的距离不一定是$m$。所以这里需要倒着dp,即从第$\frac{n}{2}$个到第$i$个字符产生$j$个距离可不可行。

注意点:看着很像贪心但是没有具体策略的时候一定要想一想dp!不一定只贪心或者只dp,也不一定是用贪心优化dp,像这题就是在dp得到的表上进行贪心

C - LCIS

题意:给出$n$个数的序列$a$和$m$个数的序列$b$,问公共的上升的并且数值连续的子序列的最长长度。
题解:对$a$扫一遍得到以$x$结尾的连续值上升子序列的最长长度,同样地对$b$扫一遍,最后枚举结尾是什么数字,取两个结果的较小值更新答案。

注意点:当对子序列的限制非常强时,很有可能可以每个序列分开做,最后再合并到答案。

D - Black White Tree

题意:$n$个节点的无根树$T$,每个节点是黑色或者白色,求$W = \displaystyle\sum_{a=0}^{n}\sum_{b=0}^{n}{(a+1)(b+1)S(a,b)}$,其中$S(a,b)=1$表示存在一个子树恰好由$a$个白色节点和$b$个黑色节点构成,$S(a,b)=0$表示不存在。$T$的一个子树定义为$T$的一个子图并且是树。
题解:对于确定大小的子树,如果可以知道最少以及最多有几个黑色节点,那么答案直接两重循环加一个判断就可以算出来了。所以我们可以进行树形dp求出这个最少和最多。先规定$1$作为根,那么题意中的子树就是规定根以后的连通块,用$f[u][i],g[u][i]$分别表示以$u$为根,大小为$i$时最少和最多的黑色节点数,用$F[i],G[i]$表示连通块大小为$i$时最少和最多的黑色节点数。这个转移直接借助代码来说还更好一点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void dfs(int u,int fa)
{
sz[u]=1;
f[u][1]=g[u][1]=s[u]-'0';
for (int v:eg[u]) {
if (v==fa) continue;
dfs(v,u);
for (int i=sz[u];i>=1;i--) {
for (int j=1;j<=sz[v];j++) {
f[u][i+j]=min(f[u][i+j],f[u][i]+f[v][j]);
g[u][i+j]=max(g[u][i+j],g[u][i]+g[v][j]);
}
}
sz[u]+=sz[v];
}
for (int i=1;i<=sz[u];i++) {
F[i]=min(F[i],f[u][i]);
G[i]=max(G[i],g[u][i]);
}
}

每个节点被访问深度次,所以最终的复杂度是$O(n^2)$。

注意点:无根树的子树等价于确定一个根以后的连通块

F - Aaronson

题意:$x_{0}+2x_{1}+4x_{2}+…+2^{m}x_{m}=n$的解是$(x_0,x_1,x_2,…,x_m)$,$x_i \ge 0$,求$\displaystyle\sum_{i=0}^{m} x_i$的最小值,$(0 \le n,m \le 10^9)$。
题解:若$m$比较小,特殊处理一下$x_m$,剩下的以及其他的情况都是二进制表示的$1$的个数。

G - Bellovin

题意:长度为$n$的$a$序列,求一个长度也为$n$的$b$序列满足,$a$中以$a_i$结尾的$LIS$长度和$b$中以$b_i$结尾的$LIS$长度相等$(1\le i \le n)$,$b$的字典序最小。
题解:因为$b_i$最小是$1$,直接把$a$中以$a_i$结尾的$LIS$长度当作$b_i$即可。

H - Colmerauer

题意:一个矩阵的权值定义为其所含的所有鞍点的值的和,若一个点在列上是唯一最大值,在行上是唯一最小值,则其为鞍点。又在矩阵$M$上定义$S(a,b)$,表示所有大小为$a$行$b$列的子矩阵的权值和。现给出矩阵$M$,求$W = (\displaystyle\sum_{a=1}^{n}\sum_{b=1}^{m}{a \cdot b \cdot S(a,b)}) \text{ mod } 2^{32}$。
题解:很容易想到单点贡献。对于矩阵中的每一个点,我们暴力出(或者用单调栈优化一下)它能往上下左右延伸的长度,然后直接贡献即可。

注意点:左右长度的算式没有理清楚,应该写出原始的公式再进行化简

I - Dertouzos

题意:$n$的真因子是不为$n$的因子。给出$n$和$d$,问有多少小于$n$的数的最大真因子是$d$。
题解:即$pd=m<n$,显然有

  1. $p \le \frac{n-1}{d}$;
  2. $p$必须为质数;【如若不然,则$p$有真因子$q$,$qd$是比$d$更大的$m$的真因子。
  3. $p \le c$,其中$c$为$d$的最小质因子。【如若不然,则$\frac{d}{c}\times p$是比$d$更大的$m$的真因子。

由2,我们先做一遍筛法以及前缀和。再算出1的界,最后用筛出来的质数去算3的界。

注意点:用筛出来的质数去算3的界会有$O(\sqrt{d})$的复杂度,当$d$很大($\approx 10^{9}$)时会超时,而此时1的界必然比较小,应该在超过已有的界时及时退出

J - Eades

题意:长度为$n$的$a$序列,定义$g(l,r)$为$a_l$到$a_r$的最大值,定义$f(l,r)=\displaystyle\sum_{i=l}^{r}[a_i = g(l,r)]$。求对于所有$1\le k \le n$的$k$分别有多少对$(l,r)$满足$f(l,r)=k$。
题解:如果$a_i$要对$f$函数有贡献的话必须是这个区间内最大的,所以首先用单调栈求出往左以及往右第一个大于$a_i$的位置。那么在$L+1…R-1$中,$a_i$这个值将区间分为若干段,朴素的想法是直接枚举左端点和右端点在哪一段上然后累加到答案,但是这样还是$O(n^2)$的【其实处理得好能卡过,不过进一步可以发现具体贡献到哪一个答案其实只跟$j-i$(两个段编号的差)有关,那么把其中一个反过来就是一个卷积形式,可以套一个$fft$。

注意点:具体细节较多,想不清楚时一定要耐心&动手模拟一下

K - LCP Array

题意:$s$是一个$1base$的字符串,记$a_i=lcp(ssuff_i,suff_{i+1})$,$(1 \le i < n)$。现给出$a$序列,问有多少只含小写字母的字符串$s$满足这个序列。
题解:若$a_i$不为$0$,那么$s_i…s_{i+a_{i}}$这些字符必须全都相同(手动模拟一下),由此推出从后往前:$a_i$不为$0$则必须连续地增加,若不满足答案为$0$;$a_i$为$0$则将答案乘上25。

L - Shortest Path

题意:$n$个点的无向图,原来在$i$和$i+1$之间有边,现在添加3条边,所有边的权值都是$1$,每次询问$u$到$v$的最短路是多少。
题解:实际上就是改变了6个点(或者不到6个)之间的距离,直接Floyd。询问的时候直接暴力枚举穿过哪两个点。

注意点:不要忘记跟初始的距离取$min$。

M - Transform

题意:给出$n$个数,可以对整数$x$进行两种操作,

  1. 翻转$x$的一个bit;
  2. $x \leftarrow x\ xor\ a_i$ 。

每次询问把$S$变成$T$最少需要几步。
题解:两个操作都可以归结为$xor$,所以从$S$走到$T$跟从$0$走到$S\ xor\ T$是等价的。直接以$0$为起点按两种操作进行$bfs$,$O(1)$回答。

注意点:状态数trick,虽然每次有几十条边,但是最后询问的范围只有$10^5$左右,最多也就是$0$到$(2^{17}-1)$每个点都走一遍。

N - Toposort

题意:有向无环图有$n$个点$m$条边,问恰好删除$k$条边可以做到的字典序最小的拓扑序。
题解:考虑字典序最小,首先$1$号点放在第一绝对比放在第二好,那么:如果$1$号点当前的入度$d_1$小于等于$k$,直接将这$d_1$条边全部删除即可;如果大于,再测试$2$号点、$3$号点……。用优先队列保证每次取出的是最小编号的点,每条边访问一次,每个点最多入队$n$次,复杂度感觉上是$O((n+m)log{n})$。

注意点:对字典序和贪心的理解不够深刻

O - Deletion

题意:无向图$G$有$n$个点$m$条边,每次可以删除一个边集,要求这个边集组成的导出子图的每个连通分量最多只有一个环。问最少几次可以把图$G$完全删除。
题解:对于一个连通分量,若至多一个环,那它就是一个广义的环加外向树(可以没有环或者没有树)。环加树又可以理解为每个点最多一个出度,再反推回去,若有答案为$k$,那么等价于给图$G$中的每条边定向,使得所有点的出度均不超过$k$。考虑到一条边$(u,v)$,要么在$u$是出度要么在$v$是出度,新建一个点$x_{uv}$表示原图中的这条边,那么它要么与$u$匹配要么与$v$匹配。在这个新图中,左边的点(原图的点)最多匹配$k$次,右边的点(原图的边)最多匹配$1$次,且当右边的点完全匹配时$k$是一个可行的答案,可以二分答案每次判断最大流是不是等于$m$。xg最后提到其实二分可以不要,因为右边的点到汇的容量始终是$1$,每次改改增广路啥的。【然而这种操作本菜鸡就没必要学了吧。。。

注意点:环、树、环加树的点数边数以及度数都有特殊的结论。

P - Card Game

题意:Soda 和 Beta 各有$n$张牌,两人随机抽$m$张牌,用它们的和比大小,问 Soda 能不能稳赢。
题解:取 Soda 最小的$m$张跟 Beta 最大的$m$张,它们的和比一下大小。

Q - LCS

题意:有两个排列${a_1, a_2, …, a_n}$,${b_1, b_2, …, b_n}$,要找到另一个排列${p_1, p_2, …, p_n}$,使得${a_{p_1},a_{p_2},…,a_{p_n}}$和${b_{p_1},b_{p_2},…,b_{p_n}}$的$LCS$最长,输出$LCS$长度的最大值。
题解:$b$是$a$的置换,长度为$l$的环能产生$l-1$的$LCS$。

注意点:特判环长度为1。

R - Beauty of Sequence

题意:定义魅力值为一个序列去除序列中连续重复元素(每一段只保留一个)后的序列的和。给出$n$个数的序列$a$,求$a$的所有子序列的魅力值之和。
题解:考虑单点贡献,并且出现连续相同值时只有最左边的要贡献。那么对于$a_i$,只要之前的子序列不以$a_i$结尾就可以贡献,累加答案以后更新一下以$a_i$结尾的子序列的数量即可。

注意点:不用考虑本质不同。

U - Souvenir

题意:$p$块钱可以买1个纪念品,$q$块钱可以买纪念品套装,内含$m$个纪念品,问要给$n$个人各发一个纪念品至少要多少钱。
题解:只有三种情况,只用$p$,只用$q$,用$q$直到剩下不到$m$的用$p$。

注意点:显然是可以多买的。

W - Sequence

题意:一个数列的第$n(n \ge 1)$项为$3n(n-1)+1$,给出一个数$m$,问至少几个数的和能恰好等于$m$。如,$22 = 19 + 1 + 1 + 1 = 7 + 7 + 7 + 1$。若不能,输出$-1$。
题解:联想到三角形数$a_{n}=\frac{1}{2}n(n-1)$,至多3个三角形数可以表示任意自然数。而$3n(n-1)+1=6a_{n}+1$,那么$m\equiv ans \mod 6$。特判一下$ans$等于$1$或$2$,否则就是$3\dots 8$中与$m$同余的数。

注意点:特判也需要考虑复杂度