輸入總結

    兩道水題，但輸入要用點心。

Babelfish

Time Limit: 3000MS	Memory Limit: 65536K
Total Submissions: 32291	Accepted: 13885

Description

You have just moved from Waterloo to a big city. The people here speak an incomprehensible dialect of a foreign language. Fortunately, you have a dictionary to help you understand them.

Input

Input consists of up to 100,000 dictionary entries, followed by a blank line, followed by a message of up to 100,000 words. Each dictionary entry is a line containing an English word, followed by a space and a foreign language word. No foreign word appears more than once in the dictionary. The message is a sequence of words in the foreign language, one word on each line. Each word in the input is a sequence of at most 10 lowercase letters.

Output

Output is the message translated to English, one word per line. Foreign words not in the dictionary should be translated as "eh".

Sample Input

dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay

atcay
ittenkay
oopslay
      

Sample Output

cat
eh
loops
      

Hint

Huge input and output,scanf and printf are recommended. 字典樹模闆題。

#include<stdio.h>
#include<string.h>
#define max 26
typedef struct TrieNode
{
	int ncount;
	char ch[26];
	TrieNode *next[max];
}TrieNode;
int allocp=0;
TrieNode Memory[1000000];
TrieNode *root;
void InitTrieRoot(TrieNode**pRoot)
{
	*pRoot=NULL;
}
TrieNode *creatTrie()
{
	int i,k;
	TrieNode *p;
	p=&Memory[allocp++];
	p->ncount=0;
	p->ch[0]=0;
	for(i=0;i<max;i++)
	{
		p->next[k]=NULL;
	}
	return p;
}
void InsertTrie(char *s,char *res)
{
	int i,k;
	TrieNode *p=root;
	i=0;
	while(s[i])
	{
		k=s[i++]-'a';
		if(p->next[k]);
		else
		p->next[k]=creatTrie();
		p=p->next[k];
	}
	strcpy(p->ch,res);
	p->ncount=1;
}
char *SearchTrie(char *s)
{
	int i,k;
	TrieNode *p=root;
	i=0;
	while(s[i])
	{
		k=s[i++]-'a';
		if(p->next[k]==NULL) return "eh";
		else p=p->next[k];
	}
	if(p->ncount) return p->ch;
	else return "eh";
}
int main()
{
	int i,j,k,len,m;
	char a[10005],b[10005],c[10005],d[10005];
	InitTrieRoot(&root);
	root=creatTrie();
	memset(b,0,sizeof(b));
    while(gets(a)&&a[0])//确定結束字典輸入
    {
    	len=strlen(a);m=0;k=0;
    	for(i=0;i<len;i++)
    	{
    		if(a[i]==' ') {k++;i++;}//空格分開兩單詞
	      if(k==0)
	      {
      		b[i]=a[i];
      	  }
      	  else
      	  {
  	      	c[m++]=a[i];
  	      }
    	}
    	InsertTrie(c,b);
    }   
    while(scanf("%s",d)!=EOF)
	{
		printf("%s\n",SearchTrie(d));
	}   
	return 0;
           

}
           

Maximum GCD 

Input: Standard Input

Output: Standard Output

Given the N integers, you have to find the maximum GCD(greatest common divisor) of every possible pair of these integers.

Input

The first line of input is an integer N(1<N<100) that determines the number of test cases.

The following N lines are the N test cases. Each test case contains M (1<M<100) positive integers that you have to find the maximum of GCD.

Output

For each test case show the maximum GCD of every possible pair.

Sample Input	Output for Sample Input
3 10 20 30 40 7  5 12 125 15 25	20 1 25

數論，求最大的最大公約數。

#include<stdio.h>
#include<math.h>
#include<string.h>
int shu[100000005],t;
char a[100000005];
int gcd(int x,int y)
{
	int c;
	if(x<y){
		t=x,x=y,y=t;
	}
	c=x%y;
	while(c!=0)
	{
		x=y;y=c;c=x%y;
	}
	return y;
}
int main()
{
	int t,i,j,k,b,n,count,s,max=0,flag;
	char c;
	
	while(scanf("%d",&t)!=EOF)
	{
	  getchar();
	   if(t==0) break;
		while(t--)
		{
			//memset(shu,0,sizeof(shu));
			count=0,s=0,max=0;
		   gets(a);
		   n=strlen(a);
		   shu[count]=0;
		   for(i=0;i<n;i++)
		   {
   			  if(a[i]!=' ')
   			  shu[count]=shu[count]*10+(a[i]-'0');
   			  if(a[i]==' '&&a[i+1]>='0'&&a[i+1]<='9')
   			  {count++;s++;shu[count]=0;}
   		   }s++;
   		   /*while(1)//一種更好的輸入方法
   		   {
   		   	  scanf("%d",&shu[s++]);
   		   	  while((c=getchar())==' ');
   		   	  ungetc(c,stdin);
   		   	  if(c==10||c==-1) break;
   		   }*/
   		   for(i=0;i<s-1;i++)
   		   {
   		   	  for(j=i+1;j<s;j++)
   		   	  {
   		   	  	k=gcd(shu[i],shu[j]);
  	   		   	if(max<k)
  	   		   	max=k;
   		      }
   		   }printf("%d\n",max);
		   //printf("%d\n",s+1);
		}	
	}
	return 0;
}
           

對于輸入資料數量不定的題，往往能激發我們這些勞動人民的智慧。小細節有大用處。 僅以此文，展現一個弱弱的我。