hihoCoder 1543-SCI表示法

hihoCoder 1543-SCI表示法

#1543 : SCI表示法

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

每一个正整数 N 都能表示成若干个连续正整数的和,例如10可以表示成1+2+3+4,15可以表示成4+5+6,8可以表示成8本身。我们称这种表示方法为SCI(Sum of Consecutive Integers)表示法。

小Hi发现一个整数可能有很多种SCI表示,例如15可以表示成1+2+3+4+5,4+5+6,7+8以及15本身。小Hi想知道N的所有SCI表示中,最多能包含多少个连续正整数。例如1+2+3+4+5是15包含正整数最多的表示。

输入

第一行一个整数 T,代表测试数据的组数。

以下 T 行每行一个正整数N。

对于30%的数据,1 ≤ N ≤ 1000

对于80%的数据,1 ≤ N ≤ 100000

对于100%的数据,1 ≤ T ≤ 10,1 ≤ N ≤ 1000000000

输出

对于每组数据输出N的SCI表示最多能包含多少个整数。

样例输入
2  
15  
8
样例输出
5
1

每一个正整数都可以表示成一串连续正整数的和,比如15=1+2+3+4+5,8=8(8也是一串连续正整数的和,只不过该串长度为1罢了:))。给定一个正整数N,问N最长能由多少个连续的正整数的和表示。

要使连续串的长度越长,则这些数越小越好。我们可以用滑动窗口的方法,设[i,j]的累加和为sum,则当sum>n时,++i;当sum<n时,++j;当sum==n时,len=j-i+1,更新最大长度。当j>n时循环终止。

完整代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;
typedef long long ll;
ll t, n;
int main() {
	freopen("input.txt", "r", stdin);
	scanf("%lld", &t);
	while (t--) {
		scanf("%lld", &n);
		if (n == 1 || n == 2) {
			printf("1\n");
		} else {
			ll i = 1, j = 2;
			ll sum = i + j, ans = 0;
			while (true) {
				while (j <= n && sum < n) {
					++j;
					sum += j;
				}
				if (j > n)break;
				while (i < j && sum > n) {
					sum -= i;
					++i;
				}
				if (sum == n) {
					//printf("%d\n", j - i + 1);
					ans = max(ans, j - i + 1);
					break;
				}
			}
			printf("%lld\n", ans);
		}
	}
	return 0;
}

无奈,提交后TLE,只过了80%的数据。

实在想不出哪里还可以优化了,网上搜库,发现是记录A109814,但是没有递推公式,OEIS上给出的MAPLE程序也需要现算,试了一下,还是TLE。

后来请教某大神,发现一个巧妙的优化方法。如果从1加到i的累加和是sum,如果sum<n,令left=n-sum,如果left是i的正数倍,则从1~i这i个数,每个数都加上left/i,得到的新序列也是连续的,且和正好是sum+(left/i)*i=n,所以我们得到一个长度为i的连续和是n。

举个例子,当n=14时,遍历i,当i=4时,sum=1+2+3+4=10,剩余差值为left=n-sum=4,4%i=0,此时,给每个数加上left/i=1,就变成了2+3+4+5=14=n。

所以,我们只是从1开始遍历,知道累加和大于n,并没有从2开始重新遍历,这种方法需要的遍历数其实是很少的。

完整代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;
typedef long long ll;
ll t, n;
int main() {
	freopen("input.txt", "r", stdin);
	scanf("%lld", &t);
	while (t--) {
		scanf("%lld", &n);
		if (n == 1 || n == 2) {
			printf("1\n");
		}
		else {
			ll ans = 1;
			for (ll i = 1; i < n; ++i) {
				ll sum = (1 + i)*i / 2;
				if (sum > n)break;
				ll left = sum - n;
				if (left%i == 0) {
					ans = max(ans, i);
				}
			}
			printf("%lld\n", ans);
		}
	}
	return 0;
}

本代码提交AC,用时10MS。

Leave a Reply

Your email address will not be published. Required fields are marked *