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

AtCoder Beginner Contest 216(F)

F - Max Sum Counting

链接: F - Max Sum Counting

题意

两个 大小为 nnn 的序列 aiaiaibibibi,任意选取一些下标 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)
假设和为 sumsumsummax(ai)=ajmax(ai) = ajmax(ai)=ajmaxai=akmax{ai} = akmaxai=ak 两种可能,若是不按 aiaiai 排序 会导致不知道 aj,akaj, akaj,ak 那种状态可以转移

假设 sum=10sum = 10sum=10aj=100aj = 100aj=100ak=10ak = 10ak=10 当前的 ai=10ai = 10ai=10bi=10bi = 10bi=10 那么只能从 ajajaj 转移 因为只有这种才保证 max⁡(ai)>∑bi\max(ai) > \sum{bi}max(ai)>bi 但已经把 aj,akaj, akaj,ak 的状态整合在一起了不能分开。
若是按 aiaiai 排序,新来的 aiaiai 一定是目前的最大值, 一定比 ajajajakakak 都大 于是一个状态包含的所有情况都能转移。

代码

#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 链接&#xff1a; F - Max Sum Counting 题意 两个 大小为 nnn 的序列 aiaiai 和 bibibi&#xff0c;任意选取一些下标 iii&#xff0c;求 max⁡(ai)>∑bi\max(ai) > \sum{bi}max(ai)>∑bi的方案数。 解析 首先考虑状态 一是和&#xff0c;…...

每天学一点之Stream流相关操作

StreamAPI 一、Stream特点 Stream是数据渠道&#xff0c;用于操作数据源&#xff08;集合、数组等&#xff09;所生成的元素序列。“集合讲的是数据&#xff0c;负责存储数据&#xff0c;Stream流讲的是计算&#xff0c;负责处理数据&#xff01;” 注意&#xff1a; ①Str…...

MatCap模拟光照效果实现

大家好&#xff0c;我是阿赵 之前介绍过各种光照模型的实现方法。那些光照模型的实现虽然有算法上的不同&#xff0c;但基本上都是灯光方向和法线方向的计算得出的明暗结果。 下面介绍一种叫做MatCap的模拟光照效果&#xff0c;这种方式计算非常简单&#xff0c;脱离灯光的计算…...

二十一、PG管理

一、 PG异常状态说明 1、 PG状态介绍 可以通过ceph pg stat命令查看PG当前状态&#xff0c;健康状态为“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概览:内存空间与数据存储

核心的五个部分虚拟机栈&#xff1a;局部变量中基础类型数据、对象的引用存储的位置&#xff0c;线程独立的。堆&#xff1a;大量运行时对象都在这个区域存储&#xff0c;线程共享的。方法区&#xff1a;存储运行时代码、类变量、常量池、构造器等信息&#xff0c;线程共享。程…...

固态存储设备固件升级方案

1. 前言 随着数字化时代的发展&#xff0c;数字数据的量越来越大&#xff0c;相应的数据存储的需求也越来越大&#xff0c;存储设备产业也是蓬勃发展。存储设备产业中&#xff0c;发展最为迅猛的则是固态存储(Solid State Storage&#xff0c;SSS)。数字化时代&#xff0c;海量…...

Python交通标志识别基于卷积神经网络的保姆级教程(Tensorflow)

项目介绍 TensorFlow2.X 搭建卷积神经网络&#xff08;CNN&#xff09;&#xff0c;实现交通标志识别。搭建的卷积神经网络是类似VGG的结构(卷积层与池化层反复堆叠&#xff0c;然后经过全连接层&#xff0c;最后用softmax映射为每个类别的概率&#xff0c;概率最大的即为识别…...

基于Selenium+Python的web自动化测试框架(附框架源码+项目实战)

目录 一、什么是Selenium&#xff1f; 二、自动化测试框架 三、自动化框架的设计和实现 四、需要改进的模块 五、总结 总结感谢每一个认真阅读我文章的人&#xff01;&#xff01;&#xff01; 重点&#xff1a;配套学习资料和视频教学 一、什么是Selenium&#xff1f; …...

Python进阶-----高阶函数zip() 函数

目录 前言&#xff1a; zip() 函数简介 运作过程&#xff1a; 应用实例 1.有序序列结合 2.无序序列结合 3.长度不统一的情况 前言&#xff1a; 家人们&#xff0c;看到标题应该都不陌生了吧&#xff0c;我们都知道压缩包文件的后缀就是zip的&#xff0c;当然还有r…...

win10打印机拒绝访问解决方法

一直以来,在安装使用共享打印机打印一些文件的时候&#xff0c;会遇到错误提示&#xff1a;“无法访问.你可能没有权限使用网络资源。请与这台服务器的管理员联系”的问题&#xff0c;那为什么共享打印机拒绝访问呢&#xff1f;别着急&#xff0c;下面为大家带来相关的解决方法…...

深度学习训练营之数据增强

深度学习训练营学习内容原文链接环境介绍前置工作设置GPU加载数据创建测试集数据类型查看以及数据归一化数据增强操作使用嵌入model的方法进行数据增强模型训练结果可视化自定义数据增强查看数据增强后的图片学习内容 在深度学习当中,由于准备数据集本身是一件十分复杂的过程,…...

Tomcat安装及启动

日升时奋斗&#xff0c;日落时自省 目录 1、Tomcat下载 2、JDK安装及配置环境 3、Tomcat配置环境 4、启动Tomcat 5、部署演示 1、Tomcat下载 直接入主题&#xff0c;下载Tomcat 首先就是别下错了&#xff0c;直接找官方如何看是不是广告&#xff0c;或者造假 搜索Tomc…...

【专项训练】排序算法

排序算法 非比较类的排序,基本上就是放在一个数组里面,统计每个数出现的次序 最重要的排序是比较类排序! O(nlogn)的3个排序,必须要会!即:堆排序、快速排序、归并排序! 快速排序:分治 经典快排 def quickSort1(arr...

Android压测测试事件行为参数对照表

执行参数参数说明颗粒度指标基础参数--throttle <ms> 用于指定用户操作间的时延。 -s 随机数种子&#xff0c;用于指定伪随机数生成器的seed值&#xff0c;如果seed值相同&#xff0c;则产生的时间序列也相同。多用于重测、复现问题。 -v 指定输出日志的级别&#xff0c;…...

【观察】亚信科技:“飞轮效应”背后的数智化创新“延长线”

著名管理学家吉姆柯林斯在《从优秀到卓越》一书中提出“飞轮效应”&#xff0c;它指的是为了使静止的飞轮转动起来&#xff0c;一开始必须使很大的力气&#xff0c;每转一圈都很费力&#xff0c;但达到某一临界点后&#xff0c;飞轮的重力和冲力就会成为推动力的一部分&#xf…...

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即可&#xff0c;向下取整 mid l r >> 1 // 这里我用了浮点二分&#xff0c;mid (l r) / 2&#xff0c;最…...

vue3使用nextTick

发现nextTick必须放在修改一个响应式数据之后&#xff0c;才会在onUpdated之后被调用&#xff0c;如果nextTick是放在所有对响应式数据修改之前&#xff0c;则nextTick里面的回调函数会在onBeforeUpdate方法执行前就被调用了。可是nextTick必须等到onUpdated执行完成之后执行&a…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

LOOI机器人的技术实现解析:从手势识别到边缘检测

LOOI机器人作为一款创新的AI硬件产品&#xff0c;通过将智能手机转变为具有情感交互能力的桌面机器人&#xff0c;展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家&#xff0c;我将全面解析LOOI的技术实现架构&#xff0c;特别是其手势识别、物体识别和环境…...