巢穴

about:blank

P3349

hash..
tle了2次都没有想起来是我用了输入输出流的原因..
后来看了讨论才想起来...
呃.这题代码写的有点orz
#include <iostream>
#include <stdio.h>
using namespace std;
const int MAXN=100000;
const long mod=999991;
int n;
long hash[mod];
long c[7];
int len=-1;
struct node
{
  long c[7];
  long son;
};
bool isFind=false;
node list[MAXN];
int p[13];
void find_node(long x)
{
 for (int i=1;i<=6;i++)
 {
  int count=0;
  for (int j=i;j<=i+6-1;j++)
  {
   if (p[j]==list[x].c[j-i+1]) count++;
  }
  if (count==6)
  {
    isFind=true;
    return;
  }
  count=0;
  for (int j=i;j<=i+6-1;j++)
  {
   if (p[j]==list[x].c[6-(j-i+1)+1]) count++;   
  }
  if (count==6)
  {
    isFind=true;
    return;
  }
 }
 
 if (list[x].son!=-1) find_node(list[x].son);
 else
 {
     len++;
     list[x].son=len;
     list[len].son=-1;
     for (int i=1;i<=6;i++)
     {
        list[len].c[i]=c[i];
     }
     return;
     
 }
 
}
void find(long x)
{
     if (hash[x]==-1)
     {
       len++;
       hash[x]=len;
       list[len].son=-1;
       for (int i=1;i<=6;i++)
       {
        list[len].c[i]=c[i];
       }
       return;
     }
    // cout<<x<<endl;
     for (int i=1;i<=6;i++)
       p[i]=c[i];
     for (int i=7;i<=12;i++)
       p[i]=c[i-6];
     find_node(hash[x]);
}
int main()
{
    scanf("%ld",&n);
    for (int i=0;i<mod;i++)
        hash[i]=-1;
   // memset(hash,-1,sizeof(hash));
    for (int i=1;i<=n;i++)
    {
        long ans=0;
        for (int j=1;j<=6;j++)
        {
            scanf("%ld",c+j);
            ans+=c[j];
        }
        long x=ans%mod;
      //  cout<<x<<endl;
        find(x);
        
    }
    if (isFind) cout<<"Twin snowflakes found."<<endl;
    else
        cout<<"No two snowflakes are alike."<<endl;   
    //system("pause");
    return 0;
    
}

posted on 2009-10-13 21:28 Vincent 阅读(138) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理