挑战程序竞赛系列（21）：3.2反转
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434639
挑战程序竞赛系列（21）：3.2反转
详细代码可以fork下Github上leetcode项目，不定期更新。
练习题如下：
- POJ 3276: Face The Right Way
- POJ 3279: Fliptile
- POJ 3185: The Water Bowls
- POJ 1222: Extended Lights Out
POJ 3276: Face The Right Way
解题策略：
每次从最左区间开始，遍历每种可能的k，如k = 3的情况下，开始对每头牛进行翻转，如果最左区间的牛是朝前的，则可以忽略，如果是朝后的，则进行翻转。
策略证明：（从最终态想象，最左端的区间最多只会翻转一次，2次和3次效果和0次1次相同）
第一个版本（模拟）：
void solve() {
int N = ni();
char[] cow = new char[N];
for (int i = 0; i < N; ++i) cow[i] = nc();
int k = N;
int min = 1 << 30;
int minK = k;
for (int i = k; i >= 1; --i){
int cnt = 0;
char[] clone = Arrays.copyOf(cow, N);
for (int j = 0; j < N - i + 1; ++j){
if(clone[j] == 'F' ) continue;
for (int l = j; l < i + j; ++l){
clone[l] = clone[l] == 'F' ? 'B' : 'F';
}
cnt++;
}
boolean isValid = true;
for (int j = N - i + 1; j < N; ++j){
if(clone[j] == 'B'){
isValid = false;
break;
}
}
if (isValid && cnt != 0 && cnt < min){
min = cnt;
minK = i;
}
}
out.println(minK + " " + min);
}TLE了，时间复杂度为O(n3)O(n^3)，模拟是把所有情况走一遍，更客观的原因在于，如果窗口较大，虽然最多只翻转n-k+1次，但一头牛可以翻转多次，模拟把这种翻转多次体现地淋漓尽致。
从数学的角度来看，如果一个区间被翻转奇数次，那么此牛的状态与原状态互异，如果偶数次，此牛状态与原状态相同。所以，k次的翻转是否可以省略了？
按照书上的公式：
∑j=i−K+1i−1fj
\sum_{j = i - K + 1}^{i-1} fj
如果为奇数，且牛是F，则翻转，如果为偶数，且牛是B，则翻转。
第二版本：
void solve() {
int N = ni();
char[] cow = new char[N];
for (int i = 0; i < N; ++i) cow[i] = nc();
int[] f = new int[N];
int min = 1 << 30;
int minK = N;
for (int k = N; k >= 1; --k){
f = new int[N];
for (int i = 0; i < N - k + 1; ++i){
int sum = 0;
for (int j = Math.max(0, i - k + 1); j < i; ++j){
sum += f[j];
}
if ((sum & 1) != 0 && cow[i] == 'F') f[i] = 1;
else if ((sum % 2) == 0 && cow[i] == 'B') f[i] = 1;
}
//检查后续不能翻转，牛的状态
boolean isValid = true;
for (int i = N - k + 1; i < N; ++i){
int sum = 0;
for (int j = Math.max(0, i - k + 1); j < i; ++j){
sum += f[j];
}
if ((sum & 1) != 0 && cow[i] == 'F') isValid = false;
else if ((sum % 2) == 0 && cow[i] == 'B') isValid = false;
}
if(isValid){
int cnt = 0;
for (int i = 0; i < N; ++i){
cnt += f[i];
}
if (cnt != 0 && cnt < min){
min = cnt;
minK = k;
}
}
}
out.println(minK + " " + min);
}呵呵，还是TLE了，虽然没有模拟那么夸张，既要修改牛的状态，又要记录翻转次数，但观察上述代码，它还是有k次循环，内循环中的每个sum是独立的，所以慢。
如果对滑动窗口熟悉的话，它的一个优化就是把窗口大小的sum缓存下来，而每次更新窗口时，它的更新规则为：
∑j=i−K+1+1ifj=∑j=i−K+1i−1fj+fi−fi−K+1
\sum_{j = i - K + 1 + 1}^{i} fj = \sum_{j = i - K + 1}^{i-1}fj + fi - fi - K + 1
可以理解成累加和，或者缓存，或者空间换时间，whatever，但需要知道的是滑动窗口移动时，k-1元素的关联性可以有效利用起来。
第三版本：
void solve() {
int N = ni();
char[] cow = new char[N];
for (int i = 0; i < N; ++i) cow[i] = nc();
int[] f = new int[N];
int min = 1 << 30;
int minK = N;
for (int k = N; k >= 1; --k){
f = new int[N];
int sum = 0;
for (int i = 0; i < N - k + 1; ++i){
if ((sum & 1) != 0 && cow[i] == 'F') f[i] = 1;
else if ((sum % 2) == 0 && cow[i] == 'B') f[i] = 1;
sum += f[i];
if (i - k + 1 >= 0){
sum -= f[i - k + 1];
}
}
boolean isValid = true;
for (int i = N - k + 1; i < N; ++i){
if ((sum & 1) != 0 && cow[i] == 'F') isValid = false;
else if ((sum % 2) == 0 && cow[i] == 'B') isValid = false;
if (i - k + 1 >= 0){
sum -= f[i - k + 1];
}
}
if(isValid){
int cnt = 0;
for (int i = 0; i < N; ++i){
cnt += f[i];
}
if (cnt != 0 && cnt < min){
min = cnt;
minK = k;
}
}
}
out.println(minK + " " + min);
}POJ 3279: Fliptile
书上的思路讲的很清楚，因为每一格最多只会翻一次，所以翻过的就不会再翻了，这点很关键。
一般的做法是遍历所有格子，选择翻or不翻，复杂度为O(2MN)O(2^{MN})，考虑到每个格子的关联性，可以降低复杂度，比如，确定了第一行的排列，总共有2N2^N次种翻法。
那么由于第一行翻过的就不会再动，那么第一行中还存在黑色格子的情况下，只能选择第二行的某个格子去除，这是一种一一对应关系，连带着把后面所有的情况都确定了。所以复杂度就只有O(MN2MN)O(MN2^{MN}).
上述性质很难证明，此类题难道只能靠猜？
代码如下：（模拟）
int[][] dir = {{0,0},{1,0},{-1,0},{0,1},{0,-1}};
void solve() {
int M = ni();
int N = ni();
int[][] board = new int[M][N];
for (int i = 0; i < M; ++i){
for (int j = 0; j < N; ++j){
board[i][j] = ni();
}
}
int[][] click = new int[M][N];
int min = 1 << 30;
int[][] ans = new int[M][N];
for (int i = 0; i < 1 << N; ++i){
click = new int[M][N];
int[][] clone = clone(board);
for (int j = 0; j < N; ++j){
click[0][N - 1 - j] = ((i & (1 << j)) != 0) ? 1 : 0;
}
flip(clone, click, 0);
for (int j = 1; j < M; ++j){
for (int k = 0; k < N; ++k){
click[j][k] = clone[j-1][k];
}
flip(clone, click, j);
}
if(!valid(clone)) continue;
int cnt = cal(click);
if (cnt != 0 && cnt < min){
min = cnt;
ans = clone(click);
}
}
if (min == 1 << 30){
out.println("IMPOSSIBLE");
return;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < M; ++i){
for (int j = 0; j < N; ++j){
sb.append(ans[i][j] + ((j + 1 != N) ? " " : "\n"));
}
}
out.println(sb.toString());
}
public int cal(int[][] click){
int M = click.length;
int N = click[0].length;
int cnt = 0;
for (int i = 0; i < M; ++i){
for (int j = 0; j < N; ++j){
cnt += click[i][j];
}
}
return cnt;
}
public boolean valid(int[][] board){
int M = board.length;
int N = board[0].length;
for (int i = 0; i < M; ++i){
for (int j = 0; j < N; ++j){
if (board[i][j] != 0) return false;
}
}
return true;
}
public void flip(int[][] board, int[][] click, int row){
int N = click[0].length;
int M = click.length;
for (int i = 0; i < N; ++i){
if (click[row][i] == 1){
for (int[] d : dir){
int x = d[0] + row;
int y = d[1] + i;
if (x >= 0 && x < M && y >= 0 & y < N){
board[x][y] = board[x][y] == 1 ? 0 : 1;
}
}
}
}
}
public int[][] clone(int[][] board){
int M = board.length;
int N = board[0].length;
int[][] clone = new int[M][N];
for (int i = 0; i < M; ++i){
for (int j = 0; j < N; ++j){
clone[i][j] = board[i][j];
}
}
return clone;
}POJ 3185: The Water Bowls
苦苦折腾了一个小时。。。至今不知道之前的做法哪里错了，蛋疼。头尾可以翻转2个碗，中间的必须翻转3个碗，这是此题唯一的一个trick。想法是，把20扩充到21，这样当第一个元素为1时，相当于在头部翻转2个碗。
代码如下：
int MAX_N = 20 + 1;
int[] dir = new int[MAX_N];
int[] f = new int[MAX_N];
void solve() {
for (int i = 1; i < 21; ++i) dir[i] = ni();
out.println(Math.min(calc(0), calc(1)));
}
int calc(int fir){
int N = MAX_N;
f = new int[MAX_N];
dir[0] = fir;
int res = 0;
int sum = 0;
for (int i = 0; i < N - 1; ++i){
if (((dir[i] + sum) & 1) != 0){
++res;
f[i] = 1;
}
sum += f[i];
if (i - 2 >= 0) sum -= f[i -2];
}
if (((dir[N-1] + sum) & 1) != 0){
return 1 << 30;
}
return res;
}POJ 1222: Extended Lights Out
好气啊，和第二题基本一个解题模式，但此题不需要输出最小的步数，直接枚举出一种答案即可？搞不懂，为什么加个最小步数，就WA了。
代码如下：
void solve() {
int n = ni();
for (int k = 1; k <= n; ++k){
int M = 5;
int N = 6;
int[][] board = new int[M][N];
for (int i = 0; i < M; ++i){
for (int j = 0; j < N; ++j){
board[i][j] = ni();
}
}
out.println("PUZZLE #" + k);
out.println(calc(board, M, N));
}
}
int[][] dir = {{0,0},{1,0},{-1,0},{0,1},{0,-1}};
String calc(int[][] board, int M, int N) {
int[][] click = new int[M][N];
int[][] ans = new int[M][N];
for (int i = 0; i < 1 << N; ++i){
click = new int[M][N];
int[][] clone = clone(board);
for (int j = 0; j < N; ++j){
click[0][N - 1 - j] = ((i & (1 << j)) != 0) ? 1 : 0;
}
flip(clone, click, 0);
for (int j = 1; j < M; ++j){
for (int k = 0; k < N; ++k){
click[j][k] = clone[j-1][k];
}
flip(clone, click, j);
}
if(!valid(clone)) continue;
ans = clone(click);
break;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < M; ++i){
for (int j = 0; j < N; ++j){
sb.append(ans[i][j] + ((j + 1 != N) ? " " : "\n"));
}
}
return sb.toString().substring(0, sb.length() - 1);
}
public int cal(int[][] click){
int M = click.length;
int N = click[0].length;
int cnt = 0;
for (int i = 0; i < M; ++i){
for (int j = 0; j < N; ++j){
cnt += click[i][j];
}
}
return cnt;
}
public boolean valid(int[][] board){
int M = board.length;
int N = board[0].length;
for (int i = 0; i < M; ++i){
for (int j = 0; j < N; ++j){
if (board[i][j] != 0) return false;
}
}
return true;
}
public void flip(int[][] board, int[][] click, int row){
int N = click[0].length;
int M = click.length;
for (int i = 0; i < N; ++i){
if (click[row][i] == 1){
for (int[] d : dir){
int x = d[0] + row;
int y = d[1] + i;
if (x >= 0 && x < M && y >= 0 & y < N){
board[x][y] = board[x][y] == 1 ? 0 : 1;
}
}
}
}
}
public int[][] clone(int[][] board){
int M = board.length;
int N = board[0].length;
int[][] clone = new int[M][N];
for (int i = 0; i < M; ++i){
for (int j = 0; j < N; ++j){
clone[i][j] = board[i][j];
}
}
return clone;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017年06月28日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
