巢穴

about:blank

#

P2104

归并排序+线段树+二分.
二分写的我比较恶心..

#include <iostream>
#include <stdio.h>
using namespace std;

struct node
{
       int l,r,t;
}tree[400001];
const int MAXN=100001;
int n,qn;
int num[19][MAXN];

int top=0;
void mergesort(int l,int r,int t,int p)
{
 if (l==r)
 {
          
  num[t][l]=num[0][l];
  tree[p].t=t;
  tree[p].l=l;
  tree[p].r=r;
  return;  
 }
 int mid=(l+r)/2;
 mergesort(l,mid,t+1,p*2);
 mergesort(mid+1,r,t+1,p*2+1); 
 int l1=l,r1=mid+1,v=l;
 while(v<=r)
 {
  if ((num[t+1][l1]<num[t+1][r1]||r1>r)&&l1<=mid) {num[t][v++]=num[t+1][l1++];continue;}
  if ((num[t+1][r1]<num[t+1][l1]||l1>mid)&&r1<=r) {num[t][v++]=num[t+1][r1++];}
 }
 tree[p].l=l;
 tree[p].r=r;
 tree[p].t=t;
}
int find(int l,int r,int value,int p)
{
 int left_=tree[p].l;
 int right_=tree[p].r;
 int mid=(left_+right_)/2;
 int count=0;
 if (left_>=l&&right_<=r)
 {
  int ll=left_,rr=right_,t=tree[p].t;
  int mm;
  while(ll<rr)
  {
     mm=(ll+rr+1)/2;
     if (num[t][mm]<value) ll=mm; else rr=mm-1;     
  }       
  count=ll-left_;
  if (value>num[t][ll]) count++;
  return count;
 }
 else
 {
  if (l<=mid) count+=find(l,r,value,p*2);
  if (r>=mid+1) count+=find(l,r,value,p*2+1);
 }
 return count;
}
int main()
{

    cin>>n>>qn;
    for (int i=1;i<=n;i++)
    {
     cin>>num[0][i];
    }
    top++;
    mergesort(1,n,top,1);
    for (int i=1;i<=qn;i++)
    {
        int l,r,k;
        cin>>l>>r>>k;
        k--;
        int lp=1,rp=n;
        int mid;
        while(lp<rp)
        {
         mid=(lp+rp+1)/2;
         int kk=find(l,r,num[1][mid],1);
         if (kk<=k) lp=mid;
         else rp=mid-1;
        }

        cout<<num[1][lp]<<endl;
    }
     
     
     system("pause");
    
    
    return 0;
}

posted @ 2009-11-09 12:35 Vincent 阅读(174) | 评论 (0) | 编辑 收藏

ctsc2000 丘比特的烦恼

     摘要: km..第一次写km.. #include <iostream>#include <fstream>#include <string>#include <math.h>using namespace std;ifstream fin("cupid.in");ofstream&nb...  阅读全文

posted @ 2009-11-07 22:54 Vincent 阅读(205) | 评论 (0) | 编辑 收藏

usaco 4.3 lgame

/*
ID:ccl03261
LANG:C++
TASK:lgame
*/

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("lgame.in");
ifstream dfin("lgame.dict");
ofstream fout("lgame.out");
vector<string> v;
string input_str;
string str[40001];
int n=0;
int hash[26],phash[26];
int t[40001][26];
int score[26]={2,5,4,4,1,6,5,5,1,7,6,3,5,2,3,5,7,2,1,2,4,6,6,7,5,7};
int main()
{
    for (int i=0;i<26;i++)
     hash[i]=0;
    fin>>input_str;
    for (int i=0;i<input_str.length();i++)
     hash[input_str[i]-'a']++;
    for (int i=0;i<40001;i++)
     for (int j=0;j<26;j++)
      t[i][j]=0;
    while(1)
    {
     string s;
     dfin>>s;
     if (s==".") break;
     for (int i=0;i<26;i++) phash[i]=0;
     for (int i=0;i<s.length();i++)
      phash[s[i]-'a']++;
     bool ok=true;
     for (int i=0;i<26;i++)
      if (phash[i]>hash[i]) {ok=false;break;}
     if (ok) {n++;str[n]=s;for (int i=0;i<26;i++){t[n][i]=phash[i];}}
    }
    
    int max_=0;
    str[0]="";
    for (int i=0;i<=n;i++)
    {
     for (int j=i+1;j<=n;j++)
     {
      for (int l=0;l<26;l++) phash[l]=0;
      for (int k=0;k<26;k++)
       phash[k]=t[i][k]+t[j][k];
      bool ok=true;
      for (int k=0;k<26;k++)
      {
       if (phash[k]>hash[k]) {ok=false;break;}
      }
      
      if (ok)
      {
       int sum=0;
       for (int k=0;k<26;k++)
         sum+=phash[k]*score[k];
       if (max_<sum) 
       {
        max_=sum;
        v.clear();
        if (i==0) v.push_back(str[j]);
        else
            v.push_back(str[i]+" "+str[j]);
       }
       else if (max_==sum)
            { 
               if (i==0) v.push_back(str[j]);
               else
                   v.push_back(str[i]+" "+str[j]);
            }
      }
     }
    }
    fout<<max_<<endl;
    sort(v.begin(),v.end());
    for (int i=0;i<v.size();i++)
     fout<<v[i]<<endl;
   // system("pause");
    return 0;
}

