2024.11.10~2024.11.16

_Flame_ · 2024-11-10 21:06:18 · 个人记录

P8170

good one！

首先考虑二分答案 mid，然后对于每一种灌木，算出至少要减的次数 b_i=\max(0,\lfloor\dfrac{h_i+m\times d_i-mid}x\rfloor)，不难发现，每个灌木一定恰好减 b_i 次。

对于每次检查答案，直接贪心地操作当天每一个要减且可以减的灌木。这样做法的正确性是明显的，因为先操作总是优于后操作。

考虑优化，维护一个集合存储第 i 天所有可以被修剪的灌木，每修建一个就算出它下一次可以修建的时间，并在对应时间的 vector 中加入这个灌木。于是就做到了 O(mk\log V)。

2024.11.12 T1

找到一条直径，最后断开的肯定为直径两端的点。

考虑长度为 k 是另外的点是否与直径所在的集合联通，助理出树上每个点到选出的直径端点的距离的最大值，距离 k 大于这个距离时，这个点就从大块上分离成为一个新连通块，随便做就行。

看到按距离依次操作的，想想直径就会的好吧。

2024.11.12 T2

我觉得卡哈希不能算我没过。

枚举 d，再枚举前缀取的连续段数 k，那么后缀会取 \lfloor \frac{n}{d} \rfloor-k 个段，总共有 \lfloor \frac{n}{d} \rfloor 个分割方式。

用字符串哈希维护连续段，维护出每种相同段的出现次数。使用简单组合数学就能算出方案数。

2024.11.13 T2

我们考虑一个从前往后与从后往前分别贪心，即分别再每个连续段中取第一个或最后一个元素。注意到由于我们只能有一个分界点，因此我们直接枚举分界点的位置即可。

要脑子还是不行啊

奇数位反转 trick：

1. CF1615F

考虑奇数位的 01 反转，这样操作变成了交换相邻位。这样两个字符串可达当且仅当 1 个数相同，距离就是每个“第 k 个 1”的下标绝对值的差之和。容易使用组合数计算每个下标 i,j 的贡献，因为是范德蒙德卷积形式。即可做到 O(n^2+\log P)。

2. 3rd ucup Nanjing B

考虑奇数位的 01 反转，这样操作变成了删除相邻 01，显然最终一定操作成全一样（否则还能删），故长度为 01 个数之差。把 2 换成 01 使得个数差最小是容易的，时间复杂度 O(n)。

AT_abc303_g

令 f_{i,j} 表示序列里还有从第 j 个开始的 i 个物品（之所以不令 f_{i,j} 代表区间 [i,j] 是因为这样方便优化），要求此时双方都使用最优策略，最终先手减去后手的收益。我们要求的就是 f_{n,1}。

考虑转移：

• 1：拿走最左边或者最右边的物品。 f_{i,j}=\max(x_j-f_{i-1,j+1},x_{i+j-1}-f_{i-1,j}) 。

• 2：付 Z 块钱，然后拿走最左边和最右边的物品直到剩下 k 个物品。 枚举剩下 k 个物品从第几个开始，这里用 l 表示。方便起见，我们用 S(i,j) 代表从第 j 个开始的 i 个物品的价值和，可以用前缀和计算。 f_{i,j}=\max\limits_{j\le l\le j+i-k}\{S(i,j)-S(k,l)-f_{k,l}-Z\}。

总时间复杂度 O(n^3) 考虑优化。

将 2 的式子变成： f_{i,j}=S(i,j)-Z-\min\limits_{j\le l\le j+i-k}\{S(k,l)+f_{k,l}\} 我们发现，对于固定的 (i,k) 这样的 [j,j+i-k] 长度是固定的。并且对于任意的 i，只有 2 种 k。所以使用单调队列，维护 S(k,l)+f_{k,l} 的最小值即可。

时间复杂度 O(n^2)。