目录
[2019 Multi-University Training Contest 1]
训练详情
- 时间:2020-5-10 13:00~18:00
- rank:
- 完成情况：
3/6/13
题解
B Operation
补题
题意
给了一个序列，要求实现两种操作
- 给定 $l,r$ 求 $a[l..r]$ 种选出其中的一些值的最大异或和
- 在序列的后面加一个 $x$ 。
题解
开始想到线段树套线性基，发现时间和空间都爆了。后发现我们可以记录 $a[1\ldots i]$ 的线性基，添加时候则从高位到低位，尽量用当前的基去替换之前的基，这样能使所有的基离r更近。查询的时候只用位置大于 $l$ 的基。
D Vacation
solved by wxg
题意
有 $n$ 辆汽车在过绿灯，每辆车给了距离红绿灯的位置，长度和最大速度。不能超车。假设每辆车都按最优方案驾驶，问最后一辆车过红绿灯的时间
题解
可以想象，最后几辆车一定是贴在一起通过的，我们只需要枚举 $x$ ，计算最后 $x$ 俩车贴贴后通过时间，取一个最大值即可。
E Path
口胡 by fyh ，written by wxg
题意
给了一个图，去掉一个边的代价为边权，问为使 $1-n$ 的最短路变长，最小代价是多少。
题解
求出最短路径的新图，可以看出答案为最小割
F Typewriter
solved by wxg
题意
给了一个字符串，你现在要花最小代价构造出该字符串，有两种构造方法
- 花 $p$ 代价在当前字符串后添加一个字符。
- 花 $q$ 代价在当前字符串后添加一个当前字符串的字串
题解
dp ，$dp[i]$ 表示构造出长度 $i$ 的字符串的最小代价，有两种转移
- $dp[i]=dp[i-1]+p$
- $dp[i]=dp[j]+q$ , $j$ 为满足 $s[1\ldots j]$ 中存在 $s[j+1\ldots i]$ 的子串
问题是 $j$ 怎么求？
首先随着 $i$ 增加，$j$ 是单调的
我们可以构建 $s[1\ldots j]$ 的后缀自动机，当 dp 到 $i$ 时，我们在后缀自动机上匹配 $s[i]$ ,若匹配长度与 $j$ 的和大于等于 $i$ ,说明 $j$ 不用增加，反之则增加 $j$ 直到大于等于为止。
I String
补题 by hxm
题意
给定一个只包含小写字母的字符串，要求选出一个长度为$K$的子序列，满足字典序最小，同时子序列中每个字母的出现次数都在一个各自给定的范围$[L,R]$内
题解
贪心。 当前位置能选字典序小的就选字典序小的。 对于子序的第$i$个位置，从$a$开始枚举到$z$尝试将当前位置后第一个该字符放入，然后看看后面剩下的子串能不能至少满足能构成长度为$K$的合法子串。具体查看如下： 1、剩下能用字符能否至少构成长度为$K$ 2、剩下每个字符数量能否至少达到下界$L_i$，这个下界即要查看每个字符的剩余字符数是否足够，还要查看子序列剩余字符数能否提供所有的字符达到下界。
然后就完了。【很不明白比赛是怎么没调出来，，】
K Function
补题 by fyh
题意
$$ 求\sum_{i=1}^ngcd(\lfloor^3\sqrt{i}\rfloor,i),n\leq10^{21} $$
题解
很自然的对立方数进行划分， $$ \sum^n_{i=1}gcd(\lfloor^3\sqrt{i}\rfloor,i)=\sum_{i=1}^{\lfloor^3\sqrt{n}\rfloor}\sum_{j=(i-1)^3+1}^{i^3}gcd(i,j)+\sum^n_{i=\lfloor^3\sqrt{n}\rfloor^3}gcd(\lfloor^3\sqrt{n}\rfloor,i) $$ 我们发现这个式子出现了很多次$\sum_{i=1}^{n}gcd(i,a)$, $$ \sum_{i=1}^{n}gcd(i,a)=\sum_{x|a}x\sum^n_{i=1}[gcd(i,a)==x]=\sum_{x|a}x\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}[gcd(i,\frac{a}{x})==1] $$
$$ =\sum_{x|a}x\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}\sum_{k|gcd(i,\frac{a}{x})}\mu(k)=\sum_{x|a}x\sum_{k|\frac{a}{x}}\mu(k)\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}[k|i]=\sum_{x|a}x\sum_{k|\frac{a}{x}}\mu(k)\lfloor\frac{n}{xk}\rfloor $$
设$xk=d$,则上述式子等于 $$ \sum_{d|a}\lfloor\frac{n}{d}\rfloor\sum_{x|d}x\mu(\frac{d}{x})=\sum_{d|a}\lfloor\frac{n}{d}\rfloor\phi(d) $$ 故$\sum_{i=l}^{r}gcd(i,a)=\sum_{d|a}(\lfloor\frac{r}{d}\rfloor-\lfloor\frac{l-1}{d}\rfloor)\phi(d)$,对于原式右半部分的内容我们便可以通过数论分块在$O(^6\sqrt{n})$的时间内解决。
继续展开左边的式子： $$ \sum_{i=1}^{\lfloor^3\sqrt{n}\rfloor}\sum_{j=(i-1)^3+1}^{i^3}gcd(i,j)=\sum_{i=1}^{\lfloor^3\sqrt{n}\rfloor}\sum_{d|i}(\lfloor\frac{(i+1)^3-1}{d}\rfloor-\lfloor\frac{i^3-1}{d}\rfloor)\phi(d) $$ 设$xd=i$,可继续写成 $$ \sum_{d=1}^{\lfloor^3\sqrt{n}\rfloor}\phi(d)\sum_{x=1}^{\lfloor\frac{\lfloor^3\sqrt{n}\rfloor-1}{d}\rfloor}(\lfloor\frac{(xd+1)^3-1}{d}\rfloor-\lfloor\frac{(xd)^3-1}{d}\rfloor)\phi(d) $$ 左边那个整除余数是$0$，右边余数是$d-1$,再进一步展开得 $$ \sum_{d=1}^{\lfloor^3\sqrt{n}\rfloor}\phi(d)\sum_{x=1}^{\lfloor\frac{\lfloor^3\sqrt{n}\rfloor-1}{d}}3dx^2+3x+1 $$ 接下来就是平方和公式和等差数列求和，设$y=\lfloor\frac{\lfloor^3\sqrt{n}\rfloor-1}{d}\rfloor$,得： $$ \sum_{d=1}^{\lfloor^3\sqrt{n}\rfloor}\phi(d)d\frac{y(y+1)(2y+1)}{2}+\sum_{d=1}^{\lfloor^3\sqrt{n}\rfloor}\phi(d)(\frac{y(y+1)}{2}+y) $$ $y$也是一个整除形式，故依旧可以用数论分块维护，通过$O(^3\sqrt{n})$预处理出$\sum \phi(i)i$和$\sum \phi(i)$,就可以在$O(^{6}\sqrt{n})$的时间内处理每一组询问了。总时间复杂度$O(^3\sqrt{n}+^{6}\sqrt{n}*T)$
注意，读入要用__int128,但是在开数组的时候都要开int，否则会爆空间。
训练实况
0~1h fyh摸鱼了15min,hxm读E，wxg秒AD，fyh写E，疯狂CE+RE，把数据量调大之后变成WA wxg&hxm思考F B
1~2h fyh仍在尝试E hxm读M 与I,fyh放弃了E，wxg开始写F
2~3h fyh读K，L ,与hxm交流I,澄清题意后口糊出I做法，wxgAF,hxm开始写M并写完，但是发现误解题意，后放弃，wxg打算重新写E
3~4h wxgAE ,fyh推K无果，开始写I
4~5h wxg,hxm讨论B，口糊出来，没有写，fyh&hxm调I无果
结果：wxg全场最佳
训练总结
总结&反思：模板的整理是个大问题 ，本次用的全部是高中时候的板子，fyh调板子题调了一年，问题出在哪最后也不知道（重写大法好）I没写出来是因为代码能力差+脑子持续掉线+细节没想清楚
改进
- 一个题至少要两个读，之后再核对题目大意是否一致，否则白给
- 板子的整理
