HD2058The sum problem
2024-08-25 10:43:35
The sum problem
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 12422 Accepted Submission(s): 3757
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] 这也是一道水题,不过一开始没看懂题意,后面读了几遍就懂了。 题目给两个数N,M,要求找出从1开始到N里的子序列的和是M,并全部输出,一开始可能会想到求和公式,首项加末项乘以项数除以二,公式里有两个变量,题目告知M可以是一个很大的数,如果利用公式直接穷举去遍历所有的数的话的话会溢出,所以要换个角度去想。 考虑子串的长度为j,首项为i的数列满足要求,则(i+i+j-1)*j/2=m,==>(2*i-1+j)*j=2m,其中2*i-1>0; 所以j*j<2*m;j<sqrt(2*m);这样确定子串的长度了; 利用j和m,求出i的表达式,接下来就很简单了:#include<iostream>
#include<cmath>
using namespace std;
int main(){
int n,m,i;
while(cin>>n>>m && !(n==0 && m==0)){
int j = sqrt((double)2*m);
for(j;j>=1;j--){ //去掉douubl会在提交时显示编译错误,要声明函数重载时的类型
i =(2*m/j+1-j)/2;
if((2*i-1+j)*j/2==m)
cout<<"["<<i<<","<<i+j-1<<"]"<<endl;
}
cout<<endl;
}
return 0;
}
最新文章
- backup3
- Windows Azure Cloud Service (37) 浅谈Cloud Service
- Intent传参数
- MongoDB 副本集的相关概念【转】
- js系列(10)js的运用(二)
- C#的dll被其他程序调用时,获取此dll正确的物理路径
- CSS自学笔记(12):CSS3文字特效
- Break the Chocolate(规律)
- 2018年第一篇行动笔记:Reading Log
- HTTP 404 Not Found Error with .woff or .woff2 Font Files
- Python控制台颜色
- Java文件File类学习总结
- 为什么禁止在 foreach 循环里进行元素的 remove/add 操作
- 2018 python面试题
- SCOI2008着色方案(记忆化搜索)
- 终端设备 tty,pty,pts 概念与文件描述符的联系
- jenkins配置过程中踩过的一些坑
- 安卓下查看kmsg内核日志
- Rspec: everyday-rspec实操: 第10章测试其他功能,第11章TDD 第12章总结。
- Python编程核心内容 ---- 切片、迭代和列表生成式