bnu-faraway/XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Urals

Info

Date:2018.10.07

Link

Solutions

A Nutella’s Life

solved by gjy,sk


gjy’s solution

首先dp状态和转移都是容易想到的

\[f_i=\max \limits_{j<i,a_j<=a_i} f_j+a_i-\frac{(i-j-1)*(i-j)}{2}\]

如果没有\(a_j<=a_i\)的限制就是简单的斜率优化题,考虑用CDQ分治处理这个限制,需要注意的是,为了保证插入凸壳点横坐标的单调性,需要先按照\(a_i\)排序。

还需要注意的是,需要初始化答案为-inf。

因为没有判断队列为空WA了很久,谢队友不杀之恩。

B Oleg and Data Science

solved by gjy,ghc


ghc’s solution

显然,当\(X \mid Q\)时,该等式恒成立。

\(L \leq Q \leq R\),令\(S = Q\),由\(Q mod X = 0\)\(X \mid Q\)。此时,等式成立当且仅当\(X\)\(Q\)的约数。

\(Q > R\),当\(Q \leq X\)时,等式恒成立。

\(Q < L\),等式成立当且仅当\(X \mid \lfloor \frac{i}{Q} \rfloor * Q , L \leq i \leq R\)。等价于\(X \mid Q * gcd(\lfloor \frac{L}{Q} \rfloor, \lfloor \frac{L}{Q} \rfloor +1,...,\lfloor \frac{R}{Q} \rfloor)\)。所以,若\(\lfloor \frac{L}{Q} \rfloor = \lfloor \frac{R}{Q} \rfloor\),答案是\(\lfloor \frac{L}{Q} \rfloor\)的约数个数,否则,\(gcd(\lfloor \frac{L}{Q} \rfloor, \lfloor \frac{L}{Q} \rfloor +1,...,\lfloor \frac{R}{Q} \rfloor) = 1\),答案是\(Q\)的约数个数。

C Christmas Garland

solved by gjy


gjy’s solution

首先将连续一段颜色相同的缩成一个。

考虑一次更新对答案的影响为:该颜色本身的段数减去该颜色每段左右两边亮着的个数。

可以将每种颜色看成图上一个点,问题归结到,对于\(n\)个点\(2n-2\)条边的图,每次点亮一个点,询问有多少个亮着的邻居(重边计算重数)。

对于度数小于\(\sqrt{n}\)的点,每次更新暴力for一遍即可。

对于度数大于\(\sqrt{n}\)的点,由于这样的点个数不超过\(\sqrt{n}\),考虑用别的点的状态变化来更新这个点的权值,那么每次更改图上任意一个点的状态至多维护\(\sqrt{n}\)个点的权值。

时间复杂度\(O(n\sqrt{n})\)

D Anna and Lucky Tickets

solved by sk,gjy


sk’s solution

题意是求长度为n的数字串的个数,条件是允许有前导零,要回文,奇数位置的数字和等于偶数位置数字和。

\(n\)是偶数,发现只要回文就满足后一个条件了,所以答案是\(10^{n/2}\)

\(n\)是奇数,设中间位置的数是\(y\),第i个数字是\(x_i\),可以列出方程\[y+2(x_1-x_2+x_3-x_4+\dots-x_{\frac{n}{2}})=0\] \[x_2-x_1+x_4-x_3+\dots+x_{\frac{n}{2}}-x_{\frac{n}{2}-1}=\frac{y}{2}\] \[x_2+(9-x_1)+x_4+(9-x_3)+\dots+x_{\frac{n}{2}}+(9-x_{\frac{n}{2}-1})=9\times\lfloor \frac{n}{4} \rfloor +\frac{y}{2}\],用隔板法求方程非负整数解的个数。还有就是有限制\(0 \le x_i \le 9\),这个容斥一下即可。对于y,必然是9以内的偶数,枚举一下。

n个未知数总和为m的方案数\(\tbinom{n+m-1}{n-1}\)

n个未知数总和为m,每个未知数不超过S的方案数\(\sum_{i=0}^{n}(-1)^i\tbinom{n}{i}\tbinom{m+n-1-i(S+1)}{n-1}\)

E Octopus

F Secret Permutation

upsolved by sk


sk’s solution

总体思路是先找到0,再找到1,之后每个数就非常好确定了,询问次数大概是\(2n+\frac{n}{2}\)

因为\(\prod_{i=0}^{n-1}(p_i+1) mod n=0\),那么给zero设个初值,每次zero=ask(zero,i,zero)问n次之后就一定有\(p_{zero}=0\)

找1的话需要借助一点随机,每次在还不确定的集合中随机两个不同的数\(x,y\),问一下z=ask(x,y,zero),那么如果\(z\)\(x,y\)各不同的话,\(x,y\)就肯定都不是1。

然而如果\(z==x\),那么\(x\)就有一定概率是1,再把它放回集合,对于y也判断一下,这样好的情况每次从集合中扔两个数,坏的情况每次只扔一个数,随机一下应该就很快,接近\(\frac{n}{2}\)次。

最后如果已知x,那么ask(one,one,pos[x])就知道x+1了,就得到了所有数。

G Polygon Rotation

H Mikhail’s Problem

I Rat-O-Matic

J Readability

upsolved by ghc


ghc’s solution

枚举以奇数开头还是以偶数开头,然后分别计算奇数和偶数的最优排列:

显然,将所有奇(偶)数保持顺序不变放进奇(偶)数位置,花费是最优的。在此基础上,若存在两个奇(偶)数,它们由当前位置向目标位置的路径如果相交,则可以交换它们的目标位置,花费不变。

用优先队列扫一遍即可。

K Robotobor

solved by sk


sk’s solution

先预处理出\(dis[a][b][c][d]\)表示从(a,b)到(c,d)走一个回文串的最短是多少,四维状态,枚举两个点做起点,偶回文的初始状态是两个相同的点,奇回文的初始状态是两个相邻的点,相当于路径的对称中心是这条边的中点。然后再从起点正常bfs,每次枚举图上另一个点,重点是输出方案。时间复杂度\(O((nm)^2)\)

Replay

ghc

gjy

sk