2017/04/03 训练题题解

题解

A、Country Roads
题目来源：lightoj1002
迪杰斯特拉算法的运用。由于后一阶段的代价总是不小于前一阶段的代价，即从源点逐渐开始向外访问时，dis数组的值总是不会减少。（关于Dijkstra算法，更多具体可以去百度一下）
--------代码传送门--------
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　－　　　|　　　－　　|
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|

B、How Many Zeroes?
题目来源：lightoj1140
题意：问[m,n]区间中所有整数的0的个数。
一道数位DP的题目。首先，对于这道题的情况，区间减法适用（即S[0,b]-S[0,a-1]=S[a,b]）
所以求出ans[n]再求出ans[m-1]，然后用ans[n]-ans[m-1]就行了。
然后接下来是如何求出ans[n]和ans[m-1]。
先看一下这个问题的简化版本。求0到10^k-1内的所有整数有多少位零。即K位数以内的数字共有多少0
对于一个K位数，其形式为XXXXX(K个X，X为0-9)
设DP[k]为我们需要求的答案，即K位数以内共有多少0
举个简单的例子，当K为5的时候
DP[k]=sum(前一位为i时DP[K-1]，0 <= i <= 9)
就是在枚举第一位的情况下计算DP[k-1]
这样就对了吗？这样并不完整，还缺少一个状态。因为DP的边界条件是DP[0]=已经出现过的0的个数
所以还缺少一个状态用来保存之前已经有的0的个数
所以现在状态为DP[K][L]
代表处理到第K位数且高位已经有L个0的情况有的0的个数
那么用个DFS就能求这个简化版问题的解了
对于这个完整版的问题呢，我们只需要在简化版问题的基础上加上一些取数的限制就好了。
比如对于DP[3456]在枚举最高位，只能枚举到3，并且在枚举到3的时候，枚举下一位的时候只能枚举到4.
代码详情可以百度一下，和讲的差不多
PS:数位DP就是一种记忆化的搜索
--------代码传送门--------
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　－　　　|　　　－　　|充能中
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|

C、Greatest Parent
题目来源：lightoj1128
题意：求树根到v点的路径上满足权值大于k的最近的点
树上的倍增法DP
倍增两个字特别精髓。
设DP[v][i]为从v点开始到v点的第2ⁱ代祖先的路径上最大的权值
LA[v][i]为v的第i代祖先
DP[v][i]=max(DP[LA[V][i-1]][i-1],DP[v][i-1])
这个状态转移十分好理解，就是把一条长度为2ⁱ的路径分为两条长度为2^i-1长度的路径
取这两条路径中权值的最大值就可以了
处理到这里问题差不多就已经解决了
剩下的处理查询使用类似二分的思想
因为从u到v的路径上，权值的最大值是单调的
R(u,v)为u到v路径上最大的权值
p为u-v路径的中点
如果R(u,p)>=k
那么将v设为p，否则将u设为p
重复这一过程直到无法继续便得出了答案
在一般的二分算法中，L和R都是确切的上下边界
但是在这里不同，在这个问题中，
影响二分区间的两个因素为v和i
v确定了区间的起点，i确定了区间的长度
所以对于(v,i)这个区间，可以分割为
(v,i-1)和(LA[v][i-1],i-1)这两个区间，以及LA[v][i-1]这个中点
可见，不论选择哪个区间作为下一次的二分区间，长度都会变为i-1
唯一不同的是区间的起点，剩下的就好写了
PS:若v没有第2ⁱ代祖先，LA[v][i]的值为0（根节点）
代码还没写好，可以先百度看看
--------代码传送门--------
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　－　　　|　　　－　　|未充能，无法打开
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|

