hihoCoder 1543-SCI表示法

---

每一个正整数都可以表示成一串连续正整数的和，比如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时循环终止。 完整代码如下： [cpp] #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; } [/cpp] 无奈，提交后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开始重新遍历，这种方法需要的遍历数其实是很少的。 完整代码如下： [cpp] #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; } [/cpp] 本代码提交AC，用时10MS。]]>