【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