Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

数据量大时候果然要注意输入的时间,用cin超时,改用gets就AC了

Posted by lzs12348 at 2012-06-24 02:39:45 on Problem 1002 and last updated at 2012-06-24 02:43:17
参考了这位大牛的代码,多谢
http://poj.org/showmessage?message_id=171227

本来是很讨厌用scanf,gets和printf的,很不方便,很容易出错,但数据量大时候果然要注意输入的时间,用cin超时,改用gets就AC了

提交情况:同样的代码
        用G++,984K,391MS	
        用C++,556K,297MS
看来还是C++快些

有几点注意:
1、输入时候将每行转换成整数,可以提前将字母到数字的映射存为数组,相当于hash。
   最初是没有转换成整数,而是直接转换成长度为7的字符串,结果就超时了。
2、对于以000开头的输入,只要在输出的时候用0占位就可以了,如num是输出的号码,cnt是计数
  printf("%03d-%04d %d", num / 10000, num % 10000, cnt)
3、计数的时候不用map,可以边输出边计数。也就是输出时间就是n。

下面是AC code:

#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

string map("2223334445556667#77888999#"); 
          //ABCDEFGHIJKLMNOPQRSTUVWXYZ
char s[40];

int convert();   // convert s to standard form s1

int main()
{
	int n, cnt;

	scanf("%d", &n); getchar();
	vector<int> ivec(n);
	for (int i = 0; i < n; i++) {
		gets(s);
		ivec[i] = convert();
	}
	sort(ivec.begin(), ivec.end());

	// output the result
	bool no_duplicate = true;
	for (int i = 1; i < n; i++) {
		cnt = 1;
		while (i < n && ivec[i] == ivec[i - 1]) {
			cnt++;
			i++;
		}
		if (cnt > 1) {
			printf("%03d-%04d %d\n", ivec[i-1]/10000, ivec[i-1]%10000, cnt);
			no_duplicate = false;
		}
	}
	if (no_duplicate)
		printf("No duplicates. \n");

	return 0;
}

int convert()
{
	int sum = 0;
	for (unsigned i = 0; s[i] != '\0'; i++) {
		if (s[i] >= '0' && s[i] <= '9')
			sum = sum * 10 + (s[i] - '0');
		else if (s[i] >= 'A' && s[i] <= 'Z' && s[i] != 'Q' && s[i] != 'Z')
			sum = sum * 10 + (map[s[i] - 'A'] - '0');
	}
	
	return sum;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator