开关问题

一维的开关问题

题目1：http://poj.org/problem?id=3276

这题需要求对于特定的k，让所有牛都面朝前方所需的最小操作次数。要明确的是：对于同一个区间，进行两次以上的翻转，没有意义，因此我们确定一头牛是正向还是反向，可以看他的翻转次数。并且，交换区间的翻转顺序对结果没有影响。

先考虑最左端的牛，如果他面朝前方，那就不需要翻转，问题规模-1。如果它面朝后方，则翻转，然后向右找到下一个面朝后方的牛，继续执行上面的操作。

但是，这样子的时间复杂度是O(N³)，因此我们需要优化。我们可以用一个数组f[i]来表示[i, i+K-1]这个区间上的牛是否进行了翻转（他们在这次翻转中，是一个整体），然后维护一个sum，记录当前牛经过了几次翻转，那么时间复杂度可以优化到O(N²).

AC代码

#include <string.h>
#include <iostream>
using namespace std;
#define MAXN 5005

int a[MAXN];
int n;
int f[MAXN]; //代表[i, i+k-1]被翻转的次数
int main()
{
    scanf("%d", &n);
    char tmpc;
    for (int i = 0; i < n; ++i)
    {
        scanf("%s", &tmpc);
        if (tmpc == 'B')
            a[i] = 1;
        else
            a[i] = 0;
    }

    int ansk = MAXN, minm = 100 * MAXN;
    for (int k = 1; k <= n; ++k)
    {
        int sum = 0;
        int m = 0;
        memset(f, 0, sizeof(f));
        for (int i = 0; i + k <= n; ++i)
        {
            if ((a[i] + sum) % 2 != 0)
            {
                //当前的牛面朝后方,将其反转
                ++m;
                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 ((sum + a[i]) % 2 != 0)
            {
                //无解
                m = -1;
            }
            else
            {
                sum -= f[i - k + 1];
            }
        }
        if (minm > m && m >= 0)
        {
            minm = m;
            ansk = k;
        }
    }
    printf("%d %d\n", ansk, minm);
}

二维的开关问题

题目：http://poj.org/problem?id=3279

还是和上面的类似，同一个格子翻转两次以上是没有意义的。然后，和上面那题类似的思路。在上面那题中，让最左端的牛翻转的方法只有1种，但是，在这个问题里，最左上角的格子有两种翻转方式。那怎么办？我们可以先确定好第一行的翻转方式，然后从第二行开始翻转，只要当前格子的上方的格子是黑色的，那就翻转当前格子。然后，最后就检查一下最后一行，是否全为白色，如果全为白色则不行。

这里涉及到一个生成集合的方法，待会专门写一篇博文来记录一下。

AC代码

#include <iostream>
#include <string.h>
using namespace std;

typedef long long ll;
#define MAXN 17
int mp[MAXN][MAXN];
int op[MAXN][MAXN];
int opt[MAXN][MAXN];
const int dx[5] = {0, 0, 0, 1, -1};
const int dy[5] = {0, 1, -1, 0, 0};

int n, m;

bool get(int x, int y)
{
    //判断(x,y)的颜色
    int cnt = int(mp[x][y]);
    for (int i = 0; i < 5; ++i)
    {
        int x2 = x + dx[i], y2 = y + dy[i];
        if (0 <= x2 && x2 < m && 0 <= y2 && y2 < n)
            cnt += op[x2][y2];
    }
    return cnt % 2;
}
int calc()
{
    for (int a = 1; a < m; ++a)
    {
        for (int b = 0; b < n; ++b)
        {
            if (get(a - 1, b) != 0)
            {
                //当前格子上一行的格子是黑色的，需要翻转当前格子
                op[a][b] = 1;
            }
        }
    }
    for (int j = 0; j < n; ++j)
    {
        if (get(m - 1, j))
        {
            //最后一行还有黑色格子，无解
            return -1;
        }
    }

    int ans = 0;
    for (int a = 0; a < m; ++a)
    {
        for (int b = 0; b < n; ++b)
        {
            if (op[a][b])
                ++ans;
        }
    }

    return ans;
}
int main()
{
    scanf("%d%d", &m, &n);
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            scanf("%d", &mp[i][j]);
    int res = -1;
    for (int i = 0; i < (1 << n); ++i)
    {
        memset(op, 0, sizeof(op));
        //生成第一行的各种翻转方式
        for (int j = 0; j < n; ++j)
        {
            op[0][n - j - 1] = (i >> j) & 1;
        }

        int num = calc();

        if (num >= 0 && (res < 0 || res > num))
        {
            res = num;
            memcpy(opt, op, sizeof(op));
        }
    }
    if (res < 0)
    {
        printf("IMPOSSIBLE\n");
    }
    else
    {
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                printf("%d ", opt[i][j]);
            }
            printf("\n");
        }
    }
}

转载请注明来源：https://www.longjin666.top/?p=1192

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~