首页 > ACM题库 > HDU-杭电 > HDU 3633-Black and white[解题报告]HOJ
2014
11-29

HDU 3633-Black and white[解题报告]HOJ

Black and white

问题描述 :

Given a partially filled grid with N rows and M columns and each gird with a number.We define sumBlack is the sum of all Black gird and sumWhite is the sum of all White gird.
You are to calculate how many ways there are to fill the remaining part of the grid under the constraints stated below to make the absolute of (sumBlack – sumWhite) minimum and output one of these ways (if any exist).
Each cell in the grid should be colored either black or white.
All black cells in the grid should be connected with each other, and all white cells should also be connected with each other.The pictures below show two filled grids where this constraint is only fulfilled in the picture2.
A Captivating Match

There must be no 2×2 blocks in the grid which consists of only white cells, or of only black cells.
The picture3 shows a grid with a black and a white 2×2 block, while the picture4 contains no such 2×2 block.
A Captivating Match

You are not allowed to change the color of any of the cells whose color has already been assigned in the input, and all cells must be colored.

输入:

The first line in the input contains an integer T (1<=T<=30), the number of cases to follow.
Each case starts with two integers, N and M (2 ≤ N, M ≤ 8), the number of rows and columns respectively in the grid.
The next N lines contains M characters each and describes the grid using the following characters:
  # – a cell which is colored black
  o – a cell which is colored white
  . – a cell which color has not yet been assigned
The next N lines contains M integers (-1 or 0 or 1) each indicating the number of this gird.

输出:

The first line in the input contains an integer T (1<=T<=30), the number of cases to follow.
Each case starts with two integers, N and M (2 ≤ N, M ≤ 8), the number of rows and columns respectively in the grid.
The next N lines contains M characters each and describes the grid using the following characters:
  # – a cell which is colored black
  o – a cell which is colored white
  . – a cell which color has not yet been assigned
The next N lines contains M integers (-1 or 0 or 1) each indicating the number of this gird.

样例输入:

4
2 3
xxx
oox
1 1 0
0 1 0

2 3
...
...
1 1 0
0 1 -1

5 5
..x..
.....
....o
o....
.x...
1 1 0 0 1
0 -1 -1 0 1
1 1 0 -1 0
1 0 1 -1 -1
-1 -1 1 -1 0

4 5
.....
.....
.....
.....
1 1 0 0 1
0 -1 -1 0 1
1 1 0 -1 0
1 0 1 -1 -1

样例输出:

Case 1: 1 1
xxx
oox

Case 2: 0 8
xxx
xox

Case 3: 0 0

Case 4: 1 54
xxxxx
xoxox
oooox
oxxxx

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <climits>
#include <cmath>
#include <cstring>
#include <cstdlib>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
#define mp make_pair
#define rep(i, n) for (int i = 0; i < n; ++i)

struct myHash {
 const static int mod = 10007;
 const static int size = 100007;
 int head[mod], nxt[size], cs;
 int s1[size], s2[size], cnt[size], diff[size];
 int getHash(int x1, int x2, int d) { 
 return abs((x1 * x2 + x1 + x2) * (d + 65) + d + 64) % mod; 
 }
 void clear() { 
 cs = 0, memset(head, -1, sizeof(head)); 
 }
 int find(int x1, int x2, int d) {
 int u = getHash(x1, x2, d);
 for (int i = head[u]; i != -1; i = nxt[i])
 if (s1[i] == x1 && s2[i] == x2 && diff[i] == d) return i;
 return -1;
 }
 void insert(int x1, int x2, int d) {
 int u = getHash(x1, x2, d);
 s1[cs] = x1, s2[cs] = x2, diff[cs] = d, cnt[cs] = 0;
 nxt[cs] = head[u], head[u] = cs++;
 }
 int push(int x1, int x2, int d, int c) {
 int t = find(x1, x2, d);
 if (t == -1) {
 insert(x1, x2, d);
 t = cs - 1;
 }
 cnt[t] += c;
 return t;
 }
};

