26.9.2 比赛记录

更新于 2026年9月26日约 3 分钟阅读

都是 DP。

A P9980

有一篇题解说的话比较有道理,这里稍作改动抄下来了:

不难发现,我们如果要知道 ii 和 jj 有没有连边,其实等价于 ii 到 jj 的路径数(不包括直飞航班)的奇偶是否与 ii 到 jj 的路径数(包括直飞航班)的奇偶相等。

知道这个后,我们就可以直接枚举在 ii 到 jj 的路径中的第一个非 ii 的点,令其为 kk,则 i<k<ji<k<j,则我们知道 ii 与 kk 是否相连,又知道 kk 到 jj 的路径数量的奇偶,则我们可以知道,以 kk 为第一个非 ii 点的 ii 到 jj 的路径的数量的奇偶。

以上就是 DP 转移的核心思路。

for(int k=i+1;k<j;k++)
  sum^=f[i][k]&c[k][j];
f[i][j]=c[i][j]^sum;

B P9187

场切了。

求一个二进制数和已知数的最大差异(其实叫汉明距离),等价于求其取反后的最小差异。

设 fif_i 表示 ii 和已知数的最小差异。如果 ii 已知,就是 00。

设 jj 是 ii 改动一个 bit,转移就这样写:fj=min⁡(fj,fi+1) f_j=\min(f_j,f_i+1)。

一个数可以由 CC 个数转移过来,并且最多转移 CC 次(不然两个 CC 位二进制数之间的差异就超过 CC 了,这显然是不可能的)。

时间复杂度 O(2C×C2)O(2^C\times C^2),可以通过。

C P8903

背包,当时背包模板忘了所以没打。

首先,所有牛可以分成只用冰激凌收购、冰淇淋和哞尼混合收购、只用哞尼收购这三大类。一个背包是无法解决的,那就用两个。

定义 f1,i,jf_{1,i,j} 为只用冰淇淋的最大欢迎度,f2,i,jf_{2,i,j} 为冰激凌和哞尼都用的最大欢迎度。

转移方程:

  • 不选择购买第 ii 头牛
    f1,i,j=f1,i−1,jf_{1,i,j}=f_{1,i-1,j}
    f2,i,j=f2,i−1,jf_{2,i,j}=f_{2,i-1,j}
  • 全部使用冰激凌
    f1,i,j=f1,i−1,j−cx+Pif_{1,i,j}=f_{1,i-1,j-cx}+P_i
  • 全部使用哞尼
    f2,i,j=f2,i−1,j−x+Pif_{2,i,j}=f_{2,i-1,j-x}+P_i
  • 冰激凌和哞尼都用(两部分之间的转移)
    f2,i,c−k=f1,i−1,b−kx+Pi(k≤c,kx≤b)f_{2,i,c-k}=f_{1,i-1,b-kx}+P_i(k\le c,kx\le b)

D P9981

这题很显然,是 DAG 上 DP。本来它应该没有青这个难度的,但是它给每条道路加上了一个标签,并要求字典序最小。

我赛时做法假了,是在多条最长的路径中,选路径起始节点 tag 最小的那条进行转移。这回遇到一个问题,起始节点最小,不代表后面最小,在最劣的情况要把路径的每一个节点都比较一下才能知道它字典序是否最小。

这是 35pts 的做法,赛后我加上了不仅要判断起始节点标签最小,还要判断标签和最小,直接就 95pts 了!

然后特判出错的一个数据(就其中一个数据有错,说明数据太水了),就 AC 了。并且这个做法不带 log⁡\log,我没怎么卡常就轻松拿下最优解第三!

下面讲正解做法,其实判断字典序不一定要逐节点判断,我们可以先用哈希加二分找出它的最长公共前缀,然后判断字典序。复杂度带一个 log⁡\log。

Vector Log · 算法竞赛学习笔记

Built with Nuxt UI & Nuxt MDC