📄 datidama.txt
字号:
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];
作者： 61.135.146.* 2005-10-20 16:43 回复此发言
7楼天城的比赛答题源码
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;
}
作者： 61.135.146.* 2005-10-20 16:43 回复此发言
9回复：楼天城的比赛答题源码
最后一题测试了好几个有解的随机数据，在有解的情况下我的程序的平均速度是比楼天成的快的。看来我的程序如果加上对无解数据的快速判断的话，对随机数据的平均运行速度应该比楼天成快一点。
作者： xreborner 2005-10-20 17:24 回复此发言
10回复：楼天城的比赛答题源码
[quote]
最后一题测试了好几个有解的随机数据，在有解的情况下我的程序的平均速度是比楼天成的快的。看来我的程序如果加上对无解数据的快速判断的话，对随机数据的平均运行速度应该比楼天成快一点。[/quote]
仰慕...
作者： 218.108.31.* 2005-10-20 18:31 回复此发言
11回复 9：楼天城的比赛答题源码
的确如此。
作者： 220.181.27.* 2005-10-20 21:14 回复此发言
12回复 11：楼天城的比赛答题源码
可惜你当时没有时间对无解的情况做快速判断。为什么你时间会不够呢？
作者： 220.181.27.* 2005-10-20 21:16 回复此发言
13回复：楼天城的比赛答题源码
因为我几个月没有认真做过题目，因为我前一晚没睡好觉，因为我一开始浪费了太多时间想无谓的优化……
作者： xreborner 2005-10-20 21:31 回复此发言
14回复：楼天城的比赛答题源码
可是据说这题不是很经典的吗，熟悉ACM等的是不是应该知道最优的算法应是怎样的？
作者： 61.135.146.* 2005-10-21 07:33 回复此发言
15回复：楼天城的比赛答题源码
:)
作者： 61.135.146.* 2005-10-21 09:56 回复此发言
16回复：楼天城的比赛答题源码
一般的最优算法无外乎双向宽搜、A*或预处理全部可能输入状态，但具体要怎么优化则是另外一回事。ACM通常不会对速度有太苛刻的要求
作者： xreborner 2005-10-21 12:16 回复此发言
17回复：楼天城的比赛答题源码
也许百度对速度有苛刻的要求：）
作者： 61.135.146.* 2005-10-21 22:48 回复此发言
18回复：楼天城的比赛答题源码
结果不重要，关键是要报告
楼天成没报告，所以我们要bt他
作者： 灰力普 2005-10-24 15:26 回复此发言
19回复：楼天城的比赛答题源码
好象我也能看懂啊,
作者： 就想逗你玩 2005-10-25 20:59 回复此发言
20回复：楼天城的比赛答题源码
楼天城总决赛的代码运行速度不是很快...
作者： 220.166.194.* 2005-10-27 11:25 回复此发言
21回复：楼天城的比赛答题源码
哪位给解释一下总决赛中楼天城的那个无解判断的思路，看不懂啊～
作者： 218.57.243.* 2005-11-2 20:57 回复此发言
22回复：楼天城的比赛答题源码
怎么没人愿意帮忙吗？指导指导了，谢谢！
作者： 202.117.218.* 2005-11-13 16:09 回复此发言
23回复：楼天城的比赛答题源码
给个解题思路吧
作者： 219.239.33.* 2005-12-19 19:31 回复此发言
24回复：楼天城的比赛答题源码
有人给个注解吧
作者： 219.239.33.* 2005-12-20 13:03 回复此发言
25回复：楼天城的比赛答题源码
把题目也公布一下吧
作者： 219.239.33.* 2005-12-20 13:05 回复此发言
26回复：楼天城的比赛答题源码
那位出来解释一下，看不明白
作者： 219.239.33.* 2005-12-24 09:37 回复此发言
27回复 21：楼天城的比赛答题源码
找逆序数吧
作者： 58.60.63.* 2006-5-26 10:31 回复此发言
28回复：楼天城的比赛答题源码
......好搞笑的回帖们
作者： phoenixinter 2006-5-28 18:59 回复此发言
29回复：楼天城的比赛答题源码
奇怪了，怎么这贴不加精？
作者： rovingcloud 2006-5-31 14:11 回复此发言
30回复：楼天城的比赛答题源码
又是古董？有没有今年的好答案啊？
作者： 221.2.164.* 2008-6-5 15:16 回复此发言
共有贴子数29篇
标 题:
内 容:
图片/视频链接: (如何贴图/贴视频？)
用户名:您目前是匿名发表 登录 | 注册
©2008 Baidu 贴吧协议
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -