北大oj 1002 题目.cpp

北大OJ上的题目

#define MAXSIZE 100110
#include<stdio.h>
#include<string.h>

typedef struct {
	char a[MAXSIZE][10];
} sqlist;


void radixsort(sqlist &source, sqlist &destin, long n, long i)
{
	long j, memory[20], target;

	for(j = 0; j < 10; j ++) {
		memory[j] = 0;
	}
	for(j = 1; j <= n; j ++) { 
		memory[source.a[j][i] - '0'] ++;
	}
	for(j = 1; j < 10; j ++) {
		memory[j] += memory[j-1];
	}
	for(j = n; j > 0; j --) {
		target = memory[source.a[j][i] - '0'];
		strcpy(destin.a[target], source.a[j]);
		memory[source.a[j][i] - '0'] --;
	}
}


int main(void)
{
	long n, i, j, count;
	int k, l, flag;
	char str[100];
	sqlist datas, data;
	scanf("%ld", &n);
	for(i = 1; i <= n; i ++) {
		scanf("%s", str);
		for(k = 0, l = 0; str[k] != '\0'; k ++) {
			if(str[k] == '-') {
				l ++;
			} else if(l != 0){
				str[k - l] = str[k];
			}
		}
		str[k - l] = '\0';
		for(j = 0; str[j] != '\0'; j ++) {
			switch(str[j]) {
				case 'A': ;
				case 'B': ;
				case 'C': str[j] = '2'; break;
				case 'D': ;
				case 'E': ;
				case 'F': str[j] = '3'; break;
				case 'G': ;
				case 'H': ;
				case 'I': str[j] = '4'; break;
				case 'J': ;
				case 'K': ;
				case 'L': str[j] = '5'; break;
				case 'M': ;
				case 'N': ;
				case 'O': str[j] = '6'; break;
				case 'P': ;
				case 'R': ;
				case 'S': str[j] = '7'; break;
				case 'T': ;
				case 'U': ;
				case 'V': str[j] = '8'; break;
				case 'W': ;
				case 'X': ;
				case 'Y': str[j] = '9'; break;
			}
		}
		strcpy(datas.a[i], str);
	}

	for(i = 1; i <= n; i ++) {
		strcpy(data.a[i], "");
	}
	for(i = 3; i > 0; i --) {
		radixsort(datas, data, n, i * 2);
		radixsort(data, datas, n, i * 2 - 1);
	}
	radixsort(datas, data, n, 0);


	for(i = 2, count = 0, strcpy(str, data.a[1]), flag = 0; i <= n; i ++) {
		if(strcmp(str, data.a[i]) == 0) {
			count ++;
		} else {
			if(count != 0) {
				flag = 1;
				for( j = 0; j < 3; j ++) {
					printf("%c", str[j]);
				}
				putchar('-');
				for( j = 3; j < 7; j ++) {
					printf("%c", str[j]);
				}
				printf(" %ld\n", count + 1);
				count = 0;
			}
			strcpy(str, data.a[i]);
		}
	}
	if(count != 0) {
		flag = 1;
		for( j = 0; j < 3; j ++) {
			printf("%c", str[j]);
		}
		putchar('-');
		for( j = 3; j < 7; j ++) {
			printf("%c", str[j]);
		}
		printf(" %ld\n", count + 1);
		count = 0;
	}
	if(flag == 0) {
		printf("No duplicates.\n");
	}
	return 0;
}