【牛客网 2017年校招模拟笔试(第一场)】序列和

本文主要是介绍【牛客网 2017年校招模拟笔试(第一场)】序列和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

求序列和

描述

我们要找连续的一段长度大于等于L小于等于100整数和等于N,容易观察到合法的长度范围很小,于是我们从L开始枚举,然后找到第一个输出即可。

我的代码

最初提交了一次代码，用vector保存了所有满足条件的序列，输出长度最小的，提交之后说内存超出限制，看了一眼题目，发现内存貌似是限制在2w多k？伤心，之前做题没遇到过内存还有这么严格的限制。
修改了一下，其实这个代码并没有成功提交所以不知道最终是否符合条件。仍旧是用深搜。

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
using namespace std;int a;
int sum,L;
int minLen=101;
int flag=0;
string anss;void dfs(string s, int str, int n, int len)
{if (n==0 && len<=0){if (s.size()<minLen){anss=s;flag=1;}   return ;}else if (n<0){return ;}char c=str;dfs(s+c,str+1,n-str, len-1);return ;
}int main()
{int i;scanf("%d%d",&sum,&L);int n=sum;  for(i=1; i<sum; i++)dfs("",i,n,L);int min_ind=-1;if (!flag){printf("No\n");}else{int len=anss.size();for (i=0; i<len; i++){printf("%d",anss[i]);if (i<len-1) printf(" ");}printf("\n");}return 0;
}

分析

后来看了一眼牛客网上大牛写的代码真的超级简单啊，我又想复杂了。
假定连续序列起始数为A，则长度为len的连续序列之和为(A+A+len-1)*len/2，如果令：
(A+A+len-1)*len/2=sum
则可得：A=sum-(Len-1)*len/2

贴上大牛代码如下：
作者：NotDeep
链接：https://www.nowcoder.com/discuss/21599
来源：牛客网


#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>using namespace std;vector <int> sequence(int S, int L0) {vector<int> R;for(int L = L0; L <= 100; L++) {if (S - L * (L - 1) / 2 >= 0 && (S - L * (L - 1) / 2) % L == 0) {int A = (S - L * (L - 1) / 2) / L;for (int i = 0; i < L; i++) R.push_back(A + i);return R;}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             }return R;
}
int main() {int S,L;cin >> S >> L;vector<int> ans;ans = sequence(S, L);if(ans.size() == 0) cout << "No" << endl;else {for(int i = 0; i < ans.size(); i++) {i == 0 ? cout << ans[i] : cout << " " << ans[i];}}return 0;
}