Flandre Scarlet's Blog

不会数数，来切51nod普及组dp。老司机莫喷QAQ。感觉51nod题目真友好

妈呀切不动51nod了，再回BZOJ看看。

听说ljx帮我放广告，那我也只能放回去了w【DP大师传送门】

【51nod 1009】（数1-x中数字0-9的个数）人生第一道数位DP，用数学方法计算1-i*10^k中各种数出现的次数，再计算对前面的数的贡献。做法似乎很傻逼以后在来看看有没有正常做法。

【51nod 1043】（1个长度为2N的数，如果左边N个数的和 = 右边N个数的和，那么就是一个幸运号码。求长度为2N的幸运号码的数量）后一半是没有前导零的限制的，所以可以大力背包。考虑前导零对背包计数的影响，发现就是少做了一次背包，减掉就好了。

【51nod 1202】（求一个数列的不同子序列个数）若a[i]没有在之前出现，dp[i]=dp[i-1]*2+1，表示前面的序列加或者不加a[i]，或者新开一个以i为首的序列。若a[i]在之前出现了，用pre[i]表示上一个值为i的位置，dp[i]=dp[i]*2-dp[pre[i]-1]。

【51nod 1412】（ALB树，是指左右子树高度差至多为1的二叉树，并且该树的左右两个子树也均为ALB树。 求恰好有n个节点的ALB树的个数）dp[i][k]表示i个节点，高为k的ALB树，发现k十分小（是log级的，不超过15），枚举右子树形态转移。

【51nod 1259】（将N分为若干个整数的和的划分方式）好难，听说是五边形数定理。【补：小于$\sqrt n$的数大力做完全背包，大于$\sqrt n$的数用【51nod 1201】的技巧。合并就好了，复杂度$O(n\sqrt n)$】

【51nod 1296】（a是1-n的排列，现在钦点一些i使得a[i]大于其邻居或者钦点另一些j使得a[j]小于其邻居，求合法的排列a的个数）记dp[i][j]表示前i个数用1-i的排列且末尾为j的方案数。若钦点a[i]>a[i-1]，$dp[i][j]=\sum_{k=1}^{j-1}dp[i-1][k]$表示枚举的k大于j，把>=k的数+1。若钦点a[i]<a[i-1]，$dp[i][j]=\sum_{k=j}^{i-1}dp[i-1][k]$表示枚举的k小于等于j，理解为把>=k的数+1。没有限制则$dp[i][j]=\sum_{k=1}^{i-1}dp[i-1][k]$表示随便填数，前缀和优化。

【51nod 1020】（求恰有k对逆序对的1-n排列的个数）dp[i][k]表示1-i排列中恰有k对逆序列的方案数，枚举第i位加入的数即可按照逆序对数转移，可用前缀和优化。

【51nod 1274】（求一个无向图的最长边权递增路径）按照边权排序，把边权相同的放在一组更新最长路答案。

【51nod 1354】（求a的子序列使其积为k的个数）k不大，先罗出k的所有约数，在约数上进行背包dp。

【51nod 1201】（将N分为若干个不同整数的和的划分方式）dp[i][j]表示用i个数拼成j的方案，考虑如下转移：dp[i][j]=dp[i][j-i]+dp[i-1][j-i]，表示原集合每个数+1，再确认是否加入1。

【51nod 1052】（把数列划分成m个不相交子段，使得和最大）f[i][j]表示把前i个数分成j段的答案，g[i][j]表示把前i个数分成j段并且以i结尾。那么就可以大力转移了：g[i][j]=max(g[i-1][j],f[i-1][j-1])+a[i]表示把a[i]加入上一段或者作为新一段的头,f[i][j]=max(f[i-1][j],g[i][j])表示继承之前的答案或者采用新的答案。考虑f,g更新的先后顺序可以只用一维状态。

【51nod 1406】（n个整数，输出其中和x相与之后结果仍为x的数的个数，x从1到10^6）子集和变换，%lych_cys

【51nod 1376】（求LIS的数量）求LIS可以直接用权值树状数组做，查询小于a[i]的数的LIS，在a[i]上放置LIS长度。求数量顺便记录这个长度的LIS出现了几次，在树状数组里更新合并即可。

【51nod 1084】（走两次的方格取数）这题神TM n,m反过来读woc。dp[s][i][j]表示当前状态两路都走了s步，一个在i行，一个在j行。接下来就是大力傻逼转移：dp[s][i][j]=dp[s][i][j]=max(dp[s-1][i][j],dp[s-1][i-1][j-1],dp[s-1][i][j-1],dp[s-1][i-1][j])+(i==j?a[i][s-i]:a[i][s-i]+a[j][s-j])

【51nod 1055】（求从一个集合内选数的最长等差数列）把所有数排序，枚举a[j]+a[k]=2*a[i]中的i，发现j和k分布在i两侧，因为单调性，可以用双指针轻松统计答案。

