@inkysakura
2017-04-24T17:16:56.000000Z
字数 3127
阅读 1359
题解
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到10k-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点的第2i代祖先的路径上最大的权值
LA[v][i]为v的第i代祖先
DP[v][i]=max(DP[LA[V][i-1]][i-1],DP[v][i-1])
这个状态转移十分好理解,就是把一条长度为2i的路径分为两条长度为2i-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没有第2i代祖先,LA[v][i]的值为0(根节点)
代码还没写好,可以先百度看看
--------代码传送门--------
| | |
| | |
| - | - |未充能,无法打开
| | |
| | |
| | |
| | |
D、Summing up Powers
题目来源:lightoj1132
题意:求(1k+2k+3k+...+nk)mod 232
N很大- -肯定不能直接O(n)的算法直接做,尽量找O(logn)级别的算法
写出递推式
f(n+1)=f(n)+(n+1)k
如果这个递推式是一个线性变换,那么我们就可以用矩阵快速幂来求出答案了
把(n+1)k用二项式定理展开,发现这确实是一个线性变换
接下来就是构造矩阵
原矩阵为
| f(n) |
| n0 |
| n1 |
| n2 |
|......|
| nk-1 |
| nk |
要变成
| f(n+1) |
| (n+1)0 |
| (n+1)1 |
| (n+1)2 |
|......|
| (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)n0+C(k,1)n1+C(k,2)n2+C(k,3)n3+...+C(k,k)nk
f(n+1)=f(n)+C(k,0)n0+C(k,1)n1+C(k,2)n2+C(k,3)n3+...+C(k,k)nk
于是构造出第一行为
|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)n0+C(t,1)n1+C(t,2)n2+C(t,3)n3+...+C(t,t)nt
所以矩阵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个数,第二个是在末尾插入一个数
用线段树维护区间内未删除的数的个数,问题就迎刃而解。
模板题。