const char *base = "ox.";
const int maxn = 10;
const int maxs = 2000000;
int n, m, sg[maxn][maxn];
int v[maxn][maxn];
char g[maxn][maxn];
int state[maxn], cp, np, tot;
int pre[maxs];
int ynn[2][maxn][maxn];
int result, flag, tool[maxn], rd;
myHash dp[2];
vector<int> beg;

inline int get(int s, int p) {
 return (s >> p) & 1;
}

void expand(int s) {
 for (int i = 0; i < m; ++i) {
 state[i] = s & 7;
 s >>= 3;
 }
}
int encode() {
 int s = 0;
 for (int i = m - 1; i >= 0; --i) {
 s = (s << 3) | state[i];
 }
 return s;
}

void preWork() {
 dp[0].clear(); beg.clear();
 int tot = 1 << m, j, k;
 for (int s = 0; s < tot; ++s) {
 for (j = 0; j < m; ++j) {
 if (sg[0][j] != 2 && sg[0][j] != ((s>>j)&1)) break;
 }
 if (j < m) continue;
 for (k = 1, j = state[0] = 0; k < m; ++k) {
 if (((s>>k)&1) != ((s>>(k-1))&1)) ++j;
 state[k] = j;
 }
 int cc = 0;
 for (int j = 0; j < m; ++j) {
 if (s & (1 << j)) cc += v[0][j];
 else cc -= v[0][j];
 }
 int t = dp[0].push(s, encode(), cc, 1);
 beg.push_back(s);
 pre[t] = -1;
 }
}

bool checkl(int s, int x) { 
 expand(s);
 for (int i = 0; i < m; ++i) {
 if (i != x && state[i] == state[x]) return false;
 }
 return true;
}

void weihu() {
 memset(tool, -1, sizeof(tool));
 for (int i = 0, j = 0; i < m; ++i) {
 if (tool[state[i]] == -1) {
 tool[state[i]] = j++;
 }
 }
 for (int i = 0; i < m; ++i) state[i] = tool[state[i]];
}

void un(int s, int a, int b) {
 expand(s);
 b = state[b], a = state[a];
 for (int i = 0; i < m; ++i) {
 if (state[i] == b) state[i] = a;
 }
}

void create(int s, int a) {
 expand(s);
 int j = -1;
 for (int i = 0; i < m; ++i) {
 if (i != a && state[i] > j) j = state[i];
 }
 state[a] = j + 1;
}

bool checkc(int s, int x) {
 for(int i = 0; i < m; ++i) {
 if (i != x && get(s, i) == get(s, x)) return true;
 }
 return false;
}
int ans[maxn*maxn];

void dfs(int u, int p) {
 int c = pre[p]&1;
 if (pre[p] == -1) {
 int s1 = beg[p];
 for (int i = 0; i < m; ++i) {
 ans[i] = (s1 >> i) & 1;
 }
 } else {
 ans[u + m - 1] = c;
 dfs(u - 1, pre[p]>>1);
 }
}

void output(int u, int p, int c) {
 for (int i = u + 1; i < n * m; ++i) ans[i] = c;
 dfs(u, p);
}

int clac(int x, int y, int c) {
 int cc = 0;
 for (int j = y; j < m; ++j) {
 if (c) cc += v[x][j];
 else cc -= v[x][j];
 }
 for (int i = x + 1; i < n; ++i) {
 for (int j = 0; j < m; ++j) {
 if (c) cc += v[i][j];
 else cc -= v[i][j];
 }
 }
 return cc;
}

