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…...
传统图像处理之颜色特征
博主简介 博主是一名大二学生,主攻人工智能研究。感谢让我们在CSDN相遇,博主致力于在这里分享关于人工智能,c,Python,爬虫等方面知识的分享。 如果有需要的小伙伴可以关注博主,博主会继续更新的,…...
GPS问题调试—MobileLog中有关GPS关键LOG的释义
GPS问题调试—MobileLog中有关GPS关键LOG的释义 [DESCRIPTION] 在mobile log中,有很多GPS相关的log出现在main log和kernel log、properties文件中,他们的意思是什么,通过这篇文档进行总结,以便在处理GPS 问题时,能够根据这些log快速的收敛问题。 [SOLUTION] 特别先提醒…...
【企业管理】你真的理解向下管理吗?
导读:拜读陈老师一篇文章《不会向下负责,你凭什么做管理者?》,引发不少共鸣,“很多管理者有一种错误的观念,认为管理是向下管理,向上负责。其实应该反过来,是向上管理,向…...
Centos7 硬盘挂载流程
1、添加硬盘到Linux,添加后重启系统2、查看添加的硬盘,lsblksdb 8:16020G 0disk3、分区fdisk /dev/sdbmnw其余默认,直接回车再次查看分区情况,lsblksdb1 8:17 0 20G 0 part4、格式化mkfs -t ext4 /dev/sdb15、挂载mkdir /home/new…...
认识vite_vue3 初始化项目到打包
从0到1创建vite_vue3的项目背景效果vite介绍(对比和vuecli的区别)使用npm创建vitevitevuie3创建安装antdesignvite自动按需引入(vite亮点)请求代理proxy打包背景 vue2在使用过程中对象的响应式不好用新增属性的使用$set才能实现效…...
【Go】cron时间格式
【Go】cron时间格式 Minutes:分钟,取值范围[0-59],支持特殊字符* / , -;Hours:小时,取值范围[0-23],支持特殊字符* / , -;Day of month:每月的第几天,取值范…...
leetcode 55. 跳跃游戏
给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。 示例 1: 输入:nums [2,3,1,1,4] 输出:true 解释:可以先跳 1 …...
Linux:文件流指针 与 文件描述符
目录一、文件描述符二、文件流指针三、缓冲区之前讲解过了IO库函数和IO接口,库函数是对系统调用接口的封装,也就是说实际上在库函数内部是通过调用系统调用接口来完成最终功能的。 库函数通过文件流指针操作文件,系统调用接口通过文件描述符操…...
基于FPGA实现正弦插值算法
1、正弦插值的算法分析 1.1 信号在时域与频域的映射关系 在进行正弦算法分析之前,我们回顾一下《数字信号处理》课程中,对于信号在时域与频域之间的映射关系,如下图。 对于上图中的原始信号x(t),使用ADC对信号进行采样࿰…...
JavaWeb_会话技术
文章目录会话跟踪技术的概述Cookie概念Cookie工作流程Cookie基本使用发送Cookie获取CookieCookie原理分析Cookie的使用细节Cookie的存活时间Cookie存储中文SessionSession的基本使用概念工作流程Session的基本使用Session的原理分析Session的使用细节Session的钝化与活化Sessio…...
深圳宝安网站设计/抖音seo排名系统
什么是电子邮箱电子邮箱(简称:Email)是一种具有存储和收发电子信息功能的网络通信工具,可以为为用户传送文字、图片、语音、附件等各类型的信息,也可以自动接收网络任何电子邮箱所发的电子邮件并能存储多种格式的电子文件。最主要的是邮箱可以…...
做销售网站/网络营销文案实例
距离上次书写面试经验,现在已经有二个月了。也是该写写的时候了。在这两个月中发生了太多的事情,自己也成长了不少,得到了的同时也伴随着失去。10月份我去了广东省中山市东区的一所小学实习。因为它们的区教育局过来招聘,刚好我面…...
东莞做网站多少钱/搜索引擎营销原理
💥 项目专栏:【Pandas数据处理100例目录】Python数据分析玩转Excel表格数据 前言 大家好,我是阿光。 本专栏整理了《Pandas数据分析处理》,内包含了各种常见的数据处理,以及Pandas内置函数的使用方法,帮助我们快速便捷的处理表格数据。 正在更新中~ ✨ 🚨 我的项目…...
三层别墅设计图片大全 效果图/济南专业seo推广公司
在centos7的容器里面出现了一个BUG,就是serveice启动服务的时候出现报错,不能用service启动服务。[roote13c3d3802d0 /]# service httpd startRedirecting to /bin/systemctl start httpd.serviceFailed to get D-Bus connection: Operation not permit…...
保定百度网站建设/百度怎么优化网站排名
很抱歉,我并不会多功能电子钟的 VHDL 代码,因为我是一个计算机程序,我只能通过您提供的信息来回答问题。如果您有具体的问题需要我帮助,我会尽力回答。同时,您也可以尝试搜索网络,或者请求帮助来自专业人士…...
网站制作模板网站/seo助手
目录 xlrd模块 打开.xls格式的文档 获取.xls文档的列 打印第一行的数据 打印所有数据...