巢穴

P2531

枚举+dfs..
随机化也可以搞

#include <stdio.h>
#include <string>
#include <iostream>
const int MAXN=21;

int n;
int c[MAXN][MAXN];
int d=0,result=-1;
bool hash[MAXN];

void dfs(int x,int step)
{
     if (step==d)
     {
      int ans=0;
      for (int i=1;i<=n;i++)
      {
       if (!hash[i])
       {
        for (int j=1;j<=n;j++)
        {
         if (hash[j])
         {
          ans+=c[i][j];
         }
        }
       }
      }
      if (result<ans) result=ans;
      return;
     }
     for (int i=x;i<=n;i++)
     {
      hash[i]=true;
      dfs(i+1,step+1);
      hash[i]=false;
     }
}
int main()
{
    
    memset(hash,false,sizeof(hash));
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
     for (int j=1;j<=n;j++)
      scanf("%d",&c[i][j]);
    int m=n/2;
    for (int i=1;i<=m;i++)
    {
     d=i;
     dfs(1,0);
    }
     
    printf("%d\n",result);
   // system("pause");
    
    return 0;
}

posted @ 2009-11-03 16:05 Vincent 阅读(81) | 评论 (0) | 编辑 收藏

P3253

哈夫曼树
用二叉堆维护logn的最小优先队列

#include <iostream>

using namespace std;

const int MAXN=20001;
int n;
long long num[MAXN];
int len=0;

void insert(long long x)
{
 len++;
 num[len]=x;
 int pos=len;
 while(pos>1)
 {
  if (num[pos]<num[pos/2])
  {
   swap(num[pos],num[pos/2]);
   pos/=2;
  }
  else break;
 }
}
long long remove()
{
 long long x=num[1];
 swap(num[1],num[len]);
 len--;
 int pos=1;
 int k;
 while(pos*2<=len)
 {
  int l=pos*2,r=pos*2+1;
  if (r>len||num[l]<num[r])
  {
   k=l;
  }
  else k=r;
  if (num[pos]>num[k]) {swap(num[pos],num[k]);pos=k;} else break;
 }
 return x;
}
int main()
{
    cin>>n;
    long long x;
    for (int i=1;i<=n;i++)
    {
     cin>>x;
     insert(x);
    }    
    long long result=0;
    while(len>1)
    {
     long long x=remove();
     long long y=remove();
     long long z=x+y;
     result+=z;
     insert(z);
    }
    cout<<result<<endl;
    system("pause");
    return 0;
}

posted @ 2009-10-24 12:30 Vincent 阅读(83) | 评论 (0) | 编辑 收藏

P3274

hash.同余.不过这里的同余不是普通意义上的同余.

#include <iostream>
#include <fstream>
using namespace std;
//ifstream fin("1.txt");
const int MAXN=100001;
const int mod=99991;
int n,k;
int c[MAXN][30];
int d[MAXN][30];
int h[mod];
int p[MAXN],len=0;
int s[MAXN];
int result=0;
inline int hashcode(const int id)
 {
    int s = 0;
    for(int i=0; i<k; i++)
        s=((s<<2)+(d[id][i]>>4))^(d[id][i]<<10);
     s = s % mod;
    s = s < 0 ? s + mod : s;
    return s;
 }


void find_hash(int x,int id)
{
  int f[30];
  bool ok=true;
  for (int i=0;i<k;i++)
  {
   if (i==0) f[i]=c[id][i]-c[p[x]][i];
   else
   {
    f[i]=c[id][i]-c[p[x]][i];
    if (f[i]!=f[i-1]||f[i]==0) {ok=false;break;}
   }
  }
  if (ok)
  {
   if (result<id-p[x]) 
   {
   result=id-p[x];
   }
  }
  if (s[x]==-1)
  {
   len++;
   s[x]=len;
   s[len]=-1;
   p[len]=id;
   return;
  }
  else
  {
   find_hash(s[x],id);
  }
}
void hash(int u,int id)
{
     if (h[u]==-1)
     {
      len++;
      h[u]=len;
      s[len]=-1;
      p[len]=id;
      return;
     }
     find_hash(h[u],id);
}
int main()
{
    cin>>n>>k;
   if (n==1) {cout<<1<<endl;exit(0);}
    memset(h,-1,sizeof(h));
    memset(c,0,sizeof(c));
    for (int i=1;i<=n;i++)
    {
     int x;
     cin>>x;
     int l=-1;
     for (int j=0;j<k;j++)
     {
      int p=x%2;
      l++;
      c[i][l]=c[i-1][l]+p;
      x/=2;
     }
    }
    
    memcpy(d,c,sizeof(c));
    for (int i=0;i<=n;i++)
    {
     int max=MAXN;
     for (int j=0;j<k;j++)
     {
         if (max>d[i][j]) max=d[i][j];
     }
     for (int j=0;j<k;j++)
     {
         d[i][j]-=max;
     }
     int u=hashcode(i);
     //cout<<u<<endl;
     hash(u,i);
    }
    
    
    cout<<result<<endl;
  //  system("pause");
    return 0;
}

