Celery's Blog

0%

挑战程序设计竞赛-day11

发表于 Valine：

翻转（开关问题）

POJ 3276 Face The Right Way

1580175869497

1580175890110

1580175898480

思路：枚举每一个K，然后求解所需要的最小操作次数

对于一个固定的K来说：

  • 交换区间反转的顺序对结果没有影响
  • 从最左边的牛开始考虑，因为对于它来说，只有一种翻转能影响到它，即从[1, K]翻转。确定这个区间的翻转之后，开始考虑第二头牛，在[1, K]的翻转确定的情况下，只有[2, K+1]的翻转才能改变第二头牛的情况，因此，像这样依次往下考虑，直至最后剩下K - 1头牛的时候，我们只需要判断这些牛的方向是不是朝前即可。如果不是，则无解，如果是，则返回最小操作次数。

但是，我们可以看到，这样操作的复杂度是O(N3)O(N^3)

所以，需要对上述算法进行优化。采用flip[i]数组来记录第i头牛的翻转情况。

如果我们需要判断第i头牛是否朝前，则只需要计算∑j=i−k+1i−1flip[j]\sum_{j=i - k + 1}^{i -1} flip[j]是奇数还是偶数即可。如果是奇数，表示当前的牛被转向了，如果是偶数，表示当前的牛与原方向保持一致。且∑j=(i+1)−k+1iflip[j]=∑j=i−k+1i−1f[j]+f[i]−f[i−k+1]\sum_{j=(i+1) - k + 1}^{i} flip[j] = \sum_{j = i-k+1}^{i-1} f[j] + f[i]-f[i-k+1]