D、Summing up Powers
题目来源：lightoj1132
题意：求(1^k+2^k+3^k+...+n^k)mod 2³²
N很大- -肯定不能直接O(n)的算法直接做，尽量找O(logn)级别的算法
写出递推式
f(n+1)=f(n)+(n+1)^k
如果这个递推式是一个线性变换，那么我们就可以用矩阵快速幂来求出答案了
把(n+1)^k用二项式定理展开，发现这确实是一个线性变换
接下来就是构造矩阵
原矩阵为
| f(n) |
| n⁰ |
| n¹ |
| n² |
|......|
| n^k-1 |
| n^k |
要变成
| f(n+1) |
| (n+1)⁰ |
| (n+1)¹ |
| (n+1)² |
|......|
| (n+1)^k-1 |
| (n+1)^k |
首先要让一个(k+2)X1的矩阵变成另外一个(k+2)X1的矩阵
只能前面乘一个(k+2)x(k+2)的矩阵D了
接下来构造这个矩阵D的第一行
展开(n+1)^k
(n+1)^k=C(k,0)n⁰+C(k,1)n¹+C(k,2)n²+C(k,3)n³+...+C(k,k)n^k
f(n+1)=f(n)+C(k,0)n⁰+C(k,1)n¹+C(k,2)n²+C(k,3)n³+...+C(k,k)n^k
于是构造出第一行为
|1 C(k,0) C(k,1) ...C(k,k) |
继续构造第i行(2<=i<=k+2)
设t=i-2
展开(n+1)^t(在目标矩阵中第i行的指数为i-2）
(n+1)^t=C(t,0)n⁰+C(t,1)n¹+C(t,2)n²+C(t,3)n³+...+C(t,t)n^t
所以矩阵D的第i行为
|0 C(t,0) C(t,1) ... C(t,t) 0 0 ... 0|
大概像这样
|1 C(k,0) C(k,1) ...C(k,k) |
|0 1 0 0...............................|
|0 C(1,0) C(1,1) 0 0.........|
|0 C(2,0) C(2,1) C(2,2) 0..|
.................................................
构造完矩阵后，矩阵快速幂一下就好啦，
详情百度
代码也还没写 可以参考下百度
--------代码传送门--------
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　－　　　|　　　－　　|未充能，无法打开
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|

E、Dice (I)
题目来源：lightoj1145
题意：n个k个面的骰子（每个面只有1-k点，并且不能重复），问这n个骰子朝上那面的点数的和为s的方案种数
先从最简单的地方开始想，这道题肯定是个dp的题目
并且一个很简单的状态转移方程瞬间就能想到
DP[n][s]为n个k个面的骰子点数和为s的方案数
DP[n][s]=sum(DP[n-1][s-t],1<=t<=k)，DP[0][0]=1,其余的DP[0][x]都为0;
时间复杂度为o(nks)（其中有ns个状态，每个状态需要k的时间计算）
很明显要爆炸。。
可以发现能对每个状态的求解时间进行优化
使复杂度尽量变成o(nk)
对于DP[n][s]=sum(DP[n-1][a],a=s-1,s-2,s-3,...,s-k)
DP[n][s+1]=sum(DP[n-1][b],b=s,s-1,s-2,s-3,...,s-k-1)
可见[b]=[a]+s-(s-k)
所以在从左向右计算DP[n]这一行时，用sum保存sum(DP[n-1][a],a=s-1,s-2,s-3,...,s-k)的值
sum(DP[n-1][b],b=s,s-1,s-2,s-3,...,s-k-1)=sum+dp[n-1][s]-dp[n-1][s-k]
以此类推
每个状态的计算时间就变成了o(1)
PS:因为每个状态只与前一行的左边部分有关，所以一个一维数组就可以算出来了。
关于代码…惯例
--------代码传送门--------
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　－　　　|　　　－　　|未充能，无法打开
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|

F、Diablo
题目来源：lightoj1087
题意：对于一个序列，有两种操作，一种是删除并输出第k个数，第二个是在末尾插入一个数
用线段树维护区间内未删除的数的个数，问题就迎刃而解。
模板题。