【开关问题】POJ 3276 3279 3185 1222
POJ 3276
题目地址：http://poj.org/problem?id=3276
题目大意
$N$头牛排成一列，每头牛要么向前要么者向后。为了让所有牛都向前，约翰买了一台机器，这台机器在购买时就必须设定一个$K$值，机器每操作一次恰好使$K$头连续的牛转向。求出让所有牛都朝向前方需要的最少操作次数$M$和对应的$K$值。
思路
既然求最小次数，那么翻转多次是多余的。因为翻转顺序不影响最终结果，可以从第一头牛开始，若反向则必须翻转一次。
设$f(i)$表示区间$[i, i+K-1]$是否需要翻转，若需要则为1否则为0。
那么操作到第$j$头牛的时候，只需要判断$sum_j = \sum_{i=j-K+1}^{j-1}f(i)$是否为奇数，若为奇数则表示翻转过。接着根据当前$j$牛的方向来确定$f(j)$的值。最后判断剩下的牛是否全部为正向即可。
AC代码
/*************************************************************************
> File Name: 3276.cpp
> Author: Netcan
> Blog: http://www.netcan666.com
> Mail: 1469709759@qq.com
> Created Time: 2016-01-01 五 14:30:29 CST
************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int N;
bool cow[5000+5]; // 'F'为1，’B'为0
bool f[5000+5]; // F[i]表示F[i, i+K-1]部分是否进行了反转
int calc(int K) {
int res = 0;
int sum = 0; // 表示第i头牛是否反转，反转了则为奇数，否则为偶数
memset(f, false, sizeof(f));
for(int i=0; i<=N-K; ++i) {
if((sum + cow[i]) % 2 == 0) {
++res;
f[i] = true;
}
sum += f[i]; // 计算下一个sum
if(i-K+1>=0) sum-=f[i-K+1];
}
for(int i=N-K+1; i<N; ++i) {
if((sum + cow[i]) % 2 == 0) return -1;
if(i-K+1>=0) sum-=f[i-K+1];
}
return res;
}
void solve() {
int K=1, M = N;
for(int k=1; k<=N; ++k) {
int step = calc(k);
if(step < M && step > 0) {
M = step;
K = k;
}
}
printf("%d %d\n", K, M);
}
int main() {
#ifdef Oj
freopen("3276.in", "r", stdin);
#endif
cin >> N;
char c;
for (int i = 0; i < N; ++i) {
cin >> c;
cow[i] = c=='F';
}
solve();
return 0;
}
POJ 3279
题目地址：http://poj.org/problem?id=3279
题目大意
有一个$M\times N$的棋盘，棋盘格子可以翻转正反面，一面是黑色，另一面是白色。每翻转一个格子，会将其上下左右的格子也翻转，求问所有格子翻转成白色需要的最少步数的解。
思路
这题也是枚举，先枚举第一行状态，然后枚举第二第三行到最后一行，使得上一行都为白色，最后判断最后一行是否都为白色即可。
AC代码
/*************************************************************************
> File Name: 3279.cpp
> Author: Netcan
> Blog: http://www.netcan666.com
> Mail: 1469709759@qq.com
> Created Time: 2016-01-01 五 16:01:03 CST
************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int M, N;
bool tile[20][20]; // 输入棋盘状态，1为黑色，0为白色
bool flip[20][20]; // 翻转状态
bool opt[20][20]; // 最优解
// 邻接格子坐标
int dx[] = {0, -1, 1, 0, 0};
int dy[] = {0, 0, 0, 1, -1};
void show_tile(bool t[20][20]) {
for(int i=0; i<M; ++i) {
for(int j=0; j<N; ++j)
printf("%d ", t[i][j]);
printf("\n");
}
}
bool get_color(int i, int j) { // 获得(i, j)格子的颜色，黑色返回1，白色返回0
int c = tile[i][j];
for(int d=0; d<5; ++d) {
int nx = i+dx[d], ny = j+dy[d];
if(nx >= 0 && nx < M && ny >=0 && ny < N) c+=flip[nx][ny];
}
return c&1;
}
int calc() { // 计算第一行确定后，所需要的步数，不存在返回-1
for(int i=1; i<M; ++i)
for(int j=0; j<N; ++j)
if(get_color(i-1, j)) // 上一个格子为黑色的话，需要翻转
flip[i][j] = 1;
for(int j=0; j<N; ++j) // 判断最后一行是否全为0
if(get_color(M-1, j)) return -1;
int res = 0;
for(int i=0; i<M; ++i)
for(int j=0; j<N; ++j) if(flip[i][j]) ++res;
return res;
}
void solve() {
int res = -1;
for(int i=0; i<(1<<N); ++i) { // 枚举第一行所有翻转状态，有2^N种情况
memset(flip, false, 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 || res > num)) {
res = num;
memcpy(opt, flip, sizeof(flip));
}
}
if(res == -1) puts("IMPOSSIBLE");
else show_tile(opt);
}
int main() {
#ifdef Oj
freopen("3279.in", "r", stdin);
#endif
cin >> M >> N;
for (int i = 0; i < M; ++i)
for (int j = 0; j < N; ++j)
cin >> tile[i][j];
solve();
return 0;
}
POJ 3185
题目地址：http://poj.org/problem?id=3185
题目大意
有20个碗排成一行，要么朝上要么朝下。每次翻转一个碗会将旁边两个碗也翻转。问将所有碗都翻上来所需要的最少步骤数。
思路
这题也很简单啊。。只要确定第一个碗要不要翻，有两种情况，然后在枚举计算其他碗即可。。
AC代码
/*************************************************************************
> File Name: 3185.cpp
> Author: Netcan
> Blog: http://www.netcan666.com
> Mail: 1469709759@qq.com
> Created Time: 2016-01-02 六 13:38:55 CST
************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
bool bowls[20+5]; // 目标全部翻转为0
bool flip[20+5]; // flip[i]表示i是否需要翻转
bool get_stat(int i) { // 第i个碗的状态
int res = bowls[i];
for(int d=-1; d<=1; ++d) {
int nd = i + d;
if(nd >= 0 && nd < 20) res += flip[nd];
}
return res & 1;
}
int calc() {
for(int i=1; i<20; ++i)
if(get_stat(i-1)) flip[i] = true;
if(get_stat(19)) return -1;
int res = 0;
for(int i=0; i<20; ++i) if(flip[i]) ++res;
return res;
}
void solve() {
int ans = -1;
for(int i=0; i<(1<<1); ++i) {// 第一个碗有两种状态
memset(flip, 0, sizeof(flip));
for(int j=0; j<1; ++j) flip[0] = (i >> j) & 1;
int step = calc();
if(step >= 0 && (ans < 0 || ans > step)) ans = step;
}
cout << ans << endl;
}
int main() {
#ifdef Oj
freopen("3185.in", "r", stdin);
#endif
for(int i=0; i<20; ++i) cin >> bowls[i];
solve();
return 0;
}
POJ 1222
题目地址：http://poj.org/problem?id=1222
题目大意
在一个$5\times 6$的棋盘上，每个格子有一个按钮，按钮上有个灯泡。然后按下按钮会将该格子与其相邻格子的灯的状态都翻转（亮的变暗，暗的变亮），问将所有灯都熄灭所需要的操作。
思路
哈哈，1A。这题算是开关问题鼻祖（02年）了吧。。和前面POJ 3279差不多，枚举好第一行的状态，然后计算第二第三行到最后一行，使得上一行都熄灯，最后判断最后一行是否都为熄灯即可。
AC代码
/*************************************************************************
> File Name: 1222.cpp
> Author: Netcan
> Blog: http://www.netcanMAX_NMAX_NMAX_N.com
> Mail: 14MAX_N97097MAX_M9@qq.com
> Created Time: 201MAX_N-01-02 六 14:31:32 CST
************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAX_M = 5;
const int MAX_N = 6;
bool light[MAX_M][MAX_N]; // 0表示熄灯，1表示亮灯，要求最终状态都为熄灯
bool flip[MAX_M][MAX_N]; // flip[i][j]表示是(1)否(0)按下(i, j)开关
int dx[] = {0, -1, 1, 0, 0}; // 邻接开关坐标
int dy[] = {0, 0, 0, 1, -1};
int T;
bool get_stat(int i, int j) { // 获取(i, j)灯泡的状态
int res = light[i][j];
for(int d=0; d<MAX_M; ++d) {
int nx = i+dx[d];
int ny = j+dy[d];
if(nx >= 0 && nx < MAX_M && ny >= 0 && ny < MAX_N) res += flip[nx][ny];
}
return res & 1;
}
int calc() {
for(int i=1; i<MAX_M; ++i)
for(int j=0; j<MAX_N; ++j)
if(get_stat(i-1, j)) flip[i][j] = 1;
for(int j=0; j<MAX_N; ++j) // 最后一行
if(get_stat(MAX_M-1, j)) return -1;
int res = 0;
for (int i = 0; i < MAX_M; ++i)
for (int j = 0; j < MAX_N; ++j) res+=flip[i][j];
return res;
}
void show_light(bool t[MAX_M][MAX_N]) {
for(int i=0; i<MAX_M; ++i)
for(int j=0; j<MAX_N; ++j)
printf("%d%c", t[i][j], j==MAX_N-1?'\n':' ');
}
void solve() {
// 枚举第一行所有状态。
for(int i=0; i<(1<<MAX_N); ++i) {
memset(flip, 0, sizeof(flip));
for(int j=0; j<MAX_N; ++j) flip[0][j] = (i >> j) & 1;
if(calc() >= 0) {
show_light(flip);
return; // 有解即可
}
}
}
int main() {
#ifdef Oj
freopen("1222.in", "r", stdin);
#endif
scanf("%d", &T);
for(int t=1; t<=T; ++t) {
for(int i=0; i<MAX_M; ++i)
for (int j = 0; j < MAX_N; ++j) scanf("%d", &light[i][j]);
printf("PUZZLE #%d\n", t);
solve();
}
return 0;
}
- 本文标题：【开关问题】POJ 3276 3279 3185 1222
- 本文字数：1,893
- 本文作者：Netcan
- 发布时间：2016年01月01日 - 16时49分
- 最后更新：2016年09月24日 - 22时18分
- 原始链接：http://www.netcan666.com/2016/01/01/【开关问题】POJ-3276/
- 版权声明："署名-非商用-相同方式共享 3.0"转载请保留原文链接及作者。