当前位置: 首页 > news >正文

leetcode第 357/358 场周赛

2817. 限制条件下元素之间的最小绝对差

可能别人有更好的解法,我这写法是不断往线段树中插入数值,每次先插入nums[i-x],然后搜索(1到i)中的最大值和(i到max)中的最小值去更新ans。

class Solution {
public:struct node{int mx,mn;int lson,rson;};int cnt = 1;void insert(int pos,int l,int r,int d,vector<node>&tree){tree[pos].mx = max(tree[pos].mx,d);tree[pos].mn = min(tree[pos].mn,d);if(l==r)return;int mid = (l+r)>>1;if(d<=mid){if(tree[pos].lson==0){tree[pos].lson = cnt++;tree[cnt-1].mn = (1<<30);}insert(tree[pos].lson,l,mid,d,tree);}else{if(tree[pos].rson==0){tree[pos].rson = cnt++;tree[cnt-1].mn = (1<<30);}insert(tree[pos].rson,mid+1,r,d,tree);}}int getmx(int pos,int l,int r,int L,int R,vector<node>&tree){if(L<=l && r<=R)return tree[pos].mx;int mid = (l+r)>>1;int mx = 0;if(L<=mid && tree[pos].lson)mx = getmx(tree[pos].lson,l,mid,L,R,tree);if(mid<R && tree[pos].rson)mx = max(mx,getmx(tree[pos].rson,mid+1,r,L,R,tree));return mx;}int getmn(int pos,int l,int r,int L,int R,vector<node>&tree){if(L<=l && r<=R)return tree[pos].mn;int mid = (l+r)>>1;int mx = (1<<30);if(L<=mid && tree[pos].lson)mx = getmn(tree[pos].lson,l,mid,L,R,tree);if(mid<R && tree[pos].rson)mx = min(mx,getmn(tree[pos].rson,mid+1,r,L,R,tree));return mx;}int minAbsoluteDifference(vector<int>& nums, int x) {int tnx=0;for(auto i:nums)tnx = max(tnx,i);vector<node>tree(nums.size()<<5);int ans = (1<<30);tree[0].mn = (1<<30);for(int i=0;i<nums.size();++i){if(i-x>=0)insert(0,1,tnx,nums[i-x],tree);int d = getmx(0,1,tnx,1,nums[i],tree);if(d)ans = min(ans,nums[i]-d);d = getmn(0,1,tnx,nums[i],tnx,tree);if(d!=(1<<30))ans = min(ans,d-nums[i]);}return ans;}
};

看了看别人题解,直接用set写是真的牛。自己还是见识短浅了。

2813. 子序列最大优雅度

暴力乱搞,考虑两种极端情况,一种无脑选profit大的,一种优先选不同类型的。
我们先选不同类型的,记录值,然后选profit大的没选过的, 更新一下值,然后选完后就会变成profit前k个的情况。取最大值就行。

class Solution {
public:bool flag[100010];long long findMaximumElegance(vector<vector<int>>& items, int k) {sort(items.begin(),items.end(),[](vector<int>&a,vector<int>&b){return a[0]>b[0];});map<int,int>mp;auto cmp = [](pair<int,int> a,pair<int,int> b){return a.first>b.first;};priority_queue<pair<int,int> ,vector<pair<int,int>>,  decltype(cmp)>que(cmp);long a=0,b=0;int cnt =0;long long tp = 0,dc = 0;long long ans = 0;vector<bool>flag(items.size());int num = 0;for(int i=0;i<items.size();++i){if(dc<k){if(!mp[items[i][1]]){que.push({items[i][0],items[i][1]});mp[items[i][1]] = 1;dc++;flag[i] = 1;tp+=items[i][0];ans = max(ans,tp+dc*dc);num++;}}elsebreak;}for(int i=0;i<k;++i){if(num<k  && flag[i] ==0){tp += items[i][0];num++;}else if(!que.empty() && flag[i] ==0){auto [a,b] = que.top();tp-= a-items[i][0];dc--;que.pop();}ans = max(ans,tp+dc*dc);}return ans;}
};

2812. 找出最安全路径

先通过一遍bfs计算出每一个点的安全系数
然后从(0,0)开始跑bfs,每次选择安全系数最大的点,并记录每条路径中最小的安全系数。