posted @ 2009-10-21 12:46 Vincent 阅读(156) | 评论 (0) | 编辑 收藏

P1840

这题做的很搞笑..
真得总结总结..
把方程分成两半,然后计算其中一半,存入hash.
如果枚举另一半,然后与hash表对照..并累加..
可笑的我一开始用了两个大数组来当hash..直接1对1映射累加..然后内存超了..
然后后来才想起来..只用一个hash..然后另一个来找就行了..
但是我用的大数组还是大了..
应该写一个hash才好..
于是怒了..直接map扔上去..- -

#include <iostream>
#include <map>
using namespace std;

long long result=0;
map<int,int> m;
int main()
{
    int a1,a2,a3,a4,a5;
    cin>>a1>>a2>>a3>>a4>>a5;

    for (int i=-50;i<=50;i++)
     for (int j=-50;j<=50;j++)
     {
        if (i==0||j==0) continue;
        int x=i*i*i*a4+j*j*j*a5;
        map<int,int>::iterator iter=m.find(x);
        if (iter==m.end())
        {
         m.insert(make_pair(x,1));
        }
        else
        {
            iter->second++;   
        }
     }

    
    for (int i=-50;i<=50;i++)
     for (int j=-50;j<=50;j++)
      for (int k=-50;k<=50;k++)
      {
          if (i==0||j==0||k==0) continue;
          int x=i*i*i*a1+j*j*j*a2+k*k*k*a3;
         map<int,int>::iterator iter=m.find(-x);
         if (iter!=m.end())
         {
          result+=iter->second;
         }
      }
    cout<<result<<endl;
    system("pause");
    
    return 0;
}

posted @ 2009-10-21 08:39 Vincent 阅读(118) | 评论 (0) | 编辑 收藏

P2299

逆序对,归并排序统计一下.
这题我是真的wa哭了..以前没写过归并排序.虽然知道思路..
这次就真的写尴尬了..
搞到最后专门去找别人代码看来开去都没发现自己哪写错了..
终于..最后发现了.....
于是我加上了&&pl<=mid 这个东西..为啥加上..就不解释了..很尴尬的问题

#include <iostream>
//#include <fstream>
//#include <stdio.h>
using namespace std;
const int MAXN=500001;
int n;
long num[MAXN];
long c[MAXN];
long long result=0ll;
//ifstream fin("1.txt");

void sort(int l,int r)
{
 if (l==r)
 {
  return;
 }
 int mid=(l+r)/2;
 sort(l,mid);
 sort(mid+1,r);
 int t=l;
 int pl=l,pr=mid+1;
 while(t<=r)
 {
  if (pr>r||(num[pl]<=num[pr]&&pl<=mid)) {c[t++]=num[pl++];continue;}
  if (pl>mid||(num[pr]<num[pl]&&pr<=r)) { if (pl<=mid) result+=mid-pl+1;c[t++]=num[pr++];continue;}
 }
 for (int i=l;i<=r;i++)
     num[i]=c[i];
     
}
int main()
{
    while(1)
    {
     cin>>n;
     if (0==n) break;
     for (int i=1;i<=n;i++)
         cin>>num[i];
     //result=0;
     result=0ll;
     sort(1,n);
     cout<<result<<endl;
    }
//    system("pause");
    return 0;
}

posted @ 2009-10-20 17:02 Vincent 阅读(510) | 评论 (0) | 编辑 收藏

