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;
}