Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
终于过了,要建两个字碘树,附代码(注释掉的部分是WA的历程QAQ)//============================================================================ // Name : main1451.cpp // Author : // Version : // Copyright : Your copyright notice // Description : Hello World in C++, Ansi-style //============================================================================ #include <iostream> #include <string> using namespace std; /* class Word{ public: string word; int prob; Word(string s, int i): word(s), prob(i){ } Word(){ } }; */ //Word dict[1000]; //Word wNull = Word(); class node{ public: node* suc[8]; int maxProb; //int depth; string maxWord; node() { //depth = 0; maxProb = 0; maxWord = ""; for(int i = 0; i < 8; i++) suc[i] = NULL; } }; class preNode{ public: preNode* suc[26]; int prob; preNode(int p): prob(p){ for(int i = 0; i < 26; i++) suc[i] = NULL; } }; //preNode* dicts[1000]; int toInt(char c){ if(c >= 'a' && c <= 'c') return 2; if(c >= 'd' && c <= 'f') return 3; if(c >= 'g' && c <= 'i') return 4; if(c >= 'j' && c <= 'l') return 5; if(c >= 'm' && c <= 'o') return 6; if(c >= 'p' && c <= 's') return 7; if(c >= 't' && c <= 'v') return 8; if(c >= 'w' && c <= 'z') return 9; return 1; } int toIdx(int c){ return toInt(c + 'a'); } void rct(preNode* pR, node* r, string s = ""){ for(int i = 0; i < 26; i++){ if(pR->suc[i] == NULL) continue; int idx = toIdx(i) - 2; //cout << idx << endl; string news = s + (char)(i+'a'); //cout << news << endl; preNode* newpr = pR->suc[i]; //cout << newpr->prob << endl; node* newr = r->suc[idx]; if(newr == NULL){ r->suc[idx] = new node(); newr = r->suc[idx]; newr->maxProb = newpr->prob; newr->maxWord = news; } else{ if(newpr->prob > newr->maxProb){ newr->maxProb = newpr->prob; newr->maxWord = news; } } rct(newpr, newr, news); } } int main() { int cases; cin >> cases; for(int ii = 0; ii < cases; ii++){ cout << "Scenario #" << (ii+1) << ":" << endl; int numW; cin >> numW; node* root = new node(); preNode* preRoot = new preNode(0); //首先预处理 for(int jj = 0; jj < numW; jj++){ int prob; string s; cin >> s >> prob; //dict[jj] = Word(s, prob); preNode* cur = preRoot; int len = s.length(); for(int i = 0; i < len; i++){ int idx = s[i] - 'a'; if(cur->suc[idx] == NULL){ cur->suc[idx] = new preNode(prob); } else{ //cout << 1 << endl; cur->suc[idx]->prob += prob; } cur = cur->suc[idx]; } //dicts[jj] = cur; } //根据prenode的预处理数构建node树 rct(preRoot, root); /* for(int jj = 0; jj < numW; jj++){ dict[jj].prob = dicts[jj]->prob; } for(int jj = 0; jj < numW; jj++){ cout << dict[jj].word << " " << dict[jj].prob << endl; } for(int j = 0; j < numW; j++){ int prob = dict[j].prob; string s = dict[j].word; //cout << prob << " " << s << endl; int len = s.length(); node* cur = root; for(int i = 0; i < len; i++){ int idx = toInt(s[i]) - 2; //cout << idx << endl; if(cur->suc[idx] == NULL){ cur->suc[idx] = new node(); //cur->suc[idx]->depth = cur->depth + 1; cur->suc[idx]->maxProb = prob; cur->suc[idx]->maxWord = &dict[j]; } else{ int lMax = cur->suc[idx]->maxProb; if(lMax < prob){ cur->suc[idx]->maxProb = prob; cur->suc[idx]->maxWord = &dict[j]; } } //cout << (cur == root) << " " << idx << " " << cur->suc[idx]->maxWord->word << endl; cur = cur->suc[idx]; } } for(int i = 0; i < 8; i++) { if(root->suc[i] != NULL) cout << i << " " << root->suc[i]->maxWord->word << endl; } */ int numT; cin >> numT; for(int j = 0; j < numT; j++){ string s; cin >> s; int len = s.length() - 1; bool can = true; node* cur = root; for(int i = 0; i < len; i++){ int idx = s[i] - '2'; //cout << idx << endl; if(can == true && cur->suc[idx] == NULL) can = false; if(can == false) { cout << "MANUALLY" << endl; continue; } //Word w = *(cur->suc[idx]->maxWord); cout << cur->suc[idx]->maxWord << endl; cur = cur->suc[idx]; } cout << endl; } cout << endl; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator