2021HDU暑期多校第三场

排名	当场过题数	至今过题数	总题数
66/750	5	11	12

A

upsolved by JJLeo

题意

给出一棵 $n$ 个节点的树，每个节点有一个商品，价格为 $p_i$。

$q$ 次询问，每次给定树上一条路径，初始携带 $m_i$ 元，走到一个点如果钱就够就买一个商品，如果不够就不买，问最后剩多少钱。

($1\le n,q\le {10}^5$，$1\le p_i,m_i\le {10}^9$)

题解

首先将所有询问离线，并拆分成从下往上走 (到 lca) 和从上往下走两部分。

考虑先全部处理出每个询问走到 lca 时还剩多少钱，再全部处理出每个询问从 lca 走到终点还剩多少钱，下面以向上走为例：

重链剖分，将每个询问分割为 $O(\log n)$ 段重链，标记每段开始和结束的位置。逆序枚举 dfn 序，到了一个点先将这个点开始的所有询问加入数据结构，然后将数据结构中所有值 $\ge m_i$ 的全部减少 $m_i$，然后将这个点结束的所有询问移出数据结构，由于重链的 dfn 序是连续的，这样做可以保证正确性。

考虑使用 FHQ-Treap，所有询问按照其值排序，对于一次操作：

• 对于所有 $<m_i$ 的元素，不需要进行操作。

• 对于所有 $\ge m_i$ 的元素，分裂后不能直接打标记，因为合并时要保证其中一颗元素都小于另一颗，减去 $m_i$ 后可能会小于之前 $<m_i$ 的元素，考虑如下的 trick：

• 对于 $[m_i,2m_i)$ 的元素，将其分裂出来暴力一个个把权值减了再插回去，这样做一次会使得其值减少一半，因此对于每个询问至多会被执行 $O(\log p_i)$ 次。
• 对于 $\ge 2m_i$ 的元素，其减去 $m_i$ 也不会小于之前 $<m_i$ 的元素，直接打标记即可。

取出一个元素可以通过记录每个节点的父亲得到对应点的排名，从而使用对于 size 的分裂将其取出。

向下走和向上走是完全类似的，只不过初值变了，且改为正序枚举 dfn 序。总时间复杂度为 $O(n{\log }^{2}n)$。

B

upsolved by 2sozx JJLeo

题意

给定一颗 $n$ 个节点的树，一共有 $m$ 个人，每个人固定一个起点，有三个旅行方案，每个方案有各自的终点和各自的代价，问是否可以让每人选一个方案使得所有人经过的路径不相交，如果可以最小化代价之和。($1\le n\le 2\times {10}^5$，$1\le m\le {10}^5$)

题解

赛时做法：

忘了。

可惜最后没时间了，没写完，经典赛后过题。

C

solved by JJLeo

题意

给定两个串 $s,t$，问 $t$ 和多少个 $s$ 的子串至多有 $k$ 个不同的字符，对 $k=0,1,2,\dots ,|t|$ 给出答案。

字符集为 0 到 9，同时还有一个通配符。($1\le |t|\le |s|\le 2\times {10}^5$)

题解

字符集很小，很经典的 FFT 套路题，枚举每个字符，相应位置设为 $1$，否则是 $0$，卷起来即可得到每个位置的匹配数量。

对于通配符，也将其设为 $1$，但是两个通配符匹配会被算 $10$ 遍，因此再单独对通配符做一次匹配，也就是只将通配符的位置设为 $1$，减去 $9$ 倍的这个值即可。

D

solved by 2sozx Bazoka13 JJLeo

题意

$\sum$ 签到，虽然是签到，但是 HDU 不能有快读和 fread()！

题解

因为这题罚时裂了，离谱 HDU $\sum$ 好吧。

E

upsolved by JJLeo

题意

平面有向图，$1$ 能到所有点，所有点都能到 $n$，每个点有一个权值，选一些点最大化权值之和，要求所选点任意两个点都不可达，多解要求所选点的字典序最小。($1\le n\le {10}^5$)

题解

