Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

终于过了,要建两个字碘树,附代码(注释掉的部分是WA的历程QAQ)

Posted by KatrineYang at 2016-05-27 11:56:00 on Problem 1451 and last updated at 2016-05-27 11:56:32
//============================================================================
// 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator