题解 P3286 【[SCOI2014]方伯伯的商场之旅】
7KByte
·
·
题解
prework不清空，爆零两行泪。。。
神仙数位DP题。
根据题面和数据范围，显然这是一道数位DP题。
但是又不能按照数位DP的常规思路来做。
最开始想到用f[i][j][k]表示填到第i位，第i位为j，是否卡上界的答案。
很快发现这个想法太\texttt{naive}了，因为面对大量的数时，根本不知道到底要合并到哪一堆。
但观察之后我们可以发现一些有用的性质，比如向右填一个数字后，合并点（指最终剩的一堆的位置）只可能向右移动。因为加入的数一定在原来的合并点的右边，向左移动只能使代价更大，但向右移动可能使代价更小。
借助这个性质，我们可以先把所有点合并到最左边，再逐一考虑向右移动。
$f[i][j]$表示填到第$i$位，第$i$位为$j$时的答案。DP方程如下。
$$f[i][j]=j\times(i-1)\times k^{i-1}+\sum\limits_{u=0}^{k-1}{f[i-1][u]}$$
最后按照数位DP的套路试填即可。
$\texttt{Task2:}$求$1-N$的所有数，全部合并到第$s$位，其中低于$s$位的数字之和要小于高于$s$位（这里包括第$s$位）的数字之和的数的个数。
直接求也不好求，我们直接枚举$s$，再分别枚举高于和低于$s$位的数位之和。
$f[i][l][r][op]$表示填到第$i$位，$l$表示高于或等于$s$位的数字之和，$r$表示低于$s$位的数字之和。$op$表示是否卡上界（数位DP套路）。
然后枚举当前位上的数字直接转移即可。
代码如下，写了两个``namespace``分别对应上面两个``task``，可读性应该是比较高的/cy。
```cpp
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 66
#define M 255
using namespace std;
int k,a[N],n,s[N],b[N],c[N];
namespace task1{
int f[N][N];
int solve(){
memset(f,0,sizeof(f));
b[0]=1;rep(i,1,n)b[i]=b[i-1]*k;
rep(i,1,n)rep(j,0,k-1){
rep(o,0,k-1)f[i][j]+=f[i-1][o];
f[i][j]+=j*(i-1)*b[i-1];
}
int ans=0;
rep(i,0,a[n]-1)ans+=f[n][i];
rep(i,1,n)ans+=a[i]*(i-1);
pre(i,n-1,1){
rep(j,0,a[i]-1)ans+=f[i][j];
pre(j,n,i+1)ans+=a[j]*(j-1)*a[i]*b[i-1];
}
return ans;
}
}
namespace task2{
int f[N][M][M][2];
void prework(int pos){
memset(f,0,sizeof(f));
f[n+1][0][0][1]=1;
pre(i,n,1){
if(i>=pos){
rep(l,0,c[n-i]){
rep(j,0,a[i]-1)f[i][l+j][0][0]+=f[i+1][l][0][1];
rep(j,0,k-1)f[i][l+j][0][0]+=f[i+1][l][0][0];
f[i][l+a[i]][0][1]+=f[i+1][l][0][1];
}
}
else{
rep(l,0,c[n-pos+1])rep(r,0,c[pos-i-1]){
rep(j,0,a[i]-1)f[i][l][r+j][0]+=f[i+1][l][r][1];
rep(j,0,k-1)f[i][l][r+j][0]+=f[i+1][l][r][0];
f[i][l][r+a[i]][1]+=f[i+1][l][r][1];
}
}
}
}
int solve(){
int ans=0;
rep(i,2,n){
prework(i);
rep(l,1,c[n-i+1])rep(r,0,l-1){
ans+=(f[1][l][r][1]+f[1][l][r][0])*(r-l);
}
}
return ans;
}
}
int solve(int x){
n=0;while(x)a[++n]=x%k,x/=k;
rep(i,1,k)s[i]=s[i-1]+i;
rep(i,1,n)c[i]=c[i-1]+k-1;
return task1::solve()+task2::solve();
}
signed main(){
int l,r;scanf("%lld%lld%lld",&l,&r,&k);
printf("%lld\n",solve(r)-solve(l-1));
return 0;
}
/*
114514 1919810 10
*/
```