首页 > ACM题库 > HDU-杭电 > hdu 1935 Drop the Triples待解决[解题报告]C++
2013
12-26

hdu 1935 Drop the Triples待解决[解题报告]C++

Drop the Triples

问题描述 :

The inhabitants of a small Caribbean island in the region known as Bermuda’s Triangle love to spend their warm summer nights playing cards. As a tribute to the region where they live, all of their card games have some connection to triangles. One of the most popular games in the island is known as Triples, and has very simple rules.

The game is played between two players, with a set of standard playing cards. Cards are distinguished only by their values, from 1 (Ace) to 13 (King). The cards are shuffled and placed as a pile in the center of the table, face down. This pile is called the stock. The two players take turns at playing. At each turn, a player
●draws the top card from the stock, adding it to her/his hand; and
●decides whether she/he wants to "drop some triples"

Dropping a triple consists of choosing three cards (a triple) from the hand and placing them on the table, face up. The dropped triples stay on the table until the end of the game.

Only some sets of three cards form a valid triple. There are two types of valid triples:
●Perfect triples are made of three cards whose values represent the length of sides of an equilateral triangle;
●Common triples are made by three cards whose values represent the length of sides of any other (not equilateral) triangle.

The figure below shows examples of perfect triples (a), common triples (b), and invalid triples(c).

Only valid triples can be dropped, but a player may drop any number of triples at a given turn. In particular, since players know the number of cards in the stock at every turn, a player may decide to drop all triples in her/his last turn. Some players, however, normally drop some triples during the game, to maintain as few cards in their hands as possible.

The game finishes when the stock is empty. The winner is the player that dropped the largest number of perfect triples. If both players dropped the same number of perfect triples, the winner is the player that dropped the largest number of common triples. If both players dropped the same number of perfect triples and the same number of common triples, the result is a tie.

Given the description of the cards in the stock, write a program that determines the winner of a game of Triples, considering both players play as best as possible.

输入:

The input contains several test cases. The first line of a test case contains one integer N representing the number of cards in the stock (6 <= N <= 104). The next line contains N integers Xi, separated by single spaces, representing the cards in the stock (1 <= Xi <= 13, for 1 <= i <= N). The cards are given in the order they are drawn by the players: the first card in the input (X1) is the first card drawn, the second card in the input (X2) is the second card drawn, and so on. Several cards with the same value may be present in the stock, and not necessarily all card values are present in the stock. The end of input is indicated by N = 0.

输出:

The input contains several test cases. The first line of a test case contains one integer N representing the number of cards in the stock (6 <= N <= 104). The next line contains N integers Xi, separated by single spaces, representing the cards in the stock (1 <= Xi <= 13, for 1 <= i <= N). The cards are given in the order they are drawn by the players: the first card in the input (X1) is the first card drawn, the second card in the input (X2) is the second card drawn, and so on. Several cards with the same value may be present in the stock, and not necessarily all card values are present in the stock. The end of input is indicated by N = 0.

样例输入:

7
5 6 5 6 5 6 8
12
13 13 13 13 13 13 1 3 2 9 3 9
12
1 2 1 2 1 2 3 1 4 2 5 3
0

样例输出:

0
2
1


  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  2. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  3. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n