【51nod 1196】（见题面）定义合法链为递增的且不能往后添加数字的序列。记f[i][j]表示以j开头长为i的合法链的数目。显然长度是不超过logn，这个可以由前缀和优化轻松求解，并能计算出长度为i的合法链个数g[i]。考虑v[i]为合法字符串数目，则有v[i]=g[1]*v[i-1]+g[2]*v[i-2]……总的dp复杂度是nlogn。

【51nod 1486】（网格图有些格子不能走的路径计数）想不通被黈力怒D。dp[i]表示从第i个障碍点出发不经过任何障碍点到达终点T的路径数，记g[i][j]表示从第i个点走到第j个点的所有方案，可以轻易地用组合数算出来。考虑显然的容斥$dp[i]=g[i][T]-\sum_{i->j}g[i][j]*dp[j]$就数完了。

【51nod 1371】（阶梯矩阵中放置自然数使各行各列之和不超过2）想不通被黈力怒D。按行从上往下看，发现方案只和所有列的和的数量有关。dp[i][j][k]表示前i行有j列和为1，有k列和为2。第i行时只需要考虑：①什么都不放，②放1个1，③放2个1，④放1个2。按照每个情况分类讨论即可。让我来讲一波道理：dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j+1][k-1]*(j+1)+dp[i-1][j-1][k]*(i-j-k+1)+dp[i-1][j-2][k]*(i-j-k+2)*(i-j-k+1)/2+dp[i-1][j][k-1]*(i-j-k+1)*j+dp[i-1][j+2][k-2]*(j+2)*(j+1)/2+dp[i-1][j][k-1]*(i-j-k+1)

【51nod 1313】（求S[a]..S[b]+S[c]..S[d]含连续k个字母G的四元组(a,b,c,d)的个数，要求0<=a<=b<c<=d<n）神TM在泼隔膜的时候想通了。显然连续k个G的来源要么是[a,b]或[c,d]中本来就包含了连续k个G，要么是[a,b]的后缀和[c,d]的前缀拼起来获得了k个G。关键是这里不能重复计算。记gl[i]表示i左边最近的连续k个G的起点，fl[i]表示从i起左边连续G的个数，gr[i]和fr[i]换个方向同理。枚举b和c，首先可以算出[?,b]和[c,?]中本来就包含了连续k个G的方案数=gl[b]*(n-c+1)+(n-gr[c]+1)*b-gl[b]*(n-gr[c]+1)(某侧包含-两侧同时包含)，注意应避开拼起来获得k个G的情况。然后再考虑拼起来获得k个G，前提显然是fl[b]+fr[c]>=k，考虑不少于k个G的方案数很难计算，那么可以考虑计算少于k的方案数。发现还是存在两种情况：①拼起来所得的串只包含G，②拼起来的不止有G。①相当于求0<x<=fl[b],0<y<=fr[c],x+y<k的整数解的个数，画画图，用W(fl[b],fr[c])表示答案。②显然就是左（右）侧的后（前）缀G被全部包含，另一侧的包含不到k-fl[b](fr[c])个G的方案。然后就是道写了整整两天的搞笑扭脖题了。ans+=gl[b]*(n-c+1)+(n-gr[c]+1)*b-gl[b]*(n-gr[c]+1)+((b-gl[b])*(gr[c]-c)-W(fl[b],fr[c])-max(b-gl[b]-fl[b],0)*min(max(k-fl[b]-1,0),fr[c])-max(gr[c]-c-fr[c],0)*min(max(k-fr[c]-1,0),fl[b]))*(fl[b]+fr[c]>=k);

【51nod 1294】（将数列修改成严格递增的正整数数列的最少修改次数）求a[i]-i在正整数时的非严格单调上升子序列。

【51nod 1022】（石子归并）学习了经典的四边形不等式，看起来很好用，不过感觉局限性较大。

【51nod 1597】（n个物品，第i个物品大小为i，数量为i，求装满体积为n的背包的方案数）敦敦敦题。大于$\sqrt n$的数发现和数量限制无关，是完全背包，用【51nod 1259】的技巧。小于$\sqrt n$可以显然$f[i][j]=\sum_{k=0}^{i}f[i-1][j-k*i]$。用模意义下的前缀和优化：tmp[k]表示在转移范围内的f[i-1][k]的和。维护一下就能快速转移了。（大致来自SkyDec的题解）

【51nod 1232】（求区间内能被每个数位整除的数的个数）状态压缩，显然转移之和前面出现了什么数和模lcm(1,2,3..9)=2520的余数相关。前者可以用出现的数的lcm表示，只有48个不同的lcm。所以dfs(int n,bool top,int lcm,int rem)表示转移到第n位，是否在原数的top(此时随便选数可能会超过原数)，前面数的集合为lcm（这里蛤习掉了），模2520的余数为rem【如果真爱有颜色，那么一定是蓝色！】。这里发现top=0时的状态可以直接调用，记忆化搜索就大力A掉了。

