这道破题拖了我整整一天。

代数推导

转化为容斥模型

题目所给限制可以表述为,aabb 均为单调不降的序列,长度相等(记为 kk),且 a1=0,ak=n,b1=0,bk=m,i[2,k],ai=ai1bi=bi1a_1=0,a_k=n,b_1=0,b_k=m,\nexists i\in[2,k],a_i=a_{i-1}\land b_i=b_{i-1}

考虑差分序列 ai=aiai1(i[2,k]){a_i}’=a_i-a_{i-1}\quad(i\in[2,k])bi{b_i}’ 同理,它与原序列形成双射。于是不存在 ai=bi=0{a_i}’={b_i}’=0 的差分序列合法。考虑 i=2kai=n\sum_{i=2}^{k}{a_i}’=n,也就是和为 nnk1k-1 元线性方程组的一组非负整数解;bb’ 同理。容易计算“钦定至少有 cc 个位置不合法”的方案数——利用容斥原理即可得到长为 kk 的合法序列对个数为 c=0k2(k1c)(n+(k1)1c(k1)1c)(m+(k1)1c(k1)1c)(1)c\sum_{c=0}^{k-2}\binom{k-1}{c}\binom{n+(k-1)-1-c}{(k-1)-1-c}\binom{m+(k-1)-1-c}{(k-1)-1-c}(-1)^c 答案累加上式结果 ×k\times k(更多…)

More
  • 2022年12月1日

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日

仍然是中规中矩的一场模拟赛。前两题正解,第三题暴力,第四题不会。

简略题解

A – 激光

考虑是否有两条及以上双向连边,若是则无解,若有一条则枚举要将哪一侧的发射器旋转到哪一方向。简单模拟即可。

B – 碰撞

这类数轴上带标号小球相撞的题目都有一个经典套路:两球相撞调转方向时,我们不认为是球本身转向,而认为两球仍然保持原方向运动,而其编号交换(更多…)

More
  • 2022年11月20日

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日

fread 专场。44 道题里面 33 道适合用快读。

简略题解

A – 远征

由题意可得 aia_i 应为目前战斗力 xx 的子集。这一迭代过程最多只有 1010 轮(ai,x1023=2101a_i,x\leq 1023=2^{10}-1),于是处理出跳转指针暴力模拟即可。

复杂度 O(1024n)\newcommand\bigO{\operatorname{O}}\bigO(1024n)

B – 传送

观察样例可以感知到答案应当只有 1,0,1,2-1,0,1,2 四种取值。

根据题意,在原图 GG 上若有一条简单路径(在迭代加边的过程中绕回原点不符和要求) xyx\rightarrow\cdots\rightarrow y,满足其长度 l1(mod2)l\equiv 1\pmod{2},那么 GG’ 上一定存在边 (x,y)(x,y)

所以若 x,yx,y 不在同一连通块中,无解;若存在满足题意的路径,答案即为 11;否则必须经某个点中转,答案为 22

(更多…)

More
  • 2022年11月16日

中规中矩的一场模拟赛。

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日

自己东拼西凑手写了一个服务端渲染 KaTeX\KaTeX(现在本站上的所有数学公式都在服务端渲染完成)的 WordPress 插件。确实有功能相近的轮子,但是跟我以前写的文章格式不相符,客户端渲染又不对我的胃口,我不想用。PHP 在 WP 上二次开发抓取页面内容,本机开另一端口让 node.js 监听,渲染好以后返回。

于是有开启、关闭异步进程的需求。原先采用 proc_open,发送 POST 请求用 file_get_contents,插件关闭时暴力 kill 服务端进程。发现 PHP 开子线程没有什么权限,所以被迫将标准输入输出重定向到 pipe。然后进一步改进成用 cURL 处理通用请求(这样就可以给服务端发送类似命令一样的东西,更优雅地检测监听状态和关闭进程),期间服务端加了不少调试信息,用 console.log 输出。然后爆炸了。

本来以为是处理 HTTP 请求的地方出锅,但最诡异的是我手动在远程控制台运行时没有任何问题,调试信息正常输出;但一旦用 PHP 自动开子线程启动,处理完最多两个请求之后就直接 defunct,重开一次爆炸一次。排查其他可能性之后怀疑是调试信息输出有问题。于是去掉若干 console.log,正常运行。

Python 中的 os.popen 函数 与 Pipe 管道的坑

More
  • 2022年11月10日

Atcoder ARC149D – Simultaneous Sugoroku

官方题解做法是线性的,在此不再赘述。

考虑对于纸片 X=1,2,,max{Xi}X=1,2,\cdots,\max\{X_i\} 分别计算答案。每次暴力枚举显然不可取,但假若我们知晓对于 XX,在 i=0,1,,Mi=0,1,\cdots,M 次操作以后纸片在数轴上的坐标 x0=X,x1,,xmx_0=X,x_1,\cdots,x_m,其中 pos\text{pos} 是最小的取到 xpos=1x_\text{pos}=-1 的位置,则对于 x0=X=X+1{x_0}’=X’=X+1

  • 如果 pos\text{pos} 不存在,则所有坐标整体向数轴正半轴平移 11 单位;
  • 否则,pos\text{pos} 就将是起始点为 XX’ 的纸片首次到达 00 点的位置,也即题目所求。所有小于 pos\text{pos} 的坐标仍向正半轴平移 11 单位;而 pos\geq \text{pos} 的坐标,由于偏移量 DiD_i 符号翻转,则有 xixi1=(xixi1){x_i}’-{x_{i-1}}’=-(x_i-x_{i-1})。依次考虑每一坐标,就会得到 xi=1xi,posim{x_i}’=1-x_i,\forall \text{pos}\leq i\leq m。 (这里认为当 xpos=0x_\text{pos}=0 时仍然继续执行操作。维护 pos\geq\text{pos} 的坐标位置是为了计算 X>XX”>X’ 的答案。)

这是可以用区间树维护的:我们想要快速求出全局非正数最大值以及首次取到该最大值的位置,同时支持全局加 11、后缀所有数符号翻转×1\times -1)。那么同时维护区间非负数最大值、正数最小值以及首次取到他们的位置,采用延迟标记更新(两种操作对于前述信息是具有结合律的,形成幺半群)即可。

时间复杂度 O(max{Xi}logM)\operatorname{O}(\max\{X_i\}\log M),常数一般。

Submission #36155560 (更多…)

More
  • 2022年11月2日