需要利用平面图的性质，从 $1$ 开始分别顺时针和逆时针 dfs 所有点，记每个点的出栈序为 $a_i,b_i$，则 $i$ 可以到达 $j$ 当且仅当 $a_i>a_j\wedge b_i>b_j$。

充分性显然，$i$ 如果可以到达 $j$ 那么不管如何 dfs，前者出栈序必然大于后者。

必要性则考虑其逆否命题，如果 $i$ 不可达 $j$，要么 $j$ 可达 $i$，那么 $a_i<a_j\wedge b_i<b_j$；要么 $j$ 不可达 $i$，如果 $a_i>a_j$ 那么把遍历顺序反过来即 $b_i<b_j$，反之亦然。从而如果 $i$ 不可达 $j$ 则 $a_i>a_j\wedge b_i>b_j$ 不成立。

因此将点按 $a_i$ 排序后相当于求权值最大的 $b_i$ 降序子序列，如果不要求字典序最小直接树状数组 $O(n\log n)$ 就可以求。每个选点方案等价于一个 $01$ 串，因此可以用动态开点线段树存储，每次只会新增一个点，比较时在线段树上二分，找到第一个不同的位置即可得到大小关系，因此可以在 $O(n{\log }^{2}n)$ 的复杂度内完成。

一个小 trick 是，相比去年 claris 那场 hdu 多校类似用动态开点线段树存方案的题，这里不需要维护哈希值，因为对于 $01$ 串每个位置，最多只添加一次，因此两个节点不同等价于它们对应的串不同。

F

upsolved by JJLeo

题意

两侧各 $n$ 个点，$n^2-m$ 条边，左侧点权值为 $a_i$，右侧点权值为 $b_j$，一条边的边权为 $a_i+b_j$，求匹配数为 $1,2,\dots ,n$ 的最大权匹配。($1\le n\le 4000$，$1\le m\le 10000$)

题解

考虑模拟费用流，每次增广一个单位流量，将左侧点按权值从大到小排序后，依次选择能从源点到达的 (也就是还没有被匹配的) 进行 bfs，对右侧每个还能到达汇点的点记录最先被哪个左侧哪个点能到达 (不是多源 bfs，遍历完一个起点再加入下一个起点，每个点只遍历一次)，这样就可以得到目前这个点可以匹配的最大权值，遍历所有右侧点取最大的权值将其作为这次的增广路，将权值加入答案，同时模拟网络流改变增广路上的容量，并为其增加反向边。

需要注意的是这题是以补图的形式给出的，需要使用补图 bfs：

将目前没经过的点存入链表，每次遍历链表尝试从当前点到达，如果不存在这条边则跳过，否则将该点从链表中删除并到达该点。

因为只有 $O(m)$ 条边没有，所以跳过的时间复杂度为 $O(m)$，总时间复杂度为 $O(n+m)$。

需要注意本题中链表中只能存放右边的点，右边到左边的边可以通过当前的匹配情况得知，如果加入复杂度就不对了。一共增广 $O(n)$ 次，每次时间复杂度为 $O(n+m)$，总时间复杂度为 $O(n^2+nm)$。

H

upsolved by

题意

题解

I

solved by 2sozx JJLeo

题意

$n\times n$ 的格子图，从左上走到右下，只能往下或往右，每个格子有两个权值 $a_{i,j}$ 和 $b_{i,j}$，最终权值为经过所有格子的 $(\sum a_{i,j})(\sum b_{i,j})$，最大化这个权值，保证数据随机。($1\le n\le 100$)

题解

随机乱搞，每个状态记录约 $100$ 个当前 $(\sum a_{i,j})(\sum b_{i,j})$ 最大的状态就可以通过了。

J

upsolved by JJLeo

题意

$n$ 个点 $m$ 条边的无向图，每条边有两个权值 $c_i$ 和 $d_i$，分别为正常权值和折扣权值，问恰好使用 $0,1,\dots ,n-1$ 条折扣权值的最小生成树的权值和。($2\le n\le 1000$，$n-1\le m\le 2\times {10}^5$，$1\le d_i\le c_i\le 1000$)

