Prob.3 of NOIP 2002 (Junior) *Solution*

酱油 posted @ Wed, 02 Sep 2015 16:46:22 +0800 in OI life with tags Solution , 281 readers

More than two years ago, I thought it was an Ad Hoc problem and I had a try, but I failed.

Now I've realized it is just a math problem with floyd!

"Sky Gate":

Given a positive integer number n, and k ways of changing a digit.
You could change a digit in a way called x y. Which means you could change number x into y.
Then how many numbers could be produced after a series of changing operations? (Caution: We could change 0 times)
n k
xi yi(1<=i<=k)
The answer required
Sample Input:
234 2
2 5
3 6
Sample Output:
234, 264, 534, 564 are numbers available.
For all 5 testcases: 1<=n<=10^30, 1<=k<=15, 0<=xi<=9, 1<=yi<=9 

It's a problem of calculating the number of possible answers, but not a problem requiring every answer. So it's not recommended to use BFS, and that's why I failed two years ago...

Consider this situation: If a[i] means the number of ways that the i-th digit could change into, then the answer to the question is Πa[i]. It's obvious since every number couldn't be changed into zero unless it is zero at the beginning.

So use floyd to get can[i][j] indicating whether i could be changed into j.

Then get a[i]=Σcan[i][j].

Now calculate Πa[i] with higher precision.

Then it comes to coding...

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <ctime>
#include <cmath>
#include <algorithm>
using namespace std;
int k,i,j,jw,x,y,ans[110],st[110],len,f[110];
bool a[10][10];
char c;
int main()
	while((c=getchar())!=' ')st[++len]=c-48;
	for(i=ans[0];i>=1;i--)printf("%d",ans[i]);puts("");return 0;

Not very complex, in fact.


If you have a better solution, please show your solution through comments, and I'll take it seriously.

(Comments are welcomed and it is recommended that you reply in English.)


Login *

loading captcha image...
(type the code from the image)
or Ctrl+Enter