The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

ACRUSH-楼天成 百度之星答题源码

初赛一
#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];i++
        N
=N*10+(s[i]-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>&& (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
}
 


初赛二
#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<'0' || c>'9'); 
    
for (v=0;c>='0' && c<='9';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[i]
&65535]++
    
for (i=1;i<countsize;i++
        count[i]
+=count[i-1]; 
    
for (i=n;i>=1;i--
        tmp[count[A[i]
&65535]--]=i; 
    
//higher bit 
    memset(count,0,sizeof(count)); 
    
for (i=1;i<=n;i++
        count[A[i]
>>16]++
    
for (i=1;i<countsize;i++
        count[i]
+=count[i-1]; 
    
for (i=n;i>=1;i--
        arc[tmp[i]]
=(count[A[tmp[i]]>>16]--); 
}
 
void preprocess() 

    count_sort(A,arcA); 
    count_sort(B,arcB); 
    
for (int i=1;i<=n;i++
        turnB[arcB[i]]
=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[i]) 
            maxB[i]
=v; 
}
 
void add_maxL(int i,unsigned int v) 

    i
=n+1-i; 
    
for (;i<=n;i+=lowbit(i)) 
        
if (v>maxL[i]) 
            maxL[i]
=v; 
}
 
unsigned 
int get_maxB(int i) 

    unsigned 
int t=0
    
for (;i>0;i-=lowbit(i)) 
        
if (maxB[i]>t) 
            t
=maxB[i]; 
    
return t; 
}
 
unsigned 
int get_maxL(int i) 

    i
=n+1-i; 
    unsigned 
int t=0
    
for (;i>0;i-=lowbit(i)) 
        
if (maxL[i]>t) 
            t
=maxL[i]; 
    
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[i]; 
        checkmax(answer,A[i],get_maxB(LA)); 
        checkmax(answer,
1   ,get_maxL(LA)); 
        add_maxB(LA,B[i]); 
        add_maxL(LA,B[i]
-A[i]+1); 
    }
 
    printf(
"%0.0lf\n",answer); 
}
 
int main() 

    freopen(
"input.txt","r",stdin); 
    init(); 
    preprocess(); 
    solve(); 
    
return 0
}
 


初赛三:
#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]=='\n'
        lines[strlen(lines)
-1]=0
    
