题目描述

“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 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;
}

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

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()

判断合法括号序列问题

题库关键词：括号序列
$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;
    }
};

队列函数怎么用

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