DP(动态规划)

T1 的 Hack 数据提醒我,尽管时间复杂度没有变化,但所有想到剪枝和常数优化在时限不充裕的题目中仍是必要的。

T2 没有认真读题,忽略了“恰执行一次”的要求。

T3 里面没有使用自己熟悉的存边方式,时间趋紧的情况下代码实现出错。这再次告诫我应以求稳为重。

简单题解

A – 跳棋

(x,y)(x,y) 跨步跳能够跳到 (x±2,y),(x,y±2)(x\pm 2,y),(x,y\pm 2),以及 (x+k,y+k),k=±2(x+k,y+k),k=\pm 2。可以发现 x,yx,y 奇偶性均不变。我们只需要考虑所有存在棋子的格子及其邻居。它们形成若干连通块,在这些连通块上 BFS 即可。

若采用 std::map 存储,时间复杂度为 O(7nlogn)\newcommand\bigO{\operatorname{O}}\bigO(7n\log n)。需要采纳“避免遍历不存在的连通块”之类的优化。 (更多…)

More
  • 2022年11月23日

中规中矩的一场模拟赛。

T1 写得实在是太久了……这也是没办法的事情——如果不对转移作压缩优化就没办法过。

T2 有我喜欢的马拉车 Manacher 算法,是印象里第二次在模拟赛应用。

然后就没时间了。后两题仍然只有暴力分,但最近频繁遇到跟凸包和线性函数相关的题目,这使我发现 T3 跟它相关。在最后一点时间里实现了构建凸包的函数。代码本身没问题,但思路是错误的。

简略题解

A – 石蒜反冲

这好像是很早以前的译名了。现在它叫《莉可丽丝》。

遇见多模式串匹配,自然想到自动机上 DP。但我们发现题目中给定的两个串 sakana chinanago 在任何一个文本串中最多只能匹配其中一个,且匹配位置唯一。于是简单计数 DP 转移,记录当前二者匹配数之差与目前匹配位置即可。

一些不应用就过不了的优化:

  • 二者数量之差可只记录到 n15\frac{n}{15}1515 是两个串的总长度。
  • 转移时对于 ? s c a o 还有其他字符分类讨论,保证单次转移复杂度为 O(1)\newcommand\bigO{\operatorname{O}}\bigO(1)

时间复杂度 O(n2)\bigO(n^2)(更多…)

More
  • 2022年11月16日

感冒咳嗽,头实在是太晕了,打完前两题和后两题的暴力之后跑去睡了会觉。结果考得还行。

一句话题解

A – 破坏

简单的 O(m2k)\newcommand{\bigO}{\operatorname{O}}\bigO(m2^k) DP。记录每个节点的路径数奇偶性考虑是否翻转即可。

B – 共识

std::bitset 写的暴力大家都会。不过如果你胆子大些,不判断是否为部分分数据范围直接提交(加入随机化的)暴力,将喜提 100 pts\text{100 pts}

命题:现有一个由 2n2n 个元素构成的集合,保证 2n2\mid n。有 n+1n+1 个大小恰为 nn 的子集 S1,,Sn+1S_1,\cdots,S_{n+1}。则至少存在 n/2n/2 对无序对 (i,j),ij,i,j[1,n+1](i,j),i\neq j, i,j\in[1,n+1],使得 SiSjn/2|S_i\cap S_j|\geq n/2

证明(引自宋佳兴学长):记元素 p,p{1,,2n}p,p\in\{1,\cdots,2n\} 在所有子集中出现的次数为 cnt(p)\newcommand{\cnt}{\operatorname{cnt}}\cnt(p)。则显然有“所有子集两两之交的大小” i=1nj=i+1n+1SiSj=p=12n(cnt(p)2)\sum_{i=1}^{n}\sum_{j=i+1}^{n+1}|S_i\cap S_j|=\sum_{p=1}^{2n}\binom{\cnt(p)}{2}

考虑计算该式最小为何。不妨先考虑 (ab)+(nab)\binom{a}{b}+\binom{n-a}{b} 在何时取最小值。

