首页 > ACM题库 > HDU-杭电 > HDU 3266-Hamlet’s gambling[解题报告]HOJ
2014
03-13

HDU 3266-Hamlet’s gambling[解题报告]HOJ

Hamlet’s gambling

问题描述 :

“There are a thousand Hamlets in a thousand people’s eyes. ”
    —-W. William Shakespeare

Lotus is a big fan of Shakespeare. Her favorite tragedy written by Shakespeare is Hamlet, one of the most popular works in English language. However, since Lotus is really a merciful and kindhearted girl, she doesn’t like the scene of the final match, in which Hamlet fenced against Laertes. Once she had a dream of Hamlet. In that dream, Hamlet fought with Laertes in another way: flipping coins.

It sounds like gambling. In order to flip the coin in an absolutely fair way, Hamlet got a monkey to do this job instead of people. Before the monkey started to flip, Hamlet and Laertes respectively wrote down an arbitrary sequence of results (we call it a “pattern”). For example, Hamlet wrote down “Head, Tail, Head” while Laertes wrote down “Head, Head, Tail, Tail”.It was guaranteed that the pattern of Hamlet’s did not occur within the pattern of Laertes’, nor did the pattern of Laertes’ occur within the pattern of Hamlet’s. Then the monkey began to flip the coin over and over and generated a sequence of results, like “Head, Head, Tail, Head, Tail …” At any time, if the monkey obtained Hamlet’s pattern, it stopped flipping and Hamlet won. Otherwise, if the monkey obtained Laertes’s pattern, it also stopped flipping and Laertes won.

One example of the gambling is like following: Hamlet’s pattern was “HHT” (H=Head, T=Tail) and his rival’s pattern was “HTTT”. The monkey flipped the coin and obtained “H, T, H, T, T, H, T, T, T”. At that time, Laertes’ pattern appeared at the end of the sequence, so the monkey stopped and the judge declared that Laertes won the game.

Now your task is to decide that in Lotus’ gambling, who has the higher probability to win the game. Pay attention that since the monkey has no bias, the probabilities to get head or tail in one flip are always equal.

输入:

The input contains several test cases. The first line of each case contains two positive integers N and M (0<N, M<=100000). N is the length of Hamlet’s pattern and M is the length of Laertes’. The second line contains a string of length N, representing the pattern of Hamlet’s. The third line contains a string of length M, representing the pattern of Laertes’. All the strings only contain uppercase letters ‘H’ and ‘T’. The input ends by a line of two zeros.

输出:

The input contains several test cases. The first line of each case contains two positive integers N and M (0<N, M<=100000). N is the length of Hamlet’s pattern and M is the length of Laertes’. The second line contains a string of length N, representing the pattern of Hamlet’s. The third line contains a string of length M, representing the pattern of Laertes’. All the strings only contain uppercase letters ‘H’ and ‘T’. The input ends by a line of two zeros.

样例输入:

1 1
H
T
1 2
T
HH
0 0

样例输出:

Equal
Hamlet

Hint
For the first sample case, to end the game, one flip is enough. If it is head, Hamlet wins. Otherwise Laertes wins. As a result, both of them has 1/2 probability to win. For the second sample case, if the first flip is tail, Hamlet wins. Otherwise if the second flip is tail, also Hamlet wins. Otherwise Laertes wins. So the probability that Hamlet wins the game is 3/4, while the probability that Laertes wins is 1/4. Hamlet has a better chance.

#include<cstdio>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
const int mn=100100,M=379177,base=213;
int n,m;
 
#define hf(a) ((a)&0x7fffffff)%M
struct node {
 	node *nxt;
	int k,len;
} *hash[M],pool[M];
int pp;
 
node* find(int k1,int len) {
 	for(node *p=hash[hf(k1)];p;p=p->nxt)
		if(k1==p->k && len==p->len)return p;
	return 0;
}
 
void insert(int k,int len) {
	int h=hf(k);
	pool[pp].k=k;
	pool[pp].len=len;
	pool[pp].nxt = hash[h];
	hash[h]=&pool[pp++];
}
 
char ts[mn];
string a,b;
vector<int> a1,b1,a2,b2;
int pw[mn];
 
void getbit(string &str1,string &str2,vector<int> &bit)
{
	int len1,len2;
	len1=str1.size();
	len2=str2.size();
	bit.clear();
	int key=0;
	memset(hash,0,sizeof(hash));
	pp=0;
	for(int i=0;i<len1;i++)
	{
		key+=str1[len1-i-1]*pw[i];
		insert(key,i+1);
	}
	key=0;
	for(int i=0;i<len2 && i<len1;i++)
	{
		key*=base;
		key+=str2[i];
		node *p=find(key,i+1);
		if(p)bit.push_back(1);
		else bit.push_back(0);
	}
	reverse(bit.begin(),bit.end());
}
 
void mu(vector<int> &a,vector<int> &b)
{
	int i,j,c=0,tmp;
	i=a.size()-1; j=b.size()-1;
	while(1)
	{
		if(i<0 && j<0)break;
		if(i>=0)c+=a[i];
		if(j>=0)c-=b[j];
		if(c<0) { a[i]=2+c; c=-1; }
		else { a[i]=c; c=0; }
		i-=1;
		j-=1;
	}
}
 
int main()
{
	pw[0]=1;
	for(int i=1;i<mn;i++)pw[i]=pw[i-1]*base;
	while(1)
	{
		scanf("%d%d",&n,&m);
		if(n==0 && m==0)break;
		scanf("%s",ts);
		a=ts;
		scanf("%s",ts);
		b=ts;
		getbit(b,b,b1);
		getbit(b,a,b2);
		getbit(a,a,a1);
		getbit(a,b,a2);
		mu(b1,b2);
		mu(a1,a2);
		int al=0,bl=0;
		for(bl=0;bl<b1.size();bl++)if(b1[bl]!=0)break;
		for(al=0;al<a1.size();al++)if(a1[al]!=0)break;
		if(b1.size()-bl!=a1.size()-al)
		{
			if(b1.size()-bl>a1.size()-al)printf("Hamlet\n");
			else printf("Laertes\n");
		}
		else
		{
			bool f=1;
			while(1)
			{
				if(bl>=b1.size())break;
				if(b1[bl]!=a1[al])
				{
					if(b1[bl]>a1[al])printf("Hamlet\n");
					else printf("Laertes\n");
					f=0;
					break;
				}
				bl++;
				al++;
			}
			if(f)printf("Equal\n");
		}
	}
	return 0;
}

  1. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。