蓝桥杯2023年真题（3）

1.冶炼金属（二分、数学）

在这里插入图片描述

//二分
#include <iostream>
using namespace std;

int get1(int a, int b){
  int l = 0, r = 1e9;
  while(l + 1 < r){
    int mid = (l + r) / 2;
    if(a / mid <= b) r = mid;
    else l = mid;
  }
  return r;
}

int get2(int a, int b){
  int l = 0, r = 1e9;
  while(l + 1 < r){
    int mid = (l + r) / 2;
    if(a / mid < b) r = mid;
    else l = mid;
  }
  return l;
}

int main() {
  int n;
  scanf("%d", &n);
  int a, b;
  int res1 = -1e9, res2 = 1e9;
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &a, &b);
    //当前区间的最小值
    res1 = max(res1, get1(a, b));
    //当前区间的最大值 = 下一个区间的最小值减1
    //res2 = min(res2, get1(a, b - 1) - 1);
    res2 = min(res2, get2(a, b));
  }
  printf("%d %d", res1, res2); 
  return 0;
}

//数学
// 由 a / v >= b, a / v < (b + 1)
// 得 v <= a / b, v > a / (b + 1)
#include <iostream>
using namespace std;

int main() {
  int n;
  scanf("%d", &n);
  int a, b;
  int res1 = -1e9, res2 = 1e9;
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &a, &b);
    //左端点取最大值
    res1 = max(res1, a / (b + 1) + 1);
    //右端点取最小值
    res2 = min(res2, a / b);
  }
  printf("%d %d", res1, res2); 
  return 0;
}

2.飞机降落（dfs排列、状态压缩dp）

在这里插入图片描述
在这里插入图片描述

//dfs, O(n * n!)
#include<iostream>
#include<cstring>
using namespace std;
const int N = 15;
struct node{
  int a, b, c;
}p[N];
int t, n, st[N];

//当前第几个飞机，开始时间
int dfs(int u, int beg){
  if(u > n) return 1;
  for(int i = 1; i <= n; i++){
    int a = p[i].a, b = p[i].b, c = p[i].c;
    //如果当前飞机没被用过，且当前最晚降落时间大于等于上一个飞机结束的时间
    if(!st[i] && a + b >= beg){
      st[i] = 1;
      //当前出发的时间要是上一段结束，这一段开始，取靠后的
      if(dfs(u + 1, max(beg, a)+ c)) return 1;
      st[i] = 0;
    }
  }
  return 0;
}

int main(){
  scanf("%d", &t);
  while(t--){
    memset(st, 0, sizeof(st));
    scanf("%d", &n);
    int a, b, c;
    for(int i = 1; i <= n; i++){
      scanf("%d%d%d", &a, &b, &c);
      p[i] = {a, b, c};
    }
    if(dfs(1, 0)) printf("YES\n");
    else printf("NO\n");
  }
  return 0;
}

//dp, O(n * 2 ^ n)
#include<iostream>
#include<cstring>
using namespace std;
const int N = 20;
struct node{
  int a, b, c;
}p[N];
int t, n;
int f[1 << N]; //f[i]: 终点为第i位的最小值

int main(){
  scanf("%d", &t);
  while(t--){
    scanf("%d", &n);
    int a, b, c;
    for(int i = 0; i < n; i++){
      scanf("%d%d%d", &a, &b, &c);
      p[i] = {a, b, c};
    }
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    //枚举所有情况, 0101表示放好了第一个和第三个飞机
    for(int i = 1; i < 1 << n; i++){
      for(int j = 0; j < n; j++){
        int a = p[j].a, b = p[j].b, c = p[j].c;
        //如果j位放好了飞机
        if(i >> j & 1){
          //上一个结束的时间
          int st = f[i - (1 << j)];
          if(a + b >= st) f[i] = min(f[i], max(st, a) + c);
        }
      }
    }
    if(f[(1 << n) - 1] == 0x3f3f3f3f) printf("NO\n");
    else printf("YES\n");
  }
  return 0;
}

3.接龙数（最长上升子序列dp）

在这里插入图片描述

