蓝桥杯每日一题:壁画(前缀和)

news/2024/6/15 16:45:15/文章来源:https://blog.csdn.net/weixin_73612682/article/details/137270664

题目描述:

Thanh 想在一面被均分为 N 段的墙上画一幅精美的壁画。

每段墙面都有一个美观评分,这表示它的美观程度(如果它的上面有画的话)。

不幸的是,由于洪水泛滥,墙体开始崩溃,所以他需要加快他的作画进度!

每天 Thanh 可以绘制一段墙体。

在第一天,他可以自由的选择任意一段墙面进行绘制。

在接下来的每一天,他只能选择与绘制完成的墙面相邻的墙段进行作画,因为他不想分开壁画。

在每天结束时,一段未被涂颜料的墙将被摧毁(Thanh 使用的是防水涂料,因此涂漆的部分不能被破坏),且被毁掉的墙段一定只与一段还未被毁掉的墙面相邻。

Thanh 的壁画的总体美观程度将等于他作画的所有墙段的美观评分的总和。

Thanh想要保证,无论墙壁是如何被摧毁的,他都可以达到至少 B 的美观总分。

请问他能够保证达到的美观总分 B的最大值是多少。

输入格式

第一行包含整数 T,表示共有 T组测试数据。

每组数据的第一行包含整数 N。

第二行包含一个长度为 N 的字符串,字符串由数字 0∼90∼9 构成,第 i 个字符表示第 i 段墙面被上色后能达到的美观评分。

输出格式

每组数据输出一个结果,每个结果占一行。

结果表示为 Case #x: y,其中 x 为组别编号(从 1 开始),y 为 Thanh 可以保证达到的美观评分的最大值。

数据范围

1≤T≤100,
存在一个测试点N=5∗10^6,其他测试点均满足2≤N≤100

输入样例:
4
4
1332
4
9583
3
616
10
1029384756
输出样例:
Case #1: 6
Case #2: 14
Case #3: 7
Case #4: 31
样例解释

在第一个样例中,无论墙壁如何被破坏,Thanh都可以获得 66 分的美观总分。在第一天,他可以随便选一个美观评分3的墙段进行绘画。在一天结束时,第一部分或第四部分将被摧毁,但无论哪一部分都无关紧要。在第二天,他都可以在另一段美观评分 33 的墙段上作画。

在第二个样例中,Thanh 在第一天选择最左边的美观评分为 99 的墙段上作画。在第一天结束时唯一可以被毁掉的墙体是最右边的那段墙体,因为最左边的墙壁被涂上了颜料。在第二天,他可以选择在左数第二段评分为 55 的墙面上作画。然后右数第二段墙体被摧毁。请注意,在第二天,Thanh不能选择绘制第三段墙面,因为它不与任何其他作画墙面相邻。这样可以获得 1414 分的美观总分。

解题思路:

每天画一幅,冲毁一幅,且冲毁的只能是至少一个邻边没有墙,不能从中间冲毁;每天画必须和已画的相邻。

得到结论最多能画(n+1)/2 = k幅画。

于是直接枚举每个k区间,比较max。k区间的总评分用前缀和来求取socre = s[i] - s[i-k];(i从k-n)

参考代码:

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;
const int N = 5e6+10;
int s[N];
char str[N];
int n;int main()
{scanf("%d", &n);for(int ca=1;ca<=n;ca++){int x;cin>>x;cin>>str+1;for(int i=1;i<=x;i++)s[i] = s[i-1] + str[i] - '0';int sum = 0,m = (x+1)/2;for(int i=m;i<=x;i++) sum = max(sum,s[i] - s[i-m]);printf("Case #%d: %d\n",ca,sum);}return 0;
}

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

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

相关文章

基于SSM+Jsp+Mysql的美食推荐管理系统

开发语言&#xff1a;Java框架&#xff1a;ssm技术&#xff1a;JSPJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包…

输出100~200之间的素数(C语言)

一、运行结果&#xff1b; 二、源代码&#xff1b; # define _CRT_SECURE_NO_WARNINGS # include <stdio.h>//实现素数判断函数&#xff1b; int Prime(int number) {//初始化变量值&#xff1b;int divided 2;int JudgementCondition 0;//循环判断素数&#xff1b;wh…

MySQL Innodb 引擎中预防 Update 操作上升为表锁

一、MySQL 如何预防 Update 上升为表锁 在 MySQL 中&#xff0c;进行任何数据的 修改 操作都会进行一定的锁操作&#xff0c;而锁的不同直接导致性能的差异。例如 MyISAM 引擎&#xff0c;更新时采用表锁&#xff0c;并发性较差。而 Innodb 引擎支持事务&#xff0c;更新时采用…

7.1 Mysql shell 定时备份

直接上脚本----linu 定时任务执行 #!/bin/bash# 配置信息 DB_USER"your_username" # 数据库用户名 DB_PASSWORD"your_password" # 数据库密码 DB_NAME"your_database_name" # 要备份的数据库名 BACKUP_DIR"/path/to/backup/directory"…

LiDAR和Camera融合的BEV感知算法-BEVFusion

0. 简述 本次给大家讲解一篇非常经典的融合工作叫 BEVFusion&#xff0c;我们依旧从算法动机&开创性思路、主体结构、损失函数以及性能对比四个方面展开 BEVFusion 有两篇文章&#xff0c;本次主要讲解的是阿里和北大的&#xff1a;BEVFusion: A Simple and Robust LiDAR-…

[leetcode]28. 找出字符串中第一个匹配项的下标

前言&#xff1a;力扣刷题 问题&#xff1a; 给你两个字符串 haystack 和 needle &#xff0c;请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标&#xff08;下标从 0 开始&#xff09;。如果 needle 不是 haystack 的一部分&#xff0c;则返回 -1 。 示例&…

