hdu2019多校1

2019 Multi-University Training Contest 1

Problem B Operation

题意

有一个序列 $a$，刚开始长度为 $n$。一共 $m$ 次操作，共两种操作：

1，询问在区间 $[l,r]$ 中选一些元素使得异或和最大。输出异或和。

2，在该序列结尾添加一个数。

$n,m\leq 5\times 10^5,0\leq a_i < 2^{30}$

题解

一个很显然的做法是线段树维护线性基合并，时间 $O(n\log^2w\log n)$，其中 $w$ 为 $a_i$ 的位数。但是显然过不去。

因为只是从结尾加一个数，考虑维护前缀的线性基。

但查询的时候还需要知道线性基里的数是否满足它的下标比 $l-1$ 大。

这时候可以在线性基里记录第 $i$ 位的下标 $p_i$。

那么插入的时候贪心，如果遇到一个下标比它小的数，那么把 $p_i$ 和值替换，然后拿原来的数继续往下贪心即可。

询问的时候判断一下 $l\leq p_i$ 就可以了。

时间复杂度 $O(n\log w)$。

Problem D Vacation

题意

$n+1$ 辆车，每辆车有长度 $l$，车头到终点距离 $s$，最大速度 $v$。模拟整个过程，一辆车无法超过另一辆车，接触后只能以前面的车的速度行驶。问第 $0$ 辆车的车头通过终点的时间。

$n\leq 10^5,l_i,s_i,v_i\leq 10^9,s_i\geq s_{i+1}+l_{i+1}$

题解

最后 0 车通过终点的时候肯定是与前面一堆车一起的，枚举最前面的车是哪一辆，计算出通过时间，取最大值即为答案。

时间复杂度 $O(n)$

Problem E Path

题意

一个有向图，问需要割哪些边，使得 $1$ 到 $n$ 的最短路变大。一个方案费用为边权之和。输出最小费用。

题解

建出最短路图，然后跑最小割即可。

Problem F Typewriter

题意

给一个字符串 $s$，有两种操作：

1，花费 $p$ 在当前字符串后添加一个字母。

2，花费 $q$ 在当前字符串后添加一个当前字符串的子串。

当前字符串刚开始为空串，求使得变为 $s$ 的最少花费。

$n\leq 2\times 10^5$

题解

容易想到 dp，设 $f_i$ 表示匹配到第 $i$ 位时的答案。

设 $j$ 为使得 $s[1,j]\in s[j+1,i]$ 的最大的 $j$。

对于每个 $i$ 求出了 $j$ 就可以 dp 了。

发现当 $i$ 增大时 $j$ 不减。

用 SAM 维护 $s[1,j]$ ，若 $s[j+1,i]$ 匹配不了，则把 $s_{j+1}$ 扔进 SAM 里，维护一下 $s[j+1,i]$ 在 SAM 中的位置以及是否匹配。

匹配位置最多往回跳 $n$ 次，最多往前加 $n$ 次。

时间复杂度 $O(n)$

Problem I String

题意

给一个字符串 $s$，构造一个字典序最小的，第 $i$ 个小写字母出现次数在 $[l_i,r_i]$ 范围内的子序列。

$n\leq 10^5$

题解

贪心，顺次考虑当前位能填的字母，从小到大枚举，判断是否可行的办法是先用序列自动机找到最靠前的那一位，然后记录每个字母是否出现的后缀和，再判断一下就可以了。

时间复杂度 $O(|S|\sum)$，其中 $\sum$ 为字符集大小。

Problem L Sequence

题意

一个长度为 $n$ 的序列 $a$，有 $m$ 次操作，每次操作一个 $k(k\in [1,3])$ ，则新的序列 $a$ 满足 $a’{i}=\sum{j=i-kx}a_j(k\geq 0)$

求出 $m$ 次操作后的序列，模 $998244353$。

$n\leq 10^5,m\leq 10^6$

题解

设该序列生成函数为 $A(x)=\sum_{i=1}^{n}a_ix^i$

那么一次操作相当于给 $A(x)$ 乘上一个 $\sum_{i=0}x^{ik}$

因此最后答案与操作顺序无关。

很显然的做法是多项式快速幂，比较卡常，好像过不了（反正当时没有过）。

那么考虑 $(\sum_{i=0}x^{ik})^m$ 等于什么。

由于 $(\sum_{i=0}x^i)^m=\sum_{i=0}\binom{m-1+i}{m-1}x^i$

那么 $(\sum_{i=0}x^{ik})^m=\sum_{i=0}\binom{m-1+i}{m-1}x^{ik}$

这样对于每个 $k$ 就只需要做一次卷积就可以了。

时间复杂度 $O(n\log n)$