【2011集训队出题】Digit

Description:

  在数学课上,小T又被老师发现上课睡觉了。为了向全班同学证明小T刚才没有好好听课,数学老师决定出一道题目刁难一下小T,如果小T答不出,那么……
  情节就按照俗套的路线发展下去了,小T显然无法解决这么复杂的问题,可怜的小T只能向你求助:
  题目是这样的:
  求一个满足条件的n位数A(不能有前导0),满足它的数字和为s1,并且,A*d的数字和为s2.
  1≤n≤100,0≤s1≤n*9,0≤s2≤(n+1)*9,0≤d≤9

题解:

考虑从高位到低位确定每一个数字,设f[i][j][k][p]表示:当前到第i位,前i位没有乘d的数字和是j,乘了d且加上后面的进位的数字和是k,后面没有确定的位乘了d给当前第i位进p。

对于每一个状态f[i][j][k][p],可以枚举下一位以后乘上d的高位s,由于下一位以后必须进给第i位p,所以s=p*10->p*10+9,那么下一位的数字x=s/d(下取整),下两位需进给下一位p’=s-x*d。
于是得出转移f[i][j][k][p]->f[i+1][j+x][k+s%10][p’]。

以上就是最直接的dp做法。

这样直接dp,状态有100*900*909*10=818100000,再算上转移,似乎怎么优化都不可过。

然而题解给优化过去了(%%%)。

由于出题人的方法过于牛逼,所以弱弱的我们只能另辟蹊径了~~。

随便想想就知道有很多状态是无用的,并且需要的只是最小的解,这启发我们用搜索。

按照一定顺序去搜索,搜到一组解就退了,这样是很快的,当然还不足以让我们过,需要加一些剪枝。

剪枝0:如果当前的数字和已经超过s1、s2,……

剪枝1:假设剩下的位全部是9,如果依然不够s1、s2,那么直接退了。

剪枝2:记忆化
因为是按照从小到大的顺序搜索的,所以一个状态走过了可以不用再走。

但是状态数有100*900*909*10=818100000那么多,空间炸了怎么办?

可以用压位的方法来存,比如说一个32位整数,占4字节,就可以存32个布尔了,因此真正的空间是818100000/32=25565625个32位整形,c++选手直接用bitset就行了。

时间复杂度是玄学的,但是可以感受到是很难有数据把搜索卡到T。

Code:

#include<cstdio>
#include<bitset>
#define fo(i, x, y) for(int i = x; i <= y; i ++)
using namespace std;

int n, s1, s2, d, a[105], bz;

int sum(int x) {
    int s = 0;
    while(x) s += x % 10, x /= 10;
    return s;
}

int tot;

bitset<1000000000> b;

void dg(int o, int p1, int p2, int p) {
    if(bz) return;
    if(p1 > s1 || p2 > s2) return;
    if((n - o + 1) * 9 + p1 < s1) return;
    if((n - o + 1) * 9 + p2 < s2) return;
    if(p > d) return;
    int num = p + p2 * 11 + p1 * 9999 + o * 8999100;
    if(b[num]) return;
    b[num] = 1;
    if(o > n) {
        if(p != 0) return;
        if(p1 == s1 && p2 == s2 && p == 0) {
            fo(i, 1, n) printf("%d", a[i]);
            printf("\n");
            bz = 1;
        }
        return;
    }
    fo(i, p * 10, p * 10 + 9) {
        int x = i / d, np = i - x * d;
        a[o] = x;
        dg(o + 1, p1 + x, p2 + i % 10, np);
        if(bz) return;
    }
}

int main() {
    scanf("%d %d %d %d", &n, &s1, &s2, &d);
    fo(i, 1, 9) fo(p, 0, d - 1)
        a[1] = i, dg(2, i, sum(i * d + p), p);
    if(!bz) printf("-1");
}
本站公众号
   欢迎关注本站公众号,获取更多程序园信息
开发小院