题目描述

“飞行员兄弟”这个游戏,需要玩家顺利的打开一个拥有 16

个把手的冰箱。

已知每个把手可以处于以下两种状态之一:打开或关闭。

只有当所有把手都打开时,冰箱才会打开。

把手可以表示为一个 4×4
的矩阵,您可以改变任何一个位置 [i,j]

上把手的状态。

但是,这也会使得第 i
行和第 j

列上的所有把手的状态也随着改变。

请你求出打开冰箱所需的切换把手的次数最小值是多少。
输入格式

输入一共包含四行,每行包含四个把手的初始状态。

符号 + 表示把手处于闭合状态,而符号 - 表示把手处于打开状态。

至少一个手柄的初始状态是关闭的。
输出格式

第一行输出一个整数 N

,表示所需的最小切换把手次数。

接下来 N

行描述切换顺序,每行输出两个整数,代表被切换状态的把手的行号和列号,数字之间用空格隔开。

注意:如果存在多种打开冰箱的方式,则按照优先级整体从上到下,同行从左到右打开。
数据范围

1≤i,j≤4

输入样例:

-+–


-+–

输出样例:

6
1 1
1 3
1 4
4 1
4 3
4 4

样例

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
//因为每一行或者每一列都可以改变对应一整行或者一整列的元素,所以一般不能用递推来操作。因为是四成四的矩阵,直接使用暴力算法进行便利

using namespace std;
//因为这里面需要记录方案,所以要开一个数组或者容器,去记录一下方案。

typedef pair <int,int> PII;
const int N =5;
char g[N][N],backup[N][N];

void turn_one(int x,int y)
{
    if(g[x][y]=='+') g[x][y]='-';
    else g[x][y]='+';
}

void turn_all(int x,int y)
{
    for(int i=0;i<4;i++)
    {   
        turn_one(x,i);
        turn_one(i,y);
    }
    turn_one(x,y);
}

int get(int x,int y)
{
    return x*4+y;
}
int main()
{
    for(int i=0;i<4;i++) cin>>g[i];
    vector<PII> res;//存储最终结果方案的一个vector容器,因为要存两个数字,所以用到了pair
    memcpy(backup,g,sizeof g);
    for(int op=0;op<(1<<16);op++)//这个1<<16表示的的是2^16,用op代表所有可能发生的情况,进行枚举。
    {   vector<PII> temp;//创建一个临时的存放结果的地方,为了更好的更新res
    //******************************************************//  
    //这段代码就是便利16位二进制数的每一位 op>>i(i是1-16) 但是这道题目是需要记录下是按了那个开关了,所以要用双重for循环+映射的形式进行操作。
        for(int i=0;i<4;i++)
        {   for(int j=0;j<4;j++)
            {
                if(op>>get(i,j)&1)//一共有16个格子,然后发现二进制位是1的就进行操作
                {
                    temp.push_back({i,j});//先把操作的内容记录下来
                    turn_all(i,j);//进行操作
                }
            }
        }    
        //**************************************************//


        //-----------------------------------------// 检查是否还有没有开着的门
        bool has_closed =false ;
        for(int i=0;i<4;i++)
            for(int j=0;j<4;j++)
                if(g[i][j]=='+') {has_closed=true;break;}
        if(!has_closed){
            if(res.empty()||res.size()>temp.size()) res=temp;//找打一个比较优的解,就要把这个目前最优的解赋给最终答案
        }
        //-------------------------------------------//
        memcpy(g,backup,sizeof g);//因为动过了g里面的内容,所以要对g中的内容进行恢复,---恢复现场
    }
    cout<<res.size()<<endl;
    for(auto p:res) cout<<p.first+1<<" "<<p.second+1<<endl;

    return 0;
}