CA根证书——https安全保障的基石

HTTPS通信中&#xff0c;服务器端使用数字证书来证明自己的身份。客户端需要验证服务器发送的证书的真实性。这就需要一个可信的第三方机构&#xff0c;即CA&#xff0c;来颁发和管理证书。CA根证书是证书颁发机构层次结构的顶级证书&#xff0c;客户端信任的所有证书都可以追溯…

新手学python还是c?

考虑到个人情况和职业规划是非常重要的。我这里有一套编程入门教程&#xff0c;不仅包含了详细的视频讲解&#xff0c;项目实战。如果你渴望学习编程&#xff0c;不妨点个关注&#xff0c;给个评论222&#xff0c;私信22&#xff0c;我在后台发给你。 Python作为初学者入门语言…

Swift:“逻辑运算子“与“比较运算符“

1. 逻辑非 ! 逻辑非运算符 ! 是用于对布尔值取反的。当操作数为 true 时&#xff0c;! 将返回 false&#xff0c;而当操作数为 false 时&#xff0c;! 将返回 true。 let isTrue true let isFalse !isTrue // isFalse 现在是 false 2. 逻辑与 && 逻辑与运算符 &a…

PetaLinux 去除自动获取 IP 地址

问题&#xff1a;系统启动的时候会自动检测 IP 地址&#xff0c;如不需要这个功能&#xff08;该过程需耗时十几秒&#xff09;。可以自定义 IP 地址&#xff0c;去掉这一步。 操作步骤如下&#xff1a; 所有命令均需在非管理员模式下执行 1. 初始化 PetaLinux 运行环境 运行…

区块链技术与大数据结合的商业模式探索

hello宝子们...我们是艾斯视觉擅长ui设计和前端开发10年经验&#xff01;希望我的分享能帮助到您&#xff01;如需帮助可以评论关注私信我们一起探讨&#xff01;致敬感谢感恩&#xff01; 随着区块链技术和大数据技术的不断发展&#xff0c;两者的结合为企业带来了新的商业模式…

Flutter应用如何让屏幕在app运行期间保持常亮?

大家好&#xff0c;我是你们的好朋友咕噜铁蛋&#xff01;今天&#xff0c;我想和大家分享一个有趣且实用的技巧——在Flutter应用中实现屏幕常亮功能。当我们的应用需要用户长时间关注屏幕内容时&#xff0c;比如阅读、观看视频或进行游戏等&#xff0c;保持屏幕常亮就显得尤为…

Hive函数笔试题(简单)

第1题 有如下的用户访问数据 userId visitDate visitCount u01 2017/1/21 5 u02 2017/1/23 6 u03 2017/1/22 8 u04 2017/1/20 3 u01 2017/1/23 6 u01 2017/2/21 8 u02 2017/1/23 6 u01 2017/2/22 4 要求使用SQL统计出每个用户的累积访问次数&…

前端学习<三>CSS进阶——03-网页设计和开发中,那些困扰大神的关于字体的知识

前言 我周围的码农当中&#xff0c;有很多是技术大神&#xff0c;却常常被字体这种简单的东西所困扰。 这篇文章&#xff0c;我们来讲一讲关于字体的常识。这些常识所涉及到的问题&#xff0c;有很强的可操作性&#xff0c;都是在实际业务中真实遇到的&#xff0c;都是需要开…

基于Matlab的血管图像增强算法,Matlab实现

博主简介&#xff1a; 专注、专一于Matlab图像处理学习、交流&#xff0c;matlab图像代码代做/项目合作可以联系&#xff08;QQ:3249726188&#xff09; 个人主页&#xff1a;Matlab_ImagePro-CSDN博客 原则&#xff1a;代码均由本人编写完成&#xff0c;非中介&#xff0c;提供…

MSOX3104T是德科技MSOX3104T示波器

181/2461/8938产品概述&#xff1a; Keysight MSOX3104T X 系列示波器提供您更快获得测量见解所需的所有性能和功能&#xff0c;再次重新定义了您对通用示波器的期望。除了触摸的优点外&#xff0c;内置 USB 主机和 USB 设备端口还使 PC 连接变得容易。InfiniiVision MSOX3104…

网页设计图片素材-家具 里面有71张家具图片

网页设计图片素材-家具 里面有71张家具图片 链接: https://pan.baidu.com/s/1wHgpZrHXrkS-jeJxxnzIQg 提取码: t7b6

Fluentd介绍

1.什么是Fluentd Fluentd是一个开源的日志收集和分发系统&#xff0c;它能够从多种数据源采集日志信息&#xff0c;并对日志进行过滤、加工处理后发送到不同的存储和处理系统。 以下是关于Fluentd的一些关键信息&#xff1a; 基本概念&#xff1a;Fluentd被设计为一个高性能…

RPA机器人如何支持滑块验证码?泽众RPA如何轻松解决?

为了提高软件的安全性&#xff0c;很多系统&#xff0c;包括web系统和手机上的应用&#xff0c;越来越多的使用验证码来提升系统的安全性&#xff0c;防止非法访问&#xff0c;特别是防止机器人的访问。 如上图所示&#xff0c;就是最近比较常用的“滑块验证码”。它要求用户“…

K-均值聚类算法

K-均值聚类算法是一种常用的无监督学习算法&#xff0c;用于将数据集分成 K 个簇。该算法的主要思想是通过迭代的方式将数据点分配到离它们最近的簇中&#xff0c;并更新簇的中心点&#xff0c;直到满足某个停止条件为止。 以下是 K-均值聚类算法的基本步骤&#xff1a; 初始化…