TOJ 2236 Partial Sums 解题

组合数学问题
处理之前先对整个队列求一个和；
然后对每一个部分和统计一下
 1#include <stdio.h>
 2#include <string.h>
 3
 4int seq[100100];
 5int md[6000];
 6
 7long long jx(long long x) {
 8    return x*(x+1)/2;
 9}
10int main() {
11    int n, l, u;
12    int i;
13    int sum, m;
14    long long res, now, best;
15
16    while(scanf("%d%d%d", &n, &l, &u)!=EOF) {
17        for(i=0; i<n; i++) {
18            scanf("%d", &seq[i]);
19        }
20        best = (long long)-1;
21        for(m=l; m<=u; m++) {
22            memset(md, 0, sizeof(md));
23            md[0] = 1;
24            sum = 0;
25            for(i=0; i<n; i++) {
26                sum = (sum+seq[i])%m;
27                md[sum] ++;
28            }
29            now = 0;
30            for(i=0; i<m; i++) {
31                now += jx((long long)(md[i]-1));
32            }
33            //printf("%d: %I64d\n", m, now);
34            if(now > best) {
35                best = now;
36                res = m;
37            }
38        }
39        printf("%d\n", res);
40    }
41    return 0;
42}
43
44

posted on 2008-07-15 19:24 gong 阅读(182) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理


<2008年7月>
日一二三四五六
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789

导航

统计

常用链接

留言簿(6)

随笔档案

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