题解

拆成 $2m$ 条黑白边，显然原本的一条边拆成的两条边不会同时被选，因此问题等价于恰好选 $k$ 条黑边的最小生成树，这是 wqs 二分的入门题。

注意边权很小，这意味着这个下凸函数相邻两点的斜率绝对值也不会很大，可以直接将斜率 $[-1000,0]$ 能切到横坐标最小 / 最大的点算出来，最小就优先选白边，最大就优先选黑边，设为 $[l,r]$，那最终选 $[l,r]$ 条黑边的答案就可以得到了，显然最终遍历所有斜率那么可以覆盖横坐标为 $[0,n-1]$ 的所有整点。

设 $c=1000$，这样需要算 $c$ 次 $O(m\log m)$，可以先各自对黑边白边做一次最小生成树，那么只有这些边才可能被用上，可以将边数减少到 $O(n)$。总时间复杂度为 $O(cn\log n+m\log m)$。

L

upsolved by JJLeo

题意

$n$ 个数 $a_1,a_2,\dots ,a_n$，相邻数不能同时选，下标之差为 $k$ 的数不能同时选，且至少选一个数。一个方案的权值是所有选了数的乘积，求所有方案权值的和。($2\le k<n\le 300$)

题解

考虑两个算法：

• 算法一：直接记录前 $k$ 个元素的选择情况，从左往右扫一遍，时间复杂度为 $O\left(n{2}^k\right)$。
• 算法二：将序列变成一个 $k\times \lceil {\displaystyle \frac{n}{k}}\rceil$ 的矩阵，第 $i$ 个位置在 $(imodk,\lfloor {\displaystyle \frac{i}{k}}\rfloor )$ 处 (0-indexed)，强行钦定最后一列从下往上 $k\lceil {\displaystyle \frac{n}{k}}\rceil -k$ 个位置不能放数。那么这个矩阵上下左右四个位置不能同时放数，同时最后一行第 $i$ 列和第一行第 $i+1$ 列也不能同时放数，因此记录第一行的摆放情况以及当前的轮廓线 (第一次知道这个 dp 原来这个也叫轮廓线)。具体来说就是假设 dp 到第 $i$ 行第 $j$ 列，那么状态就是第 $i$ 行前 $j$ 个位置是否放数以及第 $i-1$ 行前 $j$ 个位置是否放数，最后利用最后一行和第一行的状态判断是否合法，时间复杂度为 $O\left(n{2}^{\frac{2n}{k}}\right)$。

利用根号分治，时间复杂度可以达到 $O\left(n{2}^{\sqrt{2n}}\right)$，但还是太慢了，注意到所有的二进制状态一定是独立集，数量是斐波那契数列，约为 $O\left({1.618}^k\right)$，因此 dfs 出所有状态即可将复杂度降为 $O\left(n{1.618}^{\sqrt{2n}}\right)$。

记录

0h：开始分题，看K签到ZYF冲，然后CSK看G签到留着给ZYF写，写完了有人过D了，MJX、CSK看着也是道sb题，CSK冲D，T了一发，然后开始了罪恶的垃圾HDU测评机器。

1h：ZYF去冲C，秒过，继续卡死D，把STL全换了，加上快速读入还是T，把排序优化还是T，加上fread后WA了，觉得是算法有点问题。

2h：想了想I，说是数据随机，MJX想就乱搞一下大概就行，喂给ZYF，ZYF WA了一发换了个乱搞方法就过了，然后过了。翻了翻Clarification。

换成scanf过了，HDU还不支持fread，西内！

3h：想了那个最小生成树和类似费用流的那题，没想出来，挂机一小时。

4h：想了个B的解法，看起来很对，ZYF冲了，没冲完，不知道哪有问题，寄了寄了。

总结

• MJX：B最后破案了，当时问ZYF那个查询是单点的么，其实不是，下次不清楚的一定要问好，最后时刻太紧张了很容易写错。

Dirt

D(+10)：HDU是逆天
I(+1)：换了个乱搞算法，没啥办法