2017/04/10 训练题题解

题解

A、Binary Simulation
题目来源：lightoj1080
题意：给出一段仅由0和1组成的序列，有两种操作，一种是讲序列区间[l,r]的0和1反转
第二种是查询当前序列的第k位是0还是1
思路：已经知道了序列的初状态，想知道某一位的后续某个时间的状态，就只需要知道这一位被反转了多少次。
每当被一个区间包含时，这一位就会被反转一次，所以就是求被多少个区间包含
若第k位被一个区间[L,R]包含，那一定有L<=k<=R
所以L<=k的区间都是有可能包含k的，
若是某个区间的R < k，那这个区间一定不包含k，
小于等于k的L的个数为a，小于k的R的个数为b，
反转次数就等于a-b
具体实现我采用的是树状数组（实现简单，比线段树简单很多）
树状数组能在logn的时间求出前缀和和修改某一个位
每翻转一个区间，就为树状数组的C数组
--------[代码传送门][3]--------
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　－　　　|　　　－　　|
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|

B、How Many Zeroes?
题目来源：[lightoj1140][4]
题意：问[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.
代码详情可以[百度一下][5]，和讲的差不多
PS:数位DP就是一种记忆化的搜索
--------代码传送门--------
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　－　　　|　　　－　　|充能中
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|

C、Greatest Parent
题目来源：[lightoj1128][6]
题意：求树根到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（根节点）
代码还没写好，可以先[百度看看][7]
--------代码传送门--------
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　－　　　|　　　－　　|未充能，无法打开
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|

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..|
.................................................
构造完矩阵后，矩阵快速幂一下就好啦，
详情[百度][8]
代码也还没写 可以参考下[百度][9]
--------代码传送门--------
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　－　　　|　　　－　　|未充能，无法打开
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|

E、Dice (I)
题目来源：[lightoj1145][10]
题意：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:因为每个状态只与前一行的左边部分有关，所以一个一维数组就可以算出来了。
关于代码…[惯例][11]
--------代码传送门--------
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　－　　　|　　　－　　|未充能，无法打开
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|
|　　　　　|　　　　　　|

F、Diablo
题目来源：
题意：