http://acm.hdu.edu.cn/showproblem.php?pid=2058
Problem Description
Given a sequence 1,2,3,......N, your job is to calculate all the possible sub-sequences that the sum of the sub-sequence is M.
Input
Input contains multiple test cases. each case contains two integers N, M( 1 <= N, M <= 1000000000).input ends with N = M = 0.
Output
For each test case, print all the possible sub-sequence that its sum is M.The format is show in the sample below.print a blank line after each test case.
Sample Input
20 10
50 30
0 0
Sample Output
[1,4]
[10,10]
[4,8]
[6,9]
[9,11]
[30,30]
组内分析
初看这个问题，首先就想到求和公式，观察了一下，等差数列。所以采用等差数列求和公式，首项为1，公差d也为1.
这时未知数是项数n和首项a1通过for循环遍历算出每个a1和n 然后带入通项合公式符合等于m就输出。
遇到问题
1.超时
for循环时候便利到m太繁杂。
在观察别人代码发现别人对循环条件的优化是：
t=(int)sqrt(2.0*m);
for(j=t;j>=1;j--)//根据数列求和公式判断
后来经过讨论最后通过查阅网上资料和讨论。摘取这段讲解：
假设首项是1，我们代入，很容易得到n(n+1)=2m这个公式（n是项数）。 这里可以把n+1看成n，n^2=2m,
n=sqrt(2m); 也就是说项数最多的情况也只有sqrt(2m)。
这也就是说，假设M给的是10的9次方，最大的答案区间撑死也只有46000左右的长度。也就是2的10次的算术平方根
那么我们枚举1---sqrt(2m)，假设是长度代入到公式中。m知道了，长度知道了，那么可以解出首项，我们知道，这个数列的每一项必定是个正整数，那么如果算出来的首项正好是个正整数，那么就是个答案，
区间就是【我们算出来的整数，整数+长度-1】输出即可。
时间复杂度为n，但是n的范围大大缩小。AC。
源代码
#include<math.h>
int main()
{
int t,n,m,i,j;//i为开始的点，j为此区间的长度
while(~scanf("%d%d",&n,&m)&&(n||m))
{
t=(int)sqrt(2.0*m);
for(j=t;j>=1;j--)//根据数列求和公式判断
{
int i;
i=(2*m/j+(1-j))/2;
if(j*(2*i+j-1)==2*m)
{
printf("[%d,%d]\n",i,i+j-1);
}
}
printf("\n");
}
}
总结
1.多写代码，多从算法优化上考虑花点时间
另外附上组员看书小总结：
vector动态数组
1> 定义
include <vector>
vector<类型名> 变量名;
例：vector<int> a;
2> 常用操作
a[i] 访问第i个元素
a.empty() 判断是否为空
a.size() 返回元素个数
a.resize() 修改动态数组大小
a.push_back(x) 在动态数组尾部加一个元素
a.pop_back() 删除尾部一个元素
a.begin() 指向头部的迭代器(指针)
a.end() 指向尾部+1位置的迭代器(指针)
3> 其他操作
c.~vector() 销毁所有元素
c.insert(pos, a) 在pos处插入元素a
c.erase(a, b) 删除区间[a, b)内的元素
c.swap(c1) 交换c,c1
c.front() 返回第一个元素
c.back() 返回最后一个元素
c.capacity() 返回当前动态容量
c.max_size() 返回最大可以装的元素个数
set集合
头文件为set 构造方式为 set< string(类型) > name(变量名)
name.insert(sth) 插入元素
name.erase(sth) 就是删除元素
name.count(sth) 类似于一个询问 如果集合里有这个元素就返回true 否则返回false
遍历也是使用迭代器
for(set< string >::iterator i=name.begin();i!=name.end();i++)
cout<<*i<<" ";
name.clear()与vector里面的同理
map映射
头文件为map 构造方式为 map< string(类型) , string(类型) > team(变量名)
