网站文件夹结构,四川省住房和城乡建设厅官方网站,百度推广技巧,深圳龙华新区住房和建设局网站文章目录题目描述题解#xff1a;代码#xff1a;添加链接描述题目描述 T 公司发现其研制的一个软件中有 n 个错误#xff0c;随即为该软件发放了一批共 m 个补丁程序。每一个补丁程序都有其特定的适用环境#xff0c;某个补丁只有在软件中包含某些错误而同时又不包含另一些…
文章目录题目描述题解代码添加链接描述题目描述 T 公司发现其研制的一个软件中有 n 个错误随即为该软件发放了一批共 m 个补丁程序。每一个补丁程序都有其特定的适用环境某个补丁只有在软件中包含某些错误而同时又不包含另一些错误时才可以使用。一个补丁在排除某些错误的同时往往会加入另一些错误。 换句话说对于每一个补丁 i都有 2 个与之相应的错误集合 B1[i]和 B2[i]使得仅当软件包含 B1[i]中的所有错误而不包含 B2[i]中的任何错误时才可以使用补丁 i。补丁 i 将修复软件中的某些错误 F1[i]而同时加入另一些错误 F2[i]。另外每个补丁都耗费一定的时间。 试设计一个算法利用 T 公司提供的 m 个补丁程序将原软件修复成一个没有错误的软件并使修复后的软件耗时最少。对于给定的 n 个错误和 m 个补丁程序找到总耗时最少的软件修复方案。 输入格式 第 1 行有 2 个正整数 n 和 mn 表示错误总数m表示补丁总数1n20, 1m100。 接下来 m 行给出了 m 个补丁的信息。每行包括一个正整数表示运行补丁程序 i 所需时间以及 2 个长度为 n 的字符串中间用一个空格符隔开。 第 1 个字符串中如果第 k 个字符 bk 为“”则表示第 k 个错误属于 B1[i]若为“-”则表示第 k 个错误属于 B21[i]若为“0”则第 k 个错误既不属于 B1[i]也不属于 B2[i]即软件中是否包含第 k 个错误并不影响补丁 i 的可用性。 第 2 个字符串中如果第 k 个字符 bk为“-”则表示第 k 个错误属于 F1[i]若为“”则表示第 k 个错误属于 F2[i]若为“0”则第 k 个错误既不属于 F1[i]也不属于 F2[i]即软件中是否包含第 k 个错误不会因使用补丁i 而改变。 输出格式 程序运行结束时将总耗时数输出。如果问题无解则输出 0。 输入输出样例 输入
3 3
1 000 00-
1 00- 0-
2 0-- -输出
8题解
样例分析 圆圈表示还没修复三角表示已修复 按照题目所给要求以及样例读入我们可以得到以下分析 所采用的补丁分别为补丁1,21,31,21. 然后错误全部修复总耗时为8 思路 我是在刷网络流24题遇到的看完后怎么想也想不到网络流。。。 感觉dp或者是最短路 看了题解还真是妙啊 ~ ~ 啥玩意还带这么坑人的 还真是网络流24题中没网络流老婆饼里没老婆 借用一张照片 第一步 怎么和最短路联系到一起 最短路无疑就是起点终点中间点还有各点之间的线段 前三种点都是节点在本题中节点就是错误修复的状态起点就是全没修复终点就是全修复了每次修复一些错误或者新添一些错误此时的修复状态就是当前状态。线段长度就是运行补丁的时间。我们在输入每一个补丁的时候可以枚举一种状态如果当前状态可以使用补丁就算出使用补丁后的状态前状态连一条边到后状态长度也就是补丁时长 第二步 状态压缩 n20也就是最多20个错误而每个错误只有修好和没修好俩状态我们可以用01来表示1表示没修好0表示修好这样20个错误其实就是一个01串 比如bug3已经修好1和2还未修好那01串就是110转化成十进制就是6。而初始状态都未修好为111对应7。结束状态是都修好了为000对应0。当有n个错误时初始状态就是n个1十进制也就是2n-1即1n-1。结束就是0 第三步 状态转移 补丁使用是有严格要求的有些位置为1有些位置为0才能使用 题目中有b1b2f1f2 软件包含b1错误不包含b2错误能够修复f1加入错误f2 我们看看补丁3
0-- -使用状态判断一个补丁包能否使用 b1是0000因为第一个字符串里面没有 b2是0113第一个字符串中 第二三位是- 记当前状态为x 1.判断x中b1位上是否都为1说明x是否含有b1错误 我们可以将x与b1按位与。如果得到的值是b1本身那就说明x的b1位上都是1 2.判断x中b2位上是否都为0说明x是否含有b2错误 也是将b2与x按位与如果得到的都是0说明x的b2位上都是0
if((xp[i].b1)p[i].b1 (xp[i].b2)0)//说明该补丁包可以使用修复状态使用后的情况 使用后f1位置会修好变成0f2会变成1。 当前状态为x如果要将f2位置变成1直接x或上f2即可。f1位置变成0我们可以或上一个f1使得当前状态的所有f1位置都变成1再异或一个f1这样就可以将f1所有位置变成0.
int y((x|p[i].f1)|p[i].f2)^p[i].f1;应该算讲的很详细了吧!
代码
//第一个字符串中
//第二个字符串-
#includebits/stdc.h
#define Maxn 100
#define Maxm 100
#define Maxnum 4000000using namespace std;inline int read(){char cgetchar();int x0,f1;while(c0||c9){if(c-)f-1;cgetchar();}while(c0c9){xx*10c-0;cgetchar();}return x*f;
}int n,m;
int ST;struct debug{int b1;int b2;int f1;int f2;int T;
}hero[Maxm2];priority_queue pairint,int q;
int dist[Maxnum];
int vis[Maxnum];
void dj(){memset(dist,0x3f,sizeof(dist));dist[ST]0;q.push(make_pair(0,ST));while(!q.empty()){int nowq.top().second;q.pop();if(vis[now]1) continue;vis[now]1;for(int i1;im;i){if( (hero[i].b1now)hero[i].b1 (hero[i].b2now)0 ){int v((now|hero[i].f1)^hero[i].f1)|hero[i].f2;if(dist[now]hero[i].Tdist[v]){dist[v]dist[now]hero[i].T;q.push(make_pair(-dist[v],v));}}}}
}int main(){nread(); mread();for(int i1;in;i)STST|(1i);//ST表 coutSTendl;for(int i1;im;i){hero[i].Tread();string B,F;cinBF;for(int j0;jn-1;j){if(B[j])hero[i].b1hero[i].b1|(1(j1));if(B[j]-)hero[i].b2hero[i].b2|(1(j1));if(F[j])hero[i].f2hero[i].f2|(1(j1));if(F[j]-)hero[i].f1hero[i].f1|(1(j1));}}dj();if(dist[0]dist[Maxnum-1])cout0;elsecoutdist[0];return 0;
}
