看到第十期bug问题的答案了.

优先队列+Dijkstra
 
我就是这么作的啊.为什么时间效率始终不能满足?
 
优先队列得处理出了点错(导致某种特例下排序失败),
 
不过改正后由于运行的时间效率不理想,放弃了.
 
板上看谁的能在starfish的机器上1秒多跑出答案来?
 
我总能找到自己的PII700上1秒多都跑不出答案的测试用例,所以特沮丧.
 
starfish把通过得源码和测试用例给大家参考一下吧!

 
 

14 个解决方案

#1

哇赛，居然都买到了，ft，太快了

#2

我的dijkstra 和 优先队列 全对，但严重超时，sigh，真奇怪阿

#3

dongmen(东门吹气) :是啊,我ft死了.
 
要不要知道新一期的题目啊.
 
就是使用给出了一大堆8.3的dos文件名,
其中有一些是要保留的,有一些是要删除的, 
要求输出一条使用通配符的DEL命令,把需要删除的文件一次删除,同时不能删除不希望删除的文件.

#4

是不是通配符*和?，还有别的吗？

#5

没了.

#6

TO: Zig, 
虽然那些题目都是老题目，但是拜托你知道题目也不要说出来，否则大家做的就没有意思了呀，OK? 
我把你的那篇帖子删掉了，请你不要再说了，谢谢：）

#7

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

#define MAXPATCH 1000
#define MAXBUGS 20
#define MAXSTATES 1048577

FILE* fin;
FILE* fout;

int pre_yes[MAXPATCH],pre_no[MAXPATCH],post_yes[MAXPATCH],post_no[MAXPATCH];
int dist[MAXSTATES],hptr[MAXSTATES],h[MAXSTATES],t[MAXPATCH];
int n,m,hsize,case_no=1;

int read_data()
{
  char a[MAXBUGS+1],b[MAXBUGS+1];
  int i,j;

  fscanf(fin,"%d %d",&n,&m);
  if(n == 0 && m == 0) return 0;
  for(i=0;i<m;i++)
    {
      fscanf(fin,"%d %s %s",t+i,a,b);
      assert((strlen(a) == n) && (strlen(b) == n));
      pre_yes[i] = pre_no[i] =  post_yes[i] = post_no[i] = 0;
      for(j=0;j<n;j++)
{
  if(a[j] == '+') pre_yes[i] |= 1<<j;
  if(a[j] == '-') pre_no[i]  |= 1<<j;
  if(b[j] == '+') post_yes[i] |= 1<<j;
  if(b[j] == '-') post_no[i]  |= 1<<j;
}
      post_no[i] = ((1<<n)-1)^post_no[i];
    }
  return 1;
}

void hinit()
{
  hsize = 0;
}

int hempty()
{
  return (hsize == 0);
}

void hsiftup(int p)
{
  int d,ptr;

  ptr = h[p];
  d = dist[h[p]];
  while(p > 1 && d < dist[h[p/2]])
    {
      h[p] = h[p/2];
      hptr[h[p]] = p;
      p /= 2;
    }
  h[p] = ptr;
  hptr[h[p]] = p;
}

void hsiftdn(int p)
{
  int d,ptr;

  ptr = h[p];
  d = dist[h[p]];
  while(2*p <= hsize)
    {
      if(2*p+1 <= hsize && dist[h[2*p]] > dist[h[2*p+1]] &&
 dist[h[2*p+1]] < d)
{
  h[p] = h[2*p+1];
  hptr[h[p]] = p;
  p = 2*p+1;
}
      else
if(dist[h[2*p]] < d)
  {
    h[p] = h[2*p];
    hptr[h[p]] = p;
    p = 2*p;
  }
else
  break;
    }
  h[p] = ptr;
  hptr[h[p]] = p;
}

void hpush(int s, int d)
{

  if(dist[s] != -1 && dist[s] <= d) return;
  dist[s] = d;
  if( hptr[s] != -1) {
hsiftup(hptr[s]);
hsiftdn(hptr[s]);
  } else {
h[++hsize] = s;
hptr[s] = hsize;
hsiftup(hsize);
  }

}