class Solution {
public:struct node{int x,y,val;bool operator<(const node &a)const{return val<a.val;}};int maximumSafenessFactor(vector<vector<int>>& grid) {int n = grid.size();int m = grid[0].size();vector dis(n,vector<int>(m,(1<<30)));queue<pair<int,int>>q;for(int i=0;i<n;++i)for(int j=0;j<m;++j)if(grid[i][j]){dis[i][j] = 0;q.push({i,j});}int f[] = {0,-1,0,1,1,0,-1,0};while(!q.empty()){auto [x,y] = q.front();q.pop();for(int i=0;i<4;++i){int nx = x+f[i<<1];int ny = y+f[i<<1|1];if(nx>=0 && nx<n && ny>=0 &&ny<m){if(dis[nx][ny]>dis[x][y]+1){dis[nx][ny] = dis[x][y]+1;q.push({nx,ny});}}}}vector cost(n,vector<int>(m,0));vector flag(n,vector<bool>(m,0));priority_queue<node>que;que.push({0,0,dis[0][0]});cost[0][0] = dis[0][0];while(!que.empty()){auto u = que.top();que.pop();if(flag[u.x][u.y])continue;flag[u.x][u.y] = 1;for(int i=0;i<4;++i){int nx = u.x+f[i<<1];int ny = u.y+f[i<<1|1];if(nx>=0 && nx<n && ny>=0 &&ny<m){if(cost[nx][ny]<cost[u.x][u.y] && !flag[nx][ny]){cost[nx][ny] = min(cost[u.x][u.y],dis[nx][ny]);que.push({nx,ny,dis[nx][ny]});}}}}return cost[n-1][n-1];}
};

2818. 操作使得分最大

统计每一个数字的最大区间 [ L , R ] [L,R] [L,R],满足当 L < = l < = i 且 i < = r < = R L<=l<=i 且 i<=r<=R L<=l<=ii<=r<=R时,该区间的分数为 n u m s [ i ] nums[i] nums[i],这个区间使用单调栈统计,然后每个 n u m [ i ] num[i] num[i]可以被使用次数就为 ( i − L + 1 ) ∗ ( R − i + 1 ) (i-L+1)*(R-i+1) (iL+1)(Ri+1)。最后把数字从大到小排序,然后选择k个即可。

class Solution {
public:const int mod = 1e9+7;int maximumScore(vector<int>& nums, int k) {vector<int> score(nums.size());auto calscore = [](int a){int ret = 0;for(int i=2;i*i<=a;++i){if(a%i==0){ret++;while(a%i==0)a/=i;}}if(a!=1)ret++;return ret;} ;for(int i=0;i<nums.size();++i)score[i] = calscore(nums[i]);vector<int>pre(nums.size());vector<int>sa(nums.size(),nums.size());stack<int>ddz;for(int i=0;i<nums.size();++i){while(!ddz.empty() && score[i]>score[ddz.top()]){sa[ddz.top()] = i;ddz.pop();}if(ddz.empty())pre[i] = -1;else pre[i] = ddz.top();ddz.push(i);}auto cmp = [](pair<int,long long>a,pair<int,long long>b){if(a.first==b.first)return a.second<b.second;return a.first<b.first;};priority_queue< pair<int,long long>, vector<pair<int,long long> > , decltype(cmp) > que(cmp);for(int i=0;i<nums.size();++i){que.push({nums[i],(sa[i]-i)*(i-pre[i])});}long long ans = 1;auto qpow = [=](long long a,long long b)->long long{long long ret = 1;while(b){if(b&1) ret = (a*ret)%mod;a = a*a%mod;b>>=1;}return ret;};while(k){auto [x,y] = que.top();que.pop();ans = ans*qpow(x,min(y,1ll*k))%mod;k -= min(y,1ll*k);}return ans;}
};

相关文章:

leetcode第 357/358 场周赛

2817. 限制条件下元素之间的最小绝对差 可能别人有更好的解法&#xff0c;我这写法是不断往线段树中插入数值&#xff0c;每次先插入nums[i-x]&#xff0c;然后搜索&#xff08;1到i)中的最大值和(i到max)中的最小值去更新ans。 class Solution { public:struct node{int mx,…...

Jmeter 分布式性能测试避坑指南

