蓝桥杯青少年创意编程大赛题解：求和比较

题目描述

小蓝在学习C+ +数组时，突发奇想想知道如果将一个连续的正整数数组拆分成两个子数组，然后对拆分出的两个子数组求和并做差，且差值正好等于一个固定的正整数，像这样同一连续的正整数数组拆分方案有多少种。

我们一起帮助小蓝设计一下规则：

• 第一、给出两个正整数N和M
• 第二、从1到N组成一个连续正整数数组A (A={1,2,3,4……N})
• 第三、将数组A拆分成两个子数组A1、A2：
  1. 两个子数组中不能出现相同的数
  2. 子数组中的数字可以是连续的也可以是不连续的
  3. 拆分出的两组子数组的元素个数可以不同，但总数量等于A数组元素个数
• 第四、对A1、A2两个子数组分别求和
• 第五、对A1、A2两个子数组的和做差（大的数字减去小的数字）
• 第六、如果差值正好等于固定值M，则判定此拆分方案成立。

如：N = 5, M = 1,连续正整数数组A={1, 2, 3, 4, 5}。符合条件的拆分方案有3种：

• A1={1, 2, 4}, A2={3, 5}，其中A1的和为7， A2的和为8，和的差值等于1
• A1 ={1, 3, 4}, A2={2, 5}，其中A1的和为8， A2的和为7，和的差值等于1
• A1={3, 4}, A2={1,2,5}，其中A1的和为7，A2的和为8，和的差值等于1

输入格式

分别输入两个正整数N($3<N<30$)和M($0<M<500$)，两个正整数由一个空格隔开

输入格式

输出一个正例，表示1到N (包含1和N)连续的正整数数组中有多少种方案，使得拆分的两个子数组部分和的差值等于M

输入样例

5 1

输出样例

3

算法思想1（DFS）

由于$n$的规模较小，可以暴力搜索所有方案。在搜索的过程中，对于1~n的每个数字，都有两种选择，要么加入到集合A1，要么加入到集合A2。用两个变量s1、s2分别记录集合A1、A2的和。当前分支搜索结束后，如果s1和s2的差满足要求，则方案数增加1。

代码实现1

#include 
using namespace std;
int n, m, ans;void dfs(int t, int s1, int s2)
{if(t > n){if(s1 - s2 == m) ans ++;return;}dfs(t + 1, s1 + t, s2);dfs(t + 1, s1, s2 + t);
}int main()
{cin >> n >> m;dfs(1, 0, 0);cout << ans << endl;return 0;
}

算法思想2（状态压缩，暴力枚举）

再提供一种思路，对于1~n的每个数字，要么在集合A1中，要么在集合A2中，只有两种选择。因此，可以使用状态压缩的思想，将n个数的状态看作n位的二进制串，枚举所有状态空间，选择符合条件的方案即可。

注意：该算法的时间复杂度为 O ( 2 n × n ) O(2^n\times n) O(2n×n)，所以当$n\ge 25$时，会TLE。

代码实现2

#include 
using namespace std;int main()
{int n, m, sum = 0;cin >> n >> m;for(int i = 1; i < (1 << n) - 1; i ++){int s1 = 0, s2 = 0;for(int j = 0; j < n; j ++){if((i >> j) & 1) s1 += j + 1;else s2 += j + 1;}if(s1 - s2 == m) sum ++;}cout << sum << endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！