蓝桥杯打卡Day10

这篇具有很好参考价值的文章主要介绍了蓝桥杯打卡Day10。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

蓝桥杯打卡Day10,蓝桥杯,蓝桥杯,职场和发展


文章目录

  • 最长ZigZag子序列
  • 最小面积子矩阵

一、最长ZigZag子序列IO链接

本题思路:本题是一道dp问题, 集合划分:只有一个a[i]或者倒数第二个元素是第j个数字并且需要是下降得到a[j]:g[j]+1,状态计算f[i]=max(f[i],g[j]+1),这是第一种情况,还有一种是只有一个a[i]或者倒数第二个元素是第j个数字并且需要是上升得到a[j]:f[j] + 1状态计算g[i]=max(g[i],f[j]+1),这是第二种满足条件,那么每个状态最长的即为res=max(f[i],g[i])中最长的子序列。

#include <bits/stdc++.h>

constexpr int N=55;

//集合划分:【只有一个a[i]】【其他:倒数第二个元素是第j个数字并且需要是下降得到a[j]:g[j] + 1】
//状态计算:f[i] = max(f[i], g[j] + 1);
int n;
int a[N];
int f[N];//表示以第i个数字结尾并且是前一个数字上升得到的a[i]
int g[N];//表示以第i个数字结尾并且是前一个数字下降得到的a[i]

int main()
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);std::cout.tie(nullptr);
  
  std::cin>>n;
  for(int i=1;i<=n;i++) std::cin>>a[i];
  
  int res=0;
  for(int i = 1; i <=n; i ++ ){
        f[i] = g[i] = 1; 
        for(int j = 1; j < i; j ++ ){
            if(a[i] > a[j]) f[i] = std::max(g[j] + 1, f[i]);
            else if(a[i] < a[j])
                g[i] = std::max(f[j] + 1 , g[i]);
        }
        res = std::max(res, std::max(f[i], g[i]));
    }
  
  std::cout<<res<<std::endl;
  return 0;
}

二、最小面积子矩阵IO链接

 本题思路:本题可以采用前缀和和双指针的方式,暴力也可以做知识复杂度比较高,将每一列进行一维前缀和操作,然后我们首先枚举上下边界,然后枚举左右边界,要求包含元素最少的子矩阵(右边界固定的时候,左边界往右总和变小,面积也变小)。文章来源地址https://www.toymoban.com/news/detail-732910.html

#include <bits/stdc++.h>

constexpr int N=110;
#define INF 0x3f3f3f3f

int n,m,k;
int g[N][N];
int ans=INF;

int main()
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);std::cout.tie(nullptr);
  
  std::cin>>n>>m>>k;
  for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
      std::cin>>g[i][j];
      g[i][j]+=g[i-1][j];
    }
    
  for(int x=1;x<=n;x++)//处理上下边界
    for(int y=x;y<=n;y++)
      for(int l=1,r=1,sum=0;r<=m;r++){//对边界中的矩阵进行枚举
        sum+=g[y][r]-g[x-1][r];
        while(sum-g[y][l]+g[x-1][l]>=k)
        {
          sum-=g[y][l]-g[x-1][l];
          l++;
        }
        
        if(sum>=k) ans=std::min(ans,(y-x+1)*(r-l+1));
      }
      
      if(ans==INF) std::cout<<-1<<std::endl;
      else std::cout<<ans<<std::endl;
  return 0;
}

