AtCoder Beginner Contest 216(F)
F - Max Sum Counting
链接: F - Max Sum Counting
题意
两个 大小为 nnn 的序列 aiaiai 和 bibibi,任意选取一些下标 iii,求 max(ai)>=∑bi\max(ai) >= \sum{bi}max(ai)>=∑bi的方案数。
解析
首先考虑状态 一是和, 二是最大值, 但这样我们发现需要三重循环,在 n=5000n = 5000n=5000 的情况下是不能接受的复杂度,于是我们想到按 aiaiai 排序后,我们只计算 ∑bi\sum{bi}∑bi 的方案,将所有满足条件的方案再计入答案,就变成一个普通的背包求方案数了。
对于要按 aiaiai 排序的证明:
因为我们没有多开一维来记录 max(ai)\max(ai)max(ai) 最大值, 所以对于每一种 bibibi 和为 sumsumsum 他的状态集合可能有许多不同的 max(ai)max(ai)max(ai)。
假设和为 sumsumsum 有 max(ai)=ajmax(ai) = ajmax(ai)=aj,maxai=akmax{ai} = akmaxai=ak 两种可能,若是不按 aiaiai 排序 会导致不知道 aj,akaj, akaj,ak 那种状态可以转移。
假设 sum=10sum = 10sum=10, aj=100aj = 100aj=100 ,ak=10ak = 10ak=10 当前的 ai=10ai = 10ai=10 ,bi=10bi = 10bi=10 那么只能从 ajajaj 转移 因为只有这种才保证 max(ai)>∑bi\max(ai) > \sum{bi}max(ai)>∑bi 但已经把 aj,akaj, akaj,ak 的状态整合在一起了不能分开。
若是按 aiaiai 排序,新来的 aiaiai 一定是目前的最大值, 一定比 ajajaj 和 akakak 都大 于是一个状态包含的所有情况都能转移。
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5010, mod = 998244353, MAX = 5000;
struct node{int ai, bi;bool operator < (const node &A)const{return ai < A.ai;}
}s[N];
int f[N];//bi之和价值为i的方案数
int main(){int n;cin >> n;for(int i = 1; i <= n; i ++) cin >> s[i].ai;for(int i = 1; i <= n; i ++) cin >> s[i].bi;sort(s + 1, s + 1 + n);f[0] = 1;int ans = 0;for(int i = 1; i <= n; i ++){for(int j = MAX; j >= s[i].bi; j --){f[j] = (f[j] + f[j - s[i].bi]) % mod;if(j <= s[i].ai) ans = (ans + f[j - s[i].bi]) % mod;}}cout << ans;return 0;
}
相关文章:
AtCoder Beginner Contest 216(F)
F - Max Sum Counting 链接: F - Max Sum Counting 题意 两个 大小为 nnn 的序列 aiaiai 和 bibibi,任意选取一些下标 iii,求 max(ai)>∑bi\max(ai) > \sum{bi}max(ai)>∑bi的方案数。 解析 首先考虑状态 一是和,…...
每天学一点之Stream流相关操作
StreamAPI 一、Stream特点 Stream是数据渠道,用于操作数据源(集合、数组等)所生成的元素序列。“集合讲的是数据,负责存储数据,Stream流讲的是计算,负责处理数据!” 注意: ①Str…...
MatCap模拟光照效果实现
大家好,我是阿赵 之前介绍过各种光照模型的实现方法。那些光照模型的实现虽然有算法上的不同,但基本上都是灯光方向和法线方向的计算得出的明暗结果。 下面介绍一种叫做MatCap的模拟光照效果,这种方式计算非常简单,脱离灯光的计算…...
二十一、PG管理
一、 PG异常状态说明 1、 PG状态介绍 可以通过ceph pg stat命令查看PG当前状态,健康状态为“active clean” [rootrbd01 ~]# ceph pg stat 192 pgs: 192 activeclean; 1.3 KiB data, 64 MiB used, 114 GiB / 120 GiB avail; 85 B/s rd, 0 op/s2、pg常见状态 状…...
SAPUI5开发01_01-Installing Eclipse
1.0 简要要求概述: 本节您将安装SAPUI 5,以及如何在Eclipse Juno中集成SAPUI 5工具。 1.1 安装JDK JDK 是一种用于构建在 Java 平台上发布的应用程序、Applet 和组件的开发环境,即编写 Java 程序必须使用 JDK,它提供了编译和运行 Java 程序的环境。 在安装 JDK 之前,首…...
Qt之高仿QQ系统设置界面
QQ或360安全卫士的设置界面都是非常有特点的,所有的配置项都在一个垂直的ScrollArea中,但是又能通过左侧的导航栏点击定位。这样做的好处是既方便查看指定配置项,又方便查看所有配置项。 一.效果 下面左边是当前最新版QQ的系统设置界面,右边是我的高仿版本,几乎一毛一样…...
JVM概览:内存空间与数据存储
核心的五个部分虚拟机栈:局部变量中基础类型数据、对象的引用存储的位置,线程独立的。堆:大量运行时对象都在这个区域存储,线程共享的。方法区:存储运行时代码、类变量、常量池、构造器等信息,线程共享。程…...
固态存储设备固件升级方案
1. 前言 随着数字化时代的发展,数字数据的量越来越大,相应的数据存储的需求也越来越大,存储设备产业也是蓬勃发展。存储设备产业中,发展最为迅猛的则是固态存储(Solid State Storage,SSS)。数字化时代,海量…...
Python交通标志识别基于卷积神经网络的保姆级教程(Tensorflow)
项目介绍 TensorFlow2.X 搭建卷积神经网络(CNN),实现交通标志识别。搭建的卷积神经网络是类似VGG的结构(卷积层与池化层反复堆叠,然后经过全连接层,最后用softmax映射为每个类别的概率,概率最大的即为识别…...
基于Selenium+Python的web自动化测试框架(附框架源码+项目实战)
目录 一、什么是Selenium? 二、自动化测试框架 三、自动化框架的设计和实现 四、需要改进的模块 五、总结 总结感谢每一个认真阅读我文章的人!!! 重点:配套学习资料和视频教学 一、什么是Selenium? …...
Python进阶-----高阶函数zip() 函数
目录 前言: zip() 函数简介 运作过程: 应用实例 1.有序序列结合 2.无序序列结合 3.长度不统一的情况 前言: 家人们,看到标题应该都不陌生了吧,我们都知道压缩包文件的后缀就是zip的,当然还有r…...
win10打印机拒绝访问解决方法
一直以来,在安装使用共享打印机打印一些文件的时候,会遇到错误提示:“无法访问.你可能没有权限使用网络资源。请与这台服务器的管理员联系”的问题,那为什么共享打印机拒绝访问呢?别着急,下面为大家带来相关的解决方法…...
深度学习训练营之数据增强
深度学习训练营学习内容原文链接环境介绍前置工作设置GPU加载数据创建测试集数据类型查看以及数据归一化数据增强操作使用嵌入model的方法进行数据增强模型训练结果可视化自定义数据增强查看数据增强后的图片学习内容 在深度学习当中,由于准备数据集本身是一件十分复杂的过程,…...
Tomcat安装及启动
日升时奋斗,日落时自省 目录 1、Tomcat下载 2、JDK安装及配置环境 3、Tomcat配置环境 4、启动Tomcat 5、部署演示 1、Tomcat下载 直接入主题,下载Tomcat 首先就是别下错了,直接找官方如何看是不是广告,或者造假 搜索Tomc…...
【专项训练】排序算法
排序算法 非比较类的排序,基本上就是放在一个数组里面,统计每个数出现的次序 最重要的排序是比较类排序! O(nlogn)的3个排序,必须要会!即:堆排序、快速排序、归并排序! 快速排序:分治 经典快排 def quickSort1(arr...
Android压测测试事件行为参数对照表
执行参数参数说明颗粒度指标基础参数--throttle <ms> 用于指定用户操作间的时延。 -s 随机数种子,用于指定伪随机数生成器的seed值,如果seed值相同,则产生的时间序列也相同。多用于重测、复现问题。 -v 指定输出日志的级别,…...
【观察】亚信科技:“飞轮效应”背后的数智化创新“延长线”
著名管理学家吉姆柯林斯在《从优秀到卓越》一书中提出“飞轮效应”,它指的是为了使静止的飞轮转动起来,一开始必须使很大的力气,每转一圈都很费力,但达到某一临界点后,飞轮的重力和冲力就会成为推动力的一部分…...
QT编程从入门到精通之十四:“第五章:Qt GUI应用程序设计”之“5.1 UI文件设计与运行机制”之“5.1.1 项目文件组成”
目录 第五章:Qt GUI应用程序设计 5.1 UI文件设计与运行机制 5.1.1 项目文件组成 第五章:Qt GUI应用程序设计...
(二分)730. 机器人跳跃问题
目录 题目链接 一些话 切入点 流程 套路 ac代码 题目链接 AcWing 730. 机器人跳跃问题 - AcWing 一些话 // 向上取整 mid的表示要写成l r 1 >> 1即可,向下取整 mid l r >> 1 // 这里我用了浮点二分,mid (l r) / 2,最…...
vue3使用nextTick
发现nextTick必须放在修改一个响应式数据之后,才会在onUpdated之后被调用,如果nextTick是放在所有对响应式数据修改之前,则nextTick里面的回调函数会在onBeforeUpdate方法执行前就被调用了。可是nextTick必须等到onUpdated执行完成之后执行&a…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...
Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...
Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...
