反转(开关问题)(挑战程序设计竞赛)

系统管理员 2022-12-28 12:45 122阅读 0赞

### 文章目录 ###

*  例题1
 *   *  题目描述
     *  输入描述
     *  输出描述
     *  输入
     *  输出
     *  提示
     *  算法分析
     *  代码
 *  例题2
 *   *  题目描述
     *  输入描述
     *  输出描述
     *  输入
     *  输出
     *  算法分析
     *  解题代码
 *  例题3：

--------------------

# 例题1 #

## 题目描述 ##

农场主约翰把他的\*\*N(1 ≤ N ≤ 5,000)\*\*头奶牛排成一排，很多都是面向前方的，就像好奶牛一样。然而，有些人是面向过去的，而他需要所有人都面向未来，以使他的生活变得完美。

幸运的是，FJ最近买了一台自动翻牛机。因为他购买的是折扣型，所以必须一次性转\*\*K(1 ≤ K ≤ N)\*\*头，且只能转排在一起的奶牛。每次使用该机器时，它都会反转该行中一个连续的K头奶牛组的朝向(不能在少于K头的奶牛上使用，例如在该行的任意一端)。每头奶牛都保持着和之前一样的位置，但最终却朝着相反的方向。一头牛一开始朝前，机器就会把它向后转，反之亦然。

因为FJ必须选择一个单一的，不变的值K，请帮助他确定K的最小值，使机器所需的操作数量最小化，以使所有的牛面朝前。还要确定M，即使用K值使所有奶牛面向前方所需的机器操作的最小数量。

## 输入描述 ##

> 第1行：单个整数：**N**  
> 第2 . .N+1行：第**i+1**行包含一个字符**F或B**，表示\*\*cowi\*\*是面向前还是面向后。

## 输出描述 ##

> 第1行：两个用空格分隔的整数：**K和M**

## 输入 ##

7
    B
    B
    F
    B
    F
    B
    B

## 输出 ##

3 3

## 提示 ##

> 对于K = 3，机器必须操作三次：翻牛(1,2,3)，(3,4,5)，最后(5,6,7)

## 算法分析 ##

![1][] ![2][]

## 代码 ##

int N;
    int dir[Max_N];//表示每头牛的朝向
    int flag[Max_N];//flag[i]标志以第i头牛为首的k个位置的牛是否需要转向　1表示需要转向　0表示不需要转向
    
    int calc(int k)
    {
        
        fill(flag, flag + N, 0);//初始化标志数组
        int res = 0;
        int sum = 0;  //sum＝flag[i-1]+flag[i-2]+...+flag[i-k+1]记录在没有计算到第i头牛时，第i头牛被连带转向了几次
        for (int i = 0; i + k <= N; i++)
        {
        
          	//类似尺取法
            if((dir[i] + sum) % 2 != 0)//表示第i头牛正面向后方，需要转向
            {
        
                res++;
                flag[i] = 1;
            }
    
            sum += flag[i];
            if(i - k + 1 >= 0)
            {
        
                sum -= flag[i - k + 1];
            }
        }
      	//类似尺取法
        
        //最后一个区间的情况已经被前K-1个区间确定了
        //枚举这K-1个区间的sum情况
        //即可判断是否全部转向正确
        for (int i = N - k + 1; i < N; i++)
        {
        
            if((dir[i] + sum) % 2 != 0)//表示第i头牛正面向后方，需要转向
            {
        
                return -1;
            }
            if(i - k + 1 >= 0)
            {
        
                sum -= flag[i - k + 1];
            }
        }
    
        return res;
    }
    
    //枚举每一种的K值
    void solve()
    {
        
    		int k = 1, m = n;
        for (k = 1; k <= N; k++)
        {
        
            m = calc(k);
            if(m < M && m > 0)
            {
        
                M = m;
                K = k;
            }
        }
        cout << K << " " << M << endl;
    }

# 例题2 #

## 题目描述 ##

农夫约翰知道一头智力满足的奶牛是一头快乐的奶牛，它会产更多的奶。他为奶牛安排了一项脑力活动，让它们操作一个**M × N**的网格\*\*(1 ≤ M ≤ 15;1 ≤ N ≤ 15)\*\*方片，每方片一面为黑色，另一面为白色。

正如人们所猜测的那样，当一个白色的瓦片翻转时，它会变成黑色;当一个黑色的瓦片翻转时，它会变成白色。当奶牛翻转瓷砖使每一块瓷砖的白色面朝上时，它们就会得到奖励。然而，奶牛的蹄子相当大，当它们试图翻转某个瓦片时，它们也会翻转所有相邻的瓦片(与翻转的瓦片共享完整边缘的瓦片)。由于抛硬币很累人，奶牛们想尽量减少抛硬币的次数。

