规则的右部无法为零,空间范围

1009 产生数

2000年NOIP全国际联盟赛普及组

时限: 一 s

空间范围: 12柒仟 KB

标题等级 : 黄金 高尔德

 

题目叙述 Description

  给出叁个整数 n(n<十^30) 和 k 个转移规则(k<=壹5)。
  规则:
   一人数可变换来另一个一位数:
   规则的右部不可能为零。
  例如:n=234。有规则(k=2):
    2-> 5
    3-> 6
  上边包车型地铁平头 23肆 经过变换后大概发生出的整数为(包罗原数):
   234
   534
   264
   564
  共 四 种不一样的发出数
问题:
  给出1个平头 n 和 k 个规则。
求出:
  经过任意次的更换(0次或频仍),能发生出多少个例外整数。
  仅须要输出个数。

输入描述 Input Description

键盘输人,格式为:
   n k
   x1 y1
   x2 y2
   … …
   xn yn

输出描述 Output Description

 荧屏输出,格式为:
  一个整数(满意条件的个数)

样例输入 萨姆ple Input

   234 2
   2 5
   3 6

样例输出 Sample Output

4

数码范围及提示 Data Size & Hint

 

思路:

  符合转移规则的数能够在更换2次后的新数如故符合转移规则

  所以咱们考虑将之转化为八个图论难题

  正是牵记从i到j必要通过多少点

  经过的点的个数正是足以变换来的数

  然而怎么求呢?

  用Freud算法

  Freud是个n^3的动态规划

  枚举几个点i,j,k

  如若i到j的偏离超过i到k加上k到i的相距就会更新i到j的相距

  遵照那个规律大家得以追加3个计数器

  即每更新2回i到j的离开则i的变换数的个数加壹

  因为n的作者也算是一种排列

  所以全数数的转换个数开端为1、

  将具备的变换数的个数都求出后

  可以由此相乘的积得出总个数

 

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 long long ans=1,num[10];
 6 int n,map[10][10];
 7 char cur[50];
 8 int main()
 9 {
10     memset(map,127/3,sizeof(map));
11     scanf("%s",cur);
12     scanf("%d",&n);
13     for(int a,b,i=1;i<=n;i++)
14     {
15         scanf("%d%d",&a,&b);
16         map[a][b]=1;
17     }
18     for(int k=0;k<=9;k++)
19     {
20         for(int i=0;i<=9;i++)
21         {
22             for(int j=0;j<=9;j++)
23             {
24                 if(i!=j&&j!=k&&k!=i)
25                 if(map[i][k]+map[k][j]<map[i][j])
26                 {
27                     map[i][j]=map[i][k]+map[k][j];
28                 }
29             }
30         }
31     }
32     for(int i=0;i<=9;i++)
33     {
34         num[i]++;
35         for(int j=0;j<=9;j++)
36         {
37             if(j==i) continue;
38             if(map[i][j]<10000) num[i]++;
39         }
40     }
41     for(int i=0;i<strlen(cur);i++) ans=(ans*num[(int)(cur[i]-'0')]);
42     cout<<ans<<endl;
43     return 0;
44 }

 

标题叙述 Description

  给出三个整数 n(n<拾^30) 和 k 个转移规则(k<=一5)。
  规则:
   1个人数可转移成另贰个1位数:
   规则的右部无法为零。
  例如:n=234。有规则(k=2):
    2-> 5
    3-> 6
  上边的整数 23四 经过变换后可能发生出的平头为(包涵原数):
   234
   534
   264
   564
  共 四 种分裂的发生数
问题:
  给出叁个整数 n 和 k 个规则。
求出:
  经过任意次的变换(0次或频仍),能发出出有个别个不等整数。
  仅必要输出个数。

输入描述 Input Description

键盘输人,格式为:
   n k
   x1 y1
   x2 y2
   … …
   xn yn

出口描述 Output Description

 显示器输出,格式为:
  一个平头(知足条件的个数)

样例输入 Sample Input

   234 2
   2 5
   3 6

样例输出 萨姆ple Output

4

#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
bool road[11][11] = {false};
int main()
{
    string n;
    int T;
    cin>>n>>T;
    int u,v;
    while (T--)
    {
        cin>>u>>v;
        road[u][v]=true;
    }
    for(int k=0;k<=9;++k) 
        for(int i=0; i<=9;++i)
           for(int j=0; j<=9;++j)
                if(k!=i&&i!=j&&k!=j)
                    if(road[i][k]&&road[k][j]) road[i][j]=true;
    long long sum=1;
    for(int i=0;i<n.length();++i)
    {
        int preNum=n[i]-48,changes=1;
        for (int j=0;j<=9;++j)
            if(road[preNum][j]&&preNum!=j) ++changes;
        sum*=changes;
    }
cout<<sum<<endl;
return 0;
}

 把每一条规则转化成u到v的通路..

相关文章

网站地图xml地图