40分和80分的同学可以过来这里看看

P1037 [NOIP2002 普及组] 产生数

40分的原因:只考虑到了自己与别人的一条边的关系,实际上没有考虑到例如2->3,3->5则2->5的情况,这个时候需要的是结合图(构造有向图),构造floyd的最短路表示各个数位之间的关系。 80分的原因:炸了数据范围(最坑的地方是最后一点ans的long long 只能到21位,而正解22位,肯定是故意的!!!) 而且用unsigned long long也是一样的。 望有所帮助
by Lyrics @ 2017-10-22 21:58:37


而且要注意的是0是不能做右边的数的(题目提供的)
by Lyrics @ 2017-10-22 21:59:13


40分评测记录: https://www.luogu.org/record/show?rid=3893359 80分评测记录: https://www.luogu.org/record/show?rid=3893889
by Lyrics @ 2017-10-22 22:00:04


此题解>>顶顶
by Preccc_LHW @ 2017-10-25 22:28:14


需要用高精才能做,因为long long是不能用的 ```cpp #include<iostream> #include<cstdio> #include<cstring> using namespace std; int cng[10][11],num[10]; //cng[i][j]代表数字i的第j种变法是什么,num[i]代表数字i有多少变法 (这里没包括它自己) int n[35],ans[35];//ans最大是10的30次方 int k,a,b,len=0; char x; bool find(int x,int y){//找数字x是否已经有y这种变法 for(int i=1;i<=num[x];i++) if(cng[x][i]==y) return 1; if(x==y) return 1;//已经有或者是其本身返回1 return 0; } int main(){ //freopen("number.in","r",stdin); //freopen("number.out","w",stdout); while(scanf("%c",&x)&&x!=' ') n[++len]=x-48; cin>>k; for(int i=1;i<=k;i++){ scanf("%d%d",&a,&b); cng[a][++num[a]]=b; } //对i的一种变法找它有的变法,如果不存在在i的变法中,则加上它,num[i]+1; for(int i=0;i<=9;i++) for(int j=1;j<=num[i];j++)//此为a处 for(int k=1;k<=num[cng[i][j]];k++) if(!find(i,cng[cng[i][j]][k])) cng[i][++num[i]]=cng[cng[i][j]][k]; //此处增加立刻使得num[i]增长,a处发生变化 //下面是高精 ans[0]=1; for(int i=1;i<=len;i++){//对于每一个数字,乘它的变法数 int d=n[i],p=0; if(num[d]){ for(int i=0;i<=31;i++){ ans[i]=ans[i]*(num[d]+1)+p; p=ans[i]/10; ans[i]%=10; } } } bool ok=0; for(int i=31;i>=0;i--) if(ans[i]||ok){ ok=1; cout<<ans[i]; } return 0; } ```
by 风行哥 @ 2017-10-31 21:51:12


%%%%%%%%%%%%%%%%%%%%%%%%%
by 旴谨 @ 2018-09-28 22:22:22


Orz %%%
by clarkwang @ 2019-12-28 13:13:29


|