Difference between revisions of "2019 Multi-University,HDU Day 1"
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
Line 122: | Line 122: | ||
Upsolved by Kilo_5723. (-19) | Upsolved by Kilo_5723. (-19) | ||
+ | |||
+ | 题意:给出 $n$ 个限制条件 $a_i\cdot x+b_i \cdot y+2>0$ 或 $<0$,求是否存在解。 | ||
+ | |||
+ | 题解:每个限制条件都相当于一个半平面,半平面交模板题。 |
Revision as of 13:05, 30 July 2019
Problem A
Upsolved by Xiejiadong.
题意:给长度为 $N$ 的空格染色,有一些限制要求一些区间中出现的颜色数量,求方案数。
题意:谁能想到,$O(T\cdot n^4)$ 的复杂度稍微优化一下卡卡常就能进去。
用 $f[i][j][k][l]$ 分别表示四种颜色出现最后的位置,已知这四个信息,我们只需要查询限制的右端点是 $max\{i,j,k,l\}$ 的是否满足要求就好了。
这样开数组是会 MLE 的,我们要强行滚动一下,不妨假设 $i>j>k>l$ 即可,用维度 $i$ 滚动。
Problem B
Upsolved by Weaver_zhu. (-1)
题意:求区间$(l,r)$的任意取数是的异或和最大。
题解:考虑线性基,但是有些改动。考虑维护前缀线性基,维护基内所有数,尽量保留靠右边的基就行了。实现方法就是记录这个基的位置,把左边的换出来。
Problem C
Upsolved by Xiejiadong.
题意:平面上的一些地方有牛奶,喝牛奶需要花费一定的时间,每次可以左右走,或者在每行中间向下走,求最少的时间喝 $1,2,\cdots k$ 盒牛奶。
题解:把牛奶先按照 $x$ 离散。
显然对于每一行,只能从上面的行过来,于是我们可以针对每一行单独处理。
对于每一行分别处理左边和右边喝 $x$ 盒牛奶所需要的最少时间,把两部分合并起来得到在这一行喝 $x$ 盒牛奶并回/不回到中点(可以在任意行结束)所需要的最少时间。
然后再同前面行处理出来的信息合并,得到走到当前行喝 $x$ 盒牛奶所需要的最少时间。
需要特判第一行,因为是从 $(1,1)$ 出发的。
思路不是很难。写起来是真的恶心。
Problem D
Solved by Xiejiadong. 01:55:24 (+)
题意:给出每个小车距离终点的距离、车的长度和车的最快速度。求最后一辆车头到达终点的最少时间。要求本来排在后面的车不能冲到前面去。
题解:二分答案。考虑在时间 $mid$ 的时候,车最多能到达的地方。
显然第一辆车全速开,如果后面的车在时间 $mid$ 的时候冲到了前面的车的后面,说明在某个时刻这辆车已经追上了前车,那么这辆车肯定和前辆车连续排布。
如此考虑最后一辆车是否超过了终点即可。
Problem E
Solved by Kilo_5723. 01:45:39 (+1)
题意:求删除最小长度和的边,使得删边后的图最短路长度变大。
题解:最短路建最短路网络,求网络流的最小割。
Problem F
Upsolved by Xiejiadong. (-1)
开场改题目的操作也太秀了。 KMP 都写完交了,反馈 WA ,突然看到上面飘过一行红字,心态崩了。
题意:要输出目标串,有两个选择,可以花费 $p$ 在字符串末尾输出任意字符,或者花费 $q$ 复制一段已经输出的子串到末尾,求输出目标串的最小代价。
题解:考虑如果以 $i$ 结尾字符串可以通过复制得到,那么一定存在一个或者多个 $j$ 满足 $s[1\cdots j]$ 中存在子串 $s[j+1\cdots i]$ ,显然,我们需要的是这样的 $j$ 中最小的来转移,我们令这样的 $j=g[i]$。
于是可以得到 dp 方程就是两部分构成, $dp[i]=min\{dp[i-1]+p,dp[g[i]]+q\}$ 。
问题关键就是怎么快速的得到 $g[i]$ ,考虑用 SAM 来维护, SAM 的维护都是通过增量构造的。
假设当前已经得到了 $s[1\cdots j]$ 中存在子串 $s[j+1\cdots i]$ ,现在新加入字符 $s[i+1]$ :
- 如果从当前状态直接能够转移到 $s[i+1]$ ,直接转移即可,此时 $g[i+1]=g[i]=j$ ;
- 如果不能直接转移,也就是 $s[1\cdots j]$ 中不存在子串 $s[j+1\cdots i+1]$ ,我们需要从字符 $s[j+1]$ 开始不断地向 SAM 插入字符,以获得子串 $s[j+1\cdots i+1]$ ,每次插入新字符以后,状态通过 link 跳到当前状态,判断能够转移即可。
Problem G
Unsolved.
Problem H
Solved by Xiejiadong. 04:15:04 (+1)
题意:求长度为 $K$ 的 $26$ 个字母出现次数在规定的区间内的字典序最小的子序列。
题解:贪心地按位确定。
按照字典序判断这一位是否可以放,如果可以放一定放最前面的一个字母。
判断的方法是,不能超过这个字母出现次数的上限,在这个字母之后的其他字母数量能够满足剩余需要满足的数量(这部分可以先预处理)。
Problem I
Unsolved.
Problem J
Unsolved.
Problem K
Upsolved by Weaver_zhu.
题意:求 $\sum\limits_{i=1}^{n}gcd(i, i^{\frac{1}{3}}) n \le 10^{21}$
题解:引理:$\sum\limits_{i=1}^{n}{gcd(i, a)} = \sum\limits_{d|a}d\sum\limits_{i=1}^{n}{[gcd(i,a)==d]}=\sum\limits_{d|a}d\sum\limits_{i=1}^{n}[gcd(i/d, a/d)==1]=\sum\limits_{d|a}d\sum\limits_{i=1}^{n}u * 1(gcd(i/d,a/d))=\sum\limits_{d|a}\sum\limits_{i}\sum_{t|gcd(i/d, a/d)}\mu(t) 拿T=td替换,有d|T,=\sum\limits_d\sum\limits_{i}\sum_{T|gcd(a,d)}d\cdot \mu(T/d)=\sum\limits_{T|a}\frac{n}{T}\sum\limits_{d|T}d\mu{(\frac{T}{d})} = \sum\limits_{T|a}\frac{n}{T}\phi(T)$, 现已加入模板豪华午餐
原式=$r=n^{1/3}, \sum\limits_{i=1}^{r}\sum\limits_{j=i^3}^{(i+1)^3-1}gcd(i,j) + \sum\limits_{i=r^3}^{n}gcd(r,i)$,全部套用引理,再加上数论分块,然后就出来了。注意 $n$ 太小可能 $r=0$ ,因此 $n \le 10$ 情况暴力跑出来就行了
Problem L
Upsolved by Kilo_5723.
题意:长度为 $n$ 的数组 $\{a_n\}$,$m$ 次操作,每次操作将 $a_i$ 从替换成 $\sum a_j (j<i,i-j {\rm mod} k = 0,k \in \{1,2,3\})$,求最后的 $\{a_n\}$。
题解:可以证明改变操作顺序不会影响最后的结果。而同种类型的操作对于同种模数的元素可以合并成为卷积的形式,任意模数 FFT 模板就能过。
Problem M
Upsolved by Kilo_5723. (-19)
题意:给出 $n$ 个限制条件 $a_i\cdot x+b_i \cdot y+2>0$ 或 $<0$,求是否存在解。
题解:每个限制条件都相当于一个半平面,半平面交模板题。