【51nod 1254】（交换两个数后的最大字段和）提问后被lych怒斥。显然只要求出“一段以a[i]结尾的后缀+前面不在后缀里的某数”的最大值即可，这个部分被lych一眼秒掉，可以通过前缀最大值-前缀和来转移，觉得十分高明，自己就是SB。然后左右反一反再做一边就A掉了。

【51nod 1230】（求区间内数位之和为质数，数位平方和也为质数的数的个数）比【51nod 1232】简单到不知道哪里去了。dfs(int n,bool top,int sum1,int sum2)就扭出来了。

【51nod 1291】（求n*m的01矩阵中所有x*y的矩阵个数）只会n^3，开启卡常大战。枚举矩形的左下角和矩形的宽，用悬线法轻松写出n^3dp卡卡常数优化一维数组就A掉了。

【51nod 1299】（树上有m个罪犯，需要在没有罪犯的节点上布置总数最少的警卫使得没有罪犯可以不经过警卫直达叶子节点）看不懂题目讨论里的技巧写错被日死。任选一个叶子节点为根dfs，f[i][0]表示i所在子树没有罪犯能到达i也没有叶子能到达i的答案（最小警卫布置数），f[i][1]表示i所在子树没有罪犯能到达i但存在叶子能到达i的答案，f[i][2]表示i所在子树存在罪犯能到达i但没有叶子能到达i的答案。开始XJB转移：当前点u有罪犯，那么显然f[u][0]和f[u][1]没有意义，只需要更新f[u][2]=sum(min(f[v][0],f[v][1]+1,f[v][2]);)；在当前点u布置警卫，那么只需要更新f[u][0]=sum(min(f[v][0],f[v][1],f[v][2]))+1;（只要更新f[u][0]的原因是f[u][0]能当f[u][1]和f[u][2]用）；不在当前点u布置警卫，就不能同时从f[v][1]和f[v][2]转移过来了，大力转移就A掉了f[u][1]=sum(min(f[v][1],f[v][0]));f[u][2]=sum(min(f[v][2],f[v][0]));f[u][0]=sum(f[v][0]);两种转移的f[u][0]不要忘记比较答案..

【51nod 1250】（1-n排列，求做恰好k次相邻数交换能得到不同序列个数和做不超过k次交换能得到不同序列个数）傻逼题怎么没人领榜..第一问就是问0-k中和k同奇偶的逆序对数的序列数，XJBDP见【51nod 1020】。第二问就是n个数构成不少于n-k个环的方案数。考虑f[i][j]为i个数含j个环的方案数。现在加入一个数i，可以自环，可以从1到i-1构成环的集合中随便找一条边插入。f[i][j]=f[i-1][j-1]+f[i-1][j]*(i-1);

【51nod 1327】（见题面）难得TM飞起来。f[i][j][k]表示前i列已经放了j个棋子并且有k个放在了后缀里。以列为阶段，当前列有四种情况：什么也不放，放后缀，放中缀，放前缀。这里放前缀当且仅当第i列是某个前缀的末尾时才触发。写的丑不放转移方程w。

【51nod 1231】（n个人互相alb，被啊的不加续命，啊成功的+1s，给定被擦去几个分数的续命牌，求方案数）前置定理，f[i][j][s]表示数字i用了j个，前缀和为s，傻鸡转移不动脑子。

【51nod 1261】（n位数，数位从左至右不递减，求整除k的方案数）要取膜，不能矩阵乘法浑身难受。发现数字一定是由若干个111..1拼成的，计算一下%k不同余数的个数就能转移了。还是推荐tangjz题解。

Remaining：【51nod 1578】【51nod 1303】【51nod 1245】

51nod切不动了TAT，转战梁晏大视野。

【BZOJ 1801】（在棋盘上放互不攻击的炮）【51nod 1371】的变形，枚举每列放什么，XJBDP即可。

【BZOJ 4321】（求没有相邻两数相邻的排列数，后面的相邻指两数差1）思考第i个数放入前i-1个数时只有相邻数差1的个数变化。大概兹磁dp了。一开始想f[i][j]表示1-i的排列有j对相邻数差1，发现情况还不够：i可能插在i-1和i-2之间。那么再用一维记录一下i和i-1是否相邻就能转移了。【不看题解鏼题真开心】

【BZOJ 2660】（n用斐波那契数之和表示的方案数）看不懂，搁着

【BZOJ 1925】（见题面）【51nod 1296】变形

【BZOJ 3174】（见题面）把人按照身高+手长排序以后螺杆，不懂啊。

【】()