posted @ 2009-11-06 12:12 Vincent 阅读(150) | 评论 (0) | 编辑 收藏

P3267

动态规划

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

int w,l;
string message;
string ch[601];
int f[301];
int main()
{
 cin>>w>>l;
 cin>>message;
 for (int i=0;i<w;i++)
  cin>>ch[i];
 memset(f,0,sizeof(f));
 for (int i=0;i<l;i++)
  f[i]=1000000;
 
 for (int i=l-1;i>=0;i--)
 {
  int min_=1000000;
  for (int j=0;j<w;j++)
  {
   
   int pos=i,p=0;
   while(pos<l)
   {
    if (message[pos]==ch[j][p]) p++;
    pos++;
    if (p==ch[j].length()) break;
   }
   if (p==ch[j].length())
   {
    for (int k=pos;k<=l;k++)
    {
     if (min_>k-i-ch[j].length()+f[k]) min_=k-i-ch[j].length()+f[k];
    }
   } 
  }
  f[i]=min_;
 }
 cout<<f[0]<<endl;
 system("pause");
    
 return 0;
}

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

P1276

还是背包..

#include <iostream>
using namespace std;
const int MAXN=11;
int cash;
int n;
int t[MAXN];
int g[MAXN];
bool f[100001];
int main()
{
 while(cin>>cash>>n)
 {
  for (int i=1;i<=n;i++)
  {
   cin>>t[i]>>g[i];
  }
  memset(f,false,sizeof(f));
  f[0]=true;
  for (int i=1;i<=n;i++)
   for (int j=cash;j>=0;j--)
   {
    if (f[j])
    {
     for (int k=1;k<=t[i];k++)
     {
      int p=j+k*g[i];
      if (p<=cash) f[p]=true;
     }
    }
   }
  for (int i=cash;i>=0;i--)
   if (f[i]) {cout<<i<<endl;break;}
 }
 
    
 return 0;
}

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

P1837

背包..
wa了一次,因为漏了物品的个数..所以数组申小了..
#include <iostream>
using namespace std;

int f[21][32*25*20+1];
int mid=16*25*20;
int n,m;
int t[21];
int g[21];
int main()
{
 cin>>n>>m;
 for (int i=1;i<=n;i++)
 {
  cin>>t[i];
 }
 for (int i=1;i<=m;i++)
 {
  cin>>g[i];
 }
 
 memset(f,0,sizeof(f));
 for (int i=1;i<=n;i++)
 {
  f[1][t[i]*g[1]+mid]++;
 }
 
 for (int i=2;i<=m;i++)
 {
  for (int j=1;j<=n;j++)
  {
   for (int k=0;k<=32*25*20;k++)
   {
    if (f[i-1][k]==0) continue;
    f[i][k+g[i]*t[j]]+=f[i-1][k];
   }
  
  }
 } 
 cout<<f[m][mid]<<endl;
 system("pause");
 return 0;
}


posted @ 2009-11-04 16:55 Vincent 阅读(92) | 评论 (0) | 编辑 收藏

P2676

老老老老老题..能继续剪枝的..但是我懒..
就不剪了..
1y.我喜欢木陷阱的题...

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

int c[10][10];
int ca;
struct node
{      
       int x,y,value;
};
vector<node> v;
bool h[10][10],l[10][10];
bool mat[10][10];
bool ok;