//暴力枚举
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, a[N];
int main()
{
  scanf("%d", &n);
  for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
  int res = 0;
  //前一个数字
  for(int i = 1; i < n; i++){
    int x = a[i] % 10;
    //后一个数字
    for(int j = i + 1; j <= n; j++){
      int t = a[j], y;
      while(t){
        y = t % 10;
        t /= 10;
      }
      if(x != y){
        res++;
      }else{
        i = j - 1;
        break;
      }
    }
  }
  printf("%d", res);
  return 0;
}

//O(n ^ 2)
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, l[N], r[N];
int f[N]; //f[i]: 以a[i]结尾的接龙子序列长度最大值
int main()
{
  scanf("%d", &n);
  string s;
  for(int i = 1; i <= n; i++){
    cin>>s;
    l[i] = s[0] - '0';
    r[i] = s[s.size() - 1] - '0';
  }
  int res = 0;
  //右边界
  for(int i = 1; i <= n; i++){
    f[i] = 1;
    //左边界
    for(int j = 1; j < i; j++){
      if(l[i] == r[j]) f[i] = max(f[i], f[j] + 1);
    }
    res = max(f[i], res);
  }
  printf("%d", n - res);
  return 0;
}

//O(n)
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, l[N], r[N];
int f[N], g[10]; //f[i]: 以a[i]结尾的接龙子序列长度最大值
int main()
{
  scanf("%d", &n);
  string s;
  for(int i = 1; i <= n; i++){
    cin>>s;
    l[i] = s[0] - '0';
    r[i] = s[s.size() - 1] - '0';
  }
  int res = 0;
  //右边界
  for(int i = 1; i <= n; i++){
    f[i] = 1;
    f[i] = max(f[i], g[l[i]] + 1);
    g[r[i]] = max(g[r[i]], f[i]);
    res = max(f[i], res);
  }
  printf("%d", n - res);
  return 0;
}

//最优！
要求使得数列变成接龙数列的最少删除个数， 相当于求该数列的最长接龙子数列的长度， 用总长度减去最长接龙长度即为最少删除个数。

定义dp[i][j]为前i个数中， 以数字j结尾的最长接龙数列的长度。

设第i个数的首位数字是a， 末位数字是b。 则dp[i]中相对于dp[i-1]可能发生变化的只有dp[i][b], 因为第i个数只可能加到一个以a结尾的接龙数列中， 使得这个接龙数列长度加1并且结尾数字变成b.

所以状态转移方程为dp[i][b] = max(dp[i - 1][b], dp[i - 1][a] + 1)

而显然第一维可以优化掉。

#include <iostream>
using namespace std;
int f[10]; //f[j]: 以数字j结尾的最长接龙子序列长度
int main()
{
  int n, res = 0;
  scanf("%d", &n);
  string s;
  for(int i = 1; i <= n; i++){
    cin>>s;
    //首尾数字
    int l = s[0] - '0', r = s[s.size() - 1] - '0';
    f[r] = max(f[r], f[l] + 1);
    res = max(res, f[r]);
  }
  printf("%d", n - res);
  return 0;
}

4.岛屿个数（dfs、bfs）

在这里插入图片描述

//dfs
#include<iostream>
using namespace std;
const int N = 55;
char g[N][N];
int n, m;

int dx[] = {0, 0, -1, 1, 1, 1, -1, -1};
int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};

void dfs1(int x, int y){
  g[x][y] = '2';
  for(int i = 0; i < 8; i++){
    int a = x + dx[i], b = y + dy[i];
    if(a < 0 || a > n + 1 || b < 0 || b > m + 1 || g[a][b] != '0') continue;
    dfs1(a, b);
  }
}

void dfs2(int x, int y){
  g[x][y] = '2';
  for(int i = 0; i < 4; i++){
    int a = x + dx[i], b = y + dy[i];
    if(a < 1 || a > n || b < 1 || b > m || g[a][b] == '2') continue;
    dfs2(a, b);
  }
}

int main(){
  int t;
  cin>>t;
  while(t--){
    int res = 0;
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
      for(int j = 1; j <= m; j++)
        cin>>g[i][j];

    //往外面再扩展一圈，方便打标记
    for(int i = 0; i <= n + 1; i++) g[i][0] = g[i][m + 1] = '0';
    for(int j = 0; j <= m + 1; j++) g[0][j] = g[n + 1][j] = '0';

    //开始遍历，把最外面一圈海水打上标记
    dfs1(0, 0);

    for(int i = 1; i <= n; i++)
      for(int j = 1; j <= m; j++)
        if(g[i][j] == '1'){
          res++;
          //遍历所在岛屿和他内部，全部打上标记
          dfs2(i, j);
        }
  
    cout<<res<<endl;
  }
  return 0;
}

5.子串简写（逆序对、双指针）

在这里插入图片描述

#include <iostream>
using namespace std;
long long res, ans;

int main()
{
  int k;
  string s;
  char c1, c2;
  cin>>k>>s>>c1>>c2;
  //双指针，逆序对写法，左指针遇到一个就++，右指针累加，区间长度为k，一位一位移动
  for(int i = 0, j = k - 1; j < s.size(); i++, j++){
    if(s[i] == c1) res++;
    if(s[j] == c2) ans += res;
  }
  cout<<ans;
  return 0;
}

6.整数删除（优先队列、双链表）

在这里插入图片描述

#include<iostream>
#include<queue>
using namespace std;
#define int long long
const int N = 5e5 + 10;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; // 小根堆，存储元素和下标

int l[N], r[N]; // 存储左右下标
int st[N]; // 存储变化后的值
int n, k, x;

signed main(){
  cin >> n >> k;
  for(int i = 0; i < n; i++){
    cin >> x;
    st[i] = x;
    q.push(make_pair(x, i));
    l[i] = i - 1;
    r[i] = i + 1;
    if(r[i] == n) r[i] = -1;
  }

  while(k){
    // 取出最小值
    pair<int, int> it = q.top();
    q.pop();
    // 如果当前的值不等于更新后的值，说明还没更新
    if(it.first != st[it.second]){
      q.push(make_pair(st[it.second], it.second));
      continue;
    }
    k--;

    // 获取该元素的下标和值
    int pos = it.second, x = it.first;
    // 加到左边
    if(l[pos] >= 0) st[l[pos]] += x;
    // 加到右边
    if(r[pos] >= 0) st[r[pos]] += x;

    // 更新左右指向
    if(l[pos] >= 0) r[l[pos]] = r[pos];
    if(r[pos] >= 0) l[r[pos]] = l[pos];

    // 删除当前元素
    st[pos] = -1;
  }

  // 输出结果
  for(int i = 0; i < n; i++){
    if(st[i] != -1) cout << st[i] << " ";
  }
  cout << endl;
  return 0;
}

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

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

相关文章

FL Studio 21.2.3.4004 All Plugins Edition Win/Mac音乐软件

FL Studio 21.2.3.4004 All Plugins Edition Win/Mac音乐软件

FL Studio 21.2.3.4004 All Plugins Edition 是一款功能强大的音乐制作软件&#xff0c;提供了丰富的音频处理工具和插件&#xff0c;适用于专业音乐制作人和爱好者。该软件具有直观的用户界面&#xff0c;支持多轨道录音、混音和编辑&#xff0c;以及各种音频效果和虚拟乐器。…
阅读更多...
六、Datax通过json字符串运行

六、Datax通过json字符串运行

Datax通过json字符串运行 一、场景二、代码实现 一、场景 制作一个web应用&#xff0c;在页面上配置一个json字符串&#xff0c;保存在数据库里面。在执行json的时候&#xff0c;动态在本地创建一个json文件后执行&#xff0c;并识别是否成功&#xff0c;将执行过程保存在数据…
阅读更多...
变形金刚：第 2 部分：变形金刚的架构

变形金刚：第 2 部分：变形金刚的架构

