【NOIP2002】【Luogu1037】产生数(高精乘低精,DFS暴力搜索)

            

problem

  • 给定一个整数n和k个变换规则(一位数可变换成另一个一位数)
  • 经过任意次的变换( 0 次或多次),能产生出多少个不同整数
  • n < 1e30, k <= 15

例:
n=234 。有规则( k=2 ):22 -> 55 且 33 -> 66
则能产生234、534、264、564四种数

solution

  • 一共有15种操作,说明一个数能变成多个不同的数。比如a->b,且b->c,那么存在a->c。可以DFS搜索出每个数能到达的其他所有数的个数(1~9)
  • 最多可能有30位数,所以复杂度上限O(9^30)。乘法要用高精且每次乘数不超过9。

codes

#include
#include
#include
using namespace std;

//search
const int maxk = 20;
int op[maxk][maxk], ss, vis[maxk];
void dfs(int x){
    if(vis[x])return ;
    vis[x] = 1;  ss++;
    for(int i = 0; i <= 9; i++)
        if(op[x][i])dfs(i);
}

//高精度 *= 低精(只有1位)
int val[33], len = 1;
void mul(int x){
    int t = 0; //进位
    for(int i = 1; i <= len; i++){
        val[i] = val[i]*x+t;
        t = val[i]/10;
        val[i] %= 10;
    }
    if(t > 0)val[++len] = t;
    return ;
}

int main(){
    //datein
    string s; int k;  cin>>s>>k;
    if(k==0){cout<<1;return 0;}
    for(int i = 1; i <= k; i++){
        int a, b;  cin>>a>>b;  
        op[a][b] = 1;
    }
    //每个数可以转化的个数
    val[1] = 1; //高精初始化
    for(int i = 0; i < s.size(); i++){
        memset(vis,0,sizeof(vis));  ss=0;//初始化
        dfs(s[i]-'0');//搜索并更新ss的值
        mul(ss);//累加答案
    }
    //dateout
    for(int i = len; i >= 1; i--)
        cout<cout<<'\n';
    return 0;
}
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像