http://acm.hdu.edu.cn/showproblem.php?pid=1075

C++版本一

題解：字典樹||map

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int using namespace std; typedef long long ll; //typedef __int128 lll; const int N=500000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,q; int ans,cnt,flag,temp; int a[N][26]; char str[N],rec[N],str1[N],str2[N]; map<string,string>p; bool en[N]; char cp[N][20]; void insert(char *s,char *s2){int len=strlen(s),p=0;for(int i=0;i<len;i++){int ch=s[i]-'a';if(a[p][ch]==0)a[p][ch]=++cnt;p=a[p][ch];}en[p]=1;strcpy(cp[p],s2); } void search(char* s){int len=strlen(s),p=0;for(int i=0;i<len;i++){int ch=s[i]-'a';if(a[p][ch]==0){printf("%s",s);return;}p=a[p][ch];}if(en[p])printf("%s",cp[p]);elseprintf("%s",s);}int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//scanf("%d",&n);//scanf("%d",&t);//while(t--){}scanf("%s",str);while(scanf("%s",str)){if(strcmp(str,"END")==0)break;scanf("%s",str2);insert(str2,str);}scanf("%s",str);getchar();while (gets(str) && strcmp(str, "END")) {int len = strlen(str);int idx = 0;for (int i=0;i<=len - 1;i++) {if (islower(str[i])) {rec[idx++] = str[i];} else {rec[idx] = 0;search(rec);idx = 0;printf("%c", str[i]);}}puts("");}//cout << "Hello world!" << endl;return 0; }

C++版本二

題解：

可以用map赤裸裸地做，但是比較花費時間，雖然這題時間給了5s，map解法是能過的。?
不過Trie解法500+ms，果然Trie字典樹才是正解啊。?
Trie入門題。

另外發現ios_base::sync_with_stdio(0)這句話是關閉IO同步的，如果把cin和gets混用就不同步...坑了好久..

#include <cstdio> #include <cstring> #include <cctype> #include <map> #include <iostream> #include <algorithm> using namespace std;#define repf(i,a,b) for(int i=(a);i<=(b);i++) typedef long long ll;string a, b; char s[3010]; map<string, string> mp;int main() {// ios_base::sync_with_stdio(0);cin >> a;while (cin >> a) {if (a == "END")break;cin >> b;mp[b] = a;}cin >> a;getchar();while (1) {gets(s);if (!strcmp(s, "END"))break;int len = strlen(s);a = "";repf (i, 0, len - 1) {if (islower(s[i])) {a += s[i];} else {if (mp.find(a) != mp.end())cout << mp[a];elsecout << a;a = "";cout << s[i];}}cout << endl;}return 0; }

C++版本三

#include <cstdio> #include <cstring> #include <cctype> #include <iostream> #include <algorithm> using namespace std;#define repf(i,a,b) for(int i=(a);i<=(b);i++) typedef long long ll;const int N = 3010; const int SIZE = 26;// pointer trie struct Node {char* val;Node *next[SIZE]; };struct PTrie {Node *root;PTrie() { root = newNode(); }void init() { del(root); root = newNode(); }inline int idx(char c) { return c - 'a'; }Node *newNode() {Node *u = new Node;repf (i, 0, SIZE - 1) {u->next[i] = NULL;}u->val = NULL;return u;}void insert(char *s, char *v) {Node *u = root;int len = strlen(s);repf (i, 0, len - 1) {int c = idx(s[i]);if (u->next[c] == NULL)u->next[c] = newNode();u = u->next[c];}u->val = new char[11];strcpy(u->val, v);}void find(char *s) {Node*u = root;int len = strlen(s);repf (i, 0, len - 1) {int c = idx(s[i]);if (u->next[c] == NULL) {printf("%s", s);return;}u = u->next[c];}if (u->val)printf("%s", u->val);elseprintf("%s", s);}void del(Node *rt) {if (rt == NULL)return;else {repf (i, 0, SIZE - 1)if (rt->next[i])del(rt->next[i]);}delete rt->val;delete rt;} } trie;char a[11], b[11]; char str[N], rec[N];int main() {// ios_base::sync_with_stdio(0);scanf("%s", a);while (scanf("%s %s\n", a, b) && strcmp(a, "END")) {//cout << a << b << endl;trie.insert(b, a);}while (gets(str) && strcmp(str, "END")) {int len = strlen(str);int idx = 0;repf (i, 0, len - 1) {if (islower(str[i])) {rec[idx++] = str[i];} else {rec[idx] = 0;trie.find(rec);idx = 0;printf("%c", str[i]);}}puts("");} }

?

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的What Are You Talking About的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。