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

酱油 posted @ Wed, 02 Sep 2015 16:46:22 +0800 in OI life with tags Solution , 457 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":http://www.luogu.org/problem/show?pid=1037

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)
Input:
n k
xi yi(1<=i<=k)
Output:
The answer required
Sample Input:
234 2
2 5
3 6
Sample Output:
4
Explanations:
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;
	scanf("%d",&k);
	for(i=1;i<=k;i++){scanf("%d%d",&x,&y);a[x][y]=1;}for(i=0;i<=9;i++)a[i][i]=1;
	for(i=1;i<=9;i++)for(j=0;j<=9;j++)for(k=1;k<=9;k++)a[j][k]=a[j][k]||a[j][i]&&a[i][k];
	ans[0]=ans[1]=1;
	for(i=0;i<=9;i++)for(j=0;j<=9;j++)f[i]+=a[i][j];
	for(i=1;i<=len;i++)
	{
		for(j=1;j<=ans[0];j++){ans[j]=ans[j]*f[st[i]]+jw;jw=ans[j]/10;ans[j]%=10;}
		while(jw){ans[++ans[0]]=jw%10;jw/=10;}
	}
	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