巢穴

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 閱讀(87) | 評論 (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 閱讀(91) | 評論 (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 閱讀(162) | 評論 (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 閱讀(128) | 評論 (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 閱讀(523) | 評論 (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 閱讀(119) | 評論 (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 閱讀(99) | 評論 (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 閱讀(76) | 評論 (0) | 編輯 收藏

SRM450

算上有道..第三次玩tc..
不知道是div1...看第一題挺簡單的..就得意忘形了...也沒有仔細看看..想當然了..最后終于被cha了..

posted @ 2009-10-18 01:34 Vincent 閱讀(149) | 評論 (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 閱讀(215) | 評論 (0) | 編輯 收藏