帮助奶牛确定最少需要翻几次，以及达到最少需要翻几次的位置。如果有多种方法可以用最少的翻转次数来完成任务，那么在将输出视为字符串时，请返回字典排序最少的方法。如果任务不可能完成，打印一行“IMPOSSIBLE”。

## 输入描述 ##

> 第1行：两个用空格分隔的整数：**M和N**  
> 第2 . .M+1行：第i+1行描述网格第i行的颜色(从左到右)，用N个空格分隔的整数，其中1表示黑色，0表示白色

## 输出描述 ##

> 第1 . .M行：每行包含N个以空格分隔的整数，每个整数指定翻转该特定位置的次数。

## 输入 ##

4 4
    1 0 0 1
    0 1 1 0
    0 1 1 0
    1 0 0 1

## 输出 ##

0 0 0 0
    1 0 0 1
    1 0 0 1
    0 0 0 0

## 算法分析 ##

![3][]

## 解题代码 ##

#include <iostream>
    #include <stack>
    #include <cstring>
    using namespace std;
    
    int m,n;
    int mp[20][20]; //输入
    int f[20][20];  //存储中间过程的按钮情况
    int ansf[20][20];   //存储结果的按钮情况
    int dx[5] = {
        -1, 0, 0, 0, 1};
    int dy[5] = {
        0, -1, 0, 1, 0};
    
    //查询一个点的颜色
    int get(int x, int y)
    {
        
        int c = mp[x][y];
        for(int d = 0; d < 5; d++){
        
            int x2 = x + dx[d], y2 = y + dy[d];
            if(x2 >= 0 && x2 <= m + 1 && y2 >= 0 && y2 <= n + 1)
                c += f[x2][y2];
        }
        
        return c % 2;
    }
    //查询一个点的颜色
    
    //求出在第一行按钮确定的情况下的最小操作数
    int calc()
    {
        
        for(int i = 2; i <= m; i++)
            for(int j = 1; j <= n; j++){
        
            //如果这行上面的格子是黑的，那么就要在这行翻转，使得上行都为白色
                if(get(i - 1, j)){
        
                    f[i][j] = 1;
                }
            }
    
        //检测最后一行是否存在黑色格子
        //如果存在黑色格子就说明这个情况不正确
        for(int i = 1; i <= n; i++){
        
            if(get(m, i))
                return -1;
        }
        
        //统计按下按钮的次数
        int res = 0;
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
                res += f[i][j];
        
        return res;
    }
    //求出在第一行按钮确定的情况下的最小操作数
    
    void solve()
    {
        
        int ans = -1;
        
        for(int i = 0; i < (1 << n); i++){
        
            memset(f, 0, sizeof(f));
            
            //十进制转换成二进制
            //第一行按钮的情况可以看成一个二进制代码
            for(int j = 1; j <= n; j++){
        
                //从右往左分配进制，为了保证最后答案是字典序最小
                //例如0000,0001,0010......
                f[1][n - j + 1] = i >> (j - 1) & 1;
            }
            //十进制转换成二进制
            
            int num = calc();
            if(num >= 0 && (ans < 0 || ans > num)){
        
                ans = num;
                memcpy(ansf, f, sizeof(f));
            }
        }
        
        if(ans < 0)
            cout << "IMPOSSIBLE\n";
        else{
        
            for(int i = 1; i <= m; i++){
        
                for(int j = 1; j <= n; j++){
        
                    cout << ansf[i][j] << " ";
                }
                cout << endl;
            }
        }
        
    }
    
    int main()
    {
        
        cin >> m >> n;
        
        for(int i = 1; i <= m; i++){
        
            for(int j = 1; j <= n; j++)
                cin >> mp[i][j];
        }
        
        solve();
        
        return 0;
    }

# 例题3： #

[熄灯问题(OpenJ\_Bailian - 2811)][OpenJ_Bailian - 2811]

[1]: https://s1.ax1x.com/2020/03/17/8a1Kn1.jpg
[2]: /images/20221120/8d7bf29896a1490fb6ae3a1594dbfacb.png
[3]: https://s1.ax1x.com/2020/03/17/8a1Zp4.jpg
[OpenJ_Bailian - 2811]: https://blog.csdn.net/weixin_43845956/article/details/111213648