(开关问题)(枚举)(模拟)(位运算)116. 飞行员兄弟

简介: (开关问题)(枚举)(模拟)(位运算)116. 飞行员兄弟

题目链接

116. 飞行员兄弟 - AcWing题库

一些话

切入点

//  开关问题,每个开关只按一次,顺序不重要

每个开关都可能被按,下一层的开关不影响到上一层,就可以递推,除了递推还可以枚举所有开关的按法:用位运算

// 思路复杂,操作繁琐,模拟题

求满足条件的情况,枚举时储存

流程

求符合条件的方案,字典序和全打开,直接从0开始枚举,步数严格小的才储存方案,空方案则储存

因为开关会影响到上下左右的开关,所以不能一层一层递推

// 图较小,用2e16个数转化为矩阵,每个数位表示开关的操作与否、

// 读入部分,直接读入字符数组

//  get函数,输入i,j return i * 4 + j

// turn _ont函数,是+就变成-,反之则+

// turn_all 函数,循环turnone,最后turn_one中心点

// doit函数:枚举1-1<< 16-1,备份数组,一重循环枚举二进制的数位,是1则根据当前的j获取对应的x,y,turn_all(x,y),把x,y压入vector遍历数组检查是否全关

// 是的话比较vector元素个数和res,严格少则替换,或者res空则替换

// 输出部分:遍历res,输出元素+1

套路

1.一维数模拟二维数组


前提条件表示一个只有01或其他两种元素的矩阵n*m矩阵,开关问题


利用位运算,用2^n*m个整数来表示一个只有01或其他两种元素的矩阵n*m矩阵


for(int op = 0;op < 1 << 16;op++)


运用:可以通过这个来枚举开关问题的解法


2.……<PII>的遍历


for(auto t: res) cout << t.first + 1 << " " << t.second + 1 << endl;

ac代码

// 19:55 - 20 :06 想
// 06 ~ 24 wa
// 24!30看答案
// 30~37看题解,不理解turnall是啥,get和位运算
//  开关问题,每个开关只按一次,顺序不重要
// 码量大,操作繁琐,模拟题
// 求符合条件的方案,字典序和全打开,直接从0开始枚举,步数严格小的才储存方案,空方案则储存
// 因为开关会影响到上下左右的开关,所以不能一层一层递推
// 图较小,用2e16个数转化为矩阵,每个数位表示开关的操作与否、
// 读入部分,直接读入字符数组
//  get函数,输入i,j return i * 4 + j
// turn _ont函数,是+就变成-,反之则+
// turn_all 函数,循环turnone,最后turn_one中心点
// doit函数:枚举1-1<< 16-1,备份数组,一重循环枚举二进制的数位,是1则根据当前的j获取对应的x,y,turn_all(x,y),把x,y压入vector遍历数组检查是否全关
// 是的话比较vector元素个数和res,严格少则替换,或者res空则替换
// 输出部分:遍历res,输出元素+1
#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];
vector<PII>res;
int get(int i,int j){
    return i * 4 + j;
}
void turn_one(int i,int j){
    if(g[i][j] == '+') g[i][j] = '-';
    else g[i][j]  = '+';
}
void turn_all(int x,int y){
    for(int i = 0;i < 4;i++){
        turn_one(i,y);
        turn_one(x,i);
    }
    turn_one(x,y);
}
void input(){
    for(int i = 0;i < 4;i++){
        cin >> g[i];
    }
}
void doit(){
    for(int op = 0;op < 1 << 16;op++){
        vector<PII>temp;
        memcpy(backup,g,sizeof g);
        for(int i = 0;i < 4;i++){
            for(int j = 0;j < 4;j++){
                if(op >> get(i,j) & 1){
                    temp.push_back({i,j});
                    turn_all(i,j);
                }
            }
        }
        bool flag = true;
        for(int i = 0;i < 4;i++){
            for(int j = 0;j < 4;j++){
                if(g[i][j] == '+') {
                    flag = false;
                }
            }
        }
        if(flag){
            if(res.empty() || res.size() > temp.size()) res = temp;
        }
        memcpy(g,backup,sizeof g);
    }    
}
void output(){
    cout << res.size() << endl;
    for(auto t: res) cout << t.first + 1 << " " << t.second + 1 << endl;
}
int main(){
    input();
    doit();
    output();
    return 0;
}
目录
相关文章
|
4天前
|
弹性计算 人工智能 安全
云上十五年——「弹性计算十五周年」系列客户故事(第二期)
阿里云弹性计算十五年深耕,以第九代ECS g9i实例引领算力革新。携手海尔三翼鸟、小鹏汽车、微帧科技等企业,实现性能跃升与成本优化,赋能AI、物联网、智能驾驶等前沿场景,共绘云端增长新图景。
|
10天前
|
存储 弹性计算 人工智能
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
2025年9月24日,阿里云弹性计算团队多位产品、技术专家及服务器团队技术专家共同在【2025云栖大会】现场带来了《通用计算产品发布与行业实践》的专场论坛,本论坛聚焦弹性计算多款通用算力产品发布。同时,ECS云服务器安全能力、资源售卖模式、计算AI助手等用户体验关键环节也宣布升级,让用云更简单、更智能。海尔三翼鸟云服务负责人刘建锋先生作为特邀嘉宾,莅临现场分享了关于阿里云ECS g9i推动AIoT平台的场景落地实践。
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
|
2天前
|
云安全 人工智能 安全
Dify平台集成阿里云AI安全护栏,构建AI Runtime安全防线
阿里云 AI 安全护栏加入Dify平台,打造可信赖的 AI
|
9天前
|
人工智能 自然语言处理 自动驾驶
关于举办首届全国大学生“启真问智”人工智能模型&智能体大赛决赛的通知
关于举办首届全国大学生“启真问智”人工智能模型&智能体大赛决赛的通知
|
5天前
|
人工智能 运维 Java
Spring AI Alibaba Admin 开源!以数据为中心的 Agent 开发平台
Spring AI Alibaba Admin 正式发布!一站式实现 Prompt 管理、动态热更新、评测集构建、自动化评估与全链路可观测,助力企业高效构建可信赖的 AI Agent 应用。开源共建,现已上线!
471 12
|
3天前
|
编解码 文字识别 算法
一张图能装下“千言万语”?DeepSeek-OCR 用视觉压缩长文本,效率提升10倍!
一张图能装下“千言万语”?DeepSeek-OCR 用视觉压缩长文本,效率提升10倍!
361 10
|
10天前
|
编解码 自然语言处理 文字识别
Qwen3-VL再添丁!4B/8B Dense模型开源,更轻量,仍强大
凌晨,Qwen3-VL系列再添新成员——Dense架构的Qwen3-VL-8B、Qwen3-VL-4B 模型,本地部署友好,并完整保留了Qwen3-VL的全部表现,评测指标表现优秀。
678 7
Qwen3-VL再添丁!4B/8B Dense模型开源,更轻量,仍强大
|
12天前
|
存储 机器学习/深度学习 人工智能
大模型微调技术:LoRA原理与实践
本文深入解析大语言模型微调中的关键技术——低秩自适应(LoRA)。通过分析全参数微调的计算瓶颈,详细阐述LoRA的数学原理、实现机制和优势特点。文章包含完整的PyTorch实现代码、性能对比实验以及实际应用场景,为开发者提供高效微调大模型的实践指南。
805 2