2022icpc亚洲区域赛(南京站)Problem D - 聊天程序

2024-05-29 02:04

本文主要是介绍2022icpc亚洲区域赛(南京站)Problem D - 聊天程序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2022 i c p c 亚洲区域赛(南京站) P r o b l e m D − 聊天程序 \Huge{2022icpc亚洲区域赛(南京站)Problem D - 聊天程序} 2022icpc亚洲区域赛(南京站)ProblemD聊天程序

文章目录

  • 题意
  • 思路
  • 标程

题目链接:Problem - D - Codeforces

官方题解:D - 聊天程序 - SUA Wiki

题意

本题首先给出 n , k , m , c , d n,k,m,c,d n,k,m,c,d,然后给出 n n n个整数 a 1 , a 2 . . . a n a_1,a_2...a_n a1,a2...an

题目要求执行以下操作至少一次:

  • 选择一个长度恰好为 m m m的子数组 a a a,然后将长度也为 m m m的等差数组(首项为 c c c,公差为 d d d)依次加到对应的子数组 a a a上。

求至多一次操作之后,序列中第 k k k大的值最大可能是多少?

数据范围:

  • 1 ≤ k , m ≤ n ≤ 2 × 1 0 5 1\le k,m\le n \le 2\times 10^5 1k,mn2×105
  • 0 ≤ c , d ≤ 1 0 9 0\le c,d \le 10^9 0c,d109
  • 0 ≤ a i ≤ 1 0 9 0\le a_i\le 10^9 0ai109

思路

通过题意,我们可以发现题目要求的答案符合单调性,即如果答案 k k k符合要求,那么小于 k k k的数也必然符合要求(忽略能否构造出 k k k)。

因此,我们考虑使用二分答案。

那么,对于答案 k k k,当我们枚举小于 k k k的时候,check()函数必然是返回true,所以说使用二分答案最终枚举到的 k k k必定可以构造出。

但是,这道题目的难点就在于check()函数的判断,check()函数的时间复杂度必须保持在 O ( n ) O(n) O(n)的时间复杂度下可通过本题。

具体做法为:

  • 首先二分答案 m i d mid mid,将大于等于 m i d mid mid的数看成 1 1 1,小于 m i d mid mid的数看成 0 0 0。问题变为“判断能否通过至多一次操作,使序列中 1 1 1的数量大于等于 m i d mid mid”。
  • 接下来枚举操作位置,并计算进行操作后能否满足要求。考虑一个元素 a t ( a t < x ) a_t(a_t<x) at(at<x)容易发现,在操作范围从左往右移的过程中,当 a t a_t at第一次进入操作范围时,它会变成最大值,之后慢慢变小,最后又变回原来的值。因此每个数只会从 0 0 0变成 1 1 1 一次,再从 1 1 1变成 0 0 0一次。
  • 我们只要对每个元素找出这两次变化的位置,就能利用前缀和算出在每个位置进行操作对 1 1 1的数量的影响。

标程

#include<bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
#define int long long 
#define ULL unsigned long long 
#define PII pair<int, int>
#define lowbit(x) (x & -x)
#define Mid ((l + r) >> 1)
#define ALL(x) x.begin(), x.end()
#define endl '\n'
#define fi first 
#define se secondconst int INF = 0x7fffffff;
const int Mod = 1e9 + 7;
const int N = 2e5 + 10; int n, k, m, c, d;
vector<int> a, f;bool check(int mid) {int cnt = 0;//记录不小于mid的个数for(int i = 1; i <= n; i ++ ) if(a[i] >= mid) cnt ++;if(cnt >= k) return true;//剪枝,个数符合直接范围truef.clear(); f.resize(n + 5);		//关键的f数组,用于记录前缀和for(int i = 1; i <= n; i ++ ) {if(a[i] >= mid) continue;    //只判断小于mid的数字int r = min(m - 1, i - 1);int mx = a[i] + c + d * r;  //当前数字最大能加多少if(mx < mid) continue;f[max(m, i)] ++;            //记录这个数字大于mid的区间的起点的坐标int mi = a[i] + c;          //当前数字最小能加多少if(mi >= mid) f[min(i + m, n + 1)] --;//若加最小也满足,则只有其不在区间m中时才去掉else {int t = mid - a[i] - c;int pos = (t + d - 1) / d - 1;f[min(n + 1, i + m - pos - 1)] --;}}for(int i = m; i <= n; i ++ ) {cnt += f[i];if(cnt >= k) return true;}return false;
}void Solved() { cin >> n >> k >> m >> c >> d;a.resize(n + 1);for(int i = 1; i <= n; i ++ ) {cin >> a[i];}int l = 0, r = 1e15, mid;//需要根据题目计算出答案可能的最大值while(l < r) {mid = l + r + 1 >> 1;if(check(mid)) l = mid;else r = mid - 1;}cout << l << endl;
}signed main(void) {IOSint ALL = 1; // cin >> ALL;while(ALL -- ) Solved();// cout << fixed;//强制以小数形式显示// cout << setprecision(n); //保留n位小数return 0;
}

这篇关于2022icpc亚洲区域赛(南京站)Problem D - 聊天程序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1012330

相关文章

python编写朋克风格的天气查询程序

《python编写朋克风格的天气查询程序》这篇文章主要为大家详细介绍了一个基于Python的桌面应用程序,使用了tkinter库来创建图形用户界面并通过requests库调用Open-MeteoAPI... 目录工具介绍工具使用说明python脚本内容如何运行脚本工具介绍这个天气查询工具是一个基于 Pyt

Ubuntu设置程序开机自启动的操作步骤

《Ubuntu设置程序开机自启动的操作步骤》在部署程序到边缘端时,我们总希望可以通电即启动我们写好的程序,本篇博客用以记录如何在ubuntu开机执行某条命令或者某个可执行程序,需要的朋友可以参考下... 目录1、概述2、图形界面设置3、设置为Systemd服务1、概述测试环境:Ubuntu22.04 带图

Python程序打包exe,单文件和多文件方式

《Python程序打包exe,单文件和多文件方式》:本文主要介绍Python程序打包exe,单文件和多文件方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录python 脚本打成exe文件安装Pyinstaller准备一个ico图标打包方式一(适用于文件较少的程

Python程序的文件头部声明小结

《Python程序的文件头部声明小结》在Python文件的顶部声明编码通常是必须的,尤其是在处理非ASCII字符时,下面就来介绍一下两种头部文件声明,具有一定的参考价值,感兴趣的可以了解一下... 目录一、# coding=utf-8二、#!/usr/bin/env python三、运行Python程序四、

无法启动此程序因为计算机丢失api-ms-win-core-path-l1-1-0.dll修复方案

《无法启动此程序因为计算机丢失api-ms-win-core-path-l1-1-0.dll修复方案》:本文主要介绍了无法启动此程序,详细内容请阅读本文,希望能对你有所帮助... 在计算机使用过程中,我们经常会遇到一些错误提示,其中之一就是"api-ms-win-core-path-l1-1-0.dll丢失

Java内存区域与内存溢出异常的详细探讨

《Java内存区域与内存溢出异常的详细探讨》:本文主要介绍Java内存区域与内存溢出异常的相关资料,分析异常原因并提供解决策略,如参数调整、代码优化等,帮助开发者排查内存问题,需要的朋友可以参考下... 目录一、引言二、Java 运行时数据区域(一)程序计数器(二)Java 虚拟机栈(三)本地方法栈(四)J

SpringBoot后端实现小程序微信登录功能实现

《SpringBoot后端实现小程序微信登录功能实现》微信小程序登录是开发者通过微信提供的身份验证机制,获取用户唯一标识(openid)和会话密钥(session_key)的过程,这篇文章给大家介绍S... 目录SpringBoot实现微信小程序登录简介SpringBoot后端实现微信登录SpringBoo

uniapp小程序中实现无缝衔接滚动效果代码示例

《uniapp小程序中实现无缝衔接滚动效果代码示例》:本文主要介绍uniapp小程序中实现无缝衔接滚动效果的相关资料,该方法可以实现滚动内容中字的不同的颜色更改,并且可以根据需要进行艺术化更改和自... 组件滚动通知只能实现简单的滚动效果,不能实现滚动内容中的字进行不同颜色的更改,下面实现一个无缝衔接的滚动

Java使用WebView实现桌面程序的技术指南

《Java使用WebView实现桌面程序的技术指南》在现代软件开发中,许多应用需要在桌面程序中嵌入Web页面,例如,你可能需要在Java桌面应用中嵌入一部分Web前端,或者加载一个HTML5界面以增强... 目录1、简述2、WebView 特点3、搭建 WebView 示例3.1 添加 JavaFX 依赖3

防止SpringBoot程序崩溃的几种方式汇总

《防止SpringBoot程序崩溃的几种方式汇总》本文总结了8种防止SpringBoot程序崩溃的方法,包括全局异常处理、try-catch、断路器、资源限制、监控、优雅停机、健康检查和数据库连接池配... 目录1. 全局异常处理2. 使用 try-catch 捕获异常3. 使用断路器4. 设置最大内存和线