首页 > ACM题库 > HDU-杭电 > hdu 2738 Frugal Search[解题报告]hoj
2014
02-14

hdu 2738 Frugal Search[解题报告]hoj

Frugal Search

问题描述 :

For this problem you will write a search engine that takes a query, searches a collection of words, and finds the lexicographically smallest word that matches the query (i.e., the matching word that would appear first in an English dictionary). A query is a sequence of one or more terms separated by single vertical bars ("|"). A term is one or more letters followed by zero or more signed letters. A signed letter is either +s ("positive" s) or -s ("negative" s), where s is a single letter. All letters are lowercase, and no letter will appear more than once within a term. A query will not contain spaces. A term matches a word if the word contains at least one of the unsigned letters, all of the positive letters, and none of the negative letters; a query matches a word if at least one of its terms matches the word.

输入:

The input consists of one or more test cases followed by a line containing only "#" that signals the end of the input. Each test case consists of 1�100 words, each on a line by itself, followed by a line containing only "*" that marks the end of the word list, followed by one or more queries, each on a line by itself, followed by a line containing only "**" that marks the end of the test case. Each word will consist of 1�20 lowercase letters. All words within a test case will be unique. Each query will be as defined above and will be 1�79 characters long.

输出:

The input consists of one or more test cases followed by a line containing only "#" that signals the end of the input. Each test case consists of 1�100 words, each on a line by itself, followed by a line containing only "*" that marks the end of the word list, followed by one or more queries, each on a line by itself, followed by a line containing only "**" that marks the end of the test case. Each word will consist of 1�20 lowercase letters. All words within a test case will be unique. Each query will be as defined above and will be 1�79 characters long.

样例输入:

elk
cow
bat
*
ea
acm+e
nm+o|jk+l
**
debian
slackware
gentoo
ubuntu
suse
fedora
mepis
*
yts
cab-e+n
r-e|zjq|i+t|vs-p+e-u-c
**
#

样例输出:

bat
NONE
elk
$
gentoo
ubuntu
NONE
$

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <ctime>

#include <iostream>

#include <string>

#include <vector>

#include <map>

#include <set>

#include <algorithm>

using namespace std;

#define pub(x) push_back(x)

#define x first

#define y second

#define MP make_pair

typedef long long ll;

typedef long double real;



struct word
{
	string t;
	int s[30];
	void make()
	{
		memset(s, 0, sizeof s);
		for (size_t i = 0; i < t.size(); ++i)
			s[t[i]-'a']++;
	}
} dic[121]; 
char s[100];

int b[80][30];
bool cmp(const word &a, const word &b)
{ return a.t < b.t; }

bool match(int *s, int k)
{
	bool us = false, un =false;
	for (int i = 0; i < 26; ++i)
	{
		if (b[k][i] == 1 && s[i] == 0) return false;
		if (b[k][i] == 2 && s[i] > 0) return false;
		if (b[k][i] == 3 && s[i] > 0) us = true;
		if (b[k][i] == 3) un = true;
	}
	//printf("%d\n", k);
	if (!un) return true;
	return us;
}


int main()

{
	while (1)
	{
		gets(s);
		if (s[0] == '#') break;
		int m = 0;
		while (s[0] != '*')
		{
			dic[++m].t = s;
			dic[m].make();
			gets(s);
		}
		sort(dic + 1, dic + 1 + m, cmp);
		for (int i = 1; i <= m; ++i) dic[i].make();
		//for (int i = 1; i <= m; ++i){puts(dic[i].t.c_str());}	puts("----");
		//printf("%d\n", dic[1].s[0]);
		memset(b, 0, sizeof b);
		while (1)
		{
			gets(s);
			if (s[0] == '*') break;
			memset(b, 0, sizeof b);
			int k = 1;
			for (int i = 0; s[i]; ++i)
				if ('a' <= s[i]  && s[i] <= 'z')
				{
					if (i > 0 && s[i - 1] == '+')
						b[k][s[i] - 'a'] = 1; else
					if (i > 0 && s[i - 1] == '-')
						b[k][s[i] - 'a'] = 2; else
						b[k][s[i] - 'a'] = 3;
				} else
				if (s[i] == '|') 
					++k;
			//printf("%s %d %d\n", s, b[1]['e' - 'a'] , b[1]['a' - 'a']);
			int ans = -1;
			for (int i = 1; i <= m; ++i)
			{
				for (int j = 1; j <= k; ++j)
				if (match(dic[i].s, j)) {ans = i; break;}
				if (ans >= 0) break;
			}
			if (ans == -1) puts("NONE"); 
				else puts(dic[ans].t.c_str());
				
		}
		puts("$");
	}
	return 0;

}

  1. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  2. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.