BestCoder Round 36($)(一、二題解題報告)

Strange Class
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 89    Accepted Submission(s): 71
Problem Description
In Vivid’s school, there is a strange class(SC). In SC, the students’ names are very strange. They are in the same format: 
anbncn (a,b,c must not be the same with each other). For example studens whose names are“abc”,”ddppqq” are in SC, however studens whose names are “aaa”,“ab”,”ddppqqq” are not in SC.
Vivid makes friends with so many students, he wants to know who are in SC.
 
Input
There are multiple test cases (about 10), each case will give a string S which is the name of Vivid’s friend in a single line.
Please process to the end of file.
[Technical Specification]
1≤|S|≤10 .
|S| indicates the length of S.
S only contains lowercase letter.
 
Output
For each case, output YES if Vivid’s friend is the student of SC, otherwise output NO.
 
Sample Input

   
   
   
   

    
    
    
    abc
bc
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    YES
NO
   
   
   
   

 
Source
BestCoder Round #36 ($)
 
問題を解く思想:

       ，        3   。
                    。
                   。

AC  code:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<string.h>
#include<string>
#define MAXN 1000010
#define LL long long
using namespace std;
int main()
{
	string s;
	int i,j,k,fg,t1,t2;
	while(cin>>s)
	{
		if(s.size()%3!=0)
		{
			printf("NO
");
		}
		else
		{
			if(s.size()==3)
			{
				if(s[0]!=s[1]&&s[1]!=s[2]&&s[0]!=s[3])
				{
					printf("YES
");
				}
				else
				{
					printf("NO
");
				}
			}
			else
			{
				fg=1;
				for(i=1;i<s.size()/3;i++)
				{
					if(s[i]!=s[i-1])
					{
						fg=0;
						break;
					}
				}
				for(j=i+1;fg&&j<i+s.size()/3;j++)
				{
					if(s[j]!=s[j-1])
					{
						fg=0;
						break;
					}
				}
				for(k=j+1;fg&&k<s.size();k++)
				{
					if(s[k]!=s[k-1])
					{
						fg=0;
						break;
					}
				}
				if(fg)
				{
					if(s[i-1]!=s[j-1]&&s[j-1]!=s[k-1]&&s[k-1]!=s[i-1])
					{
						fg=1;
					}
					else
					{
						fg=0;
					}
				}
				if(fg)
				{
					printf("YES
");
				}
				else
				{
					printf("NO
");
				}
			}
		}
	}
	return 0;
 } 

Gunner
Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 484    Accepted Submission(s): 223
Problem Description
Long long ago, there is a gunner whose name is Jack. He likes to go hunting very much. One day he go to the grove. There are 
n  birds and 
n  trees. The 
i−th  bird stands on the top of the 
i−th  tree. The trees stand in straight line from left to the right. Every tree has its height. Jack stands on the left side of the left most tree. When Jack shots a bullet in height H to the right, the bird which stands in the tree with height 
H  will falls.
Jack will shot many times, he wants to know how many birds fall during each shot.
a bullet can hit many birds, as long as they stand on the top of the tree with height of 
H .
 
Input
There are multiple test cases (about 5), every case gives 
n,m  in the first line, 
n  indicates there are 
n  trees and 
n  birds, 
m  means Jack will shot 
m  times.
In the second line, there are 
n  numbers 
h[1],h[2],h[3],…,h[n]  which describes the height of the trees.
In the third line, there are m numbers 
q[1],q[2],q[3],…,q[m]  which describes the height of the Jack’s shots.
Please process to the end of file.
[Technical Specification]
1≤n,m≤1000000(106)
1≤h[i],q[i]≤1000000000(109)
All inputs are integers.
 
Output
For each 
q[i] , output an integer in a single line indicates the number of birds Jack shot down.
 
Sample Input

   
   
   
   

    
    
    
    4 3
1 2 3 4
1 1 4
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    1
0
1


    
    
    
    
 
     
 
      Hint 
     
Huge input, fast IO is recommended. 
    
    
    
    
     
   
   
   
   

 
Source
BestCoder Round #36 ($)
 
問題を解く思想:

        ，              。          。
        hash，          。

  ：         ，  0    printf，  TLE！！！   puts  。。。

AC  code:

/*printf("%s
",s);
puts(s);
           
               （        ）
 puts()  ，              ，          。*/
#include<iostream>
#include<stdio.h>
#include<map>
#include<vector>
#include<set>
#include<cstdlib>
#include<string.h>
#include<algorithm>
#include<cmath>
#define MAXN 1000010
using namespace std;
struct node{
	int val;
	int num;
}a[MAXN];
int cnt;
int h[MAXN],q;
bool vis[MAXN];
bool cmp(node a,node b)
{
	return a.val<b.val;
}
int read()
{
	int fg=1,ret=0;
	char ch;
	ch=getchar();
	while(!(ch>='0'&&ch<='9')){
		if(ch=='-')
			fg=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		ret=ret*10+ch-'0';
		ch=getchar();
	}
	return ret*fg;
}
int er(int x)
{
	int l=1,r=cnt,mid;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(a[mid].val==x)
		{
			return mid;
		}
		else if(a[mid].val>x)
		{
			r=mid-1;
		}
		else
		{
			l=mid+1;
		}
	}
	return 0;
}
int main()
{
	int n,m,i;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(i=1;i<=n;i++)
		{
			h[i]=read();
		}
		sort(h+1,h+n+1);
		cnt=1;
		a[cnt].num=1;
		a[cnt].val=h[1];
		for(i=2;i<=n;i++)
		{
			if(h[i]==h[i-1])
			{
				a[cnt].num++;
			}
			else
			{
				a[++cnt].num=1;
				a[cnt].val=h[i];
			}
		}
		memset(vis,0,sizeof(vis));
		while(m--)
		{
			q=read();
			int id=er(q);
			if(vis[id]||id==0)
			{
				puts("0");
				//printf("0
");//   printf，  puts  ，  TLE！！！ 
			}
			else{
				printf("%d
",a[id].num);
				vis[id]=1;
			}
		}
		
	}
	return 0;
}