【HDOJ】2828 Lamp

DLX简单题目。

 /*  */
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 const int INF = 0x3f3f3f3f; typedef struct {
static const int maxn = 1e6+; int L[maxn], R[maxn], U[maxn], D[maxn];
int H[maxn];
int row[maxn], col[maxn], S[maxn]; bool visit[];
int sz;
int ans[maxn], ansd; void init(int n) {
rep(i, , n+) {
L[i] = i - ;
R[i] = i + ;
U[i] = i;
D[i] = i;
col[i] = i;
} memset(S, , sizeof(S));
memset(visit, false, sizeof(visit));
memset(H, -, sizeof(H));
R[n] = ;
L[] = n;
sz = n + ;
} void link(int r, int c) {
U[sz] = c;
D[sz] = D[c];
U[D[c]] = sz;
D[c] = sz;
if (H[r] < ) {
H[r] = L[sz] = R[sz] = sz;
} else {
L[sz] = H[r];
R[sz] = R[H[r]];
L[R[H[r]]] = sz;
R[H[r]] = sz;
} ++S[c];
col[sz] = c;
row[sz] = r;
++sz;
} void remove(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[col[j]];
}
}
} void restore(int c) {
L[R[c]] = c;
R[L[c]] = c;
for (int i=D[c]; i!=c; i=D[i]) {
for (int j=R[i]; j!=i; j=R[j]) {
U[D[j]] = j;
D[U[j]] = j;
++S[col[j]];
}
}
} void remove_(int c) {
for (int i=D[c]; i!=c; i=D[i]) {
L[R[i]] = L[i];
R[L[i]] = R[i];
}
} void restore_(int c) {
for (int i=D[c]; i!=c; i=D[i]) {
L[R[i]] = i;
R[L[i]] = i;
}
} bool dfs(int cur) {
if (!R[]) {
return true;
} int c = R[];
for (int i=R[]; i!=; i=R[i]) {
if (S[i] < S[c])
c = i;
} for (int i=D[c]; i!=c; i=D[i]) {
if (visit[row[i]^])
continue;
visit[row[i]] = true;
remove_(i);
for (int j=R[i]; j!=i; j=R[j])
remove_(j);
if (dfs(cur+)) return true;
for (int j=L[i]; j!=i; j=L[j])
restore_(j);
restore_(i);
visit[row[i]] = false;
} return false;
} } DLX; DLX solver; int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int n, m;
int ln, k;
char op[];
bool flag; while (scanf("%d %d", &n, &m)!=EOF) {
solver.init(n);
rep(i, , n+) {
scanf("%d", &ln);
while (ln--) {
scanf("%d %s", &k, op);
--k;
if (op[] == 'N') {
solver.link(k<<, i);
} else {
solver.link(k<<|, i);
}
}
} flag = solver.dfs();
if (flag) {
if (solver.visit[]) {
printf("OFF");
} else {
printf("ON");
}
m <<= ;
for (int i=; i<m; i+=) {
if (solver.visit[i]) {
printf(" ON");
} else {
printf(" OFF");
}
}
putchar('\n');
} else {
puts("-1");
}
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}
上一篇:Android事件分发机制浅谈(二)--源码分析(ViewGroup篇)


下一篇:浅析基于ARM的Linux下的系统调用的实现