首页 > ACM题库 > HDU-杭电 > hdu 2593 Pirates’ Code[解题报告]C++
2014
02-10

hdu 2593 Pirates’ Code[解题报告]C++

Pirates’ Code

问题描述 :

Davy Jones has captured another ship and is smiling contently under the sun. Today is a good day for him. He will get more souls to serve on his crew. The day, however, looks so nice, the sun shining brightly above all and the ocean spilled calmly around, that he decides to be merciful and give some
chance to the wretched seamen of the captured ship. He decides to play the following game.
He will line a group of captives in front of him, and then write a number of his choice on each
man’s forehead. After that, he wants to check if the set of numbers is 3-free. What does it mean for a set to be 3-free? It means that there are no 3 numbers in the set that form an increasing arithmetic progression (weird games have damned Jones, aye), i.e., a sequence of numbers such that the difference of any two successive members of the sequence is a positive constant, such as {1 2 3}, {4 6 8}, or {-2, 1, 4}. If the the set of numbers on men’s foreheads is 3-free, the group is free, too (what an irony).
However, if not, those who have the numbers of the lexicographically first triple that proves (i.e. is a witness) that the set is not 3-free will serve on Jones’ crew for an eternity.
And you … You will be Jones’ assistant in this game. Checking each group whether it is 3-free or not. And you’d better check right or you will end up on Jones’ crew as well.
A triple (a1, a2, a3) is an increasing arithmetic progression if a2-a1=a3-a2, and a2-a1>0.
A triple (a1, a2, a3) is lexicographically smaller than (b1, b2, b3) if
a1 < b1, or
a1 = b1 and a2 < b2, or
a1 = b1, a2 = b2 and a3 < b3.
Note that you will be looking at triples (a1, a2, a3) of increasing order, i.e. a1 ≤ a2 ≤ a3. The numbers on men’s foreheads need not be in increasing order though.

输入:

Input consists of a single line with the numbers written on the captured men’s foreheads. The first number of the line denotes how many men are there in the group(it will not exceed 10000) and should not be included in the sequence.

输出:

Input consists of a single line with the numbers written on the captured men’s foreheads. The first number of the line denotes how many men are there in the group(it will not exceed 10000) and should not be included in the sequence.

样例输入:

4 1 5 6 8
7 1 3 5 2 -7 0 -1

样例输出:

Sequence is 3-free.
Sequence is not 3-free. Witness: -7,-1,5.

这题做了以后发现,其实数据很弱!!就是用了容器就能过了!!

#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
int x[10009];
int main()
{
 int n,i,j;
 set<int>set1;
 while(scanf("%d",&n)!=EOF)
 {
  for(i=0;i<n;i++)
  {
   scanf("%d",&x[i]);
   set1.insert(x[i]);
  }
  sort(&x[0],&x[n]);
  int ok=0;
  for(i=0;i<n;i++)
  {
   for(j=i+2;j<n;j++)
   {
    if((x[i]+x[j])%2==0&&set1.find((x[i]+x[j])/2)!=set1.end())
    {
     ok=1;
     printf("Sequence is not 3-free. Witness: %d,%d,%d.\n",x[i],(x[i]+x[j])/2,x[j]);
     break;
    }
   }
   if(ok==1)break;
  }
  if(ok==0)
   printf("Sequence is 3-free.\n");
 }
 return 0;
}

 


  1. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

  2. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。