数列求和腾讯马拉松比赛代码,C代码库,德仔网

代码语言

代码分类

【C】数列求和腾讯马拉松比赛

作者:天朝小浪子 / 发布于2013/10/23/ 579


	给定n个数字和一个范围[x,y]，求从这n个数字中任意取出一些数字，使得它们的和在范围[x,y]中有多少种取法。
	输入：
	输入第一行为整数case，case<=10 表示有case组测试数据。
	对于每一组测试数据，第一行为一个整数n (n<=30)，第二行为n个整数a[i]，第三行为两个整数x和y。其中，a[i]>=0，sum(a[i])<2^31，0<x,y<sum(a[i])< span="">。</x,y<sum(a[i])<>
	输出：
	对于每组数据输出一行，总的取法数。
	样例输入：
	2
	3
	1 2 4
	1 7
	3
	1 2 4
	2 5
	样例输出：
	7
	4

	

	

	

	/*Sample code to read in test cases:*/
	#include <iostream>
	#include <cstdio>
	#include <cstdlib>
	#include <vector>
	#include <algorithm>

	using namespace std;

	void getSet(vector<int>::const_iterator start, vector<int>::const_iterator end, int currentSum, vector<int>& ret)
	{
	 if(currentSum)
	 ret.push_back(currentSum);
	 while(start != end)
	 {
	 getSet(start+1, end, currentSum+*start, ret);
	 start++;
	 }
	}

	int count(vector<int>::const_iterator start, vector<int>::const_iterator end, int lower, int upper)
	{
	 if(end - start <= 1)
	 if(start == end || *start < lower || *start > upper)
	 return 0;
	 else
	 return 1;
	 vector<int>::const_iterator mid = start + ((end - start) >> 1);
	 int ret = count(start, mid, lower, upper) + count(mid, end, lower, upper);
	 vector<int> leftSet, rightSet;
	 getSet(start, mid, 0, leftSet);
	 getSet(mid, end, 0, rightSet);
	 vector<int>::size_type leftSize = leftSet.size(), rightSize = rightSet.size();
	 sort(leftSet.begin(), leftSet.end());
	 sort(rightSet.begin(), rightSet.end());
	 ret += leftSize * rightSize;
	 int i = 0, j = rightSize - 1;
	 while(i < leftSize && j >= 0)
	 {
	 while(j >= 0 && leftSet[i] + rightSet[j] >= lower)
	 j--;
	 ret -= j+1;
	 i++;
	 }
	 i = leftSize - 1, j = 0;
	 while(i >= 0 && j < rightSize)
	 {
	 while(j < rightSize && leftSet[i] + rightSet[j] <= upper)
	 j++;
	 ret -= rightSize - j;
	 i--;
	 }
	 return ret;
	}

	int main()
	{
	 freopen("{sysFileUrl}", "r", stdin);
	 int om;
	 cin>>om;
	 while(om--)
	 {
	 int n;
	 cin>>n;
	 vector<int> v;
	 while(n--)
	 {
	 int tmp;
	 cin>>tmp;
	 v.push_back(tmp);
	 }
	 int lower, upper;
	 cin>>lower>>upper;
	 cout<<count(v.begin(), v.end(), lower, upper)<<endl;
	 }
	 return 0;
	}

试试其它关键字

　数列求和　

同语言下

可能有用的

天朝小浪子贡献的其它代码(1)

.数列求和腾讯马拉松比赛