天天看点

输入总结

    两道水题,但输入要用点心。

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;
}
           

对于输入数据数量不定的题,往往能激发我们这些劳动人民的智慧。小细节有大用处。 仅以此文,展现一个弱弱的我。

继续阅读