P2388

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
vector<int> vec;
int main()
{
    cin>>n;
    for (int i=0;i<n;i++)
    {
        int x;cin>>x;
        vec.push_back(x);
    }
    sort(vec.begin(),vec.end());
    cout<<vec.at(n/2)<<endl;
    //system("pause");
}

posted @ 2009-10-19 21:44 Vincent 阅读(106) | 评论 (0) | 编辑 收藏

P3080

枚举+kmp..再不练kmp都忘了..orz
wa了一次..注意一下求出的串要最小的那个

#include <iostream>
#include <string>
//#include <fstream>
using namespace std;
//ifstream fin("t3080.in");
const int MAXN=100;
int k;
int n;
string str[MAXN];
string s_,result;
int p[MAXN];
void match_self()
{
     memset(p,sizeof(p),0);
     p[0]=-1;
     int x=-1;
     for (int i=1;i<s_.length();i++)
     {
         while (x>-1&&s_[x+1]!=s_[i]) x=p[x];
         if (s_[x+1]==s_[i]) x++;
         p[i]=x;
     }
}
bool match(string s)
{
     int x=-1;
     for (int i=0;i<s.length();i++)
     {
      while (x>-1&&s_[x+1]!=s[i]) x=p[x];
      if (s_[x+1]==s[i]) x++;
      if (x==s_.length()-1) return true;
      //p[i]=x;
     }
     return false;
}
int main()
{
    cin>>k;
    while(k--)
    {
     cin>>n;
     bool ok=false;
     for (int i=1;i<=n;i++)
     {
         cin>>str[i];
     }
     string st=str[1];
     for (int i=st.length();(i>=3)&&(ok==false);i--)
     {
      for (int j=0;(j<=i+j-1)&&(i+j-1<st.length());j++)
      {
       s_=st.substr(j,i);
       match_self();
       int count=0;
       for (int k=2;k<=n;k++)
       {
        if (match(str[k])) count++;
       }
       if (n-1==count)
       {
        if (!ok) result=s_; else if (result>s_) result=s_;
        ok=true;
       }
      }
     }
     if (ok)
     {
      cout<<result<<endl;
     }
     else
     {
      cout<<"no significant commonalities"<<endl;
     }
    }
    system("pause");
    return 0;
}

posted @ 2009-10-19 21:30 Vincent 阅读(84) | 评论 (0) | 编辑 收藏

P1936

水题..直接帖代码

#include <iostream>
#include <string>
using namespace std;

string s,t;
int main()
{
    while(cin>>s>>t)
    {
     int x=0;
     bool ok=false;
     for (int i=0;i<t.length();i++)
     {
      if (s[x]==t[i]) x++;
      if (x==s.length()-1) {ok=true;break;}
     }
     if (ok) cout<<"Yes"<<endl; else cout<<"No"<<endl;
    }
    
    return 0;
}

posted @ 2009-10-19 21:28 Vincent 阅读(68) | 评论 (0) | 编辑 收藏

SRM450

算上有道..第三次玩tc..
不知道是div1...看第一题挺简单的..就得意忘形了...也没有仔细看看..想当然了..最后终于被cha了..

posted @ 2009-10-18 01:34 Vincent 阅读(131) | 评论 (0) | 编辑 收藏

ITAT

预赛66....orz..只能说是个很吉利的数字...
长期放置java..这个成绩还在接受范围呢..
进复赛应该没问题吧...
话说当初我就说了..这样的题60分就应该能进..除非专门天天去背来背去..
现在果然灵验了..
好了..吃点东西去..下午还有ural..晚上还有topcoder..forza


ural做了2个半小时..
做的很糟..只切了2道题...
除了能力,另一个就是英语问题..
根据提交来看..应该有4-5道水题...
题目大致能看懂...但几个细节一直看不懂..
于是一个wa on 5..一个wa on 3...orz啊..orz..
B. Sandro's Book..
这题最水..枚举字符串就完了..
不过我wa了一次..因为有个细节没看懂...- -我都快怀疑我在猜题目了..
J. Dill..
最最最最最简单的构造..对于第一组箱子..可以把1-n给第一组..
那么第二组的m个可以构造成n+1,n+1+n,n+1+2*n.....
因为代码都很短..就不帖了..囧

posted @ 2009-10-17 10:36 Vincent 阅读(203) | 评论 (0) | 编辑 收藏