【t098】符文之语

Time Limit: 1 second

Memory Limit: 128 MB

【问题描述】

当小FF来到神庙时，神庙已经破败不堪了。但神庙的中央有一个光亮如新的石台。小FF走进石台， 发现石台上有一个数串，而数串

的上方刻着一串古老的符文之语。精通古符文之语的小FF不费吹灰之力就读懂了文章的意思，其大意是：对于石台上的一串数

字，你可以在适当的位置加入乘号（设加了k个，当然也可不加，即分成k+1个部分），设这k+1个部分的乘积（如果k=0，则乘

积即为原数串的值）对m的余数（即mod m）为x;现求x能达到的最小值及该情况下k的最小值，以及x能达到的最大值及该情况下

的k的最小值(可以存在x的最小值与最大值相同的情况)。小FF还知道，如果他找到了正确的答案，那么就可以通往神庙的下层

了。但这个问题似乎不太好解决，小FF就找到了你，并答应找到财宝以后和你二八分（当然你拿二……）。

【数据范围】

对于30%的数据：2≤字符串的长度L≤50。

对于100%的数据：2≤字符串的长度L≤1000；2≤m≤50。

【输入格式】

第一行为数串，且数串中不存在0； 第二行为m。

【输出格式】

四个数，分别为x的最小值和该情况下的k，以及x的最大值和该情况下的k，相邻两个数之间用以个空格隔开。

Sample Input

4421

22

Sample Output

0 1 21 0

【题目链接】:http://noi.qz5z.com/viewtask.asp?id=t098

【题解】

设f[i][j]表示前i个数字组成的数字%m的值为j时最少需要加入的乘号个数;

设mod[i][j]表示从第i到第j个数字组成的数字%m的值为多少;(这个可以用同余率搞出来);

令t = (j*mod[i+1][k])%m;

则f[k][t] = min(f[k][t],f[i][j]+1);

最后分别顺序枚举、倒序枚举一下i输出相应的f[n][i]就好;

这里状态的表示感觉不好想。

想出来后写代码就比较轻松了;

【完整代码】

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define rei(x) scanf("%d",&x)

#define rel(x) scanf("%I64d",&x)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int MAXL = 1100;

const int MAXM = 50+10;

const int INF = 0x3f3f3f3f;

char s[MAXL];

int m,a[MAXL],len,mod[MAXL][MAXL];

int f[MAXL][MAXM];

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    scanf("%s",s+1);

    rei(m);

    len = strlen(s+1);

    rep1(i,1,len)

        a[i] = s[i]-'0';

    rep1(i,1,len)

    {

        mod[i][i] = a[i]%m;

        rep1(j,i+1,len)

            mod[i][j] = ((mod[i][j-1])*10+a[j])%m;

    }

    memset(f,0x3f3f3f3f,sizeof f);

    rep1(i,1,len)

        f[i][mod[1][i]] = 0;

    rep1(i,1,len)

        rep1(j,0,m-1)

            if (f[i][j]<INF)

            {

                rep1(k,i+1,len)

                {

                    int t = (j*mod[i+1][k])%m;

                    f[k][t] = min(f[k][t],f[i][j]+1);

                }

            }

    rep1(j,0,m-1)

        if (f[len][j]<INF)

        {

            printf("%d %d ",j,f[len][j]);

            break;

        }

    rep2(j,m-1,0)

        if (f[len][j]<INF)

        {

            printf("%d %d\n",j,f[len][j]);

            break;

        }

    return 0;

}

【t098】符文之语的相关教程结束。