UVA 658 It's not a Bug, it's a Feature! (最短路,经典)

题意:有n个bug,有m个补丁,每个补丁有一定的要求(比如某个bug必须存在,某个必须不存在,某些无所谓等等),打完出来后bug还可能变多了呢。但是打补丁是需要时间的,每个补丁耗时不同,那么问题来了:要打多久才能无bug?(同1补丁可重复打)

分析:

  n<=20,那么用位来表示bug的话有220=100万多一点。不用建图了,图实在太大了,用位图又不好玩。那么直接用隐式图搜索(在任意点,只要满足转移条件,任何状态都能转)。

  但是有没有可能每个状态都要搜1次啊?那可能是100万*100万啊,这样出题还有解么?大部分状态是怎么打补丁都到不了的,但是具体要说是多少个也不能这么说吧,这个分析可能也太麻烦了,设计100个补丁能将n个1打成所有状态都覆盖就差不多超时了。(出题人应该不会这么精明,忽略这个问题)

  那么用位表示状态要怎么办?类似于状态压缩的感觉,每个bug有3种可能(必存在,必不存在,无所谓),只要40个位搞定,但是两个位表示1个bug状态也太麻烦了吧?那就开两个数组咯,配合表示就行了,丝毫没有省空间!!但是容易看了。但是这么设计使得在匹配的时候神速啊。

思路:

  一开始所有bug是存在的,所以有sta=末尾n个1。接着我们要将其打成sta=0,任务艰巨,赶紧开始。

  (1)首先求状态的上限up。将1左移n个位置再减少1。

  (2)dijkstra来穷举每个状态,即0~up。用优先队列来优化它,一旦距离dist有更新,就进队(这么像SPFA!其实用了优先队列,一点不像,只要vis[该点]=1,那就忽略它,而spfa不忽略)。

  (3)当队列不空一直循环,直到循环了up次,或者可达状态全部遍历过了,就退出了,直接检查dist[0]是否为无穷大。

难点:

  其实这题考的不是SSSP,而是位运算的设计。

  (1)如何检查m个bug种哪些是可以转移的?

    数组pat_r1[i]表示第i个补丁需要哪些bug必须存在,存在则该位为1;

    数组pat_r2[i]表示第i个补丁对那些bug无所谓,无所谓的位为0。

    假设本状态为flag,判断第j个补丁是否可以打,应该这样:

      int res=(flag^pat_r1[j]);   //异或完,满足要求的(即相同的)位会为0(无所谓的先不管)。
      res&=pat_r2[j];        //将无所谓的位全部置为0。
      if(res==0) return true;   //满足要求

  (2)如何获取转移后的状态?

    数组pat_o1[i]表示第i个补丁打完后输出的哪些bug依然存在,存在则该位为1;

    数组pat_o2[i]表示第i个补丁打完后输出的哪些bug依然不变,不会变的位为1。

    假设本状态为flag,打完补丁j 输出的结果应该是:

      int tmp=(flag&pat_o2[j]);    //将不变的取出来
      tmp+=pat_o1[j];         //将不变的补回去
      return tmp;          //打完了

 #include <bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