引理(ab)+(nab),bn,a0,an\binom{a}{b}+\binom{n-a}{b}, b\leq n, a\geq 0, a\leq na=n/2a=\lfloor n/2\rfloor 处取最小值。

(更多…)

More
  • 2022年10月26日

堪堪能接受的一场。前两题一个半小时左右做完,后两题实在没什么思路,打完所有可能的暴力之后跑路了。

他们告诉我题目名称可以从上到下连起来读。

一句话题解

A – (种)菜

可以发现,假若同时有 ai,ai+1\newcommand{\bigO}{\operatorname{O}}a_i,a_{i+1}ai+1,ai+2a_{i+1},a_{i+2} 都可合并,则取 ai,ai+2a_i, a_{i+2} 中任意一个合并之后,质因数集合总是变为原来的超集,另外一项仍可合并。

故而可以贪心合并所有合法的邻项,最终检查是否仅剩一项即可。注意到 [1,700][1,700] 仅含 125125 个质因数,故可以用 std::bitset 保存每一项的质因子集合。复杂度 O(128nω)O(\frac{128n}{\omega})赛时竟然还开了数组保存每个质因子的实际指数! (更多…)

More
  • 2022年10月26日

签到题看了半个小时;T2 没有考虑到只需要包含最优解即可,非要确定另一多余状态,只拿了部分分。

T3 只会考虑 “x,yx, y 的公共祖先中含有 ll 的概率”,不会高效计算“当二者的 lca\operatorname{lca} 恰为 ll 时”的期望/概率与总长之和的乘积,仍然只有暴力分。

T4 无思路。

一句话(?)题解

A – 签到题

可以简单用归纳法证明,仅有所有管道中通行时间最大的会阻塞进度,是为两数据包到达终点的时间间隔。算出首个数据包到达的时间再将前者相加即可。

B – 简单题

第一反应是类似笛卡尔树一样,在区间上依次合并区域最大值并计算贡献。n300n \leq 300 似乎也在暗示这是一个区间 DP。

48 pts\text{48 pts} 做法

f(l,r,mx)f(l,r,\text{mx}) 表示“考虑完成区间 [l,r][l,r] 内所有贡献,且最大值恰好为 mx\text{mx}”的最大权值和。转移时从小到大枚举最大值 mx=Vi,j\text{mx}=V_{i,j},枚举包含它的区间,尝试转移 f(l,r,mx)f(l,i1,mx’)Ci,j+mxcalc(l,r,i)+f(i+1,r,mx”)f(l,r,\text{mx})\leftarrow f(l,i-1,\text{mx}’)-C_{i,j}+\text{mx}\cdot \operatorname{calc}(l,r,i)+f(i+1,r,\text{mx}”),其中 calc(l,r,i)\operatorname{calc}(l,r,i) 计算 l=lir=irQl,r\sum_{l’=l}^{i}\sum_{r’=i}^{r}Q_{l’,r’},可以由二维前缀和实现。稍加演算会发现,这样转移不会重复计算贡献。时间复杂度 O(KiN2)\operatorname{O}(\sum K_{i}N^2)(更多…)

More
  • 2022年10月19日

CodeForces Round #755 Div.2 F / Div.1 D Serious Business

此题整整困了我一天半,耗费了好几张草稿纸。实在走投无路,翻看题解,却发现正解曾经近在咫尺。有必要稍作整理。

考虑DP。

错误转移1

这道题与清理班次(《算法竞赛进阶指南》上的一道例题)过于相似,都是“给定一些段落[lp,rp][l_p, r_p],选择其中一些完整覆盖[l0,r0][l_0,r_0],求最小花费”的形式。记上述花费为f(l0,r0)f(l_0, r_0)。但本题与原题不一样之处在于其起点和终点是任意给定的。我的第一反应是枚举在x2x_2位置从第22行转到第33行,利用数据结构维护所有x1x2x_1\leq x_2,在x1x_1转移到第二行,解锁到达x2x_2的最小代价。对于各行前缀和,我们可以利用线段树或树状数组维护。同时我们也知道可以利用数据结构优化在O(nlogn)\mathrm{O}(n \log n)的时间内,计算出对于一个固定的起点l0l_0,所有f(l0,r0),r0[l0,n],p,rp=r0f(l_0, r_0), r_0 \in [l_0, n], \exists p, r_p=r_0的值。 (更多…)