到了这里,关于蓝桥杯打卡Day10的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 蓝桥杯打卡Day1

        文章目录 全排列 八皇后 本题思路: 本题是一道经典的全排列问题,深度优先搜索即可解决。 利用STL库中的next_permutation函数来求全排列问题: 本题思路: 利用dfs的方式找出92组解,判定该点是否可以放皇后时,用了三个bool类型的数组col[N], dg[N], udg[N]来储存某列,某正对角

    2024年02月10日
    浏览(41)
  • 蓝桥杯打卡Day9

    文章目录 直角三角形 最长平衡串 本题思路: 本题就是利用欧几里得距离求解即可。  本题思路: 找一个连续的子串, 使得子串中‘0’和‘1’的个数能抵消,利用前缀和a[i]统计前i个字符中有多少个‘1’, 前缀和b[i]统计前i个字符中有多少个‘0’,记该最大连续子串开始地方为

    2024年02月07日
    浏览(45)
  • 蓝桥杯备赛 | 洛谷做题打卡day4

    高精度加法,相当于 a+b problem, 不用考虑负数 。 分两行输入。 a , b ≤ 1 0 500 a,b leq 10^{500} a , b ≤ 1 0 500 。 输出只有一行,代表 a + b a+b a + b 的值。 样例输入 #1 样例输出 #1 样例输入 #2 样例输出 #2 学会利用新知,自己多试试并尝试积攒一些固定解答方案,debug,以下是我的

    2024年01月17日
    浏览(46)
  • 蓝桥杯备赛 | 洛谷做题打卡day2

    ​ 题目来源:洛谷P2670 [NOIP2015 普及组] 扫雷游戏 NOIP2015 普及组 T2 扫雷游戏是一款十分经典的单机小游戏。在 n n n 行 m m m 列的雷区中有一些格子含有地雷(称之为地雷格),其他格子不含地雷(称之为非地雷格)。玩家翻开一个非地雷格时,该格将会出现一个数字——提示

    2024年01月16日
    浏览(62)
  • 蓝桥杯备赛 | 洛谷做题打卡day5

    题目描述 小 K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个(也有可能没有)参考文献的链接指向别的博客文章。小 K 求知欲旺盛,如果他看了某篇文章,那么他一定会去看这篇文章的参考文献(如果他之前已经看过这篇参考文献的话就不用再看它了)。 假设洛谷

    2024年01月17日
    浏览(59)
  • 蓝桥杯 题库 简单 每日十题 day10

    最少砝码 问题描述 你有一架天平。现在你要设计一套砝码,使得利用这些砝码 可以出任意小于等于N的正整数重量。那么这套砝码最少需要包含多少个砝码? 注意砝码可以放在天平两边。 输入格式 输入包含一个正整数N。 输出格式 输出一个整数代表答案。 样例输入 样例输

    2024年02月07日
    浏览(44)
  • [职场] 会计学专业学什么 #其他#知识分享#职场发展

    会计学专业学什么 会计学专业属于工商管理学科下的一个二级学科,本专业培养具备财务、管理、经济、法律等方面的知识和能力,具有分析和解决财务、金融问题的基本能力,能在企、事业单位及政府部门从事会计实务以及教学、科研方面工作的工商管理学科高级专门人才

    2024年02月20日
    浏览(49)
  • 学习平台助力职场发展与提升

    近年来,随着互联网技术的发展, 学习平台 逐渐成为了职场发展和提升的必备工具。学习平台通过提供丰富的课程内容、灵活的学习时间和个性化的学习路径,帮助职场人士更好地提升自己的技能和知识储备,为职场发展打下坚实的基础。 学习平台的优势在于提供了丰富多

    2024年02月11日
    浏览(51)
  • 如何手机搜学法减分答案? #媒体#职场发展

    今天分享拥有拍照搜题、文字搜题、语音搜题、多重搜题等搜题模式,可以快速查找问题解析,加深对题目答案的理解。 1.证件照全能管家(APP) 一个非常好用的证件照APP 常用的证件照尺寸和底色都有、日常的证件照编辑完全够用,支持一键智能拍摄证件照,还可以对照片

    2024年02月19日
    浏览(47)
  • 【职业人生】如何有效的在职场当中避免工作失误和提高个人发展

         《左传·宣公二年》:“人谁无过,过而能改,善莫大焉。”古往今来,多少人犯过错误。强大如“智绝”的诸葛孔明,也有街亭之失。职场人更是难免会在工作中出现失误。     在职场生涯当中避免不了在工作当中带来的失误,在这过程当中,我们应当要学会怎么去

    2024年02月08日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包