《挑战程序设计竞赛》3.2.2 常用技巧-反转 POJ3276 3279 3185 1222

本文主要是介绍《挑战程序设计竞赛》3.2.2 常用技巧-反转 POJ3276 3279 3185 1222，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

POJ3276

http://poj.org/problem?id=3276

题意

N头牛排成一列1<=N<=5000。每头牛或者向前（表示为F）或者向后（表示为B）。为了让所有牛都面向前方，农夫每次可以将K头连续的牛转向1<=K<=N，求操作的最少次数M和对应的最小K。

思路

所有情况穷举O（2^N）肯定超时。
顺序考虑每头牛的反转方向能不能行呢？因为想改变一头牛的方向就必定影响k头牛，但再思考一下，当一头牛被反转2的倍数次时，与初始方向相同，可视为无反转，所以对于每头牛来说，只有被反转和未反转两种操作。
但我们要枚举的是大小为K的区间的反转，顺序考虑时每个区间的反转状态可以被前面的状态所确定，这时候最坏情况下复杂度O（N^3）。这里可以用sum来记录前面的反转状态和，从而将复杂度降到O（N^2），具体见代码。
此题值得注意的地方：
（1）判断条件很容易出错，需要考虑清楚n和k的所有情况，我因为没写好判断，WA了两次。
（2）这个题中二进制的妙用可在代码中细细体会。
（3）用bool存储似乎能进一步缩减内存使用，当然代码需要同步优化。

代码

Source CodeProblem: 3276       User: liangrx06
Memory: 276K        Time: 360MS
Language: C++       Result: Accepted
Source Code
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;const int N = 5000;int main(void)
{int n;int f[N], t[N];cin >> n;char c[2];for (int i = 0; i < n; i ++) {scanf("%s", c);if (c[0] == 'F')f[i] = 0;elsef[i] = 1;}int ansm = n, ansk = 1;for (int k = 1; k <= n; k ++) {int m = 0;int sum = 0;for (int i = 0; i <= n-k; i ++) {t[i] = (f[i] + sum)&1;m += t[i];sum += t[i];if (i-k+1 >= 0) sum += t[i-k+1];}int flag = 1;for (int i = n-k+1; i < n; i ++) {if ( ((f[i] + sum)&1) == 1)flag = 0;if (i-k+1 >= 0) sum += t[i-k+1];}if (flag == 1 && m < ansm) {ansm = m;ansk = k;}}printf("%d %d\n", ansk, ansm);return 0;
}

POJ3279

http://poj.org/problem?id=3279

题意

一个m*n的01矩阵，每次点击(x,y),那么她的上下左右以及本身就会0变1，1变0，问把矩阵变成全0的，最小需要点击多少步。如果有多个符合条件，求字典序最小的。

思路

枚举第一行翻转情况，2^m，然后验证，由于第一行确定了，后面就可以跟着确定了。
这个题看似思路清晰，实际做的过程中却出了不少错误，比如：
（1）字典序弄反了；
（2）应该验证最后一行，结果想错了；
（3）最优解首先要求的是最小步数，而不是字典序最小，我把顺序弄反了。
代码最终基本和书中例题一样了。

代码

Source CodeProblem: 3279       User: liangrx06
Memory: 248K        Time: 547MS
Language: C++       Result: Accepted
Source Code
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;const int N = 15;int m, n;
int f0[N][N], f[N][N], t[N][N], opt[N][N];
int d[5][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {0, 0}};void flip(int i, int j)
{if (t[i][j] == 0) return;for (int k = 0; k < 5; k ++) {int ii = i+d[k][0];int jj = j+d[k][1];if (0 <= ii && ii < m && 0 <= jj && jj < n)f[ii][jj] = (f[ii][jj]+1) & 1;}
}int main(void)
{cin >> m >> n;for (int i = 0; i < m; i ++)for (int j = 0; j < n; j ++)scanf("%d", &f0[i][j]);int minfcount = n*m+1;for (int r = 0; r < (1<<n); r ++) {int fcount = 0;memcpy(f, f0, sizeof(f));for (int j = 0; j < n; j ++) {t[0][n-1-j] = (r>>j)&1;fcount += t[0][n-1-j];flip(0, n-1-j);}for (int i = 1; i < m; i ++) {for (int j = 0; j < n; j ++) {t[i][j] = f[i-1][j];fcount += t[i][j];flip(i, j);/*printf("i=%d, j=%d==========\n", i, j);if (t[i][j]) {for (int ii = 0; ii < m; ii ++)for (int jj = 0; jj < n; jj ++)printf("%d%c", f[ii][jj], (jj == n-1) ? '\n' : ' ');}*/}}bool flag = true;for (int j = 0; j < n; j ++) {if (f[m-1][j] == 1) {flag = false; break;}}if (flag == true && fcount < minfcount) {minfcount = fcount;memcpy(opt, t, sizeof(t));}}if (minfcount == n*m+1)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 == n-1) ? '\n' : ' ');}return 0;
}

