这套题就感觉很神.像C这种如果以前遇到过就觉得简单,没遇到过还真不太好想.
A. Infinite Sequence
题目给定3个数$a, b, c ( - 10^9 ≤ a, b, c ≤ 10^9)$,用$a$和$c$形成一个序列$s$,使得$s_1 = a$且$s_i - s_{i-1} = c$ 问$b$是否在序列$s$中.
水题,直接根据$b - a$的差值看$c$是否能够整除就行了,但是要注意$c = 0$的情况以及除得的结果需要是正数.
B. Restoring Painting
给一个$3 × 3$的格子和$n, a, b, c, d (1 ≤ n ≤ 100 000, 1 ≤ a, b, c, d ≤ n)$,在格子中填数字,每个数字$i$范围为$(1 ≤ i ≤ n)$.现在要给格子填数字,问有多少种填法满足任意$2 × 2$的格子和相等.
不难看出中间的格子取任意满足范围的值都行,只要计算4个角上的数与其相邻的两个数的和,如果4个和是一样的,那么中间的数取任何值都满足条件.
简单的做法就是枚举左上角的值,判断要符合相等条件的话另外三个角的值是不是在合法范围内,如果在,那么最后结果就会多n种(中间的数取1到n).当然,也可以根据大小关系直接算出左上角取值能有多少种,然后乘以n就可以了.
C. Money Transfers
给一个含有$n$个数的序列$a$,其中$n (1 ≤ n ≤ 100 000), a_i ( - 10^9 ≤ a_i ≤ 10^9), \sum_{i=1}^n a_i = 0$.每个$a_i$都表示一个银行存款,存款可以是负数.现在可以从一个银行向相邻的银行转账(将$a_n$与$a_1$视为相邻),求要将所有银行的存款变成0,最少需要转账多少次.
首先,考虑两个相邻的位置$x,y (x < y)$, 如果$a_y$要给$a_x$转账$m$,则可以看做$a_x$向$a_y$转账$-m$.即$a_y \to^m a_x \Leftrightarrow a_x \to^{-m} a_y$,即任意一种转账方法都能转换成从前一个银行向后一个银行转账.
因此,我们可以把序列$1,2,3,-6$看成链$1 \to^1 2 \to^3 3 \to^6 -6$,因为首尾都为0,不需要互相转账.这样长度为$n$的序列最多只需要$n-1$次转账(也可以以其他任意位置的数开头,如$2 \to^2 3 \to^5 -6 \to^{-1} 1$,我们可以把序列看成一个环,从不同地方剖开可以得到不同的链).
当然,也有特殊情况,如对于序列$-1,0,1,0$,可以看成链$-1 \to^{-1} 0 \to^{-1} 1 \to^0 0$,这里面有一个箭头转账是$0$,所以是可以去掉的.容易发现,出现转账为$0$的情况一定有两侧的链和分别为$0$(也就是链上的前缀和为$0$).这样,我们可以把一个链切分成多个和为$0$的子链,切分的越多那么减掉的无用箭头(转账操作)就越多.
总结上面的分析,可以得到以下结论:
1.一个长度$n$的序列能从任意点切成一个长度为$n$的链
2.如果一个长度为$n$的链不能切分成多个和为$0$的链,那么需要的转账次数为$n-1$
3.如果一个长度为$n$的链切分成$k$条和为$0$的链,那么需要的转账次数为$n-k$
有了以上结论,我们就能得出初步的解法:只要枚举每个起始点,计算从起始点前切分的链最多能切成多少个和为$0$的子链(也就是前缀和为$0$出现多少次).这样复杂度是$O(n^2)$.
我们考虑,如果原序列从位置$x$到$y$组成的链的和$Sum(a_x, a_y) = 0$,则可以看成$Sum(a_1, a_{x-1}) + Sum(a_x, a_y) = Sum(a_1, a_y) = Sum(a_1, a_{x-1})$.这样我们只用对原序列做前缀和,如果$Sum(a_1, a_{x-1}) = Sum(a_1, a_y)$,则将$x$至$y$分为一段.最多可分的段数就是出现次数最多的前缀和的出现次数.
因此题目转化为,给定长度为$n$的序列,求出现次数最多的前缀和的出现次数$k$,输出$n-k$.
D. Tree Construction
给一个长度$n (2 ≤ n ≤ 100 000)$序列$a$,每个值$a_i (1 ≤ a_i ≤ 10^9)$且$a_i$互不相同,这些数按顺序插入二叉排序树中,求每个数(根除外)的父节点的值是多少.
直接用二叉排序树去模拟肯定是会挂的,毕竟查找和插入会退化成$O(n)$,所以从数值特性上入手.
如果一个数要插入查找树中,这个数肯定是比他大的且最接近的数的左儿子,或者比他小的且最接近的数的右儿子.
假设要插入的数是$x$,已经插入的刚好比他小的数是$a$,刚好比他大的数是$b$.根据查找树的性质,$a$和$b$是相邻的两个数,要么$a$是$b$左儿子,要么是$b$是$a$右子树最靠左的点(毕竟中序遍历中两个数需要挨在一起).如果是前者,那%x%肯定是$a$的右儿子.$a$如果已经有右儿子了?不可能!如果有右儿子$c$,那么$x < c < b$或者$a < c < x$,与$a,b$定义不符.
如果是后者,那$a$肯定有右儿子,$x$只用放在$b$的左儿子上就行了.
也就是说,只用找到已经插入的数中刚好小于和大于$x$的数$a$和$b$,判断一下$a$有没有右儿子,有就放在$b$的左儿子上,没有就放在$a$的右儿子上.
至于怎么找$a,b$,如果用c++的话,只需要把数扔进set里面跑lower_bound就行了,然而js并没有这么好用的东西,我只有离散化以后扔树状数组里面瞎搞了.
E. Trains and Statistic
有$n (2 ≤ n ≤ 100 000)$个火车站,每个站有一个值$a_i (i + 1 ≤ a_i ≤ n)$,表示在第&i&个站能买到去第$i+1$到第$a_i$站的车票($i$从$1$开始标号).现在用$ρ_{i, j}$表示从车站$i$到车站$j$最少需要的车票数,求$\sum_{i=1}^{n-1} \sum_{j=i+1}^n ρ_{i, j}$,即任意两个车站间最少需要的车票数之和.
根据数据范围可以判断是个$O(n\log(n))$的DP问题.
如果用$f(i,j)$表示从车站$i$到$j$的最少票数,则有:
如果$j ≤ a_i$,则$f(i,j) = 1$
否则$f(i,j) = 1 + \min(f(k,j))$,其中$k (i + 1 ≤ k ≤ a_i)$
从上式可以推论出,如果$a_x ≤ a_y$,则$f(x,j) ≤ f(y,j)$
如果用$g(i,j)$表示从车站$i$到$j$及其之后任意车站需要的最小票数和,同理也有当$a_x ≤ a_y$,则$g(x,j) ≤ g(y,j)$
因此,如果用$dp[i]$表示从车站$i$到其之后任意车站需要的最小票数和,则有:
$$dp[i] = g(k,a_i + 1) + (n - i) \qquad k|a_k = \max(a_{i + 1},a_{a_i})$$
当$a_i < a_k$时$g(k,a_i + 1) = dp[k] - (a_i - k)$,且可知$\min(k|a_k = \max(a_{i + 1},a_{a_i})) ≥ a_i + 1$
综上有:
$$dp[i] = dp[k] - (a_i - k) + (n - i) \qquad k|a_k = \max(a_{i + 1},a_{a_i})$$
有了转移方程,用树状数组去找到$k$,就可以计算了,最后只用将dp数组求和就能得到最终结果了.