2015 Multi-University Training Contest 8 solutions BY 绍兴一中

##[1001.Travel with candy](http://acm.hdu.edu.cn/showproblem.php?pid=5380) 每时每刻油箱都装满,使用退油的办法,维护所有不同价格的退油油量。路上把推油少的油消耗掉。卖油相当于所有价格取max,买油时可以先把贵的退光然后买满。可以用双端队列维护。 ##[1002.The sum of gcd](http://acm.hdu.edu.cn/showproblem.php?pid=5381) 可以发现,从一个$i$开始向后,不同的区间$gcd$只有$log(a_i)$种 于是我们先把询问都存下来,然后从大到小枚举$l$,用树状数组维护即可 ##[1003.GCD?LCM!](http://acm.hdu.edu.cn/showproblem.php?pid=5382) $G(n) = \sum_{d|n}[~gcd(d,\frac{n}{d})=1~] $ $T(n) = \sum_{i=1}^n\sum_{j=1}^n[~lcm(i,j)+gcd(i,j)=n~] $ $ = \sum_{d=1}^n\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}[~ijd+d=n~][~gcd(i,j)=1~] $ $ = \sum_{d=1}^n\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}[~d(ij+1)=n~][~gcd(i,j)=1~] $ $ = \sum_{d|n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}[~ij=\frac{n}{d}-1~][~gcd(i,j)=1~] $ $ = \sum_{d|n}G(\frac{n}{d}-1) $ $F(n) = \sum_{i=1}^n\sum_{j=1}^n[~lcm(i,j)+gcd(i,j)\geq n~] $ $ = \sum_{i=1}^n\sum_{j=1}^n[~lcm(i,j)+gcd(i,j)\geq n-1~]-\sum_{i=1}^n\sum_{j=1}^n[~lcm(i,j)+gcd(i,j)=n-1~] $ $ = \sum_{i=1}^n\sum_{j=1}^n[~lcm(i,j)+gcd(i,j)\geq n-1~]-T(n-1) $ $= \sum_{i=1}^{n-1}\sum_{j=1}^{n-1}[~lcm(i,j)+gcd(i,j)\geq n-1~]+(2n-1)-T(n-1) $ $ = F(n-1)+(2n-1)-T(n-1) $ $S(n) = \sum_{i=1}^nF(i)$ 容易发现$G(n)$是积性函数,且对于质数$p$,$G(p^k)=2$,那么可以$O(n)$计算$1\sim n$的$G(n)$。 考虑枚举最大公约数$d$,再枚举$k$,计算$G(k-1)$对$T(kd)$的贡献,复杂度$O(n\ln n)$。 得到$T(n)$后,再$O(n)$计算$F(n)$,最后$O(n)$计算$S(n)$即可。 ##[1004.Yu-Gi-Oh!](http://acm.hdu.edu.cn/showproblem.php?pid=5383) 可以建立二分图,把Tuner Monster视为二分图左侧的点,Non-Tunner Monster视为二分图右侧的点。 计算出两两能配成的最高攻击力后连边,利用费用流计算。 建图:点规模$O(n)$,边规模$O(n^2)$ ##[1005.Danganronpa](http://acm.hdu.edu.cn/showproblem.php?pid=5384) 一个串的所有子串可以表示为它所有前缀的后缀。 把所有$A_i$、$B_j$放在一起建立AC自动机,再对AC自动机建fail树。在fail树上,$B_j$如果在$A_i$某个前缀的祖先节点中出现,那么就会产生$1$的贡献。 可以对fail树进行dfs遍历,可以计算出每个节点的祖先中有多少$B_j$。 时间复杂度$O(\sum|A_i|+\sum|B_j|)$ ##[1006.The path](http://acm.hdu.edu.cn/showproblem.php?pid=5385) 如果我们知道每个点的$dis$值和最短路径树的话,方案是很容易构造的 我们可以采取贪心做法,一开始将$1$号点作为最短路径树的根,然后左边从$2$开始,右边从$n$开始,只要之前加入的点有边连向他们就加入 这样一个点加入的时间就是他的$dis$值,最短路径树上的父亲也可以确定,于是输出时非树边长度为$n$,树边长度为两个端点$dis$之差 ##[1007.Cover](http://acm.hdu.edu.cn/showproblem.php?pid=5386) 水题,我们只要每次找一行或一列颜色除了$0$都相同的,然后如果有对应的操作,就把这行这列都赋值成$0$即可 其实初始矩阵并没有什么卵用 稍微优化下复杂度是$O(n^2)$的,但是为了简易些范围开到了$100$ ##[1008.Clockr](http://acm.hdu.edu.cn/showproblem.php?pid=5387) 我都不知道该如何写题解了。。。 根据时间算出每根针离原点的角度大小,然后减一下即可,要注意处理钝角. [1009.Geometer's Sketchpad](http://acm.hdu.edu.cn/showproblem.php?pid=5388) 简要题意就是,给出三维空间中的$N$个点,要求支持区间平移、缩放、旋转,每次询问点的坐标、区间内相邻点的距离和。 本题的标准算法分为两部分: 【第一部分】 首先这三种变换都是线性的,一个点做变换可以表示成一个向量与矩阵的乘积。如,把点$(x,y,z)$表示成一个$1 \times 4$的向量$\left[\begin{array}{cccc}x & y & z & 1\\ \end{array}\right]$,一个平移变换$(a,b,c)$可以表示成一个$4 \times 4$的矩阵$ \left[ \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ a & b & c & 1 \\ \end{array} \right] $则点平移后的向量即它们的乘积。 现在假设对每种变换都求出了它们对应的矩阵(求法见第二部分),如何维护每个点的坐标和相邻点的距离和。我们维护每个点被乘上的矩阵的积,于是问题就变成了区间修改、单点询问,直接套用线段树等数据结构即可。 然后是维护区间内相邻点的距离和。记$l[i]=|P_iP_{i+1}|$。可以发现,平移、旋转变换不会改变区间内部的信息,即$l[L] \sim l[R-1]$都不变,只有$l[L-1],l[R]$会变;对于缩放变换,也只是把$l[L] \sim l[R-1]$都乘上了$k$。所以问题就变成了区间修改、区间询问,再套一棵线段树等数据结构即可。     【第二部分】 现在考虑如何求出三种变换对应的矩阵。 平移矩阵比较简单。对于一个平移变换$(a,b,c)$,它对应的矩阵$ Trans(a,b,c)=\left[ \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ a & b & c & 1 \\ \end{array} \right] $ 然后是缩放变换。对于一个缩放变换$(a,b,c,k)$,可以看成先把中心点平移到原点,再做缩放变换,最后再移回来。于是它对应的矩阵 $Scale(a,b,c,k)=Trans(-a,-b,-c)\begin{bmatrix} k & 0 & 0 & 0 \\ 0 & k & 0 & 0 \\ 0 & 0 & k & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}Tracs(a,b,c)$ $=\begin{bmatrix} k & 0 & 0 & 0 \\ 0 & k & 0 & 0 \\ 0 & 0 & k & 0 \\ (1-k)a & (1-k)b & (1-k)c & 1 \\ \end{bmatrix}$ 最后是旋转变换。先考虑每次绕坐标轴旋转。根据平面上的旋转公式,易得$ Rotate_x(\theta)=\left[ \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & \cos\theta & \sin\theta & 0 \\ 0 & -\sin\theta & \cos\theta & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right]$ $ Rotate_y(\theta)=\left[ \begin{array}{cccc} \cos\theta & 0 & -\sin\theta & 0 \\ 0 & 1 & 0 & 0 \\ \sin\theta & 0 & \cos\theta & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right]$$ $$ Rotate_z(\theta)=\left[ \begin{array}{cccc} \cos\theta & \sin\theta & 0 & 0 \\ -\sin\theta & \cos\theta & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right] $对于一个普通的旋转变换$(a,b,c,a',b',c',\theta)$ (为了方便,这里假设方向向量$(a',b',c')$为单位向量,即$a'\ ^2+b'\ ^2+c'\ ^2=1$),基本思路是,首先把点($a,b,c$)平移到原点,再把旋转轴分别绕$x$轴、$y$轴旋转合适的角度后与$z$轴重合,然后绕$z$轴旋转$\theta$角,最后再转回来、移回来。 1. 把点$(a,b,c)$平移到原点。即乘上一个矩阵$ T=Trans(-a,-b,-c)=\left[ \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ -a & -b & -c & 1 \\ \end{array} \right]$ 2. 把旋转轴绕$x$轴旋转合适的角度,使之与$xOz$平面重合。令点$P=(a',b',c')$,旋转的角度$\alpha$即$OP$在$yOz$平面上的投影与$z$轴的夹角,令$u=\sqrt{b'\ ^2+c'\ ^2}$,则$ \cos\alpha=\frac{c'}{u} \quad \sin\alpha=\frac{b'}{u}$ $ R_x=Rotate_x(\alpha)=\left[ \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & \cos\alpha & \sin\alpha & 0 \\ 0 & -\sin\alpha & \cos\alpha & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right]=\left[ \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & \frac{c'}{u} & \frac{b'}{u} & 0 \\ 0 & -\frac{b'}{u} & \frac{c'}{u} & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right]$ 3. 把已在$xOz$平面内的旋转轴绕$y$轴旋转合适的角度,使之与$z$轴重合。当前的$P$点坐标为$(a',0,u)$,旋转的角度$\beta$即$OP$与$z$轴的夹角,但现在变成了顺时针,所以要取负号。令$v=\sqrt{a'\ ^2+u^2}=\sqrt{a'\ ^2+b'\ ^2+c'\ ^2}=1$,则$ \cos\beta=\frac{u}{v}=u \quad \sin\beta=\frac{a'}{u}=a'$ $ R_y=Rotate_y(-\beta)=\left[ \begin{array}{cccc} \cos\beta & 0 & \sin\beta & 0 \\ 0 & 1 & 0 & 0 \\ -\sin\beta & 0 & \cos\beta & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right]=\left[ \begin{array}{cccc} u & 0 & a' & 0 \\ 0 & 1 & 0 & 0 \\ -a' & 0 & u & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right]$ 4. 绕$z$轴旋转$\theta$角。这个就不用说了,$ R_z=Rotate_z(\theta)=\left[ \begin{array}{cccc} \cos\theta & \sin\theta & 0 & 0 \\ -\sin\theta & \cos\theta & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right]$ 5. 转回来、移回来。即上述三个矩阵$T,R_x,R_y$的逆矩阵。不过由于变换矩阵的特殊性,可以很容易求出$ T^{-1}=Trans(a,b,c)=\left[ \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ a & b & c & 1 \\ \end{array} \right]$ $ R_x^{-1}=Rotate_x(-\alpha)=\left[ \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & \cos\alpha & -\sin\alpha & 0 \\ 0 & \sin\alpha & \cos\alpha & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right]=\left[ \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & \frac{c'}{u} & -\frac{b'}{u} & 0 \\ 0 & \frac{b'}{u} & \frac{c'}{u} & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right]$ $ R_y^{-1}=Rotate_y(\beta)=\left[ \begin{array}{cccc} \cos\beta & 0 & -\sin\beta & 0 \\ 0 & 1 & 0 & 0 \\ \sin\beta & 0 & \cos\beta & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right]=\left[ \begin{array}{cccc} u & 0 & -a' & 0 \\ 0 & 1 & 0 & 0 \\ a' & 0 & u & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right]$ 最后我们终于得出了旋转变换$(a,b,c,a',b',c',\theta)$对应的矩阵$ Rotate(a,b,c,a',b',c',\theta)=TR_xR_yR_zR_y^{-1}R_x^{-1}T^{-1} $ 化(bai)简(du)一下,可以得到一个比较好看的式子 $T\begin{bmatrix} a'\ ^2(1-\cos\theta)+\cos\theta & a'b'(1-\cos\theta)+c'\sin\theta & a'c'(1-\cos\theta)-b'\sin\theta & 0 \\ a'b'(1-\cos\theta)-c'\sin\theta & b'\ ^2(1-\cos\theta)+\cos\theta & b'c'(1-\cos\theta)+a'\sin\theta & 0 \\ a'c'(1-\cos\theta)+b'\sin\theta & b'c'(1-\cos\theta)-a'\sin\theta & c'\ ^2(1-\cos\theta)+\cos\theta & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}T^{-1}$ 至此,原问题得到解决。 时间复杂度$O(4^3m\log_2 n)$。 ##[1010.Zero Escape](http://acm.hdu.edu.cn/showproblem.php?pid=5389) 一个数的数字根只和它$mod~9$之后的值有关,只要类似背包就能完成人员分配的计算。 具体证明:数字根=$\sum_{i=0}^{w}a_i$,数字=$\sum_{i=0}^{w}10^i*a_i$ 数字-数字根=$\sum_{i=0}^{w}(10^i-1)*a_i$,这个数字在$mod$ $9$域下为$0$ 时间复杂度$O(n)$ ##[1011.tree](http://acm.hdu.edu.cn/showproblem.php?pid=5390) 首先,询问一个元素和一个集合中某元素的最大异或和,可以对集合元素化为二进制从高位到低位建立trie,询问时贪心选择。 于是,有个比较一眼流的$O(nw\log n)$($w$为权值二进制位数)做法如下: 建立dfs序,用线段树套trie维护dfs序,每次修改权值,由于只对修改节点的子树产生贡献,于是修改dfs序中该子树所代表区间。 每次修改需要删除该节点原来权值的信息,插入新的信息。 询问只需要在线段树单点询问即可,在线段树上每个经过的节点都在该区间代表的trie中贪心选择一遍即可。 这样的做法时空复杂度都是$O(nw\log n)$,然而时间复杂度可以接受,空间复杂度难以接受。 可以选择改进这种做法,将询问离线,做$\log n$次,每次只做线段树的一层节点,操作覆盖该区间的修改操作,每次询问这一层的信息。 比如当前做到$[1,2],[3,4],[5,6],[7,8]$这一层线段树。 若某修改区间为$[2,7]$,那么在线段树中的覆盖区间应为$[2,2],[3,6],[7,7]$,并没有本层的区间,因此忽略该修改。 若某修改区间为$[2,4]$,那么在线段树中的覆盖区间应为$[2,2],[3,4]$,于是修改$[3,4]$这个区间。 若某询问点为$4$,那么本层的区间即为$[3,4]$,询问该区间,和以前得到的答案取最大值,最后输出即可。 这样空间复杂度从$O(nw\log n)$降为了$O(nw)$,时间复杂度不变。

2015 Multi-University Training Contest 8 solutions BY 绍兴一中》上有4条评论

  1. whoami

    1005存在这样的字符串吗
    1
    1 1
    长度为10^5,全是a的字符串
    长度为10^5,全是a的字符串

评论已关闭。