int bfs() {
 preWork();
 int u = tot = 0;
 cp = 0, np = 1;
 for (int i = 0; i < n; ++i) {
 for (int j = ((!i)?(m-1):(0)); j < m; ++j) {
 if (i == n - 1 && j == m - 1) return u;
 dp[np].clear();
 tot += dp[cp].cs;
 for (int st = 0; st < dp[cp].cs; ++st) {
 for (int c = 0; c < 2; ++c) {
 int x = i, y = j, s1 = dp[cp].s1[st], s2 = dp[cp].s2[st];
 int x1 = get(s1, j), x2 = get(s1, j + 1), x3 = get(s1, m);
 if (j == m - 1) {
 s1 ^= x3 << m;
 x1 = x3 = -1, x2 = get(s1, 0); ++x, y = -1;
 }
 if (sg[x][y+1] != 2 && sg[x][y+1] != c) continue;
 if (x == n - 1 && y + 1 == m - 1 && x1 != c && x2 != c && x3 == c) continue;
 if (x1 == c && x2 == c && x3 == c) continue;
 if (x2 != c && checkl(s2, y + 1)) {
 if (checkc(s1, y + 1) || ynn[!c][x][y+1]) continue;
 if (x < n - 1 || (y + 1) < m - 2) continue;
 
 int ccc = abs(dp[cp].diff[st] + clac(x, y + 1, c));
 if (ccc < rd) { 
 rd = abs(ccc);
 result = dp[cp].cnt[st];
 output(u, tot + st - dp[cp].cs, c);
 } else if (ccc == rd) {
 result += dp[cp].cnt[st];
 }
 continue;
 }
 if (x3 != -1) s1 ^= (x3 << m);
 s1 ^= (x2 << (y + 1));
 s1 |= (x2 << m) | (c << (y + 1));
 if (x1 == c && x2 == c) un(s2, y, y + 1);
 else if (x1 != c && x2 != c) create(s2, y + 1);
 else if (x1 == c && x2 != c) {
 expand(s2);
 state[y + 1] = state[y];
 } else if (x1 != c && x2 == c) expand(s2);
 weihu();
 int ccc = dp[cp].diff[st];
 if (c) ccc += v[x][y+1];
 else ccc -= v[x][y+1];
 int t = dp[np].push(s1, encode(), ccc, dp[cp].cnt[st]) + tot;
 pre[t] = ((tot + st - dp[cp].cs)<<1)|c;
 }
 }
 ++u;
 np = 1 - np;
 cp = 1 - cp;
 }
 }
 return -1;
}

void calc(int u) {
 memset(tool, -1, sizeof(tool));
 for (int st = 0;st < dp[cp].cs; ++st) {
 expand(dp[cp].s2[st]);
 int c = 0;
 for (int i = 0; i < m; ++i) {
 if (tool[state[i]] != -st) {
 tool[state[i]] = -st, ++c;
 }
 }
 if (c <= 2) {
 if (abs(dp[cp].diff[st]) < rd) {
 rd = abs(dp[cp].diff[st]);
 result = dp[cp].cnt[st];
 output(u, tot + st, pre[st]&1);
 } else if (abs(dp[cp].diff[st]) == rd) {
 result += dp[cp].cnt[st];
 }
 }
 }
}

void solved(int nT) {
 scanf("%d %d", &n, &m);
 rep(i, n) {
 scanf("%s", g[i]);
 rep(j, m) sg[i][j] = find(base, base + 3, g[i][j]) - base;
 }
 rep(i, n) rep(j, m) scanf("%d", &v[i][j]);
 int t[2] = {0, 0};
 for (int i = n - 1; i >= 0; --i) {
 for (int j = m - 1; j >= 0; --j) {
 for (int u = 0; u <= 1; ++u) {
 ynn[u][i][j] = sg[i][j] == u || t[u];
 t[u] = ynn[u][i][j];
 }
 }
 }
 result = flag = 0, rd = 10086;
 calc(bfs());
 if (rd == 10086) rd = 0;
 printf("Case %d: %d %d\n", nT, rd, result);
 if (result) {
 for (int i = 0, c = 0; i < n; ++i) {
 for (int j = 0; j < m; ++j, ++c) {
 putchar(ans[c]?'x':'o');
 } puts("");
 }
 }
 puts("");
}

int main() {
 int T = 1;
 scanf("%d", &T);
 for (int nT = 1; nT <= T; ++nT) {
 solved(nT);
 }
 return 0;
}

  1. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }