第十四届蓝桥杯C/C++大学B组题解(二)

6、岛屿个数

#include <bits/stdc++.h>
using namespace std;
const int M=51;
int T,m,n;
int vis[M][M],used[M][M];
int dx[]={1,-1,0,0,1,1,-1,-1};
int dy[]={0,0,1,-1,1,-1,1,-1};
string mp[M];
struct node{//记录一点坐标 
	int x,y;
};
void bfs_col(int x,int y){ 
    queue<node>q;
    q.push({x,y});vis[x][y]=1;
    while(q.size()){
        auto u=q.front();
        q.pop();
        for(int i=0;i<4;i++){//搜索岛屿只有四个方向 
            int a=u.x+dx[i];
            int b=u.y+dy[i];
            if(a<0||b<0||a>m-1||b>n-1||vis[a][b]==1||mp[u.x][u.y]=='0')continue;
            q.push({a,b});vis[a][b]=1;//打上标记判重 
        }
    }
}
bool bfs_edge(int x,int y){
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            used[i][j]=0;//初始化 
        }
    }
    queue<node>q;
    q.push({x,y});used[x][y]=1;
    while(q.size()){
        auto t=q.front();
        q.pop();
        //能走到边界了说明不是子岛屿 
        if(t.x==0||t.x==m-1||t.y==0||t.y==n-1)return true;
        for(int i=0;i<8;i++){//判断是否到边界有八方向 
            int a=t.x+dx[i];
            int b=t.y+dy[i];
            if(a<0||b<0||a>m-1||b>n-1||used[a][b]==1||mp[a][b]=='1') continue;
            q.push({a,b});used[a][b]=1;
        }
    }
    return false;
}
void solve(){
    int ans=0;
    cin>>m>>n;
    for(int i=0;i<m;i++){
        cin>>mp[i];  
        for(int j=0;j<n;j++){
            vis[i][j]=0;//初始化为0 
        }
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(!vis[i][j]&&mp[i][j]=='1'){ 
                bfs_col(i,j);//搜索每"一块"岛屿 
                if(bfs_edge(i,j))ans++;
            }
        }
    }
    cout<<ans<<'\n';
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
    int T;
    cin>>T;
    while(T--)solve();
    return 0;
}

7、字串简写

#include <bits/stdc++.h>
using namespace std;
int k;
string s;
char c1,c2;
long long ans,sum_c1;
int main(){
	cin>>k;
	cin>>s>>c1>>c2;
	//以c2为窗口的尾巴,找到所有距离大于等于k的c1,把所有满足条件的c1数加起来 
	for(int i=k-1,j=0;i<s.length();i++,j++){//i,j同时移动,形成滑动窗口 
		if(s[j]==c1)sum_c1++;//找到头,c1数加一 
		if(s[i]==c2)ans+=sum_c1;//找到尾巴了,累加答案数 
	}
	cout<<ans;
	return 0;
}

8、整数删除

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 5e5 + 10;
int n, k;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q;//优先队列维护最小值
int pre[N], ne[N];//维护左边元素和右边元素的下标的下标
int cnt[N], a[N], tmp;//cnt代表下标为i的元素需要修改的值
signed main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> tmp;
        q.push(make_pair(tmp, i));
        pre[i] = i - 1;//下标为i的元素的左边元素的下标为i-1
        ne[i] = i + 1;//下标为i的元素的右边的元素的下标为i+1
    }
    while (q.size() > n - k) {//查找k次
        int num = q.top().first;//获取最小值
        int id = q.top().second;//获取最小值的下标
        q.pop();
        /*这里cnt非0,说明在前面的操作过程中,该元素已经进行修改了,但是队列中还没有更新
        现在对队列的这个值进行修正,修正后重新查找最小值*/
        if (cnt[id]) {
            q.push({ num + cnt[id],id });
            cnt[id] = 0;
        }
        else {
            int left = pre[id];
            int right = ne[id];
            cnt[left] += num;//对左边的值进行修改
            cnt[right] += num;//对右边的值进行修改
            //将该元素在双向链表中删除
            ne[left] = right;
            pre[right] = left;
        }
    }
    while (!q.empty()) {
        int num = q.top().first;
        int id = q.top().second;
        q.pop();
        a[id] = num + cnt[id];
    }
    for (int i = 1; i <= n; i++) {
        if (a[i]) {
            cout << a[i] << " ";
        }
    }
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/531635.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

