题意是说给你一个数n,它可能是一些连续的整数串的和(整数最小是2),求对于每一个n,这样的串有多少个。
太年轻了,对于每一个n都去枚举串的长度,一直TLE,做了读入优化,记忆化搜索也不管用,后来看了另外一个妹子的代码才发现,应该先打一次表,但是姿势略有不同。先枚举串的长度,接着枚举串的起始点,然后用公式计算出值,在合法范围内就给该位置加一。对于每一个内循环,值超过最大值就跳出。
#include <iostream> #include <stdlib.h> #include <stdio.h> #include <string.h> #include <math.h> using namespace std; const int maxn = 1e6 + 10; int ans[maxn]; template <class T> char scanf(T *argu) { char ch = getchar(); (*argu) = 0; while(ch > '9' || ch < '0') { if(ch == EOF) return ch; ch = getchar(); } while(ch >= '0' && ch <= '9') { (*argu) *= 10; (*argu) += ch - '0'; ch = getchar(); } return ch; } void init() { memset(ans, 0, sizeof(ans)); int mt = 2 * sqrt(maxn) + 1; long long sum; for(int t = 1; t < mt; t++) { for(int x = 1; x < maxn; x++) { sum = x * t + t * (t + 1) / 2; if(sum > 1e6) break; else ans[sum]++; } } } int main() { int n; init(); while(scanf(&n) && n) printf("%d\n", ans[n]); return 0; }