SDUTOJ 3059 C#中类的继承性 ——字典树（哈希用法），map

本文主要是介绍SDUTOJ 3059 C#中类的继承性 ——字典树（哈希用法），map，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

C#中类的继承性

Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^

题目描述

在C#中，类的继承遵循以下原则。

（1）派生类只能从一个类中继承，即单继承。

（2）类的继承是可以传递的，例如：假设类C继承于类B，类B又继承于类A，那么类A是类C的祖先类。

那么现在问题来了，给出一些类的继承关系，求出最多的继承层数。

输入

多组输入。

对于每组输入。

第一行输入一个整数n(1 <= n <= 50000)。

接下来的n行，每行只会符合下面两种格式：

（1）仅包含一个类名。此时表明此类是基类，即不继承与任何类。

（2）类名A ：类名B。此时表明类A继承于类B。

类名仅由小写英文字母且长度 <= 6。

数据保证合法。

输出

对于每组数据，输出最多的继承层数。

示例输入

2abcxyz:abc

示例输出

提示

来源

zmx

#include <stdio.h>
#include <string.h>struct node
{int flag;int next[26];
}ls[6000010];int pr[50010];
int top,num;int creat(char sr[])
{int xb = 0,zh;char *p = sr;while(*p != '\0'){zh = *p - 'a';if(!ls[xb].next[zh]){ls[top].flag = 0;memset(ls[top].next,0,sizeof(ls[top].next));ls[xb].next[zh] = top++;}xb = ls[xb].next[zh];p++;}if(!ls[xb].flag)ls[xb].flag = num++;return ls[xb].flag;
}int main()
{char str[15];char sr1[10],sr2[10];int n;while(~scanf("%d",&n)){num = 1;memset(ls[0].next,0,sizeof(ls[0].next));top = 1;int mx = -(1 << 28);for(int i = 0;i < n;i++){scanf("%s",str);char *p = str;char *q = sr1;while(*p != '\0'){if(*p == ':')break;*q = *p;p++;q++;}*q = '\0';if(*p != '\0'){q = sr2;p++;while(*p != '\0'){*q = *p;p++;q++;}*q = '\0';int x = creat(sr1);int y = creat(sr2);// printf("pr[y] = %d\n",pr[y]);pr[x] = pr[y] + 1;if(mx < pr[x])mx = pr[x];}else{int x = creat(sr1);pr[x] = 1;}}printf("%d\n",mx);}return 0;
}

当时想多了，比赛完后才发现。。。。。就是用字典树就是自己想多了。。。。。。不多解释

C++STL中的map也能过。。。。。

这篇关于SDUTOJ 3059 C#中类的继承性 ——字典树（哈希用法），map的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！