华师一附中OI组

标题: P1037 产生数 [打印本页]

---

作者: 倚窗倾听风吹雨    时间: 2018-10-3 18:47
标题: P1037 产生数
https://www.luogu.org/problemnew/show/P1037


题目描述
给出一个整数n(n<300)和 k 个变换规则(k≤15)。

规则：

一位数可变换成另一个一位数：

规则的右部不能为零。

例如：n=234。有规则（k=2）：

2－>5
3－>6
上面的整数234经过变换后可能产生出的整数为（包括原数）:

234
534
264
564
共4 种不同的产生数

问题：

给出一个整数 n 和 k 个规则。

求出：

经过任意次的变换（0次或多次），能产生出多少个不同整数。

仅要求输出个数。

输入输出格式
输入格式：
键盘输入，格式为：

n k
x_1 y_1
x_2 y_2
... ...

x_n y_n
输出格式：
屏幕输出，格式为：

1个整数（满足条件的个数）：

输入输出样例
输入样例#1：
234 2
2 5
3 6
输出样例#1：
4

---

作者: 倚窗倾听风吹雨    时间: 2018-10-3 19:03

1. #include<iostream>
   
2. #include<cstring>
   
3. #define FOR(i,a,b) for(register int i=a;i<=b;i++)
   
4. #define ROF(i,a,b) for(register int i=a;i>=b;i--)
   
5. using namespace std;
   
6. string n;
   
7. int len,k,m[11][3],c[200],ans[200];
   
8. bool num[11][11];
   
9. void add(int *a)
   
10. {
    
11.     a[1]++;a[0]=1;
    
12.     if(a[1]>=10){a[2]++;a[1]=0;a[0]=2;}
    
13.     return;
    
14. }
    
15. void mul(int *a,int *b)
    
16. {
    
17.     memset(c,0,sizeof(c));
    
18.     int ex;
    
19.     FOR(i,1,a[0])
    
20.     {
    
21.         ex=0;
    
22.         FOR(j,1,b[0])
    
23.         {
    
24.             c[i+j-1]+=a[i]*b[j]+ex;
    
25.             ex=c[i+j-1]/10;
    
26.             c[i+j-1]%=10;
    
27.         }
    
28.         c[i+b[0]]+=ex;
    
29.     }
    
30.     c[0]=a[0]+b[0]+1;
    
31.     while(c[0]>1 && !c[c[0]])c[0]--;
    
32.     FOR(i,0,c[0])a[i]=c[i];
    
33. }
    
34. void print(int *a){ROF(i,a[0],1)cout<<a[i];cout<<endl;return;}
    
35. void Floyd()
    
36. {
    
37.     FOR(k,0,9)FOR(i,0,9)FOR(j,0,9)if(num[i][k] && num[k][j])num[i][j]=1;
    
38. }
    
39. int main()
    
40. {
    
41.     cin>>n>>k;FOR(i,0,9)num[i][i]=1;len=n.size();
    
42.     FOR(i,1,k){int a,b;cin>>a>>b;num[a][b]=1;}
    
43.     Floyd();///FOR(i,0,9){FOR(j,0,9)cout<<num[i][j]<<" ";cout<<endl;}
    
44.     FOR(i,0,9)FOR(j,0,9)if(num[i][j])add(m[i]);//FOR(i,0,9)print(m[i]);
    
45.     ans[0]=1;ans[1]=1;
    
46.     FOR(i,0,len-1)mul(ans,m[n[i]-'0']);
    
47.     print(ans);
    
48.     return 0;
    
49. }
    

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2