[POJ 3283] Card Hands【Trie】

  • 2018-02-26
  • 0
  • 0

Problem:

Time Limit: 1000MS Memory Limit: 65536K

Description

Jim is writing a program for statistically analyzing card games. He needs to store many different card hands in memory efficiently. Each card has one of four suits and one of thirteen values. In his implementation, each hand is stored as a linked list of cards in a canonical order: the cards are first ordered by suit: all the clubs come first, followed by all the diamonds, then all the hearts, and finally the spades. Within each suit, the cards are ordered by value: A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K. Each hand contains at most one of any given card.

The card hands are using lots of memory. Jim therefore decides to try a more efficient representation. Whenever any two lists share a common tail, they can be updated to share one copy of the tail, and the other copy can be discarded. This process can be repeated until no two lists share a common tail.

Your job is to tell Jim how many linked list nodes he needs to store all the card hands.

Input

The input contains several test cases followed by a line containing 0. The first line of each case contains the number of card hands. Each subsequent line describes a card hand. It starts with a number indicating the number of cards in the hand. The cards follow, separated by spaces, in the canonical order defined above. For each card, the value is given first, followed by the suit (C, D, H, or S). There are at most 100,000 cards in all hands.

Output

For each test case, output a line containing the number of linked list nodes needed to store all the lists.

Sample Input

3
3 7D AH 5S
4 9C 3D 4D 5S
2 AH 5S
0

Sample Output

6

Source

Waterloo Local Contest, 2006.5.27

Solution:

很明显的 Trie 模板。。

我们将牌的信息映射到 [1, 52] 上,同时将序列反序,将公共后缀转化为公共前缀。

题目就变成了求建出来的 Trie 的节点数

注意每组数据处理后要将 Trie 清空,否则会有上一组数据的残留影响。

Code: O(Tnk), n为牌手数, k为各牌手牌数 [27672K, 500MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

inline int getcard(){
	char *ch = new char[5]; int val, suit;
	scanf("%s", ch);
	if(ch[0] == 'A') val = 1;
	else if(ch[0] == 'J') val = 11;
	else if(ch[0] == 'Q') val = 12;
	else if(ch[0] == 'K') val = 13;
	else if(ch[0] == '1') val = 10, ch[1] = ch[2];
	else val = ch[0] - '0';
	suit = ch[1] == 'C' ? 0 : ch[1] == 'D' ? 1 : ch[1] == 'H' ? 2 : 3;
	return val + suit * 13 - 1;
}

int n, k, a[53], topp;
int trie[100003][53];

inline void insert(int *card, int cnum){
	int cur = 0;
	for(register int i = 1; i <= cnum; i++){
		if(!trie[cur][card[i]]) trie[cur][card[i]] = ++topp;
		cur = trie[cur][card[i]];
	}
}

int main(){
	while(scanf("%d", &n) != EOF && n){
		topp = 0, memset(trie, 0, sizeof(trie));
		while(n--){
			scanf("%d", &k);
			for(register int i = k; i; i--) a[i] = getcard();
			insert(a, k);
		}
		printf("%d\n", topp);
	}
	return 0;
}

评论

还没有任何评论,你来说两句吧



新博客地址: darkleafin.cf

常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
Please refresh the page if the code cannot be displayed normally.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai