今天终于把计算机三级考完了。。上机自然是没有压力,只愿笔试可以60以上水过。
最近做了些Trie树的水题,总结如下,神题还没敢去碰。。
Poj 1065
#include <cstdio> #include <cstring> struct Trie { bool flag; int next[2]; }trie[200]; int e; bool Insert (char str[]) { int i,p=1; bool f=true,f2=false; for (i=0;str[i];i++) { if (trie[p].next[str[i]-'0']==0) //构造新的节点 { trie[p].next[str[i]-'0']=++e; f2=true; //创建了一个新节点 } p=trie[p].next[str[i]-'0']; if (trie[p].flag) //如果这个节点是之前某个单词的结束 f=false; } trie[p].flag = true; //标记该点为一个单词的结束 if (f2==false) //如果没有创建新节点 f=false; return f; } int main () { #ifdef ONLINE_JUDGE #else freopen("read.txt","r",stdin); #endif char str[20]; for (int cas=1;~scanf("%s",str);cas++) { e=1; memset(trie,0,sizeof(trie)); Insert(str); bool flag=true; while (scanf("%s",str) && str[0]!='9') if (flag && Insert(str)==false) flag=false; if (flag) printf("Set %d is immediately decodable\n",cas); else printf("Set %d is not immediately decodable\n",cas); } return 0; }
Poj 1204
/*POJ 1204 Word Puzzles 题目:给出一个字母的矩阵。已知对于一个给定的单词(长度为len), 一定存在从矩阵某一个位置开始,沿着这个位置周围的八个方向之一的连续len个字母恰好组成这个单词。 求出这个位置和这个方向。 样例的第一行是三个数N(矩阵的行,N<=1000)、M(矩阵的列,M<=1000)和W(单词的个数)。 接下来给出这个矩阵和这W个单词。对于样例中给出的第一个单词MARGARITA ,答案是0 15 G,也就是从(0,15)这个位置开始向左的9个字母恰好组成这个单词。 现在已知A-H分别代表上、右上、右、右下、下、左下、左、左上。 思路:先将输入的W个单词插入到Trie树中。然后,暴力枚举矩阵中每个位置P的8个方向。 枚举时,从该位置P一直枚举到矩阵的边缘,在这个过程中,如果有某个字母有标记为是某个单词的最后一个字母,那么P就是该单词的位置。 */ #include <iostream> using namespace std; struct Trie { int id,next[26]; }trie[1000005]; int e; char map[1005][1005]; int dx[8]={-1,-1,0,1,1,1,0,-1}; int dy[8]={0,1,1,1,0,-1,-1,-1}; int n,m,w; int ans[1005][3]; void Insert (char str[],int num) { int p=1; for (int i=0;str[i];i++) { if (trie[p].next[str[i]-'A']==0) { trie[p].next[str[i]-'A']=++e; trie[e].id=-1; } p=trie[p].next[str[i]-'A']; } trie[p].id=num; //标记这个点为某单词的结尾 } void Search (int x,int y,int dir) { int p=1; int xx=x,yy=y; while (xx>=0 && xx<n && yy>=0 && yy<m) { if (trie[p].next[map[xx][yy]-'A']==0) break; else p=trie[p].next[map[xx][yy]-'A']; if (trie[p].id!=-1) { ans[trie[p].id][0]=x; ans[trie[p].id][1]=y; ans[trie[p].id][2]=dir; } xx+=dx[dir]; yy+=dy[dir]; } } int main () { #ifdef ONLINE_JUDGE #else freopen("read.txt","r",stdin); #endif scanf ("%d%d%d",&n,&m,&w); int i; char str[1005]; trie[1].id=-1; e=1; for (i=0;i<n;i++) scanf("%s",map[i]); for (i=0;i<w;i++) { scanf("%s",str); Insert (str,i); } for (i=0;i<n;i++) for (int j=0;j<n;j++) for (int k=0;k<8;k++) Search (i,j,k); for (i=0;i<w;i++) printf("%d %d %c\n",ans[i][0],ans[i][1],ans[i][2]+'A'); return 0; }
Poj 2001
/*题意:给你许多字符串,然后让你找出最短的前缀字符串。但不能跟下面的单词的前缀相同。 思路:trie建树,设置一个变量num,计算每个单词出现的次数。 查找的时候如果num = 1则说明这是第一次出现过的单词,直接返回。 */ #include <cstdio> struct Trie { int num,next[30]; }trie[1005*30]; int e; char str[1005][30],output[30]; void Insert (char str[]) { int i,p=1; for (i=0;str[i];i++) { if (trie[p].next[str[i]-'a']==0) //构造新的节点 { trie[p].next[str[i]-'a']=++e; trie[e].num=0; } p=trie[p].next[str[i]-'a']; trie[p].num++; } } void Search (char str[]) { int i,p=1; for (i=0;str[i];i++) { if (trie[p].num==1) return; printf("%c",str[i]); p=trie[p].next[str[i]-'a']; } } int main () { #ifdef ONLINE_JUDGE #else freopen("read.txt","r",stdin); #endif int n=0; e=1; while (~scanf("%s",str[n])) Insert(str[n++]); for (int i=0;i<n;i++) { printf("%s ",str[i]); Search (str[i]); printf("\n"); } return 0; }
Poj2418
/*POJ 2418 Hardwood Species 题目:给出N(N<=1000,000)棵树木,已知这N棵树木包含M(M<=10000)种。 输出每种树在给出的N棵树中所占的比率。(输出按照字母表升序输出)。 思路:结点中设置一个num域,表示树的数目。插入时结点保存该种树的数目。 输出时前序遍历输出。注意测试数据中有字母和空格以外的字符 */ #include <cstdio> struct Node { int num,next[95]; }; Node a[100005]; int n,len,e; char output[35]; void Insert (char str[]) { int i,p=1; for (i=0;str[i];i++) { if (a[p].next[str[i]-' ']==0) //构造新的节点 { a[p].next[str[i]-' ']=++e; a[e].num=0; } p=a[p].next[str[i]-' ']; } a[p].num++; } void PreTravers (int p) { int i; if (a[p].num) { for (i=0;i<len;i++) printf("%c",output[i]); printf(" %.4lf\n",a[p].num*100.0/n); } for (i=0;i<95;i++) if (a[p].next[i]) { output[len++]=i+' '; PreTravers (a[p].next[i]); len--; } } int main () { #ifdef ONLINE_JUDGE #else freopen("read.txt","r",stdin); #endif char str[35]; n=0; len=0; e=1; while (gets(str)) Insert (str),n++; PreTravers (1); return 0; }