"百度之星"楼天城的比赛答题源码

yiyiyi4321

　 在征得楼天城本人的同意（谢谢楼天城同学）后，我们在这里公布他的三轮比赛的答题源码，供有兴趣的各位参考。  
  
初赛#1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define _MAXL 2000000

void GetN(char *s,long long &N)
{
N=0;
for (int i=0;s;i++)
N=N*10+(s-48);
}
void print_bigint(long long n)
{
if (n>=10)
print_bigint(n/10);
printf(\"%d\",int(n%10));
}
void Solve(long long N)
{
bool find_answer=false;
long long L,T,A1,k;
for (L=2;L<=_MAXL && L*(L-1)/2<N;L++);
for (L--;L>=2;L--)
{
T=L*(L-1)/2;
if (N>T && (N-T)%L==0)
{
find_answer=true;
A1=(N-T)/L;
for (k=0;k<L;k++)
{
if (k>0)
printf(\" \");
print_bigint(A1+k);
}
printf(\"\\n\");
}
}
if (!find_answer)
printf(\"NONE\\n\");
}
int main(int argc,char *arg[])
{
long long N;
GetN(arg[1],N);
Solve(N);
return 0;
}


初赛#2
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

//buf
const int bufsize=128*1024;
int bufL,bufP;
char buf[bufsize];
//segments
const int maxn=1000005;
int n;
unsigned int A[maxn],B[maxn];
//sort
const int countsize=65536;
int arcA[maxn],arcB[maxn],turnB[maxn];
int count[countsize],tmp[maxn];
//solve
unsigned int maxB[maxn],maxL[maxn];

void swap(unsigned int &a,unsigned int &b)
{
unsigned int t=a;
a=b;
b=t;
}
char readchar()
{
   if (bufL==bufP)
   {
      bufL=read(0,buf,bufsize);
      if (bufL==0)
           return 0;
      bufP=0;
   }
   return buf[bufP++];
}   
bool readnumber(unsigned int &v)
{
   char c;
   do{
      c=readchar();
      if (c==0)
           return false;
   }while (c<&#39;0&#39; || c>&#39;9&#39;);
   for (v=0;c>=&#39;0&#39; && c<=&#39;9&#39;;c=readchar())
      v=v*10+(c-48);
   return true;
}
void init()
{
   bufL=bufP=0;
for (n=0;readnumber(A[n+1]) && readnumber(B[n+1]);)
{
n++;
if (A[n]>B[n])
swap(A[n],B[n]);
}
}
void count_sort(unsigned int A[],int arc[])
{
int i;
//lower bit
memset(count,0,sizeof(count));
for (i=1;i<=n;i++)
count[A&65535]++;
for (i=1;i<countsize;i++)
count+=count[i-1];
for (i=n;i>=1;i--)
tmp[count[A&65535]--]=i;
//higher bit
memset(count,0,sizeof(count));
for (i=1;i<=n;i++)
count[A>>16]++;
for (i=1;i<countsize;i++)
count+=count[i-1];
for (i=n;i>=1;i--)
arc[tmp]=(count[A[tmp]>>16]--);
}
void preprocess()
{
count_sort(A,arcA);
count_sort(B,arcB);
for (int i=1;i<=n;i++)
turnB[arcB]=i;
}
void checkmax(double &answer,unsigned int S,unsigned int T)
{
if (S>T)
return;
double t=double(T)-double(S)+1;
if (t>answer)
answer=t;
}
#define lowbit(n) (((n)^((n)-1))&(n))
void add_maxB(int i,unsigned int v)
{
for (;i<=n;i+=lowbit(i))
if (v>maxB)
maxB=v;
}
void add_maxL(int i,unsigned int v)
{
i=n+1-i;
for (;i<=n;i+=lowbit(i))
if (v>maxL)
maxL=v;
}
unsigned int get_maxB(int i)
{
unsigned int t=0;
for (;i>0;i-=lowbit(i))
if (maxB>t)
t=maxB;
return t;
}
unsigned int get_maxL(int i)


　  
　 作者： 61.135.146.*  2005-10-20 16:43 　 回复此发言   
　
--------------------------------------------------------------------------------

2  楼天城的比赛答题源码  
　 {
i=n+1-i;
unsigned int t=0;
for (;i>0;i-=lowbit(i))
if (maxL>t)
t=maxL;
return t;
}
void solve()
{
double answer=0;
memset(maxB,0,sizeof(maxB));
memset(maxL,0,sizeof(maxL));
for (int T=1;T<=n;T++)
{
int i=turnB[T],LA=arcA;
checkmax(answer,A,get_maxB(LA));
checkmax(answer,1  ,get_maxL(LA));
add_maxB(LA,B);
add_maxL(LA,B-A+1);
}
printf(\"%0.0lf\\n\",answer);
}
int main()
{
freopen(\"input.txt\",\"r\",stdin);
init();
preprocess();
solve();
return 0;
}


初赛#3
#include <stdio.h>
#include <string.h>
#include <unistd.h>

//buf
const int bufsize=128*1024;
int bufL,bufP;
char buf[bufsize];

char readchar()
{
   if (bufL==bufP)
   {
      bufL=read(0,buf,bufsize);
      if (bufL==0)
return 0;
      bufP=0;
   }
   return buf[bufP++];
}

//data
const int max_strlen=512*1024;
const int hashsize=30011;

struct THashPoint
{
char *s1,*s2;
THashPoint *next;
};
char lines[max_strlen],*s1,*s2;
FILE *f;
THashPoint *Hash[hashsize];

bool read_str()
{
lines[0]=0;
fgets(lines,max_strlen,f);
if (strlen(lines)>0 && lines[strlen(lines)-1]==&#39;\\n&#39;)
lines[strlen(lines)-1]=0;
if (strlen(lines)<3)
return false;
for (int i=0;lines;i++)
if (lines==&#39; &#39; || lines==&#39;\\t&#39;)
{
s1=lines;
s2=lines+i+1;
lines=0;
return true;
}
return false;
}
int HashTable_function(char *s)
{
int address=strlen(s)%hashsize;
for (int i=0;s;i++)
address=(address*107+s+128)%hashsize;
return address;
}
void HashTable_Insert()
{
int address=HashTable_function(s1);
THashPoint *p;
for (p=Hash[address];p!=NULL;p=p->next)
if (strcmp(p->s1,s1)==0)
{
p->s2=new char[strlen(s2)+1];
strcpy(p->s2,s2);
return;
}
p=new THashPoint;
p->s1=new char[strlen(s1)+1];
p->s2=new char[strlen(s2)+1];
strcpy(p->s1,s1);
strcpy(p->s2,s2);
p->next=Hash[address];
Hash[address]=p;
}
void Print(char *s)
{
int address=HashTable_function(s);
THashPoint *p;
for (p=Hash[address];p!=NULL;p=p->next)
if (strcmp(p->s1,s1)==0)
{
printf(\"%s\",p->s2);
return;
}
printf(\"%s\",s);
}
void Init_HashTable()
{
f=fopen(\"dict.txt\",\"r\");
   while (read_str())
HashTable_Insert();
fclose(f);
}
int main()
{
Init_HashTable();
//Main
freopen(\"text.txt\",\"r\",stdin);
bufL=bufP=0;
int L=0;
for (char c;(c=readchar())!=0;)
if (c==&#39; &#39; || c==&#39;\\t&#39; || c==&#39;\\n&#39;)
{
lines[L]=0;
Print(lines);
printf(\"%c\",c);
L=0;
}
else
lines[L++]=c;
lines[L]=0;
Print(lines);
   return 0;
}   

初赛#4
#include <stdio.h>
#include <string.h>
#include <unistd.h>

const int bufsize=128*1024;
int bufL;
char buf[bufsize];

struct THashPoint
{
   char *s;
int c;
   THashPoint *next;
};
int MemoryID=0;
THashPoint **Hash,*Memory;

char *text;
int L,HashSize,minC;

void ReadFile()
{
   text=new char[bufsize+5];
   L=0;
int textL=bufsize+5;
   while (1)
   {
      bufL=read(0,buf,bufsize);
      if (bufL==0)


　  
　 作者： 61.135.146.*  2005-10-20 16:43 　 回复此发言   
　
--------------------------------------------------------------------------------

3  楼天城的比赛答题源码  
　            break;
      while (L+bufL>=textL)
      {
        char *t_text=text;
        textL*=2;
        text=new char[textL];
        memcpy(text,t_text,L);
      }
      memcpy(text+L,buf,bufL);
L+=bufL;
   }
   text[L]=0;
}
bool Prime(int n)
{
for (int i=2;i*i<=n;i++)
if (n%i==0)
return false;
return true;
}
void Prepare()
{
   int N=0,i;
   for (i=0;i<L;i++)
if (text==&#39; &#39; || text==&#39;\\t&#39; || text==&#39;\\n&#39;)
text=0;
for (i=0;i<L;i++)
      if ((i==0 || text[i-1]==0) && text!=0)
N++;
   for (HashSize=N*2+10;!Prime(HashSize);HashSize++);
Hash=new THashPoint* [HashSize];
for (i=0;i<HashSize;i++)
Hash=NULL;
MemoryID=0;
Memory=new THashPoint[N+10];
}
int HashTable_function(char *s)
{
int address=strlen(s)%HashSize;
for (int i=0;s;i++)
address=(address*137+s+128)%HashSize;
return address;
}
void HashTable_Insert(char *s)
{
int address=HashTable_function(s);
THashPoint *p;
for (p=Hash[address];p!=NULL;p=p->next)
if (strcmp(p->s,s)==0)
{
p->c++;
return;
}
p=&Memory[MemoryID++];
p->s=s;
p->c=1;
p->next=Hash[address];
Hash[address]=p;
}
bool Print(char *s)
{
int address=HashTable_function(s);
THashPoint *p;
for (p=Hash[address];p!=NULL;p=p->next)
if (strcmp(p->s,s)==0 && p->c==minC)
return false;
return true;
}
void Solve()
{
int i;
for (i=0;i<L;i++)
      if ((i==0 || text[i-1]==0) && text!=0)
HashTable_Insert(text+i);
minC=2000000000;
for (i=0;i<MemoryID;i++)
if (Memory.c<minC)
minC=Memory.c;
bool first=true;
for (i=0;i<L;i++)
      if ((i==0 || text[i-1]==0) && text!=0 && Print(text+i))
{
if (!first)
printf(\" \");
first=false;
printf(\"%s\",text+i);
}
}
int main()
{
   freopen(\"corpus.txt\",\"r\",stdin);
   ReadFile();
   Prepare();
Solve();
   return 0;
}   

网上决赛#1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

const int maxn2=100000+5;
const int maxn=5000+5;
const int max_outputL=10000000;
const int oo=1000000000;
//buf
const int bufsize=256*1024;
int bufL,bufP;
char buf[bufsize];
char *bufp;
//输入图
int n2,indexID[maxn2],indexP[maxn2];
int deg2[maxn2],*G2[maxn2],*W2[maxn2];
//并查集
int father[maxn2],sortlist[maxn2];
//新建图
int n,listM[maxn],G[maxn][maxn],tG[maxn][maxn];
//输出
int outputL=0;
char outputs[max_outputL];
//最小树形图
int prev[maxn],tmpG[maxn];
bool saved[maxn],incycle[maxn];
//深度优先搜索
int DFS_count;
bool DFS_vis[maxn];

//输入数据函数
char readchar()
{
if (bufL==bufP)
{
bufL=read(0,buf,bufsize);
if (bufL==0)
return 0;
bufP=0;
}
return buf[bufP++];
}   
bool Valid(char c)
{
return (c!=&#39; &#39;) && (c!=&#39;\\t&#39;) && (c!=&#39;\\n&#39;) && (c!=0);
}
bool ReadString(char *s)
{
while (1)
{
if (*bufp==0)
return false;
if (Valid(*bufp))
break;
bufp++;
}
int L=0;
for (;Valid(*bufp);bufp++)
s[L++]=*bufp;
s[L]=0;
return true;
}
void ReadLine()


　  
　 作者： 61.135.146.*  2005-10-20 16:43 　 回复此发言   
　
--------------------------------------------------------------------------------

4  楼天城的比赛答题源码  
　 {
char c;
while (1)
{
int L=0;
while (1)
{
c=readchar();
if (c==&#39;\\n&#39; || c==0)
break;
outputs[L++]=c;
}
outputs[L]=0;
if (L>=2)
break;
}
}
//输出数据函数
void push_char(char c)
{
outputs[outputL++]=c;
}
void write(int v)
{
if (v>=10)
write(v/10);
push_char(&#39;0&#39;+v%10);
}
//并查集函数
int getfather(int v)  
{
return (father[v]==0)?vfather[v]=getfather(father[v]));
}
void merge(int i,int j)
{
i=getfather(i);
j=getfather(j);
if (i<j)
father[j]=i;
if (j<i)
father=j;
}

void ReadData()
{
int i,j,v,k;
char s[100];
ReadLine();
bufp=outputs;
ReadString(s);
for (n2=0;ReadString(s);)
{
sscanf(s,\"%d\",&v);
indexID[++n2]=v;
}
int maxd=0;
for (i=1;i<=n2;i++)
{
ReadLine();
bufp=outputs;
ReadString(s);
sscanf(s,\"%d\",&v);
for (k=1;indexID[k]!=v;k++);
//calc deg[k]
deg2[k]=0;
for (;ReadString(s);)
{
if (s[0]==&#39;/&#39;)
continue;
sscanf(s,\"%d\",&v);
if (v>0)
deg2[k]++;
}
if (deg2[k]>maxd)
maxd=deg2[k];
G2[k]=new int[deg2[k]+5];
W2[k]=new int[deg2[k]+5];
//read again
bufp=outputs;
ReadString(s);
deg2[k]=0;
for (j=1;j<=n2;j++)
{
ReadString(s);
if (s[0]==&#39;/&#39;)
continue;
sscanf(s,\"%d\",&v);
if (v>0)
{
G2[k][++deg2[k]]=j;
W2[k][deg2[k]]=v;
}
}
}
}
void DFS(int v)
{
if (DFS_vis[v])
return;
DFS_vis[v]=true;
DFS_count++;
for (int i=1;i<=n;i++)
if (G[v]<oo)
DFS(i);
}
bool process()
{
if (n==1)
{
write(listM[1]);
push_char(&#39; &#39;);
write(0);
push_char(&#39;\\n&#39;);
return true;
}
int i,j,u,v;
int answer=oo,total;
for (int srcp=1;srcp<=n;srcp++)
{
for (u=1;u<=n;u++)
for (v=1;v<=n;v++)
G[v]=tG[v];
DFS_count=0;
for (i=1;i<=n;i++)
DFS_vis=false;
DFS(srcp);
if (DFS_count<n)
continue;
total=oo;
for (i=1;i<=n;i++)
if (G[srcp]<total)
total=G[srcp];
if (total==oo)
continue;
for (i=1;i<=n;i++)
{
prev=0;
saved=true;
}
while (1)
{
int minCost=oo;
for (i=1;i<=n;i++) if(i!=srcp && prev==0 && saved)
for (j=1;j<=n;j++) if (saved[j])
if (G[j]<minCost)
{
minCost=G[j];
u=j;
v=i;
}
if (minCost==oo)
break;
total+=minCost;
//insert edge (u,v)
prev[v]=u;
for (i=u;prev!=0 && i!=v;i=prev);
if (prev==0)
continue;
//cycle
for (i=1;i<=n;i++)
incycle=false;
incycle[v]=true;
for (i=u;i!=v;i=prev)
incycle=true;
for (i=1;i<=n;i++)
tmpG=oo;
for (i=1;i<=n;i++) if (saved && !incycle)
for (j=1;j<=n;j++) if (saved[j] && incycle[j])
{
if (G[j]<G[v])
G[v]=G[j];
if (G[j]<oo)
{
int t=G[j]-G[prev[j]][j];
if (t<tmpG)
tmpG=t;
}
}
for (i=1;i<=n;i++) if (saved && !incycle)
if (prev>0 && incycle[prev])
prev=v;
prev[v]=0;
for (i=u;i!=v;i=prev)


　  
　 作者： 61.135.146.*  2005-10-20 16:43 　 回复此发言   
　
--------------------------------------------------------------------------------

5  楼天城的比赛答题源码  
　 saved=false;
for (i=1;i<=n;i++)
G[v]=tmpG;
}
if (total<answer)
answer=total;
}
if (answer==oo)
return false;
for (i=1;i<=n;i++)
{
write(listM);
push_char(&#39; &#39;);
}
write(answer);
push_char(&#39;\\n&#39;);
return true;
}
int qsort_comp(const void *p1,const void *p2)
{
int t1=*(int *)p1,t2=*(int *)p2;
if (getfather(t1)!=getfather(t2))
return getfather(t1)-getfather(t2);
return t1-t2;
}
void solve()
{
int i,j,u,v;
memset(father,0,sizeof(father));
for (i=1;i<=n2;i++)
for (j=1;j<=deg2;j++)
merge(i,G2[j]);
for (i=1;i<=n2;i++)
sortlist=i;
qsort(sortlist+1,n2,sizeof(int),qsort_comp);
for (i=1;i<=n2;i=j)
if (father[sortlist]==0)
{
for (j=i;j<=n2 && getfather(sortlist)==getfather(sortlist[j]);j++);
n=j-i;
if (n>maxn-5)
{
printf(\"NONE\\n\");
return;
}
for (v=i;v<j;v++)
{
listM[v-i+1]=indexID[sortlist[v]];
indexP[sortlist[v]]=v-i+1;
}
for (u=1;u<=n;u++)
for (v=1;v<=n;v++)
tG[v]=oo;
for (u=i;u<j;u++)
for (v=1;v<=deg2[sortlist];v++)
tG[indexP[sortlist]][indexP[G2[sortlist][v]]]=W2[sortlist][v];
if (!process())
{
printf(\"NONE\\n\");
return;
}
}
outputs[outputL]=0;
printf(\"%s\",outputs);
}
int main()
{
freopen(\"sites.txt\",\"r\",stdin);
bufP=bufL=0;
ReadData();
solve();
return 0;
}


网上决赛#2
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

const char *rules_filename=\"rules.txt\";
const char *facts_filename=\"facts.txt\";
const int hashsize=1000007;
const int maxm=100000+5;
const int maxn=1000000+5;
const int bufsize=256*1024;

//读入
int bufL,bufP;
char buf[bufsize];
char str[1000000];
//读入函数
char readchar()
{
if (bufL==bufP)
{
bufL=read(0,buf,bufsize);
bufP=0;
if (bufL==0)
return 0;
}
return buf[bufP++];
}
bool valid(char c)
{
return (c!=0 && c!=&#39;\\t&#39; && c!=&#39;\\n&#39; && c!=&#39; &#39; && c!=&#39;&&#39; && c!=&#39;-&#39; && c!=&#39;>&#39;);
}
bool readstring(char *s)
{
int L=0;
char c;
do{
c=readchar();
if (c==0)
return false;
if (L==0 && c==&#39;>&#39;)
s[L++]=c;
}while (!valid

gungun2001

十分感谢，楼主辛苦！