在做后端服务器性能测试中&#xff0c;我们会经常听到分布式。那你&#xff0c;是否了解分布式呢&#xff1f;今天&#xff0c;我们就来给大家讲讲&#xff0c;在企业实战中&#xff0c;如何使用分布式进行性能测试&#xff0c;实战过程中&#xff0c;又有哪些地方要特别注意&a…...

基于SpringCloud的会议室预约系统Java基于微服务的会议室报修系统【源码+lw】

&#x1f495;&#x1f495;作者&#xff1a;计算机源码社 &#x1f495;&#x1f495;个人简介&#xff1a;本人七年开发经验&#xff0c;擅长Java、微信小程序、Python、Android、大数据等&#xff0c;大家有这一块的问题可以一起交流&#xff01; &#x1f495;&#x1f495…...

idea设置忽略大小写

1.点击file 2.点击settings 3.点击Editor选项 4.点击general选项 5.点击code completion 6.点击左上角match case...

re学习(35)攻防世界-no-strings-attached(动调)

参考文章&#xff1a;re学习笔记&#xff08;28&#xff09;攻防世界-re-no-strings-attached_Forgo7ten的博客-CSDN博客 攻防世界逆向入门题之no-strings-attached_攻防世界 no-strings-attached_沐一 林的博客-CSDN博客 本人题解&#xff1a; 扔入Exepeinfo中查壳和其他信息…...

STM32 F103C8T6学习笔记8:0.96寸单色OLED显示屏显示字符

使用STM32F103 C8T6 驱动0.96寸单色OLED显示屏: OLED显示屏的驱动&#xff0c;在设计开发中OLED显示屏十分常见&#xff0c;因此今日学习一下。一篇文章从程序到显示都讲通。 文章提供源码、原理解释、测试工程下载&#xff0c;测试效果图展示。 目录 OLED驱动原理—IIC通信…...

vscode的配置和使用

1.侧边栏调整大小 放大&#xff1a;View -> Appearance -> Zoom in&#xff08;快捷键Ctrl &#xff09; 缩小&#xff1a;View -> Appearance -> Zoom out&#xff08;快捷键Ctrl -&#xff09; 侧边栏字体调整到合适大小后&#xff0c;可以按下一步调整代码区…...

SpringBoot统⼀功能处理

前言&#x1f36d; ❤️❤️❤️SSM专栏更新中&#xff0c;各位大佬觉得写得不错&#xff0c;支持一下&#xff0c;感谢了&#xff01;❤️❤️❤️ Spring Spring MVC MyBatis_冷兮雪的博客-CSDN博客 本章是讲Spring Boot 统⼀功能处理模块&#xff0c;也是 AOP 的实战环节&…...

LeetCode 每日一题 2023/8/14-2023/8/20

记录了初步解题思路 以及本地实现代码&#xff1b;并不一定为最优 也希望大家能一起探讨 一起进步 目录 8/14 617. 合并二叉树8/15 833. 字符串中的查找与替换8/16 2682. 找出转圈游戏输家8/17 1444. 切披萨的方案数8/18 1388. 3n 块披萨8/19 2235. 两整数相加8/20 8/14 617. 合…...

进入微服务阶段后的学习方法

微服务SpringCloud学习的特点 陌生&#xff0c;多&#xff0c;复杂。 技术陌生&#xff0c;技术栈多&#xff0c;实现复杂。 学习方式 对于每一个组件&#xff1a; 1.知道是什么、有什么用 2.知道操作步骤&#xff08;跟着讲义操作即可&#xff09;&#xff0c;包括&#…...

C/C++中const关键字详解

为什么使用const&#xff1f;采用符号常量写出的代码更容易维护&#xff1b;指针常常是边读边移动&#xff0c;而不是边写边移动&#xff1b;许多函数参数是只读不写的。const最常见用途是作为数组的界和switch分情况标号(也可以用枚举符代替)&#xff0c;分类如下&#xff1a;…...

【2023新教程】树莓派4B开机启动-树莓派第一次启动-树莓派不使用显示器启动-树莓派从购买到启动一步一步完全版!

背景 闲来无事&#xff0c;在咸鱼上买了一个树莓派4B。买来配件都十分齐全&#xff0c;于是就想着启动来测试一下。下面是树莓派无显示器第一次启动的全过程&#xff0c;包含安装系统。 网上的教程大多需要额外使用显示器、鼠标、键盘之类的外设。然而&#xff0c;树莓派本身就…...