int getPos(int x,int y)
{
    return (x-1)/3*3+(y-1)/3+1;
}
void dfs(int pos)
{
 if (pos==v.size())
 {
  for (int i=1;i<=9;i++)
  {
   for (int j=1;j<=9;j++)
   {
    cout<<c[i][j];
   }
   cout<<endl;
  }
  ok=true;
  return;
 }
 
 node p=v[pos];
 int x=p.x;
 int y=p.y;
 for (int i=1;i<=9&&(!ok);i++)
 {
  if (h[x][i]) continue;
  if (l[i][y]) continue;
  if (mat[getPos(x,y)][i]) continue;
  h[x][i]=true;
  l[i][y]=true;
  mat[getPos(x,y)][i]=true;
  c[x][y]=i;
  dfs(pos+1);
  h[x][i]=false;
  l[i][y]=false;
  mat[getPos(x,y)][i]=false;
 }
}
int main()
{
    
    cin>>ca;
    while(ca--)
    {
     v.clear();
     memset(h,false,sizeof(h));
     memset(l,false,sizeof(l));
     memset(mat,false,sizeof(mat));
     ok=false;
     char ch;
     for (int i=1;i<=9;i++)
      for (int j=1;j<=9;j++)
      {
       cin>>ch;
       c[i][j]=ch-'0';
       if (c[i][j]==0)
       {
        node p;
        p.x=i;
        p.y=j;
        p.value=0;
        v.push_back(p);
       }
       else
       {
        h[i][c[i][j]]=true;
        l[c[i][j]][j]=true;
        mat[getPos(i,j)][c[i][j]]=true;
       }
       
      }
      dfs(0);
    // solve();
    }
    //system("pause");
    return 0;
}

posted @ 2009-11-04 12:50 Vincent 阅读(113) | 评论 (0) | 编辑 收藏

P2186

求强连通分量,用邻接表储存,然后缩点,统计出度的点.话说我很勇敢的使用了邻接矩阵..然后就mle了
orz的是求强连通分量我还只会kosajura..

#include <iostream>
#include <stdio.h>
using namespace std;

int n,m;
int t=0;
const int MAXN=10001;
const int MAXM=50001;
bool used[MAXN];
int p[MAXN];
int pos[MAXN];
int len;
int d[MAXN];
int b[MAXN],bb[MAXN];
int x_[MAXM],y_[MAXM];
struct node
{
 int v;
 int next;
}ts[MAXM],tss[MAXM];
void dfs(int x)
{
 used[x]=true;
 int p_=b[x];
 while(p_>0)
 {
  int i=ts[p_].v;
  if (used[i]) {p_=ts[p_].next;continue;}
  dfs(i);
  p_=ts[p_].next;
 }
 t++;
 p[t]=x;
}
void dfs1(int x)
{
 used[x]=true;
 int p=bb[x];
 while(p>0)
 {
  int i=tss[p].v;
  if (used[i]) {p=tss[p].next;continue;}
  dfs1(i);
  p=tss[p].next;
 }
 pos[x]=len;
}


void insert(int x,int y,int i)
{
     ts[i].v=y;
     ts[i].next=b[x];
     b[x]=i;
     tss[i].v=x;
     tss[i].next=bb[y];
     bb[y]=i;
}
int main()
{
    memset(b,0,sizeof(b));
    memset(bb,0,sizeof(bb));
    scanf("%d %d",&n,&m);
    for (int i=1;i<=m;i++)
    {
     int x,y;
     scanf("%d %d",&x,&y);
     x_[i]=x;
     y_[i]=y;
     insert(x,y,i);
    }
    memset(used,false,sizeof(used));
    for (int i=1;i<=n;i++)
    {
     if (!used[i])
     {
      dfs(i);
     }
    }
    len=0;
    memset(used,false,sizeof(used));

    for (int i=t;i>=1;i--)
    {
     int k=p[i];
     if (!used[k]) 
     {
      len++;
      dfs1(k);
     }
    }
    
    memset(d,0,sizeof(d));
    for (int i=1;i<=m;i++)
    {
     int x=pos[x_[i]];
     int y=pos[y_[i]];
     if (x==y) continue;
     d[x]++;
    }
    int result=0;
    int max_=0;
    int co=0;
    for (int i=1;i<=len;i++)
    {
       if  (d[i]==0) co++;
    }
    if (co!=1) cout<<0<<endl;
    else
    {
        for (int i=1;i<=len;i++)
         if (d[i]==0)
         {
          for (int j=1;j<=n;j++)
           if (pos[j]==i) result++;
         }
        cout<<result<<endl;
    }
    system("pause");
    return 0;
}

