算法

44 道题全部只会暴力。还不如直接发下来当练习做呢,省得在场上罚坐三小时浪费时间。

简略题解

A – 神灵庙

观察发现:

  • 当树的形态确定时,我们总是将权值更大的节点安插到深度更小的叶子上。可以将 aa 降序排序后逐层填写。
  • 一个节点只可能有 00 个或者 22 个儿子。如果只有 11 个儿子,显然可将该节点删除而整棵子树全部向上平移。

f(d,i,c1,c2)f(d,i,c_1,c_2) 表示“现在位于第 dd 层(此处“层”指的是节点实际深度)。已经填写好了 a1,a2,,aia_1,a_2,\cdots,a_i,且第 dd 层共 c1c_1 个空置(非叶子)节点,第 d1d-1 层有 c2c_2 个此类节点”。那么两层的每一空置节点,均会有一个第 d+1d+1 层的儿子。枚举“下一层要填写 kk 个元素”,有转移 f(d+1,i+k,c1+c2k,c1)f(d,i,c1,c2)+(j=i+1i+kaj)(d+1)f(d+1,i+k,c_1+c_2-k,c_1)\leftarrow f(d,i,c_1,c_2)+\left(\sum_{j=i+1}^{i+k}a_j\right)(d+1) (更多…)

More
  • 2022年11月18日

LibreOJ #138 类欧几里得算法

题意

T1000T \leq 1000 组数据。给定 n,a,b,c[0,109],k1,k2[0,10],k1+k210n, a, b, c\in [0, 10^9], k_1,k_2\in [0, 10], k_1+k_2\leq 10,求取 x=0nxk1ax+bck2 \sum_{x=0}^{n}x^{k_1}\left\lfloor\frac{ax+b}{c}\right\rfloor^{k_2}

部分分——观察性质

k1=0,k2=1k_1=0,k_2=1 时,是为一般类欧几里得算法的模板。上述链接亦给出了 k1=0,k2=2;k1=1,k2=1k_1=0,k_2=2; k_1=1,k_2=1 时的解法。

k2=0k_2=0 时,该式退化为 x=0nxk1\sum_{x=0}^{n}x^{k_1},即 k1k_1 次的等幂求和。有一个模糊的结论:

nn 为正整数。则kk 次的等幂求和,x=0nxk\sum_{x=0}^{n}x^k,是一个关于 nnk+1k+1 次多项式。

该结论来源于 zyw 学姐多项式专题所选题目 BZOJ 3453 – tyvj 1858 XLkxc。之所以说模糊,是因为该多项式的系数是已知的。不过我们仍然可以暴力计算 k+2k+2 个点以插值。

再观察 OI-Wiki 上对于 k1+k22k_1+k_2\leq 2 时的解法。在求取 h(n,a,b,c)=x=0nax+bc2h(n,a,b,c)=\sum_{x=0}^n\left\lfloor\frac{ax+b}{c}\right\rfloor^2时采取了如下转化:

x2=2×x(x+1)2x=2(y=1xy)xx=0nax+bc2=x=0n2(y=1ax+bcy)ax+bc\begin{aligned} x^2&=2\times \frac{x(x+1)}{2}-x\\ &=2\left(\sum_{y=1}^{x}y\right)-x\end{aligned} \quad\begin{aligned} \Longrightarrow\sum_{x=0}^n\left\lfloor\frac{ax+b}{c}\right\rfloor^2=\sum_{x=0}^n2\left(\sum_{y=1}^{\left\lfloor\frac{ax+b}{c}\right\rfloor}y\right)-\left\lfloor\frac{ax+b}{c}\right\rfloor\\ \end{aligned}

这样一来,由于 yy 是一个线性算子,在 ax+bycax+b\geq yc 时都有 yy 向总和贡献,于是我们可以应用类似于 k1=0,k2=1k_1=0,k_2=1 时的方法转化贡献。这个过程对 k2k_2 作了降次。