cwr
2分钟前
#include<bits/stdc++.h>
using namespace std;
const int N=110;
const int M=25010;
int a[N];
int dp[M];//dp[N][m];
int cnt;
int main() {
    int t;
    cin>>t;
    while(t--) {
        cnt=0;
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        sort(a+1,a+1+n);
        //初始化
        memset(dp,0,sizeof dp);//一定要重置为0
        dp[0]=1; 
        for(int i=1;i<=n;i++) {
            if(!dp[a[i]]) cnt++;
            for(int j=0;j<=a[n];j++) {
                if(j>=a[i])
                dp[j]+=dp[j-a[i]];
            }
        }
        cout<<cnt<<"\n";
    }
    return 0;
}


新鲜事 原文

用Python写算法tle真烦呐,写三遍三种方法全部tle!
图片



e = [0]*100000
ne = [0]*100000
head = -1
num = 0
def hinsert(item):
    global head,num
    e[num] = item
    ne[num] = head
    head = num
    num += 1
def iinsert(k,item):
    global head,num
    e[num] = item
    ne[num] = ne[k]
    ne[k] = num
    num += 1
def ddel(k):
    global head,num
    if k == 0:
        head = ne[head]
        return
    ne[k-1] = ne[ne[k-1]]
def show():
    global head,num
    cur = head
    while(True):
        if ne[cur] == -1:
            print(e[cur],end = ' ')
            break
        else:
            print(e[cur],end = ' ')
            cur = ne[cur]
n = int(input())
for i in range(n):
    row = input().split()
    if row[0] == 'H':
        hinsert(int(row[1]))
    elif row[0] == 'D':
        ddel(int(row[1]))
    elif row[0] == 'I':
        iinsert(int(row[1]) - 1,int((row[2])))

show()



MNIST
10分钟前

判断合法括号序列问题

题库关键词:括号序列
$O(n)$
左括号进栈 优化空间复杂度-> 遍历字符,记录左括号数量,若遍历过程中出现负数则为false
星号处理:用 low 和 high 记录左括号的数量范围,若出现 low > high 则为false
边界条件:low 最小值为0

class Solution {
public:
    bool checkValidString(string s) {
        int low = 0, high = 0;
        for(auto c: s) {
            if(c == '(') low++, high++;
            else if(c == ')') low--, high--;
            else low--, high++;
            low = max(0, low);
            if(low > high) return false;
        }
        return low == 0;
    }
};



ZCPUZZLE
23分钟前

队列函数怎么用



新鲜事 原文

Flamevo
25分钟前
AcWing《算法基础课》拼团优惠!https://www.acwing.com/activity/content/introduction/11/group_buy/138585/



#include<iostream>
using namespace std;

int main() {
    long long a, b, n, cnt = 1;
    cin >> a >> b >> n;
    long long sev=5*a+2*b;
    long long temp=0;
    if(n>sev){
        long long bc=n/sev;
        n=n%sev;
        temp=7*bc;
    }
    while (n > 0) {
        if (cnt % 7 == 0 || cnt % 6 == 0) {
            n = n - b;
        }
        else {
            n = n - a;
        }

        cnt++;
    }
    cout << cnt + temp - 1;
  return 0;
}



#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
#define endl  "\n"
const int N = 200010;

int s[N];
int n , k;

int main()
{
    ios::sync_with_stdio(false); 
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> T;
    while(T--)
    {
        cin >> n >> k;
        memset(s , 0 , sizeof s);
        for(int i = 1 ; i <= n ;i ++ )
        {
            int a; cin >> a;
            s[i % k] += a;
        }
        sort(s , s + k);
        int len = 0 , max_len = 0;
        for(int i = 0 ; i < k ; i ++ )
        {
            if(i && s[i] == s[i - 1]) len ++;
            else 
            {
                max_len = max(max_len , len);
                len = 1;
            }
        }

        max_len = max(max_len , len);
        cout << k - max_len << endl;
    }
    return 0;
}


新鲜事 原文

ysc
44分钟前
AcWing《第二届ACC(AcWing Cup)全国联赛》拼团优惠!https://www.acwing.com/activity/content/introduction/3043/group_buy/138693/