[UVa] 10126 - Zipf's Law

題目網址: http://goo.gl/WlHph1

題 意: 給定一篇文章，定義一個字為連續的字元，且不記大小寫，問文章中出現次數是 n 的有哪些字。


解法: 二叉搜尋樹來存取資訊，可以用STL map。

TAG: binary search tree

注意:

程式碼:

	/**
	* Tittle: 10126 - Zipf's Law
	* Author: Cheng-Shih, Wong
	* Date: 2015/04/04
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <map>
	#include <string>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define sd second
	#define ft first
	typedef map<string,int> MST;
	// declarations
	int n;
	MST cnt;
	// functions
	inline const bool isalpha( char ch )
	{
	return ('a'<=ch&&ch<='z')||('A'<=ch&&ch<='Z');
	}
	inline const char tolower( char ch )
	{
	if( 'A'<=ch && ch <= 'Z' )
	ch = ch-'A'+'a';
	return ch;
	}
	// main function
	int main( void )
	{
	string word;
	char buf;
	MST::iterator it;
	bool nl = false;
	bool hasans;
	// input
	while( scanf( "%d", &n )==1 ) {
	// init
	cnt.clear();
	hasans = false;
	if( nl ) putchar('\n');
	else nl = true;
	// solve & output
	while( true ) {
	word.clear();
	while( !isalpha(buf=getchar()) );
	word += tolower(buf);
	while( isalpha(buf=getchar()) )
	word += tolower(buf);
	if( word == "endoftext" ) break;
	++cnt[word];
	}
	for( it=cnt.begin(); it!=cnt.end(); ++it ) {
	if( (*it).sd == n ) {
	cout << (*it).ft << endl;
	hasans = true;
	}
	}
	if( !hasans ) puts("There is no such word.");
	}
	return 0;
	}

view raw 10126 - Zipf's Law.cpp hosted with ❤ by GitHub