绝望是一种怎样的体验

learningman 2月 06, 2018

CNM


完美的网络
小Z最近了解到了一种被称为完美网络的东西。
完美网络,是一个拥有N+1层的一个简单无向图(简单,指的是无重边,无自环),从0到N编号。每一层上面的节点只与下一层连边,而且第0层有且只有一个顶点。每一层的节点,与下一层节点的连边数是要求严格相同的,也就是说,对于第i-1层的节点,与第i层节点相连的边数必须是deg[i],而这个deg[i]必须在ll[i]和rr[i]的范围内。
对于一个完美网络,我们可以计算出该网络的完美度就是从第0层节点依次逐层到达第N层节点的不同的路径数。两条路径不同,当且仅当至少存在一个对应层的节点不同。
小Z希望计算出完美度至少是〖10〗^k(10的k次幂)且层数为N+1的最小的完美网络的对应点数。一个完美网络的大小即为该网络的点数。

输入格式:
第一行两个正整数N和k。
接下来N行,每行两个正整数表示ll[i]和rr[i].保证ll[i]<=rr[i].

输出格式:
一行一个正整数表示答案。若不存在答案则返回-1.

输入样例: 2 2 9 11 9 11输出样例: 21数据规模: 对于30%的数据,保证N<=5,k<=10. 对于100%的数据,保证N<=100,k<=200,1<=ll[i],rr[i]<=100.
#include <cstdio>#include <cstdlib>#include <algorithm>#include <iostream>#include <cstring>#include <cmath>#define maxn 101char numberN[300];int n,k;int ll[maxn],rr[maxn];int deg[maxn];long long point;int error=0;int sw;int cf(int gjd){ int ans=0; char numberM[300]; if(gjd=1) { return point; } else if(gjd=100) { point+=2; return point; } else { numberM[0]=(gjd/10)+48; numberM[1]=(gjd%10)+48; } int n = strlen(numberN), m = strlen(numberM); int a[n], b[m]; int i, j; for (i = 0, j = n - 1; i < n; i++, j--) { a[i] = numberN[j] - '0'; } for (i = 0, j = m - 1; i < m; i++, j--) { b[i] = numberM[j] - '0'; } int c[600]; for (i = 0; i < 300; i++) { c[i] = 0; } for (i = 0; i < n; i++) { for (j = 0; j < m; j++) { c[i + j] += a[i] * b[j]; } } for (i = 0; i < n + m; i++) { if (c[i] >= 10) { c[i + 1] += c[i] / 10; c[i] %= 10; } } for (j = 599; j > 0; j--) { if (c[j] != 0) break; } for (i = j; i >= 0; i--) { ans++; } return ans;}using namespace std;int main(){ freopen("network.in","r",stdin); freopen("network.out","w",stdout); memset(ll,0,sizeof(ll)); memset(rr,0,sizeof(rr)); memset(deg,0,sizeof(deg)); scanf("%d %d",&n,&k); for(int i=0; i<n; i++) scanf("%d %d",&ll[i],&rr[i]); for(int i=0; i<n; i++) deg[i]=ll[i]; sw=0;//位置标记 while(point<k) { while(point<k) { point=0; for(int i=0;i<n;i++) cf(deg[i]); //int exist=1; /*for(int i=0; i<n; i++) { if(deg[i]==1) { continue; } else if(deg[i]==100) { point+=2; } else { } }*/ /*for(int i=0; i<n ; i++) point=deg[i]*point;*/ //printf("%lld\n",point); deg[sw]++; //printf("deg[sw]=%d rr[sw]=%d point=%d\n",deg[sw],rr[sw],point); //system("pause"); if(deg[sw]>=rr[sw]) break; } sw++; //printf("one\n"); if(sw==n) { error=1; break; } } if (error==0) { printf("-1"); return 0; } int result=1; for(int i=0; i<n; i++) result+=deg[i]; printf("%d",result-2); fclose(stdin); fclose(stdout); return 0;}

本文采用 CC BY-NC-SA 3.0 协议进行许可,在您遵循此协议的情况下,可以自由共享与演绎本文章。
本文链接:https://learningman.top/archives/28.html

发表评论

电子邮件地址不会被公开。 必填项已用*标注




you're currently offline