if (strlen(lines)<3
        
return false
    
for (int i=0;lines[i];i++
        
if (lines[i]==' ' || lines[i]=='\t'
        

            s1
=lines; 
            s2
=lines+i+1
            lines[i]
=0
            
return true
        }
 
        
return false
}
 
int HashTable_function(char *s) 

    
int address=strlen(s)%hashsize; 
    
for (int i=0;s[i];i++
        address
=(address*107+s[i]+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==' ' || c=='\t' || c=='\n'
        

            lines[L]
=0
            Print(lines); 
            printf(
"%c",c); 
            L
=0
        }
 
        
else 
            lines[L
++]=c; 
    lines[L]
=0
    Print(lines); 
    
return 0
}
     


初赛四:
#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
            
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[i]==' ' || text[i]=='\t' || text[i]=='\n'
            text[i]
=0
    
for (i=0;i<L;i++
        
if ((i==0 || text[i-1]==0&& text[i]!=0
            N
++
    
for (HashSize=N*2+10;!Prime(HashSize);HashSize++); 
    Hash
=new THashPoint* [HashSize]; 
    
for (i=0;i<HashSize;i++
        Hash[i]
=NULL; 
    MemoryID
=0
    Memory
=new THashPoint[N+10]; 
}
 
int HashTable_function(char *s) 

    
int address=strlen(s)%HashSize; 
    
for (int i=0;s[i];i++
        address
=(address*137+s[i]+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[i]!=0
            HashTable_Insert(text
+i); 
    minC
=2000000000
    
for (i=0;i<MemoryID;i++
        
if (Memory[i].c<minC) 
            minC
=Memory[i].c; 
    
bool first=true
    
for (i=0;i<L;i++
        
if ((i==0 || text[i-1]==0&& text[i]!=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
}
     



网上决赛一:
#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!=' '&& (c!='\t'&& (c!='\n'&& (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() 

    
char c; 
    
while (1
    

        
int L=0
        
while (1
        

            c
=readchar(); 
            
if (c=='\n' || 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(
'0'+v%10); 
}
 
//并查集函数 
int getfather(int v)  

    
return (father[v]==0)?v:(father[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[i]
=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]=='/'
                
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]=='/'
                
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][i]<oo) 
            DFS(i); 
}
 
bool process() 

    
if (n==1
    

        write(listM[
1]); 
        push_char(
' '); 
        write(
0); 
        push_char(
'\n'); 
        
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[u][v]
=tG[u][v]; 
        DFS_count
=0
        
for (i=1;i<=n;i++
            DFS_vis[i]
=false
        DFS(srcp); 
        
if (DFS_count<n) 
            
continue
        total
=oo; 
        
for (i=1;i<=n;i++
            
if (G[i][srcp]<total) 
                total
=G[i][srcp]; 
        
if (total==oo) 
            
continue
        
for (i=1;i<=n;i++
        

            prev[i]
=0
            saved[i]
=true
        }
 
        
while (1
        

            
int minCost=oo; 
            
for (i=1;i<=n;i++if(i!=srcp && prev[i]==0 && saved[i]) 
                
for (j=1;j<=n;j++if (saved[j]) 
                    
if (G[j][i]<minCost) 
                    

                        minCost
=G[j][i]; 
                        u
=j; 
                        v
=i; 
                    }
 
                    
if (minCost==oo) 
                        
break
                    total
+=minCost; 
                    
//insert edge (u,v) 
                    prev[v]=u; 
                    
for (i=u;prev[i]!=0 && i!=v;i=prev[i]); 
                    
if (prev[i]==0
                        
continue
                    
//cycle 
                    for (i=1;i<=n;i++
                        incycle[i]
=false
                    incycle[v]
=true
                    
for (i=u;i!=v;i=prev[i]) 
                        incycle[i]
=true
                    
for (i=1;i<=n;i++
                        tmpG[i]
=oo; 
                    
for (i=1;i<=n;i++if (saved[i] && !incycle[i]) 
                        
for (j=1;j<=n;j++if (saved[j] && incycle[j]) 
                        

                            
if (G[j][i]<G[v][i]) 
                                G[v][i]
=G[j][i]; 
                            
if (G[i][j]<oo) 
                            

                                
int t=G[i][j]-G[prev[j]][j]; 
                                
if (t<tmpG[i]) 
                                    tmpG[i]
=t; 
                            }
 
                        }
 
                        
for (i=1;i<=n;i++if (saved[i] && !incycle[i]) 
                            
if (prev[i]>0 && incycle[prev[i]]) 
                                prev[i]
=v; 
                        prev[v]
=0
                        
for (i=u;i!=v;i=prev[i])  
                            saved[i]
=false
                        
for (i=1;i<=n;i++
                            G[i][v]
=tmpG[i]; 
        }
 
        
if (total<answer) 
            answer
=total; 
    }
 
    
if (answer==oo) 
        
return false
    
for (i=1;i<=n;i++
    

        write(listM[i]); 
        push_char(
' '); 
    }
 
    write(answer); 
    push_char(
'\n'); 
    
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[i];j++
            merge(i,G2[i][j]); 
    
for (i=1;i<=n2;i++
        sortlist[i]
=i; 
    qsort(sortlist
+1,n2,sizeof(int),qsort_comp); 
    
for (i=1;i<=n2;i=j) 
        
if (father[sortlist[i]]==0
        

            
for (j=i;j<=n2 && getfather(sortlist[i])==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[u][v]
=oo; 
            
for (u=i;u<j;u++
                
for (v=1;v<=deg2[sortlist[u]];v++
                    tG[indexP[sortlist[u]]][indexP[G2[sortlist[u]][v]]]
=W2[sortlist[u]][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
}
 




网上决赛二:
#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!='\t' && c!='\n' && c!=' ' && c!='&' && c!='-' && c!='>'); 
}
 
bool readstring(char *s) 

    
int L=0
    
char c; 
    
do
        c
=readchar(); 
        
if (c==0
            
return false
        
if (L==0 && c=='>'
            s[L
++]=c; 
    }
while (!valid©); 
    
for (;valid©;c=readchar()) 
        s[L
++]=c; 
    s[L]
=0
    
return true
}
 
//目标变量 
int goal; 
//规则集合 
struct TRule 

    
char *rule_name; 
    
int n,*C,A; 
}

int m; 
TRule Rules[maxm]; 
int _n,_C[1000000]; 
int left[maxm],nlist,list[maxm]; 
//命题集合 
struct Tpoint 

    
int v; 
    Tpoint 
*next; 
}

int n; 
bool fact[maxn],need_prove[maxn],org_fact[maxn]; 
Tpoint 
*Appear[maxn]; 
//HashTable,用于保存(命题名)->(int)的映射 
struct THashTable 

    
char *var; 
    
int id; 
    THashTable 
*next; 
}

THashTable 
*Hash[hashsize]; 

int find(char *s) 

    
int L=strlen(s); 
    
int address=L; 
    
for (int i=0;s[i];i++
        address
=(address*101+s[i])%hashsize; 
    THashTable 
*p; 
    
for (p=Hash[address];p!=NULL;p=p->next) 
        
if (strcmp(p->var,s)==0
            
return p->id; 
    p
=new THashTable; 
    p
->next=Hash[address]; 
    Hash[address]
=p; 
    p
->var=new char[L+2]; 
    strcpy(p
->var,s); 
    p
->id=(++n); 
    
return n; 
}
 
void insert_Point(int v,int pp) 

    Tpoint 
*p=new Tpoint; 
    p
->v=pp; 
    p
->next=Appear[v]; 
    Appear[v]
=p; 
}
 
void read_rules() 

    m
=0
    
while (1
    

        
if (!readstring(str)) 
            
return
        m
++
        Rules[m].rule_name
=new char[strlen(str)+2]; 
        strcpy(Rules[m].rule_name,str); 
        _n
=0
        
while (1
        

            readstring(str); 
            
if (str[0]=='>'
            

                Rules[m].A
=find(str+1); 
                
break
            }
 
            
else 
                _C[
++_n]=find(str); 
        }
 
        Rules[m].C
=new int[_n+2]; 
        Rules[m].n
=_n; 
        
for (int k=1;k<=_n;k++
        

            Rules[m].C[k]
=_C[k]; 
            insert_Point(_C[k],m); 
        }
 
    }
 
}
 
void read_facts() 

    memset(fact,
false,sizeof(fact)); 
    FILE 
*f=fopen(facts_filename,"r"); 
    
while (fscanf(f,"%s",&str)!=-1
        fact[find(str)]
=true
    fclose(f); 
}
 
void TPsort() 

    
int i,j,k; 
    Tpoint 
*p; 
    nlist
=0
    
for (i=1;i<=m;i++
    

        left[i]
=0
        
for (j=1;j<=Rules[i].n;j++
            
if (!fact[Rules[i].C[j]]) 
                left[i]
++
        
if (left[i]==0
            list[
++nlist]=i; 
    }
 
    
for (i=1;i<=nlist;i++
    

        k
=Rules[list[i]].A; 
        
if (fact[k]) 
            
continue
        fact[k]
=true
        
for (p=Appear[k];p!=NULL;p=p->next) 
        

            left[p
->v]--
            
if (left[p->v]==0
                list[
++nlist]=p->v; 
        }
 
    }
 
}
 
void solve_data() 

    
for (int i=1;i<=nlist;i++
    

        printf(
" %s",Rules[list[i]].rule_name); 
        
if (Rules[list[i]].A==goal) 
            
break
    }
 
    printf(
"\n"); 
}
 
void solve_goal() 

    
int i,k; 
    memset(need_prove,
false,sizeof(need_prove)); 
    need_prove[goal]
=true
    
for (i=1;i<=nlist;i++
        
if (Rules[list[i]].A==goal) 
            
break
    
for (;i>0;i--
        
if (need_prove[Rules[list[i]].A] && !org_fact[Rules[list[i]].A]) 
        

            printf(
" %s",Rules[list[i]].rule_name); 
            
for (k=1;k<=Rules[list[i]].n;k++
                need_prove[Rules[list[i]].C[k]]
=true
        }
 
        printf(
"\n"); 
}
 
int main(int argc,char *arg[]) 

    
if (argc!=3
    

        printf(
"Argument Error!\n"); 
        
return 0
    }
 
    freopen(rules_filename,
"r",stdin); 
    bufP
=bufL=n=0
    memset(Hash,
0,sizeof(Hash)); 
    memset(Appear,
0,sizeof(Appear)); 
    goal
=find(arg[2]); 
    read_rules(); 
    read_facts(); 
    memcpy(org_fact,fact,
sizeof(fact)); 
    
if (fact[goal]) 
    

        printf(
"TRUE %s\n",arg[1]); 
        
return 0
    }
 
    TPsort(); 
    
if (!fact[goal]) 
        printf(
"UNCERTAIN\n"); 
    
else 
    

        printf(
"TRUE %s",arg[1]); 
        
if (strcmp(arg[1],"data")==0
            solve_data(); 
        
else 
            solve_goal(); 
    }
 
    
return 0
}
 



总决赛:
#include <stdio.h> 
#include 
<stdlib.h> 
#include 
<string.h> 

const int hashsize=70001
const int maxnode=50000
const int maxp=40
const int ten[]={1,10,100,1000,10000,100000,1000000,10000000,100000000}
const int C[]={2,3,2,3,4,3,2,3,2}
const int EP[][4]={{1,3,0,0},{0,2,4,0},{1,5,0,0},{0,4,6,0},{1,3,5,7},{2,4,8,0},{3,7,0,0},{4,6,8,0},{5,7,0,0}}

struct Tlist 

    
int data,d; 
    Tlist 
*next; 
}

struct Thashpoint 

    
int data; 
    Thashpoint 
*next; 
}

//Memory 
int ID; 
Tlist listM[maxnode],
*q; 
Thashpoint hashM[maxnode],
*p; 
//data 
int src,dest; 
//heap 
Tlist *head[maxp],*expand[maxp],*lp1,*lp2; 
//Hash 
Thashpoint *hash[hashsize]; 
//expand 
int nowp,A[9],arcT[9],dist[9][9],b,depth,swap[9][9]; 
int data,G,newdata,newG; 
bool find_answer; 

void readdata(const char *filename,int &data) 

    
int i,v; 
    FILE 
*f=fopen(filename,"r"); 
    data
=0
    
for (i=0;i<9;i++
    

        fscanf(f,
"%d",&v); 
        data
=data+v*ten[i]; 
    }
 
    fclose(f); 
}
 
bool check_noanswer() 

    
int p[9],i,b1,b2; 
    
bool vis[9]; 
    
for (i=0;i<9;i++
        p[i]
=arcT[src/ten[i]%10]; 
    
for (b1=0; src/ten[b1]%10!=0;b1++); 
    
for (b2=0;dest/ten[b2]%10!=0;b2++); 
    
int countP=0
    memset(vis,
false,sizeof(vis)); 
    
for (i=0;i<9;i++
        
if (!vis[i]) 
        

            countP
++
            
for (int k=i;!vis[k];k=p[k]) 
                vis[k]
=true
        }
 
        
return (countP-dist[b1][b2])%2==0
}
 
void preprocess() 

    ID
=0
    find_answer
=false
    memset(hash,
0,sizeof(hash)); 
    memset(head,
0,sizeof(head)); 
    memset(expand,
0,sizeof(expand)); 
    
for (int k=0;k<9;k++
        arcT[dest
/ten[k]%10]=k; 
    
for (int u=0;u<9;u++
        
for (int v=0;v<9;v++
        

            dist[u][v]
=abs(u/3-v/3)+abs(u%3-v%3); 
            swap[u][v]
=ten[u]-ten[v]; 
        }
 
}
 
void addnode() 

    
if (newdata==dest) 
    

        printf(
"%d\n",depth); 
        find_answer
=true
        
return
    }
 
    
int address=newdata%hashsize; 
    
for (p=hash[address];p!=NULL;p=p->next) 
        
if (p->data==newdata) 
            
return
    
if (ID==maxnode) 
        
return
    p
=&hashM[ID]; 
    p
->data=newdata; 
    p
->next=hash[address]; 
    hash[address]
=p; 
    q
=&listM[ID]; 
    ID
++
    q
->data=newdata; 
    q
->d=depth; 
    
if (newG>=maxp) 
        
return
    
if (newG==nowp) 
    

        q
->next=expand[depth]; 
        expand[depth]
=q; 
    }
 
    
else 
    

        q
->next=head[newG]; 
        head[newG]
=q; 
    }
 
}
 
void solve() 

    nowp
=-1
    newdata
=src; 
    newG
=0
    
for (int k=0;k<9;k++
        
if (src/ten[k]%10!=0
            newG
+=dist[arcT[src/ten[k]%10]][k]; 
    depth
=0
    addnode(); 
    
if (find_answer) 
        
return
    
for (int p=0;p<maxp;p++if (head[p]!=NULL) 
    

        nowp
=p; 
        
for (lp1=head[p];lp1!=NULL;lp1=lp2) 
        

            lp2
=lp1->next; 
            lp1
->next=expand[lp1->d]; 
            expand[lp1
->d]=lp1; 
        }
 
        
for (int d=0;d<=p;d++
            
for (;expand[d]!=NULL;) 
            

                data
=expand[d]->data; 
                G
=p-expand[d]->d; 
                depth
=expand[d]->d+1
                expand[d]
->d=-2
                expand[d]
=expand[d]->next; 
                
for (b=0;data/ten[b]%10!=0;b++); 
                
for (int v=0;v<C[b];v++
                

                    
int u=EP[b][v]; 
                    
int c=data/ten[u]%10
                    newdata
=data+swap[b][u]*c; 
                    c
=arcT[c]; 
                    newG
=depth+G-dist[c][u]+dist[c][b]; 
                    addnode(); 
                    
if (find_answer) 
                        
return
                }
 
            }
 
    }
 
    printf(
"-1\n"); 
}
 
int main() 

    readdata(
"start.txt",src); 
    readdata(
"goal.txt",dest); 
    preprocess(); 
    
if (check_noanswer()) 
        printf(
"-1\n"); 
    
else 
        solve(); 
    
return 0
}
 


posted on 2009-03-01 20:51 abilitytao 阅读(6499) 评论(4)  编辑 收藏 引用

评论

# re: ACRUSH-楼天成 百度之星答题源码 2009-03-02 15:16 梦在天涯

强!支持!  回复  更多评论   

# re: ACRUSH-楼天成 百度之星答题源码 2009-03-02 16:45 haskell

你是楼天成???  回复  更多评论   

# re: ACRUSH-楼天成 百度之星答题源码 2009-03-05 22:41 cdy20

总决赛哪个代码不知道哪种题?
题目呢  回复  更多评论   

# re: ACRUSH-楼天成 百度之星答题源码 2009-03-06 22:26 abilitytao

@cdy20
没有...  回复  更多评论   


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