LA@2@1@线性方程组和简单矩阵方程有解判定定理

文章目录 矩阵方程有解判定定理线性方程组有解判定特化:齐次线性方程组有解判定推广:矩阵方程 A X B AXB AXB有解判定证明推论 矩阵方程有解判定定理 线性方程组有解判定 线性方程组 A x b A\bold{x}\bold{b} Axb有解的充分必要条件是它的系数矩阵A和增广矩阵 ( A , b ) (A,…...

如何使用ChatGPT创作一个小说式的虚构的世界

世界构建也许是小说写作中最重要的一环&#xff0c;但也可能非常耗时。让ChatGPT加快这一过程吧。 写小说最棒的一点就是有机会从零开始创造一个新世界。你可以创造超凡脱俗的景观&#xff0c;赋予人物魔法。神话故事可以存在于你小说中的现实世界&#xff0c;而传统可以帮助你…...

用于量子通信和互联网的光量子芯片

近年来&#xff0c;新兴的光量子芯片在量子通信和量子互联网领域取得了重大进展。光量子芯片芯片具有可扩展、稳定和低成本等特点&#xff0c;为微型化应用开辟了新的可能性。 7月14日&#xff0c;一篇发表在《light: science & applications》的文章概述了用于量子通信的光…...

11. Vuepress2.x 关闭夜间模式

修改 docs/.vuepress/config.ts 配置文件 设置 themeConfig.darkMode属性详见 官网 module.exports {host: localhost, // ipport: 8099, //端口号title: 我的技术站, // 设置网站标题description: 描述&#xff1a;我的技术站,base: /, //默认路径head: [// 设置 favor.ico&a…...

netty实现websocket通信

调用注意&#xff1a; 1、端口一定要是可以访问的。 2、依赖必须注意和其他版本冲突&#xff0c;比如redis的springboot starter包&#xff0c;会与5.0版本冲突。 <netty.version>4.1.74.Final</netty.version> <dependency><groupId>io…...

两个list如何根据一个list中的属性去过滤掉另一个list中不包含这部分的属性,用流实现

你可以使用Java 8的流来实现这个功能。假设你有两个包含对象的List&#xff0c;每个对象有一个属性&#xff0c;你想根据一个List中的属性值来过滤掉另一个List中不包含这个属性值的对象。下面是一种使用流的方式来实现这个功能 import java.util.ArrayList; import java.util…...

Blender 混合现实3D模型制作指南【XR】

本教程分步展示如何&#xff1a; 减少 3D 模型的多边形数量&#xff0c;使其满足 Microsoft Dynamics 365 Guides 和使用 Microsoft Power Apps 创建的应用程序中包含的混合现实组件的特定性能目标的性能需求。将 3D 模型的多种材质&#xff08;颜色&#xff09;组合成可应用于…...

kubeasz在线安装K8S集群单master集群(kubeasz安装之二)

一、介绍 Kubeasz 是一个基于 Ansible 自动化工具&#xff0c;用于快速部署和管理 Kubernetes 集群的工具。它支持快速部署高可用的 Kubernetes 集群&#xff0c;支持容器化部署&#xff0c;可以方便地扩展集群规模&#xff0c;支持多租户&#xff0c;提供了强大的监控和日志分…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

适应性Java用于现代 API:REST、GraphQL 和事件驱动

在快速发展的软件开发领域&#xff0c;REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名&#xff0c;不断适应这些现代范式的需求。随着不断发展的生态系统&#xff0c;Java 在现代 API 方…...

如何配置一个sql server使得其它用户可以通过excel odbc获取数据

要让其他用户通过 Excel 使用 ODBC 连接到 SQL Server 获取数据&#xff0c;你需要完成以下配置步骤&#xff1a; ✅ 一、在 SQL Server 端配置&#xff08;服务器设置&#xff09; 1. 启用 TCP/IP 协议 打开 “SQL Server 配置管理器”。导航到&#xff1a;SQL Server 网络配…...

第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)

第一篇&#xff1a;Liunx环境下搭建PaddlePaddle 3.0基础环境&#xff08;Liunx Centos8.5安装Python3.10pip3.10&#xff09; 一&#xff1a;前言二&#xff1a;安装编译依赖二&#xff1a;安装Python3.10三&#xff1a;安装PIP3.10四&#xff1a;安装Paddlepaddle基础框架4.1…...