POJ3185

http://poj.org/problem?id=3185

题意

将一列碗（20个）翻成口朝上，一把下去可能同时反转3个或2个（首尾），求最小翻转次数。

思路

应该说是3276题的简单版，只有两种情况需要考虑：以第一个为中心的反转是否做。后续的反转据此可以确定，然后检验是否符合条件即可。

代码

Source CodeProblem: 3185       User: liangrx06
Memory: 164K        Time: 0MS
Language: C++       Result: Accepted
Source Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int n = 20;
int f0[n], f[n], t[n];void flip(int x)
{if (!t[x]) return;f[x] = (f[x]+1)&1;if (x > 0) f[x-1] = (f[x-1]+1)&1;if (x < n-1) f[x+1] = (f[x+1]+1)&1;
}int main(void)
{for (int i = 0; i < n; i ++)scanf("%d", &f0[i]);int best = n;for (int k = 0; k < 2; k ++) {memcpy(f, f0, sizeof(f));t[0] = k;int cnt = t[0];flip(0);for (int i = 1; i < n; i ++) {t[i] = f[i-1];cnt += t[i];flip(i);}if (f[n-1] == 0) {best = min(cnt, best);}}printf("%d\n", best);return 0;
}

POJ1222

http://poj.org/problem?id=1222

题意

poj3279的简单版，详见上文。
这个题固定了行列，而且只需要任意求一个答案就可以。

思路

直接把3279代码拿过来稍作修改即可。

代码

Source CodeProblem: 1222       User: liangrx06
Memory: 244K        Time: 16MS
Language: C++       Result: Accepted
Source Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 6;int m = 5, n = 6;
int f0[N][N], f[N][N], t[N][N], opt[N][N];
int d[5][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {0, 0}};void flip(int i, int j)
{if (t[i][j] == 0) return;for (int k = 0; k < 5; k ++) {int ii = i+d[k][0];int jj = j+d[k][1];if (0 <= ii && ii < m && 0 <= jj && jj < n)f[ii][jj] = (f[ii][jj]+1) & 1;}
}int main(void)
{int casecount;cin >> casecount;for (int puzzle = 1; puzzle <= casecount; puzzle ++) {for (int i = 0; i < m; i ++)for (int j = 0; j < n; j ++)scanf("%d", &f0[i][j]);int minfcount = n*m+1;for (int r = 0; r < (1<<n); r ++) {int fcount = 0;memcpy(f, f0, sizeof(f));for (int j = 0; j < n; j ++) {t[0][n-1-j] = (r>>j)&1;fcount += t[0][n-1-j];flip(0, n-1-j);}for (int i = 1; i < m; i ++) {for (int j = 0; j < n; j ++) {t[i][j] = f[i-1][j];fcount += t[i][j];flip(i, j);}}bool flag = true;for (int j = 0; j < n; j ++) {if (f[m-1][j] == 1) {flag = false; break;}}if (flag == true && fcount < minfcount) {minfcount = fcount;memcpy(opt, t, sizeof(t));break;}}printf("PUZZLE #%d\n", puzzle);for (int i = 0; i < m; i ++)for (int j = 0; j < n; j ++)printf("%d%c", opt[i][j], (j == n-1) ? '\n' : ' ');}return 0;
}