题解 P5261 【[JSOI2013]数字理论 】
zsq259
·
·
题解
题解 JSOI2013 数字理论
题面
luogu5261
解析
先判掉不存在的情况:S>K*9||P>K*9||(S*D \ \ mod \ \ 9)!=(P \ \ mod \ \ 9)
考虑数位 dp,
首先我们可以考虑求 k=x*D.
设 f[i][s1][s2][l]=0/1 表示是否存在一个数 x ,使得
-
dight(x/D)=s1
-
-
- 在x后面添加i位数字后能满足题目条件
其中 dight(i) 表示 i 的各位数字之和.
好奇怪的状态...
边界就是 f[0][S][P][0]=1.
再来看转移:
枚举在 x 后添加一位数字 d,则
其实其中的含义仔细分析一下就能明白了...
然后贪心地从高位往低位找,找到一个符合条件的就继续找下一位.
读到这里,细心的读者一定会发现这样做会TLE,然而,这样做确实会TLE...
发现当 $i\times 9+s1<S$ 或 $i\times 9+s2<P$是都是无意义的,
并且当 $s1$ 和 $l$ 确定时,$s2 \ \ mod \ \ 9$ 也能知道,因此可以将 $s2$ 除9.
然后就能奇妙地过了...
### code
```cpp
#include <iostream>
#include <stdio.h>
#include <cstring>
#define ll long long
#define filein(a) freopen(a".cpp","r",stdin)
#define fileout(a) freopen(a".cpp","w",stdout);
using namespace std;
inline int read(){
int sum=0,f=1;char c=getchar();
while((c<'0'||c>'9')&&c!=EOF){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9'&&c!=EOF){sum=sum*10+c-'0';c=getchar();}
return sum*f;
}
const int N=101;
int K,P,S,D;
bool f[N][N*9][N][10];
int main(){
K=read();S=read();P=read();D=read();
if(S>K*9||P>K*9||((S*D%9)^(P%9))){puts("-1");return 0;}
f[0][S][P/9][0]=1;
for(int i=1;i<K;i++){
int S_st=max(S-i*9,0),P_st=max(P-i*9,0);
for(int j=S_st;j<=S;j++){
for(int l=0;l<D;l++){
int mod=(j*D+l)%9;
for(int k=P_st/9,realk=k*9+mod;realk<=P;k++,realk+=9){
for(int d=0;!f[i][j][k][l]&&d<10;d++){
if(f[i-1][j+(l*10+d)/D][(realk+d)/9][(l*10+d)%D]) f[i][j][k][l]=1;
}
}
}
}
}
int st=D;
while(st<D*10&&!f[K-1][st/D][(st/10+st%10)/9][st%D]) st++;
if(st==D*10){puts("-1");return 0;}
printf("%d",st/D);
int I=K-1,J=st/D,K=(st/10+st%10),L=st%D;
while(I){
int d=0;
while(!f[I-1][J+(L*10+d)/D][(K+d)/9][(L*10+d)%D]) d++;
printf("%d",(L*10+d)/D);
I--;J+=(L*10+d)/D;K+=d;L=(L*10+d)%D;
}
return 0;
}
```