[Codeforces] 2

2A题目

The winner of the card game popular in Berland "Berlogging" is determined according to the following rules. If at the end of the game there is only one player with the maximum number of points, he is the winner. The situation becomes more difficult if the number of such players is more than one. During each round a player gains or loses a particular number of points. In the course of the game the number of points is registered in the line "name score", where name is a player's name, and score is the number of points gained in this round, which is an integer number. If score is negative, this means that the player has lost in the round. So, if two or more players have the maximum number of points (say, it equals to m) at the end of the game, than wins the one of them who scored at least m points first. Initially each player has 0 points. It's guaranteed that at the end of the game at least one player has a positive number of points.

Input
The first line contains an integer number n (1 ≤ n ≤ 1000), n is the number of rounds played. Then follow n lines, containing the information about the rounds in "name score" format in chronological order, where name is a string of lower-case Latin letters with the length from 1 to 32, and score is an integer number between -1000 and 1000, inclusive.

Output
Print the name of the winner.

题目大意：游戏结束后，得分最多（用maxSco表示最大分）者获胜（分数可为负），若有多个人分数最多，则得分先达到maxSco者获胜；每一轮输入的名字和分数是此轮游戏的结果，要注意的是游戏结果可以是负数；
首先我想到了用字符串哈希表的方法将同名的分数累加起来，实时更新分数的最大值（为了应对分数有负数的情况），自己感觉没什么问题，但是一直卡在test10结果错误
代码如下:

//codeforces_2A
#include<iostream>
#include<cstring>
using namespace std;
int hashtable[100000]={0};
struct player{
	char  name[33];
	int score,order,max_sc,max_order;
}player1[1005];
// BKDR Hash Function
unsigned int BKDRHash(char *str)
{
    unsigned int seed = 1313;//也可以乘以31、131、1313、13131、131313..
    unsigned int hash = 0;
    while(*str)
    {
        hash = hash*seed + (*str++);
    }
    return hash%0x7FFF;//MAX代表hash表长度
}

int exchange_char(char str[]){
	int m=0;
	int i=0;
	while(str[i]!='\0'){
		m+=m*2+(str[i++]-'a');
	}
	return m;
}

int main(){
	int n,num=0,m=-100000000,t=1,sc;

	char name1[35];
	cin>>n;
		for(int i=1;i<=n;i++){
			cin>>name1>>sc;
			//int j = exchange_char(name1);
			int j = BKDRHash(name1);
			//cout<<"hash:"<<j<<endl;
			//cout<<"zifu:"<<j<<endl;
			if(hashtable[j]){
				player1[hashtable[j]].score+=sc;
				player1[hashtable[j]].order=i;
				if(player1[hashtable[j]].max_sc < player1[hashtable[j]].score){
					player1[hashtable[j]].max_sc = player1[hashtable[j]].score;
					player1[hashtable[j]].max_order = player1[hashtable[j]].order;
				}
			}else{
				//cout<<sc<<endl;
				hashtable[j]=t++;
				player1[hashtable[j]].score=sc;
				strcpy(player1[hashtable[j]].name,name1);
				player1[hashtable[j]].order=i;
				player1[hashtable[j]].max_sc = player1[hashtable[j]].score;
				player1[hashtable[j]].max_order = player1[hashtable[j]].order;
			}
		}
		//cout<<"t:"<<t<<endl;
		int j=1,k=0;
		m=0;
		while(j<=t){
			if(m<player1[j].max_sc	){
				m=player1[j].max_sc;
				k=player1[j].max_order;
				num = j;
			}
			else if(m == player1[j].max_sc	){
				if(k>player1[j].max_order)
				{
					num = j;
					m=player1[j].max_sc;
					k=player1[j].max_order;
				}
			}
			j++;
		}
		cout<<player1[num].name<<endl;;

	return 0;
}

在网上查询的过程中，当使用map时，可以实现简单的解法，参考了这个老哥的代码
他的思路是使用map来存储输入的数据：

用string记录所有的name，用数组记录每局的结果，用map记录每个的累积得分
扫描map，找到最大的分数
寻找最先达到最大值的人
代码如下：

#include <map>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAXN 10010
#define INF 0x7fffffff
#define LL long long
using namespace std;

int num[MAXN];
string str[MAXN];
struct {
    string str;
    int num;
}maxs;
map<string, int> mp, mps;

int main(void) {
    int T;
    scanf("%d", &T);
    for(int i=0; i<T; ++i) {
        cin >> str[i] >> num[i];
        mp[str[i]] += num[i];
    }

    maxs.num = 0;//找到map中的最大值
    for(int i=0; i<T; ++i) {
        if(maxs.num < mp[str[i]]) {
            maxs.str = str[i];
            maxs.num = mp[str[i]];
        }
    }
 	//找到第一个大于max的选手
    for(int i=0; i<T; ++i) {
        mps[str[i]] += num[i];
        if(mps[str[i]] >= maxs.num && mp[str[i]] >= maxs.num) {
            cout << str[i] << endl;
            return 0;
        }
    }
    return 0;
}

2B题目

time limit per test2 secondsmemory limit per test64 megabytesinputstandard inputoutputstandard outputThere is a square matrix n × n, consisting of non-negative integer numbers. You should find such a way on it that

starts in the upper left cell of the matrix;
each following cell is to the right or down from the current cell;
the way ends in the bottom right cell.
Moreover, if we multiply together all the numbers along the way, the result should be the least "round". In other words, it should end in the least possible number of zeros.

Input
The first line contains an integer number n (2 ≤ n ≤ 1000), n is the size of the matrix. Then follow n lines containing the matrix elements (non-negative integer numbers not exceeding 109).

Output
In the first line print the least number of trailing zeros. In the second line print the correspondent way itself.
题目大意：