目录 一、说明 二、实现Transformer的过程 第 1 步&#xff1a;代币化&#xff08;Tokenization&#xff09; 第 2 步&#xff1a;对每个单词进行标记嵌入 第 3 步&#xff1a;对每个单词进行位置嵌入 第 4 步&#xff1a;输入嵌入 第 5 步&#xff1a;编码器层 2.5.1 多头自注…
阅读更多...
红队笔记Day4 --＞多层代理（模拟企业拓扑）

红队笔记Day4 --＞多层代理（模拟企业拓扑）

声明&#xff1a;本机文章只用于教育用途&#xff0c;无不良引导&#xff0c;禁止用于从事任何违法活动 前几天的红队笔记的网络拓扑都比较简单&#xff0c;今天就来模拟一下企业的真实网络拓扑&#xff0c;以及攻击方法 一般的大企业的网络拓扑如下&#xff1a;&#xff1a;…
阅读更多...
c语言操作符(上

c语言操作符(上

目录 ​编辑 原码、反码、补码 1、正数 2、负数 3、二进制计算1-1 移位操作符 1、<<左移操作符 2、>>右移操作符 位操作符&、|、^、~ 1、&按位与 2、|按位或 3、^按位异或 特点 4、~按位取反 原码、反码、补码 1、正数 原码 反码 补码相同…
阅读更多...
Linux——网络通信TCP通信常用的接口和tco服务demo

Linux——网络通信TCP通信常用的接口和tco服务demo

文章目录 TCP通信所需要的套接字socket()bind()listen()acceptconnect() 封装TCP socket TCP通信所需要的套接字 socket() socket()函数主要作用是返回一个描述符&#xff0c;他的作用就是打开一个网络通讯端口&#xff0c;返回的这个描述符其实就可以理解为一个文件描述符&a…
阅读更多...
Days 31 ElfBoard 自启脚本中打开看门狗

Days 31 ElfBoard 自启脚本中打开看门狗

1.在开机自启脚本中打开看门狗 rootELF1:~# vi /etc/rc.local 2.在自启脚本中添加上之后&#xff0c;然后在咱们的QT界面中找到看门狗应用&#xff0c; 发现显示打开看门狗失败&#xff1a; 3.修改看门狗源码&#xff0c;设置了超时时间后&#xff0c;关闭/dev/dev/watchdog节…
阅读更多...
上位机图像处理和嵌入式模块部署（借鉴与学习）

上位机图像处理和嵌入式模块部署（借鉴与学习）

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 对于很多学院派的同学来说&#xff0c;他们对市场的感觉一般是比较弱的。如果写一个软件的话&#xff0c;或者说开发一个项目的话&#xff0c;他们…
阅读更多...
OpenGL-ES 学习(1)---- AlphaBlend

OpenGL-ES 学习(1)---- AlphaBlend

AlphaBlend OpenGL-ES 混合本质上是将 2 个片元的颜色进行调和(一般是求和操作)&#xff0c;产生一个新的颜色 OpenGL ES 混合发生在片元通过各项测试之后&#xff0c;准备进入帧缓冲区的片元和原有的片元按照特定比例加权计算出最终片元的颜色值&#xff0c;不再是新&#xf…
阅读更多...
LabVIEW伺服阀动静态测试系统

LabVIEW伺服阀动静态测试系统

LabVIEW伺服阀动静态测试系统 基于LabVIEW开发了一套伺服阀动静态测试系统&#xff0c;提高伺服阀在电液伺服控制系统中的性能测试精度和效率。通过设计合理的液压系统、电控系统及软件系统&#xff0c;实现了伺服阀的动态和静态特性测试&#xff0c;采用流量-压力双闭环稳态控…
阅读更多...
【Spring】定义过滤器Filter和拦截器Interceptor

【Spring】定义过滤器Filter和拦截器Interceptor

# 定义过滤器 package com.holen.filter;import jakarta.servlet.Filter; import jakarta.servlet.FilterChain; import jakarta.servlet.ServletException; import jakarta.servlet.ServletRequest; import jakarta.servlet.ServletResponse; import java.io.IOException;pub…
阅读更多...
Web安全研究（六）

Web安全研究（六）

文章目录 HideNoSeek: Camouflaging(隐藏) Malicious JavaScript in Benign ASTs文章结构Introjs obfuscationmethodologyExample HideNoSeek: Camouflaging(隐藏) Malicious JavaScript in Benign ASTs CCS 2019 CISPA 恶意软件领域&#xff0c;基于学习的系统已经非常流行&am…
阅读更多...
JavaScript中的Symbol：加密与安全性

JavaScript中的Symbol：加密与安全性

JavaScript中的Symbol是一种唯一且不可变的数据类型&#xff0c;引入了一种新的基本数据类型&#xff0c;用于表示独一无二的标识符。在本文中&#xff0c;我们将深入介绍JavaScript中的Symbol&#xff0c;讨论如何将其应用于JS加密中&#xff0c;提供案例代码&#xff0c;并说…
阅读更多...
Codeforces Round 923(Div.3) A~G

Codeforces Round 923(Div.3) A~G

A.Make it White (模拟) 题意&#xff1a; 给一个字符串 s s s&#xff0c;找出最左边的 B B B和最右边的 B B B&#xff0c;以这两个字母为左右端点的区间包含有多少个字母。 分析&#xff1a; 按照要求&#xff0c;遍历一遍字符串找到左右端点即可。 代码&#xff1a; …
阅读更多...
TCP高频知识点

TCP高频知识点

本篇文章主要讲述一下在面试过程中TCP的高频知识点 1.TCP三次握手流程图: 客户端发送一个SYN&#xff08;同步&#xff09;报文段给服务器&#xff0c;选择一个初始序列号&#xff0c;并设置SYN标志位为1。服务器接收到客户端的SYN报文段后&#xff0c;回复一个ACK&#xff08…
阅读更多...
AI短视频一键换脸小程序源码/带流量主

AI短视频一键换脸小程序源码/带流量主

微信云开发AI一键视频换脸小程序源码是由极客二改后发布的&#xff0c;小程序增加了广告控制&#xff0c;插屏广告&#xff0c;激励广告和原生广告&#xff0c;由于采用了微信云开发没有后台&#xff0c;所以不需要域名和服务器也可以正常搭建使用&#xff0c;所有的配置都可以…
阅读更多...
面试技术栈 —— 2024网易雷火暑期实习真题

面试技术栈 —— 2024网易雷火暑期实习真题

面试技术栈 —— 2024网易雷火暑期实习真题 1. 最长递增子序列。2. 集中限流和单机限流你觉得哪个好&#xff1f;3. redis部署服务器配置&#xff0c;为什么不用哨兵&#xff1f;4. 讲讲分布式session的原理。5. 数据库&#xff1a;表数据量大了&#xff0c;如何分表&#xff1…
阅读更多...
FT2232调试记录（1）

FT2232调试记录（1）

FT2232调试记录&#xff08;1&#xff09; FT2232调试记录&#xff08;2&#xff09; FT2232调试记录&#xff08;3&#xff09; &#xff08;1&#xff09;FT2232简介&#xff1a; FT2232是一种通用的USB转串口芯片&#xff0c;用于在计算机和外部设备之间建立通信连接。它…
阅读更多...
Hive的相关概念——架构、数据存储、读写文件机制

Hive的相关概念——架构、数据存储、读写文件机制

目录 一、架构及组件介绍 1.1 Hive整体架构 1.2 Hive组件 1.3 Hive数据模型&#xff08;Data Model&#xff09; 1.3.1 Databases 1.3.2 Tables 1.3.3 Partitions 1.3.4 Buckets 二、Hive读写文件机制 2.1 SerDe 作用 2.2 Hive读写文件流程 2.2.1 读取文件的过程 …
阅读更多...
VS Code主题设置（美化VS Code）（主题+背景+图标+特效+字体）

VS Code主题设置（美化VS Code）（主题+背景+图标+特效+字体）

目录 切换整体主题&#xff08;整体主题&#xff09; 切换文件图标主题 设置VS Code背景图案 字体特效 连击特效 字体设置 主题的具体效果放在了文章末尾&#xff0c;这篇文章后续也会进行更新 ————————————————————————————…
阅读更多...
最新文章

Copyright @ 2022~2023