void hpop(int *s, int *d)
{
  *s = h[1];
  *d = dist[*s];
  hptr[*s] = -1;
  h[1] = h[hsize--];
  if(hsize != 0)
    hsiftdn(1);
}

void process_data()
{
  int snum,i,s,d;

  snum = 1<<n;
  for(i=0;i<snum;i++) hptr[i] = dist[i] = -1;
  hpush(snum-1,0);
  while(!hempty())
    {
      hpop(&s,&d);   
      for(i=0;i<m;i++)
  if(((s & pre_yes[i]) == pre_yes[i]) &&
     ((s & pre_no[i]) == 0)) /* patch can be applied */
  hpush((s & post_no[i]) | post_yes[i],d+t[i]);
    }
  fprintf(fout,"Product %d\n",case_no++);
  if(dist[0] != -1)
    fprintf(fout,"Fastest sequence takes %d seconds.\n\n",dist[0]);
  else
    fprintf(fout,"Bugs cannot be fixed.\n\n");
}

int main()
{
  fin = fopen("bugs.in","r");
  fout = fopen("bugs.out","w");
  while(read_data())
    process_data();
  fclose(fin);
  fclose(fout);
  return 0;
}

#8

下面是程龙的程序


#include "stdio.h"

#define QMAX 1050000
int qu[QMAX];  //队列
int qs,qe;          //队列指针
int buf[QMAX];   //节点到开始状态最短路径

struct node{        //补丁
int len;    //补丁时间长度
int p;      //Bi+
int a;      //Bi-
int i;      //Fi-
int r;      //Fi+
};
struct node list[101];//所有的补丁列表
int N,M;



int main()
{
int i,j,t1,t2,c,t,tl,MAX,cc;
char tmp[1024],a[30],b[30];
unsigned int mask;

FILE *fin, *fout;
fin  = fopen("bugs.in", "r");
fout = fopen("bugs.out", "w");


cc=1;   // case number
while(fscanf(fin, "%d %d",&N,&M) != EOF)
{
if (N == 0 && M == 0)
break;
fgets(tmp, 1024, fin);
mask=0;
for(i=0;i<N;i++)
{
mask*=2;
mask+=1;
}
//下面读入所有补丁信息，
for(i=0;i<M;i++)
{
fscanf(fin, "%d %s %s",&list[i].len,a,b);
list[i].p=list[i].a=list[i].i=list[i].r=0;
for(j=0;j<N;j++)
{
list[i].p*=2;
list[i].a*=2;
list[i].i*=2;
list[i].r*=2;
if (a[j] == '+')
list[i].p+=1;
else if (a[j] == '-')
list[i].a+=1;

if (b[j] == '+')
list[i].i+=1;
else if (b[j] == '-')
list[i].r+=1;
}
list[i].r=~list[i].r;
list[i].r=list[i].r&mask;
fgets(tmp,1024, fin);
}
//MAX=起点，所有bug
MAX=0;
for(i=0;i<N;i++)
{
MAX*=2;
MAX+=1;
}
//所有距离=inf
for(i=0;i<=MAX;i++)
buf[i]=1e9;
//起点放入队列
buf[MAX]=0;
qu[0]=MAX;
qs=0;
qe=1;

//BFS
while(qs != qe)
{
c=qu[qs];
qs=(qs+1)%QMAX;
for(i=0;i<M;i++)
if ( ( (c&list[i].p) == list[i].p) && ((c&list[i].a) == 0))
{
t=c|list[i].i;
t=t&list[i].r;
tl=buf[c]+list[i].len;
if (tl < buf[t] && tl < buf[0])
{
buf[t]=tl;
qu[qe]=t;
qe=(qe+1)%QMAX;
}
}
}
fprintf(fout, "Product %d\n",cc++);
if (buf[0] < 1e9)
fprintf(fout, "Fastest sequence takes %d seconds.\n",buf[0]);
else
fprintf(fout, "Bugs cannot be fixed.\n");
fprintf(fout, "\n");
}

fclose(fin);
fclose(fout);
return 0;
}


下面是屠康的程序

// 2001年第10期程序员杂志擂台赛解答
// VC6.0下编译通过
// 屠康编写

