POJ 3740 Easy Finding 位运算压缩+DFS or Dancing Links

2023-11-08 09:38

本文主要是介绍POJ 3740 Easy Finding 位运算压缩+DFS or Dancing Links,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Easy Finding

这道题运用二进制DFS是比较好的方法,当然还可以用dancing links,这个比较高级,先把我看别人的二进制思路然后写的代码贴上来。

当然本题是体现不出DLX的高级之处的。用位运算和DLX的速度应该是相当

/*
ID: sdj22251
PROG: calfflac
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAX 2000000000
#define LOCA
#define PI acos(-1.0)
using namespace std;
int n, m, bit[18], a[18][303], cnt[303];
bool flag;
void dfs(int num, int in, int out) //in是已经使用的,out是排除了的,num是深度
{int i, j;if(flag) return; // 找到了就一直returnif(num >= n) {flag = true; return;} //找到了if(cnt[num] == (cnt[num] & out)) return; //如果深搜的目标都在排除的序列中,就return int count = 0;for(i = 0; i < m && count < 2; i++)if(cnt[num] & in & bit[i]) {j = i; count++;} //如果目标已经使用并且相应位置是1if(count == 1) dfs(num + 1, in, out | cnt[num] ^ bit[j]); //则接着搜索时排除除了该1位置以外的1else if (count == 0) //还没被使用过{for(i = 0; i < m && !flag; i++)if((cnt[num] & bit[i]) && !(out & bit[i])) // 相应位置是1 并且还没被排除过dfs(num + 1, in | bit[i], out | cnt[num] ^ bit[i]); }
}
int main()
{
#ifdef LOCALfreopen("ride.in","r",stdin);freopen("ride.out","w",stdout);
#endifint i, j;bit[0] = 1;for(i = 1; i < 18; i++) //将不同位置的1预存起来bit[i] = bit[i - 1] << 1; while(scanf("%d%d", &m, &n) != EOF){memset(cnt, 0, sizeof(cnt));for(i = 0; i < m; i++){for(j = 0; j < n; j++){scanf("%d", &a[i][j]);if(a[i][j])cnt[j] |= bit[i]; //如果这一个点是1,就将1及其位置存进二进制数组}}flag = false;for(i = 0; i < n; i++) //筛掉全是0这个情况if(!cnt[i]) break;if(i >= n) dfs(0, 0, 0);if(flag) puts("Yes, I found it");else puts("It is impossible");}return 0;
}


2012年1月

然后就是传说中的DLX了。

看了网上很多的资料,只是建图的时候比较麻烦吧

每一列先建立一个列头,然后往某一列中插入元素时只需要插到列头下面就行,因为是循环链表插到哪里都一样的

而行呢,不一定要行头,但是最好能把每一行的第一个1的编号记录下来,每次插入到它之后就行了。


/*
ID: sdj22251
PROG: inflate
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 5000
#define INF 1000000000
using namespace std;
int L[MAXN], R[MAXN], C[MAXN], S[MAXN], U[MAXN], D[MAXN], H[MAXN];//H数组用来存储每一行的第一个1的编号,C数组用来存列号,S数组用来存每一列中1的个数 
int n, m, cnt, head;//head表示列头,一般取0,cnt用来记录编号
void link(int r, int c)
{S[c]++;C[cnt] = c;U[cnt] = c;D[cnt] = D[c];U[D[c]] = cnt;D[c] = cnt;if(H[r] == -1){H[r] = cnt;L[cnt] = R[cnt] = cnt;}else{L[cnt] = H[r];R[cnt] = R[H[r]];L[R[H[r]]] = cnt;R[H[r]] = cnt;}cnt++;
}
void init()
{cnt = 0;head = 0;for(int i = 0; i <= m; i++){S[i] = 0;D[i] = U[i] = i;R[i] = (i + 1) % (m + 1);L[i] = (i + m) % (m + 1);cnt++;}memset(H, -1, sizeof(H));
}
void readdata()
{char t;getchar();for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++){t = getchar();getchar();if(t == '1') link(i, j);}
}
void removes(int c)
{L[R[c]] = L[c];R[L[c]] = R[c];for(int i = D[c]; i != c; i = D[i])for(int j = R[i]; j != i; j = R[j]){U[D[j]] = U[j];D[U[j]] = D[j];S[C[j]]--;}
}
void resumes(int c)
{for(int i = U[c]; i != c; i = U[i])for(int j = L[i]; j != i; j = L[j]){U[D[j]] = j;D[U[j]] = j;S[C[j]]++;}L[R[c]] = c;R[L[c]] = c;
}
bool dfs(int k)
{if(R[head] == head) return true;int s = INF, c;for(int i = R[head]; i != head; i = R[i])if(s > S[i]){s = S[i];c = i;}removes(c);for(int i = U[c]; i != c; i = U[i]){for(int j = R[i]; j != i; j = R[j])removes(C[j]);if(dfs(k + 1)) return true;for(int j = L[i]; j != i; j = L[j])resumes(C[j]);}resumes(c);return false;
}
int main()
{while(scanf("%d%d", &n, &m) != EOF){init();readdata();if(dfs(0)) puts("Yes, I found it");else puts("It is impossible");}return 0;
}


这篇关于POJ 3740 Easy Finding 位运算压缩+DFS or Dancing Links的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/369043

相关文章

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

hdu1565(状态压缩)

本人第一道ac的状态压缩dp,这题的数据非常水,很容易过 题意:在n*n的矩阵中选数字使得不存在任意两个数字相邻,求最大值 解题思路: 一、因为在1<<20中有很多状态是无效的,所以第一步是选择有效状态,存到cnt[]数组中 二、dp[i][j]表示到第i行的状态cnt[j]所能得到的最大值,状态转移方程dp[i][j] = max(dp[i][j],dp[i-1][k]) ,其中k满足c

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D