所以，当前牛的情况以及是否需要反转是可以在常数时间计算出来的，因此，复杂度降低到了O(N2)O(N^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 20;
const int dx[5] = {-1, 0, 0, 0, 1};
const int dy[5] = {0, -1, 0, 1, 0};
// 输入
int M, N;
int tile[MAXN][MAXN];

int opt[MAXN][MAXN];    // 保存最优解
int flip[MAXN][MAXN];   // 保存中间结果

// 查询(x, y)的颜色
// 需要统计自身原始的颜色以及上下左右自己的翻转情况然后决定当前的颜色
int get(int x, int y) {
    int c = tile[x][y];
    for(int d = 0; d < 5; d++) {
        int x2 = x + dx[d], y2 = y + dy[d];
        if(0 <= x2 && x2 < M && 0 <= y2 && y2 < N) {
            c += flip[x2][y2];
        }
    }
    return c % 2;
}

// 求出第一行确定的情况下的最小操作次数，如果不存在的话返回-1
int calc() {
    // 求出从第2行开始的翻转方法
    for(int i = 1; i < M; i++) {
        for(int j = 0; j < N; j++) {
            if(get(i - 1, j) != 0) {
                // 如果(i - j)为黑色的话，就必须要翻转这个格子
                flip[i][j] = 1;
            }
        }
    }
    // 判断最后一行是否是全白
    for(int j = 0; j < N; j++) {
        if(get(M - 1, j) != 0) {
            return -1;
        }
    }
    // 统计翻转次数
    int res = 0;
    for(int i = 0; i < M; i++) {
        for(int j = 0; j < N; j++) {
            res += flip[i][j];
        }
    }
    return res;
}

void solve() {
    int res = -1;
    // 按照字典序尝试第一行的所有可能性
    // 利用二进制进行枚举
    for(int i = 0; i < 1 << N; i++) {
        memset(flip, 0, sizeof(flip));
        for(int j = 0; j < N; j++) {
            flip[0][N - j - 1] = i >> j & 1;
        }
        int num = calc();
        if(num >= 0 && (res < 0 || num < res)) {
            res = num;
            memcpy(opt, flip, sizeof(flip));
        }
    }
    if(res < 0) {
        printf("IMPOSSIBLE\n");
    } else {
        for(int i = 0; i < M; i++) {
            for(int j = 0; j < N; j++) {
                printf("%d%c", opt[i][j], j + 1 == N ? '\n' : ' ');
            }
        }
    }
}

int main() {
    while(scanf("%d%d", &M, &N) != EOF) {
        for(int i = 0; i < M; i++) {
            for(int j = 0; j < N; j++) {
                scanf("%d", &tile[i][j]);
            }
        }
        solve();
    }
}

POJ 3279 Fliptile

1580176643933

1580176655918

这道题不能像上面一样从最左边的一头牛(1, 1)考虑了，因为它的情况不能直接由自己决定，可以通过反转(1, 2), (2, 1)来改变。因此需要换一个思路。

如果我们在确定第一行的情况下，我们就可以求解第二行的翻转情况了。因为对于(1, 1)来说，此时只有(2, 1)能改变其状况。因此(2, 1)只有一种选择，接下来的(2, 2 ~ N-1)都是如此，第3 ~ M-1行也是。因此我们只需要枚举第一行的情况，就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 20;
const int dx[5] = {-1, 0, 0, 0, 1};
const int dy[5] = {0, -1, 0, 1, 0};
// 输入
int M, N;
int tile[MAXN][MAXN];

int opt[MAXN][MAXN];    // 保存最优解
int flip[MAXN][MAXN];   // 保存中间结果

// 查询(x, y)的颜色
// 需要统计自身原始的颜色以及上下左右自己的翻转情况然后决定当前的颜色
int get(int x, int y) {
    int c = tile[x][y];
    for(int d = 0; d < 5; d++) {
        int x2 = x + dx[d], y2 = y + dy[d];
        if(0 <= x2 && x2 < M && 0 <= y2 && y2 < N) {
            c += flip[x2][y2];
        }
    }
    return c % 2;
}

// 求出第一行确定的情况下的最小操作次数，如果不存在的话返回-1
int calc() {
    // 求出从第2行开始的翻转方法
    for(int i = 1; i < M; i++) {
        for(int j = 0; j < N; j++) {
            if(get(i - 1, j) != 0) {
                // 如果(i - j)为黑色的话，就必须要翻转这个格子
                flip[i][j] = 1;
            }
        }
    }
    // 判断最后一行是否是全白
    for(int j = 0; j < N; j++) {
        if(get(M - 1, j) != 0) {
            return -1;
        }
    }
    // 统计翻转次数
    int res = 0;
    for(int i = 0; i < M; i++) {
        for(int j = 0; j < N; j++) {
            res += flip[i][j];
        }
    }
    return res;
}

void solve() {
    int res = -1;
    // 按照字典序尝试第一行的所有可能性
    // 利用二进制进行枚举
    for(int i = 0; i < 1 << N; i++) {
        memset(flip, 0, sizeof(flip));
        for(int j = 0; j < N; j++) {
            flip[0][N - j - 1] = i >> j & 1;
        }
        int num = calc();
        if(num >= 0 && (res < 0 || num < res)) {
            res = num;
            memcpy(opt, flip, sizeof(flip));
        }
    }
    if(res < 0) {
        printf("IMPOSSIBLE\n");
    } else {
        for(int i = 0; i < M; i++) {
            for(int j = 0; j < N; j++) {
                printf("%d%c", opt[i][j], j + 1 == N ? '\n' : ' ');
            }
        }
    }
}

int main() {
    while(scanf("%d%d", &M, &N) != EOF) {
        for(int i = 0; i < M; i++) {
            for(int j = 0; j < N; j++) {
                scanf("%d", &tile[i][j]);
            }
        }
        solve();
    }
}

整数的集合表示

在程序中表示集合的方法有很多种，当元素数比较少时，使用二进制表示比较方便。集合{0, 1, ..., n-1}子集S可以用如下方法编码成整数：

f(S) = \underset{i \in S} \sum 2^i

像这样表示之后，一些集合运算可以对应地写成如下形式：

  • 空集ϕ\phi 0
  • 只含有第i个元素的集合{i} 1<<i
  • 含有全部n个元素的集合{0, 1, ..., n-1} (1<<n)-1
  • 判断第i个元素是否属于集合S if(S >> i & 1)
  • 向集合中加入第i个元素S∪{i} S|1<<i
  • 从集合中去除第i个元素S\{i} S&~(1<<i)
  • 集合S和T的并集S∪T S|T
  • 集合S和T的并集S∩T S&T

此外，若想将集合{0, 1, ..., n-1}的所有自己枚举出来的话，可以像下面这样书写:

1
2
3
for(int S = 0; S < 1<<n;  S++) {	
	// 对子集的处理
}

按照这个顺序循环的话，S便会从空集开始，然后按照{0}, {1}, {0, 1}, ...,{0, 1, ..., n-1}的升序顺序枚举出来

如果想要枚举某个 集合sup的自己。这里sup是一个二进制码，其本身也是某个集合的子集。例如01101101。之前是从0开始不断加1枚举出了全部的子集，但这种题型需要从sup开始每次减1直到0为止。由于sub-1并不一定是sup的子集，所以，我们把它与sup进行按位与&。这样的话，就可以将sup所有的子集按照降序列举出来。sub-1&sup或忽略sup中的0而从sub中减去1

1
2
3
4
int sub = sup;
do {
	sub = (sub - 1) & sup;
} while(sub != sup);	// 处理完0之后，会有-1&sup = sup

枚举{0, 1, ..., n-1}所包含的所有大小为k的子集的方法。

通过使用位运算我们可以像如下代码所示简单地按照字典序升序地枚举出所有满足条件的二进制代码。

1
2
3
4
5
6
int comb = (1 << k) - 1;
while(comb < 1 << n) {
    // 在这里进行针对组合的处理
    int x = comb & -comb, y = comb + x;
    comb = ((comb & ~y) / x >> 1) | y;
}

按照字典序的话，最小的子集是1 << k - 1，所以用它作为初始值。

求出comb下一个二进制码的方法：

  • (1).求出最低位的1开始的连续的1的区间：0101110 -> 0001110

  • (2).将这一区间全部变为0，并将区间左侧的那个0变为1：0101110 -> 0110000

  • (3).将第(1)步里取出的区间右移，直到剩下的1的个数减少了1个：0001110 -> 0000011

  • (4).将第(2)步和第(3)步的结果按位或0110000 | 0000011 -> 0110011

代码解析：

对于非零的整数，x & -x的值就是将其最低位的1独立出来后的值。这是由于计算机中负数采用二进制补码表示，-x实际上对应于(~x) + 1（将x按位取反然后加上1）

将最低位的1取出后，设它为x。那么通过计算y = comb + x，就将comb从最低位的1开始连续的1置为0了。通过计算z = comb & ~y就得到了最低位1开始的连续区间。比如若comb = 0101110，则x = 0000010, y = 0110000, z = 0001110

同时，y也恰好是第(2)步的要求。那么首先将z不断右移，直到最低位为1，这通过计算z/x即可完成。这样再将z/x右移一位就得到了第(3)步要求的值。这样我们就得到了comb之后的下一个二进制列。因为是从n个元素的集合中进行选择，所以comb的值不能大于等于1<<n。如此一来，就完成了大小为k的所有子集的枚举。