// 2001_10.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <iostream.h>
#include <fstream.h>
#include <time.h>

const max_bugNumber = 20;
const max_spNumber = 100;

const max_status = 1024*1024;

struct SP {
int time;
int BMinus,BPlus;
int FMinus,FPlus;
};

struct Node {
int time;
int next;
};

SP sps[max_spNumber];
Node array[max_status];

int ShortPath(int bugNumber,int spNumber,SP *sps);

int main(int argc, char* argv[])
{
ifstream inputfile("bugs.in");
ofstream outputfile("bugs.out");

int bugNumber;
int spNumber;
int minTime;

int i,j,pNumber=0;
char ch;
time_t time1,time2;

time(&time1);

inputfile>>bugNumber>>spNumber;

while (!(bugNumber==0 && spNumber==0)) {
pNumber++;

for (i=0; i<spNumber; i++) {
inputfile>>sps[i].time;
sps[i].BMinus=sps[i].BPlus=sps[i].FMinus=sps[i].FPlus=0;

inputfile.ignore();

for (j=0; j<bugNumber; j++) {
inputfile>>ch;
if (ch=='+')
sps[i].BPlus |= (1<<(bugNumber-j-1));
else if (ch=='-')
sps[i].BMinus |= (1<<(bugNumber-j-1));
}

inputfile.ignore();

for (j=0; j<bugNumber; j++) {
inputfile>>ch;
if (ch=='+')
sps[i].FPlus |= (1<<(bugNumber-j-1));
else if (ch=='-')
sps[i].FMinus |= (1<<(bugNumber-j-1));
}
}

outputfile<<"Product "<<pNumber<<endl;
minTime=ShortPath(bugNumber,spNumber,sps);
if (minTime==-1)
outputfile<<"Bugs cannot be fixed."<<endl;
else
outputfile<<"Fastest sequence takes "<<minTime<<" seconds."<<endl;
outputfile<<endl;

inputfile>>bugNumber>>spNumber;
}

time(&time2);

cout<<"Elapsed time: "<<time2-time1<<endl;

return 0;
}

int ShortPath(int bugNumber,int spNumber,SP *sps)
{
int cur_max_status=(1<<bugNumber)-1;
int i;
int head,tail,p;
int min,minp,minq;
int bugs,newtime;

for (i=0; i<cur_max_status; i++)
array[i].time=array[i].next=-1;

head=tail=cur_max_status;

for (i=0; i<spNumber; i++) {
p=head & ~sps[i].FMinus | sps[i].FPlus;
if (sps[i].BMinus==0 && p!=head) {
array[p].time=sps[i].time; array[p].next=-1;
array[tail].next=p;
tail=p;
}
}

while (array[head].next!=-1) {
minp=array[head].next; min=array[minp].time; minq=head;
for (p=minp; array[p].next!=-1; p=array[p].next)
if (array[array[p].next].time<min) {
min=array[array[p].next].time; minq=p;
}
minp=array[minq].next;
array[minq].next=array[minp].next; array[minp].next=-1;
if (tail==minp)
tail=minq;

for (i=0; i<spNumber; i++)
if (((minp | sps[i].BPlus)==minp) && ((minp & sps[i].BMinus)==0)) {
bugs=minp & ~sps[i].FMinus | sps[i].FPlus;
if (bugs!=minp) {
if (array[bugs].time==-1 && bugs!=tail) {
array[tail].next=bugs; tail=bugs;
}
newtime=array[minp].time+sps[i].time;
if (newtime<array[bugs].time || array[bugs].time==-1)
array[bugs].time=newtime;
}
}
}

return array[0].time;
}

#9

这次的题目很有意思啊，感觉不简单
我打算构造FA来试试，不知道会不会超时

#10

12期写得差不多了.
 
真是够复杂的.

#11

收藏

#12

12期的写好寄去了，不知速度如何，小范围的数据我试了一些了
里面我还偷懒用了递归，还好不是很深，估计影响不会太大
请starfish测一下吧！

#13

我也交了,呵呵
估计和TAlucard(Alucard)是走的一个路子

#14

请问第10期问题的测试数据哪里找呀？