hdu 1075 What Are You Talking About
16964 단어 HDU
제목: 비교적 간단 하고 이해 하기 쉬 우 며 여 기 는 설명 하지 않 습 니 다.
해법: 첫 번 째 방법: 맵 으로 비 추어 1000 + ms 소모;두 번 째 방법: 사전 트 리 로 처리, 500 + ms.
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cstdlib>
5 #include<cmath>
6 #include<algorithm>
7 #include<vector>
8 #define inf 0x7fffffff
9 using namespace std;
10 char s1[20],s2[20];
11 typedef struct NODE
12 {
13 NODE *child[26];
14 char str[20];
15 int ok;
16 NODE () {ok=0 ;str[0]=0 ;for (int i=0 ;i<26 ;i++) child[i]=NULL; }
17
18 }node;
19 void insert(node *root)
20 {
21 node *cur=root;
22 int len=strlen(s2);
23 int k;
24 for (int i=0 ;i<len ;i++)
25 {
26 k=s2[i]-'a';
27 if (cur->child[k]!=NULL)
28 {
29 cur=cur->child[k];
30 }else
31 {
32 node *q=new node;
33 q->ok=0;
34 q->str[0]=0;
35 for (int i=0 ;i<26 ;i++) q->child[i]=NULL;
36 cur->child[k]=q;
37 cur=cur->child[k];
38 }
39 }
40 cur->ok=1;
41 strcpy(cur->str,s1);
42 }
43 int findTree(node *root)
44 {
45 node *cur=root;
46 int len=strlen(s2);
47 for (int i=0 ;i<len ;i++)
48 {
49 int k=s2[i]-'a';
50 cur=cur->child[k];
51 if (cur==NULL) return 0;
52 }
53 if (cur->ok == 1) {printf("%s",cur->str);return 1;}
54 return 0;
55 }
56 void del(node *root)
57 {
58 for (int i=0 ;i<26 ;i++) if (root->child[i]) del(root->child[i]);
59 delete root;
60 root=NULL;
61 }
62 int main()
63 {
64 memset(s1,0,sizeof(s1));
65 memset(s2,0,sizeof(s2));
66 node *root=new node;
67 cin>>s1;
68 while (scanf("%s",s1)!=EOF)
69 {
70 if (strcmp(s1,"END")==0) break;
71 scanf("%s",s2);
72 //cout<<s1<<" "<<s2<<endl;
73 insert(root);
74 }
75 cin>>s1;
76 char s[3333];
77 memset(s,0,sizeof(s));
78 getchar();
79 while (gets(s))
80 {
81 //if (s[0]=='E' && s[1]=='N' && s[2]=='D') break;
82 if (strcmp(s,"END")==0) break;
83 memset(s2,0,sizeof(s2));
84 int cnt=0;
85 int flag=0;
86 int len=strlen(s);
87 for (int i=0 ;i<len ;i++)
88 {
89 if (s[i]>='a' && s[i]<='z')
90 {
91 flag=1;
92 s2[cnt++]=s[i];
93 }
94 else if (flag)
95 {
96 flag=0;
97 s2[cnt]=0;
98 int m=findTree(root);
99 if (!m) printf("%s",s2);
100 cnt=0;
101 memset(s2,0,sizeof(s2));
102 }
103 if (!flag) printf("%c",s[i]);
104 }
105 if (flag)
106 {
107 s2[cnt]=0;
108 int m=findTree(root);
109 if (!m) printf("%s",s2);
110 }
111 cout<<endl;
112 }
113 del(root);
114 //system("pause");
115 return 0;
116 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HDU] 4089 활성화 확률 DPdp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.