More
  • 2022年3月8日

被这玩意卡了一上午——前天CSP-S模拟的T4需要用到这类问题的转移。为什么题解TMD是错的?

g(i,j,k)g(i,j,k)表示“每个位置有ii类元素可选,且序列中必须包含指定的jj类元素的,长度为kk的序列的个数”。形式化地讲,我们需要统计满足以下条件的序列的个数:p[1,k],apS (S=i);bTS (T=j),p[1,k],ap=b\forall p \in [1,k], a_p \in S\space(|S|=i); \forall b \in T \subseteq S\space(|T|=j), \exists p \in [1,k], a_p=b

通过容斥原理,我们可以计算出至少有0,1,2,,j0,1,2,\dots,jTT中的元素没有被包含在序列中的序列的个数,然后乘上容斥系数累加既是答案。也即: g(i,j,k)=x=0j(1)x(jx)(ix)kg(i,j,k)=\sum\limits_{x=0}^{j}(-1)^x\dbinom{j}{x}(i-x)^{k}。通俗地讲,我们在 jj 个元素中选择 xx 个,并强制使得它们不出现在序列中,其余元素任选。除去组合数的预处理时间,复杂度为O(j)\mathrm{O}(j)。参阅AtCoder ABC 194 F – Digits Paradise in Hexadecimal可以使用上述计算而非DP求解(虽然DP更加简洁直观)

(更多…)

More
  • 2022年3月4日

考虑一棵无根树的生成方式:需要决定一个好的顺序从而达到不重不漏地生成所有 nn 个点的无根树。

类似有向无环图的拓扑排序,可以定义一种无根树的“拓扑排序”:每一轮将当前的叶子删去。这样可以很容易算出直径。设删除的轮数为 rr,则当最终剩余一个孤点时,直径 d=2rd=2r,否则直径 d=2r1d=2r-1。为了生成无根树,我们考虑进行逆操作,在当前的树上加叶子。在此之前,为了不重不漏地对无根树进行表示,我们考虑如下的唯一表示方法:设 dis(x)\text{dis}(x) 为节点 xx 在添加叶子过程中第几轮被添加上树的。对于S={xdis(x)=const}S=\{x\mid \text{dis}(x)=\text{const}\}(也即同一层的节点),显然两棵有标号无根树同构但标号不同,当且仅当每个上述节点xx的叶子节点的标号集合不同。我们总是将 xx 标号小的先行添加为其儿子。这样就不会出现因“两棵树本身同构,子节点编号集合相同导致重复计数的问题”。同时,为了方便、准确地计算,我们严格规定,新加入的 kk 个叶子节点在新树上就是全部的叶子节点。也即在旧树上的所有叶子节点在新树上至少有一个儿子。 (更多…)

More
  • 2022年3月4日

有集合SSS=n|S|=n,则有TS2T=k=0n2k(nk)=3n\sum\limits_{T \subseteq S}2^{|T|}=\sum\limits_{k=0}^{n}2^k\dbinom{n}{k}=3^n。因此,若我们枚举集合,枚举集合的子集的子集做状压DP时,可以得到正确的复杂度O(3n)\mathrm{O}(3^n)而非错误的O(2n×2n)=O(4n)\mathrm{O}(2^n\times 2^n)=\mathrm{O}(4^n)。参见AtCoder ABC 187 F – Close Group

可以这样证明:考虑某个子集的子集PTSP \subseteq T \subseteq S,则SS中的每个元素有三种状态:aPa\in PaP,aTa \notin P, a \in TaT,aSa \notin T, a \in S。显然这样可以唯一表示SSTT以及PP,对应了所有子集的拆分方案。故原式成立。

UPD 03.24 我们还有更加一般的结论:k=0nxk(nk)=(x+1)n\sum\limits_{k=0}^{n}x^k\dbinom{n}{k}=(x+1)^n,据说证明需使用二项式定理?

More
  • 2022年2月24日