专栏首页数据结构与算法1009 产生数 2002年NOIP全国联赛普及组

1009 产生数 2002年NOIP全国联赛普及组

009 产生数

2002年NOIP全国联赛普及组

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

  给出一个整数 n(n<10^30) 和 k 个变换规则(k<=15)。   规则:    一位数可变换成另一个一位数:    规则的右部不能为零。   例如:n=234。有规则(k=2):     2-> 5     3-> 6   上面的整数 234 经过变换后可能产生出的整数为(包括原数):    234    534    264    564   共 4 种不同的产生数 问题:   给出一个整数 n 和 k 个规则。 求出:   经过任意次的变换(0次或多次),能产生出多少个不同整数。   仅要求输出个数。

输入描述 Input Description

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

输出描述 Output Description

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

样例输入 Sample Input

   234 2    2 5    3 6

 1 #include<iostream>
 2 using namespace std;
 3 int can[1001][1001];
 4 long long int tot=1;
 5 int main()
 6 {
 7     string n;
 8     int m;
 9     cin>>n;
10     cin>>m;
11     for(int i=1;i<=m;i++)
12     {
13         int x,y;
14         cin>>x>>y;
15         can[x][y]=1;
16         can[y][x]=1;
17     }
18     for(int i=0;i<10;i++)
19     {
20         for(int j=0;j<10;j++)
21         {
22             for(int k=0;k<10;k++)
23             {
24                 if(j!=i&&i!=k&&j!=k)
25                 {
26                     if(can[i][j]==1&&can[i][k]==1)//将所有可能的情况计算出来 2->3 3->5 2->5 
27                     can[k][j]=1;
28                 }
29             }
30         }
31     }
32     for(int i=0;i<n.length();i++)
33     {
34         int d=n[i]-48;
35         int now=1;
36         for(int j=0;j<10;j++)
37         {
38             if(can[d][j]==1&&d!=j)
39             {
40                 now++;
41             }
42         }
43         tot=tot*now;// 乘法原理 
44     }
45     cout<<tot;
46     return 0;
47 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • cf547D. Mike and Fish(欧拉回路)

    attack
  • 洛谷P1734 最大约数和

    题目描述 选取和不超过S的若干个不同的正整数,使得所有数的约数(不含它本身)之和最大。 输入输出格式 输入格式: 输入一个正整数S。 输出格式: 输出最大的约...

    attack
  • HDU 3078 Network

    Problem Description The ALPC company is now working on his own network system,...

    attack
  • POJ-3866-Exclusive Access 2

    ACM模版 描述 ? ? ? 题解 这绝对是我做过最长的题,也是最难理解的题,翻译成中文都很难理解。 简单的说,就是安排任务使用两个资源的顺序,使最坏情况下,执...

    f_zyj
  • HDU 3078 Network

    Problem Description The ALPC company is now working on his own network system,...

    attack
  • HDU 2444 The Accomodation of Students(二分图判断+最大匹配数)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2444

    Ch_Zaqdt
  • 洛谷P1734 最大约数和

    题目描述 选取和不超过S的若干个不同的正整数,使得所有数的约数(不含它本身)之和最大。 输入输出格式 输入格式: 输入一个正整数S。 输出格式: 输出最大的约...

    attack
  • LeetCode 135 Candy

    ShenduCC
  • Lake Counting (POJ No.2386)

    题意:有一个M*N的圈子,雨后有积水,然后八个方位相联通的被认为是连接在一起的。请求出圈子里共有多少个水洼。

    用户7727433
  • Codeforces Round #535 (Div. 3) B. Divisors of Two Integers(思维)

    题目链接:http://codeforces.com/contest/1108/problem/B

    Ch_Zaqdt

扫码关注云+社区

领取腾讯云代金券