首页 > 其他分享 >加算操作

加算操作

时间:2023-05-02 16:55:49浏览次数:32  
标签:200 sum 样例 加算 序列 操作

【2022重庆市中考A卷数学选择压轴题】加算操作

题目背景

2022重庆市中考A卷数学选择压轴题。

题目描述

现定义加算操作为对于长度为 $n$ 的只含减法运算的序列 $a_1 -a_2-\cdots -a_{n-1}-a_n$,可以随意在其中两项加入一对括号,比如,对于 $a_1-a_2-a_3-a_4-a_5$,可以进行加算操作变成 $a_1-a_2-(a_3-a_4-a_5)$。

给定一个长度为 $n$ 的序列,可以进行 $m$ 次加算操作(不需要恰好进行 $m$ 次),最终可以得到多少种不同的序列和。

输入格式

第一行两个整数 $n,m$。

第二行输入 $n$ 项,代表序列中每个项的值。

输出格式

输出一行,表示最终可以得到多少种不同的序列和。

样例 #1

样例输入 #1

3 1
3 2 1

样例输出 #1

2

样例解释 #1

$3-2-1=0$

$3-(2-1)=1$

$(3-2)-1=0$

$(3-2-1)=0$

总共有2种不同的序列和 0、1。

样例 #2

样例输入 #2

4 2
3 2 1 1

样例输出 #2

3

样例 #3

样例输入 #3

4 2
3 1 2 2

样例输出 #3

3

样例 #4

样例输入 #4

4 2
-3 1 -2 2

样例输出 #4

3

样例解释 #4

总共有 3 种不同的序列和 -4、0、-8,可以经过以下操作得到:

$-3-1-(-2)-2=-4$

$-3-1-[(-2)-2]=0$

$-3-[1-(-2)]-2=-8$

提示

对于15%的数据,$1≤n≤15,-10≤a_i≤10,1≤m≤5$。

对于30%的数据,$1≤n≤40,-30≤a_i≤30,1≤m≤10$。

对于70%的数据,$1≤n≤120,-70≤a_i≤70,1≤m≤20$。

额外5%的数据,$1≤n≤200,-200≤a_i≤200,m=0$。

对于全部数据,$1≤n≤200,-200≤a_i≤200,0≤m≤50$。

加算操作题解

​ 首先需要把问题转换一下,发现除了 $a_2$ 前面的减号不可能变成加号以及 $a_1$ 前面始终是加号外,其他各项前面的符号都可以随意改变,且连续的一串加号会花费一次操作。不难设 $f_{i,j,0/1,s}$ 表示现在是第 i 位,包括第 i 位进行了 j 次操作,当前位的符号为正就是 0,为负就是 1,当前所有操作后得到的和是 s。

​ 不难得到:
$$
f_{i,j,0,s}=f_{i-1,j,0,s-a[i]}+f_{i-1,j-1,1,s-a[i]}\
f_{i,j,1,s}=f_{i-1,j,0,s+a[i]}+f_{i-1,j,1,s+a[i]}\
sum=\sum_{i=1}^n|a_i|\
ans=\sum_{i=0}m\sum_{j=-sum}f_{n,i,0,j}+f_{n,i,1,j}
$$
​ 时间复杂度为 $O(nmS)$,其中 $S=na$ ,即 $O(n^2am)$

​ 发现每一位的状态只有 0 和 1,用 bitset 压位得到最终复杂度 $O(\frac{n^2am}{w})$。

标签:200,sum,样例,加算,序列,操作
From: https://www.cnblogs.com/zengyeanbolt/p/17367898.html

相关文章

  • 21 文件六大基本操作
    文件的六大基本操作:新建、打开、关闭、读写、删除文件;辅助操作:操作根目录文件:操作文件,先要找到与该文件对应的rfsdir_t结构;get_rootdirfile_blk函数:获取根目录文件,先调用get_rootdir函数获取根目录的rfsdir_t结构,到一个缓冲区中;del_rootdir函数释放缓冲区;获取文件名:......
  • Halcon XLD 轮廓操作,轮廓交集补集
    8.1获取轨迹的图像数据 获取轮廓坐标get_contour_xld     算子:get_contour_xld(Contour ::: Row, Col)示例:get_contour_xld(Contours4,Row26,Col)Contours4(输入对象):输入轮廓对象Row26(输出控制参数1):输出轮廓的每一个点的行坐标Col(输出控制参数2):输出轮廓的每一个点的......
  • Halcon XLD 轮廓操作,轮廓交集补集
     8.1获取轨迹的图像数据 获取轮廓坐标get_contour_xld     算子:get_contour_xld(Contour ::: Row, Col)示例:get_contour_xld(Contours4,Row26,Col)Contours4(输入对象):输入轮廓对象Row26(输出控制参数1):输出轮廓的每一个点的行坐标Col(输出控制参数2):输出轮廓的......
  • IT工具知识-18: ADB操作笔记(自用)
    Linux下的常用命令(持续更新)终端使用bashshell查询安卓设备当前活动的APP包名和活动窗口名adbshelldumpsyswindowwindows|grep-E'mCurrentFocus|mFocusedApp'启动指定app下的指定窗口app包名和活动窗口名都要提供,否则无法启动adbshellamstart包名/活动窗口......
  • vue学习 第五天 css基础 --- ps操作 / 圆角边框(border-radius) / 阴影(盒子/文字)b
      ps基本操作1、ps的基本操作2、ps快捷操作的位置3、样式书写习惯 4、样式设置的小细节(注意)1、图片设置width:100%这样图片的宽度就不会超过父容器的宽度。2、块元素没有设置宽度,给margin左右是没有效果的。......
  • 考研408操作系统-5.3磁盘
    23王道书第4题第7题第11题第20题第21题第22题......
  • Java的stream操作
    Java中的stream只需告诉做什么,而不用管怎么做1.创建流1.1从数组创建流1.1.1Arrays提供String[]names={"nick","jack","michael","jone","jane"};//Arrays提供的返回流的接口Stream<String>stream=Arrays.stream(strs);查看Array......
  • C++文件读写常用操作整理
    C++对于文件的操作需要包含<fstream>头文件文件类型分为两种:文本文件-文件以文件的ASCII码的形式存储在计算机中二进制文件-文件以文本的二进制形式存储在计算机中,用户一般不能直接读懂它们操作文件的三大类:ofstream:写操作ifstream:读操作fstream:读写操作一、文......
  • 20 文件系统的格式化操作
    文件系统设备:使用4MB内存空间模拟真实的储存设备,rfsdevext_t结构表示,保存了内存空间的地址和大小;new_rfsdevext_mmblk函数分配了一个内存空间,初始化了一个rfsdevext_t结构实例化变量;该结构的地址放在了device_t结构的dev_extdata字段中;rfs_entry驱动函数放在驱动表中,文......
  • MySQL DDL表操作
    一、查询创建1、查询当前数据库所有表showtables;2、查看指定表结构desc表名;通过这条指令,我们可以查看到指定表的字段,字段的类型、是否可以为NULL,是否存在默认值等信息。3、查询指定表的建表语句showcreatetable表名;通过这条指令,主要是用来查看建表语句的,而有部分参数......