C++ | Leetcode C++题解之第14题最长公共前缀

题目&#xff1a; 题解&#xff1a; class Solution { public:string longestCommonPrefix(vector<string>& strs) {if (!strs.size()) {return "";}int minLength min_element(strs.begin(), strs.end(), [](const string& s, const string& t)…

同步压缩理论

参考 在频率方向进行能量重新分配&#xff08;分配到中心&#xff09; 时频重排

实验4 DHCP基础配置

实验4 DHCP基础配置 一、 原理描述二、 实验目的三、 实验内容四、 实验配置五、 实验步骤1.基本配置2.配置DHCPServer功能3.配置DHCP Client 一、 原理描述 动态主机配置协议 DHCP是一个局域网的网络协议&#xff0c;使用UDP协议工作&#xff0c;主要有两个用途&#xff1a;用…

大话设计模式——16.命令模式(Command Pattern)

简介 请求以命令的形式包裹在对象中&#xff0c;并传给调用对象。调用对象寻找可以处理该命令的对象进行执行。命令模式是一种特殊的策略模式&#xff0c;体现多个策略执行的问题&#xff0c;而不是选择的问题 UML图 应用场景 界面选择、键盘、按钮、事件操作都类似命令模式 …

前端工程化理解 (2024 面试题)

最好介绍远古世界最好随性一点&#xff0c;不要太刻板 &#xff0c;不然像背书 什么是前端工程化&#xff1f; - 知乎 前端工程化的历史 互联网初期&#xff0c;09 年以前&#xff0c;页面只需要展示一些列表、表格、文章内容以及简单图片即可&#xff0c;其目的是为了传送信…

身份证正面打印、反面打印与打印在同一页

1 打印身份证正面 将身份证正面朝下放置&#xff0c;按打印机键盘上的数字【3】&#xff0c;再按【Start】键&#xff0c;选择A4大小打印&#xff0c;如图(1)所示&#xff1a; 图(1) A4纸复印 2 打印身份证反面 将身份证反面朝下放置&#xff0c;按打印机键盘上的数字【3】&…

KVM 高级功能部署

目录 一、案例分析 1.1、案例概述 1.2、案例前置知识点 1&#xff09;KVM 虚拟机迁移 2&#xff09;KSM 内核同页合并 1.3、案例环境 1&#xff09;本案例环境 2&#xff09;案例需求 3&#xff09;案例实现思路 二、案例实施 2.1、静态迁移 1&#xff09;在…

springboot+vue药店药品进销存采购管理系统0z10z

本系统采用intellij idea支持eclipse 项目架构&#xff1a;B/S架构web 开发语言&#xff1a;java 前端技术&#xff1a;vue.jsElementUi 后端框架&#xff1a;django、mybatis、Springmvc 运行环境&#xff1a;win10/win11、jdk1.8 可行性论证 社会可行性 开发本系统&#xff…

XC6206稳压芯片

mark 662k XC6206 的基本特性。这是一个 SOT23封装的 3.3V 稳压器。它输出最大工作电流为 100mA 最大特点便宜 参考链接 XC6206稳压芯片 (qq.com)https://mp.weixin.qq.com/s?__bizMzA5NjQyNjc2NQ&mid2452268489&idx1&sn90e920c596e3c2a382f81929c6313977&c…

Linux--进程的概念(一)

目录 一、冯诺依曼体系结构二、操作系统2.1 什么是操作系统2.2 操作系统的意义 三、进程3.1 进程的基本概念3.2 描述进程——PCB3.3 进程和程序的区别3.4 task_struct-PCB的一种3.5 task_struct的内容分类 四、如何查看进程4.1 通过系统文件查看进程4.2 通过ps指令查看进程 五、…

《公安机关互联网安全监督检查规定》系列之“解决方案”