posted @ 2009-11-04 12:48 Vincent 阅读(97) | 评论 (0) | 编辑 收藏

P1416

从大到小枚举能组成的值.dfs.水题

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

int x;
string y;
int count_;
int rs,sr;
int stop,v;
int value[100],result[100];
void dfs(int p,int sum,int v_)
{
 if (sum==stop&&p==y.length()&&v_==v)
 {
  for (int i=0;i<v_;i++)
   result[i]=value[i];
  rs=v;
  count_++;
  sr=stop;
  return;
 }
 if (sum>stop) return;
 if (v_>v) return;
 if (p>=y.length()) return;
 for (int i=p;i<y.length();i++)
 {
  //if ((i-p+1>1)&&y[i]=='0') continue;
  int s=0;
  for (int j=p;j<=i;j++)
  {
   s=s*10+y[j]-'0';
  }
  value[v_]=s;
  dfs(i+1,sum+s,v_+1);
 }
}
void solve()
{
 for (int i=x;i>=0;i--)
 {
  count_=0;
  for (int j=1;j<=y.length();j++)
  {
      stop=i;
      v=j;
      dfs(0,0,0);
      
  }
  if (count_>1)
  {
   cout<<"rejected"<<endl;break;
  }
  if (count_==1)
  {
   cout<<sr;
   for (int k=0;k<rs;k++)
   {
    cout<<" "<<result[k];
   }
   cout<<endl;
   break;
  }
}
  if (count_==0)
  {
   cout<<"error"<<endl;
  }
  
  
 
}
int main()
{
 while(true)
 {
  cin>>x>>y;
  if (0==x&&"0"==y) break;
  solve();
 }
 
// system("pause");
  return 0;
 
}

posted @ 2009-11-04 12:44 Vincent 阅读(70) | 评论 (0) | 编辑 收藏

P2513

trie+并查集+欧拉回路
有空数据..其实没影响..但是讨论里有个人说空数据输出Impossible...其实应该Possible...
这个人太邪恶了..
另外用数组写tire,re了不下5次..
最后改成了动态的..
1000+ms..还是挺慢的..

#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;
struct node
{
 node *s[26];
 int count;
 int pos;
 node()
 {
  count=0;
  pos=0;
  for(int i=0;i<26;i++)
   s[i]=NULL;
 }
 
}*root;
int f[500010],o[500010];
int len=0,l=0;
char st1[11];
char st2[11];
int insert(char *ch)
{
     int ts=0;
     node *p=root;
     for (int i=0;i<strlen(ch);i++)
     {
         if ((p->s[ch[i]-'a'])==NULL)
         {
          p->s[ch[i]-'a']=new node();
         }
         p=p->s[ch[i]-'a'];
     }
     if (p->count==0)
     {
      len++;
      p->count=1;
      p->pos=len;
      ts=len;
      return ts;
     }
     else
     {
      ts=p->pos;
      return ts;
     }
     
     
}
int getfather(int x)
{
 if (f[x]==x) return x;
 f[x]=getfather(f[x]);
 return f[x];
}
int main()
{
    
    for (int i=0;i<500010;i++)
     {f[i]=i;o[i]=0;}
    root=new node();
    int u=0;
    while(scanf ("%s %s", st1, st2) != EOF)
    {
     u++;
     int x=insert(st1);
     int y=insert(st2);
     int fx=getfather(x);
     int fy=getfather(y);
     o[x]++;
     o[y]++;
     if (fx!=fy) f[fy]=fx;
    // if (u==5) break;
    }
    
    int itn=0;
    for (int i=1;i<=len;i++)
     if (getfather(i)==i) itn++;
    int odd=0;
    for (int i=1;i<=len;i++)
     if (o[i]%2) odd++;
    
    if (len==0)
    {
     cout<<"Possible"<<endl;
     exit(0);
    }
    if (itn==1&&(odd==2||odd==0)) 
    {
     cout<<"Possible"<<endl;
    }
    else
    {
     cout<<"Impossible"<<endl;
    }
   // system("pause");
     
    return 0;
}

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

仅列出标题
共8页: 1 2 3 4 5 6 7 8