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>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; 
} 


初赛二
#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 阅读(6508) 评论(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   知识库   博问   管理