那么,对于更高次项,有无办法采取同样的办法转化呢?是否可以设计一些转化,使得要求取的函数 f(,k1,k2)f(\cdots,k_1,k_2) 能够由 f(,k1?,k2?)f(\cdots,k_1-?,k_2-?) 推出呢? (更多…)

More
  • 2022年10月13日

Algorithm 457: Finding All Cliques of an Undirected Graph [H] – Coen Bron* and Joep Kerboscht – Archives of Communication of ACM

原Essay详细而准确地描述了该算法的过程,不需要额外的注解也能轻松理解。若英语阅读吃力,也有一份不错的中文详述:

极大团(maximal clique)算法:Bron-Kerbosch算法 – Bowiee – 简书

下面给出一份参考实现,能够找出所有极大团。使用unsigned long long存储各状态点的集合,二进制表示下从低到高第(x1)(x-1)位为11表示点xx存在于集合中。 (更多…)

More
  • 2022年4月14日

被这玩意卡了一上午——前天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日

看来脑瓜子还是不够灵活啊。以前看到“matching”、“bipartite”一类的标签,试图二分图时只晓得将题目中同一类的元素转化为点,将相对关系转化为边。但实际上,二分图也可以表示其他的二元逻辑关系,例如包含、排除。

例如[NOIP2010 提高组] 关押罪犯,一个经典做法是将罪犯转化为点集,将冲突关系符合一定条件的相互连边,然后二分答案作二分图匹配。(扩展域并查集实质上也是在贪心的基础上,运用“二分图匹配”的思想检查方案合法性……对吧?)

再例如AtCoder ABC 228 G – Digits on Grid,计数DP的转移也是在行、列元素分别作为左部、右部,以方格中的元素作为边权的二分图上进行的。

这道题则非常精妙——CF1634E – Fair Share。看到“要将所有元素分成两个相等的可重集”时,我认为应当用可重集作为二分图的左部和右部。但是这样一来,如何进行匹配呢?正解则是将数组ii包含元素aia_i逻辑关系转化为边——左部为各个数组,右部为相同的元素。可以发现,能够有解的充分必要条件是“每个元素均统共出现了偶数次”,同时“每个数组含有偶数个元素”,那么该图中每个节点的度数均为偶。记得小学奥数的一笔画问题么?它有一个更专业的术语,曰欧拉回路。事实上,一张无向图存在欧拉回路,当且仅当不存在度数为奇的节点。所以,我们直接求解一条欧拉回路,将从左部到右部遍历的边记作LL,从右部到左部遍历的边记作RR就是一个正确的解。

More
  • 2022年2月7日

DFS序列(dfn\mathrm{dfn}

在没有或存在一定限制条件的情况下,以DFS遍历经过的节点顺序构成的序列。记dfn(x)\mathrm{dfn}(x)为第一次访问该节点的时间戳,seq(t)\mathrm{seq}(t)为访问序为tt的节点。

容易发现,节点xx的子树节点的dfn\mathrm{dfn}一定是一段连续的区间。故我们可以使用数据结构方便地维护子树的信息。

(更多…)

More
  • 2022年2月4日

昨晚参与AtCoder ABC 236时认为G题似乎可做,直到看到数据范围才发现事情没有那么简单

由于最近学习离线数据结构,又见识过一道题意接近的题目,故想到整体二分,二分每一个节点第一次能恰好经过LL条边到达的时间,然后考虑DP求解。设计状态f(i,x)f(i, x)表示在该图上经过恰好ii次转移能否到达点xx。但很快发现每一次二分时均要重新在图上运行DP,时间复杂度无法承受。况且DP递推转移的次数LL高达10910^9,甚至不可能是线性的复杂度。

今天查看题解,发现有几个重要的,从未考虑过的trick:

  1. 既然要求能够经恰好LL次转移到达的最早的时间点,则我们将每条边的边权ww设为其加入图中的时间,则可以转化成恰有LL条边的最小瓶颈路
  2. 发现LL很大,所以考虑通过矩阵乘法加速递推,也即所谓倍增优化DP的一种。

(更多…)

More
  • 2022年1月24日