using namespace std;
const int N=+;
const int INF=0x7f7f7f7f;
int pat_r1[N]; //补丁所需要的要求1
int pat_r2[N]; //补丁所需要的要求2,记录无所谓
int val[N]; //权值
int pat_o1[N]; //打完补丁后的产出1
int pat_o2[N]; //打完补丁后的产出2,记录不变
int dist[]; //表示状态
bool vis[];
int bugs, patches, v;
int res, tmp; //临时变量 /*
int cal() //超时!!未优化的dijkstra。
{
memset(dist,0x7f,sizeof(dist));
memset(vis,0,sizeof(vis)); int t=bugs, up=1;
while(t--) up+=up;
dist[--up]=0;
for(int i=up; i>=0; i--)
{
int small=INF, flag=INF;
for(int j=0; j<=up; j++) //在状态j中找dist最短
{
if(!vis[j]&&dist[j]<small)
{
flag=j; //标记该状态
small=dist[j]; //snall保存所耗时间
}
}
if(flag==INF) return -1; //找不到 vis[flag]=1; for(int j=1; j<=patches; j++) //扫描每个补丁
{
//检查是否满足条件
res=(flag^pat_r1[j]); //异或完,满足要求的会为0(除了无所谓的)。
res&=pat_r2[j]; //将无所谓的位全部置为0。 if( !res ) //只要为0就是满足条件
{
tmp=(flag&pat_o2[j]); //将不变的取出来
tmp+=pat_o1[j]; //将不变的补回去
if( dist[tmp]>dist[flag]+val[j] ) //时间比较短的
{
dist[tmp]=dist[flag]+val[j];
if(!tmp) return dist[tmp]; //bug全部修复
}
}
}
}
return -1; //修不了 } */ int can_use(int flag, int j)
{
//检查是否满足条件
int res=(flag^pat_r1[j]); //异或完,满足要求的会为0(除了无所谓的)。
res&=pat_r2[j]; //将无所谓的位全部置为0。
if(res==) return true;
return false;
} int get_sta(int flag, int j)
{
//获取将要更新的状态
int tmp=(flag&pat_o2[j]); //将不变的取出来
tmp+=pat_o1[j]; //将不变的补回去
return tmp;
} int cal()
{
priority_queue<pii, vector<pii>, greater<pii> > que; memset(vis, , sizeof(vis));
memset(dist, 0x7f, sizeof(dist)); int t=bugs, up=;
while(t--) up+=up; //获取上限
dist[--up]=; que.push(make_pair(,up));
while(!que.empty())
{
int flag=que.top().second; que.pop();
if(vis[flag]) continue; //重复
vis[flag]=; for(int j=; j<=patches; j++) //扫描每个补丁
{
int tmp=get_sta(flag, j);
if( can_use(flag, j) && dist[tmp]>dist[flag]+ val[j] ) //只要为0就是满足条件
{
dist[tmp]=dist[flag]+ val[j];
que.push(make_pair(dist[tmp],tmp));
}
}
}
return dist[];
} int main()
{
freopen("input.txt", "r", stdin);
char s[], s2[];
int Case=;
while(scanf("%d %d", &bugs, &patches ), bugs||patches)
{
for(int i=; i<=patches; i++)
{
scanf("%d %s %s", &v, s, s2);
val[i]=v;
pat_r1[i]= pat_r2[i]= ;
for(int j=; j<=bugs; j++) //要求
{
pat_r1[i]<<=;
pat_r2[i]<<=; if(s[j-]=='+') //'+'用1表示,'-'用0表示(直接移位,不用处理)
pat_r1[i]++;
if(s[j-]!='') //无所谓用0表示
pat_r2[i]++;
} pat_o1[i]= pat_o2[i]= ;
for(int j=; j<=bugs; j++) //输出
{
pat_o1[i]<<=;
pat_o2[i]<<=;
if(s2[j-]=='+') //有bug就1,无bug为0
pat_o1[i]++;
if(s2[j-]=='') //不变为1
pat_o2[i]++;
}
}
printf("Product %d\n",++Case);
int ans=cal();
if(ans<INF) printf("Fastest sequence takes %d seconds.\n\n", ans );
else printf("Bugs cannot be fixed.\n\n");
}
return ;
}

AC代码177ms

 #include <bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
using namespace std;
const int N=+;
const int INF=0x7f7f7f7f;
int pat_r1[N], pat_r2[N], pat_o1[N], pat_o2[N], val[N], dist[], vis[];
int bugs, patches, v; int can_use(int flag, int j)
{
int res=(flag^pat_r1[j]); //异或完,满足要求的会为0(除了无所谓的)。
res&=pat_r2[j]; //将无所谓的位全部置为0。
if(res==) return true;
return false;
} int get_sta(int flag, int j)
{
int tmp=(flag&pat_o2[j]); //将不变的取出来
tmp+=pat_o1[j]; //将不变的补回去
return tmp;
} int cal()
{
priority_queue<pii, vector<pii>, greater<pii> > que;
memset(vis, , sizeof(vis));
memset(dist, 0x7f, sizeof(dist));
int up=;
while(bugs--) up+=up;
dist[--up]=; que.push(make_pair(,up));
while(!que.empty())
{
int flag=que.top().second; que.pop();
vis[flag]=;
for(int j=; j<=patches; j++) //扫描每个补丁
{
int tmp=get_sta(flag, j);
if( can_use(flag, j) && dist[tmp]>dist[flag]+ val[j] ) //只要为0就是满足条件
{
dist[tmp]=dist[flag]+ val[j];
if(!vis[tmp]) que.push(make_pair(dist[tmp],tmp));
//if(!tmp) return dist[0]; //不能这么做,可能还有更新,这只是更新第一次而已,至少要n次
}
}
}
return dist[];
} int main()
{
freopen("input.txt", "r", stdin);
char s[], s2[];
int Case=;
while(scanf("%d %d", &bugs, &patches ), bugs||patches)
{
for(int i=; i<=patches; i++)
{
scanf("%d %s %s", &v, s, s2);
val[i]=v;
pat_r1[i]= pat_r2[i]= pat_o1[i]= pat_o2[i]= ;
for(int j=; j<=bugs; j++)
{
pat_r1[i]<<=,pat_r2[i]<<=,pat_o1[i]<<=,pat_o2[i]<<=;
if(s[j-]=='+') pat_r1[i]++;
if(s[j-]!='') pat_r2[i]++;
if(s2[j-]=='+') pat_o1[i]++;
if(s2[j-]=='') pat_o2[i]++;
}
}
int ans=cal();
if(ans<INF) printf("Product %d\nFastest sequence takes %d seconds.\n\n",++Case, ans );
else printf("Product %d\nBugs cannot be fixed.\n\n",++Case);
}
return ;
}

短码AC版本

上一篇:深入理解HTTP协议


下一篇:通过修改 Apache 的配置文件 htaccess 文件实现自定义404页面