随着中国互联网和信息网络飞速发展&#xff0c;无线网络普及到国内各个家庭和公共场所&#xff0c;成为人们日常办公和生活娱乐不可或缺的一部分。无线网络在创造商业价值、带来工作和生活便捷的同时&#xff0c;也同样让犯罪份子有了可乘之机&#xff0c;越来越多的网络违法活…

如何通过数据验证防止 Web API 攻击 - Web API 安全指南

充分的数据保护和用户保密是网页开发者的主要责任。因此&#xff0c;在构建 API 终端时&#xff0c;确保最高可能的安全性至关重要。 应用程序安全是客户端和服务器开发者共同的责任&#xff0c;一方的疏忽可能会造成灾难性后果。统计数据显示&#xff0c;2023 年的数据泄露导…

windows安装Redis,Mongo,ES并快速基本掌握开发流程

前言 这里只是一些安装后的基础操作&#xff0c;后期会学习更加深入的操作 基础操作 前言RedisRedis启动idea集成Redisjedis技术 Mongodbwindows版Mongodb的安装idea整合Mongodb ES(Elasticsearch)ESwindows下载ES文档操作idea整合ES低级别ES整合高级别ES整合 Redis Redis是…

HarmonyOS 开发-Grid和List内拖拽交换子组件位置

介绍 本示例分别通过onItemDrop()和onDrop()回调&#xff0c;实现子组件在Grid和List中的子组件位置交换。 效果图预览 使用说明&#xff1a; 拖拽Grid中子组件&#xff0c;到目标Grid子组件位置&#xff0c;进行两者位置互换。拖拽List中子组件&#xff0c;到目标List子组件…

【进阶六】Python实现SDVRPTW常见求解算法——自适应大邻域算法(ALNS)

基于python语言&#xff0c;采用经典自适应大邻域算法&#xff08;ALNS&#xff09;对 带硬时间窗的需求拆分车辆路径规划问题&#xff08;SDVRPTW&#xff09; 进行求解。 目录 往期优质资源1. 适用场景2. 代码调整2.1 需求拆分2.2 需求拆分后的服务时长取值问题 3. 求解结果4…

CADMap3D2024 2023下载地址及安装教程

CAD Map 3D是由Autodesk开发的一款专业的地图制作和GIS&#xff08;地理信息系统&#xff09;软件。它是AutoCAD系列软件的一个扩展&#xff0c;提供了一系列特定于地理数据的工具和功能。 CAD Map 3D主要用于处理和管理与地理空间相关的数据&#xff0c;在地图制作、城市规划…

洗地机哪个品牌质量好?四大高口碑优质款式直入

如今&#xff0c;保持家居地面清洁整洁已成为生活中的重要任务。在这方面&#xff0c;洗地机作为一种高效的清洁工具备受青睐。然而&#xff0c;市场上的洗地机种类繁多&#xff0c;选择起来常常让人头疼。所以&#xff0c;哪个品牌的洗地机质量更好呢&#xff1f;以下是几款备…

Java 继承

1 继承 1.1 为什么需要继承 Java中使用类对现实世界中实体来进行描述&#xff0c;类经过实例化之后的产物对象&#xff0c;则可以用来表示现实中的实体&#xff0c;但是 现实世界错综复杂&#xff0c;事物之间可能会存在一些关联&#xff0c;那在设计程序是就需要考虑 比如&…

论文笔记:面向实体的多模态对齐与融合网络假新闻检测

整理了2022TMM期刊 Entity-Oriented Multi-Modal Alignment and Fusion Network for Fake News Detection&#xff09;论文的阅读笔记 背景模型改进的动态路由算法Cross-Modal Fusion 实验 背景 现有的假新闻方法对多模态特征进行各种跨模态交互和融合&#xff0c;在检测常见假…

刷题之Leetcode203题(超级详细)

203.移除链表元素 力扣题目链接(opens new window)https://leetcode.cn/problems/remove-linked-list-elements/ 题意&#xff1a;删除链表中等于给定值 val 的所有节点。 示例 1&#xff1a; 输入&#xff1a;head [1,2,6,3,4,5,6], val 6 输出&#xff1a;[1,2,3,4,5] …