开关问题

POJ3276

题意：

N 头牛排成一列，每头牛或向前或向后。每次可以反转连续的 K 头牛，求出让所有的牛都能面向前方所需要的最少操作次数 M 和对应的最小的 K。

解法：

首先加入顺序的枚举每个以向后的牛开始的区间，让其反转，之后检查可行性，复杂度为 $O(n^3)$，即顺序遍历、反转、寻找第一个面向正面的奶牛，不可取。

所以这种问题的关键就是怎样优化区间反转的那一部分。

设：$f[i] = $区间$[i,i+K-1]$进行了反转的话则为$1$，否则为$0$.

这样在考虑第 i 头牛的时候，如果 $sum_{j=i-K+1}^{i-1}f[j]$为奇数的话，则这头牛的方向与起始方向是相反的，否则方向不变

又因为：$sum_{j=(i+1)-K+1}^{i}f[j]=sum_{j=i-K+1}^{i-1}f[j]+f[i]-f[i-K+1]$

这样每个区间的牛的反转情况就可以在$O(1)$的时间内算出来，可解。

int N;
int dir[MAXN];  // 牛的方向（0：F，1：B）
int f[MAXN];    //区间（i，i-K+1）是否进行反转

//固定K，求对应的最小操作回数
//无解返回-1
int calc(int K) {
    MEM(f, 0);
    int res = 0;
    int sum = 0;  // 包含点i的所有区间f的和
    for (int i = 0; i + K <= N; i++) {
        if ((dir[i] + sum) % 2 != 0) {
            // 前端的牛朝后方
            res++;
            f[i] = 1;
        }
        sum += f[i];
        if (i - K + 1 >= 0) sum -= f[i - K + 1];//向前推进区间，减掉之前区间的头
    }
    //单独检查剩下的牛是否有朝后方的情况
    for (int i = N - K + 1; i < N; i++) {
        if ((dir[i] + sum) % 2 != 0) return -1;  //无解
        if (i - K + 1 >= 0) sum -= f[i - K + 1];
    }
    return res;
}
// M为最小操作次数，K为对应的反转的区间长度
void solve() {
    int K = 1, M = N;
    for (int k = 1; k <= N; k++) {
        int m = calc(k);
        if (m > 0 && M > m) {
            M = m;
            K = k;
        }
    }
    printf("%d %d
", K, M);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    scanf("%d", &N);
    REP(i, 0, N - 1) {
        char c[2];
        scanf("%s", c);
        dir[i] = (c[0] == 'F') ? 0 : 1;
    }
    solve();
    return 0;
}

---

POJ3185

题意：一共有一行20个数，每个数字都是0或1，每次翻一个数都会将这个数两边的数取反，保证有解，求最少的反转次数

解法：其实就是K为3的开关反转问题，不同的是，在之前我们是把连续三个数按照左顶点推进，这样在 $i+k<=N$ 的时候就要退出了，但是这里不同的是，可以在 $i+k<=N+1$ 的时候再退出，因为驱动反转的是三个的中间那一个，具体的可以看下面的代码：

int N = 20;
int dir[MAXN];
int f[MAXN];

// 0, 1
bool CanFlip(int i, int sum) { return (dir[i] + sum) & 1; }

int solve() {
    MEM(f, 0);
    int res = 0, sum = 0;
    int K = 3;
    // 在开关问题的时候，这里是 i+K<=N，为什么？
    // 假如 K=3，那么当 i=18
    // 的时候，他就不能翻了，(这也是为什么在判断最后几位的时候没有sum+=f[i]).
    // 但是这里当 i=18 的时候还可以翻， 所以往前推一位
    for (int i = 0; i + K <= N + 1; i++) {
        if (CanFlip(i, sum)) {
            res++;
            f[i] = 1;
        }
        sum += f[i];
        if (i - K + 1 >= 0) sum -= f[i - K + 1];
    }
    for (int i = N - K + 1 + 1; i < N; i++) {
        if (CanFlip(i, sum)) return INF;  //无解
        if (i - K + 1 >= 0) sum -= f[i - K + 1];
    }
    return res;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    for (int i = 0; i < 20; i++) {
        scanf("%d", &dir[i]);
    }
    int ans1 = solve();
    reverse(dir, dir + 20);
    int ans2 = solve();
    // cout << ans1 << " " << ans2 << endl;
    printf("%d", min(ans1, ans2));
    return 0;
}

---

POJ1222

题意：给定一个5行6列的棋盘，每次反转会将这个棋子的上下左右包括他自己都会反转，求最后的反转方案

解法：其实再反转第一行之后，其他行怎么翻就已经确定了，所以我们枚举第一行的状态，之后验证最终局面存不存在未翻的棋子即可

int g[MAXN][MAXN];
int tmp[MAXN][MAXN];
int ans[MAXN][MAXN];
int first_line[MAXN];
bool flag;

void flip(int i, int j) {
    tmp[i][j] = !tmp[i][j];
    tmp[i - 1][j] = !tmp[i - 1][j];
    tmp[i + 1][j] = !tmp[i + 1][j];
    tmp[i][j - 1] = !tmp[i][j - 1];
    tmp[i][j + 1] = !tmp[i][j + 1];
    return;
}

bool check() {
    rep(i, 1, 5) rep(j, 1, 6) if (tmp[i][j]) return 0;
    return 1;
}

void dfs(int idx) {
    if (flag) return;

    if (idx == 7) {
        MEM(ans, 0);
        memcpy(tmp, g, sizeof(g));
        // flip first line
        rep(j, 1, 6) if (first_line[j]) {
            flip(1, j);
            ans[1][j] = 1;
        }
        // flip other lines
        rep(i, 2, 5) rep(j, 1, 6) if (tmp[i - 1][j]) {
            flip(i, j);
            ans[i][j] = 1;
        }

        if (check()) {
            flag = 1;
        }

        return;
    }

    for (int i = 0; i <= 1; i++) {
        first_line[idx] = i;
        dfs(idx + 1);
        if (flag) return;
    }

    return;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    int T = READ();
    for (int t = 1; t <= T; t++) {
        rep(i, 1, 5) rep(j, 1, 6) g[i][j] = READ();
        flag = false;
        dfs(1);

        printf("PUZZLE #%d
", t);
        for (int i = 1; i <= 5; i++) {
            for (int j = 1; j <= 6; j++) {
                if (j == 1)
                    printf("%d", ans[i][j]);
                else
                    printf(" %d", ans[i][j]);
            }
            printf("
");
        }
    }
    return 0;
}