算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
这场比赛发挥的不错,rank 33,但是unrated。。。。 题目都很有意思,这里回忆一下

A题
数列A中有2*n-1个数,每次可以改变n个数正负,可以改变无数次,问最后数列加和最大是多少。

解法:
   找规律,n是奇数的时候,可以改变任何数量的数的正负。n是偶数的时候,只能改变偶数个数的数的正负。

代码 http://codeforces.com/contest/301/submission/3673183

B题
求不带环的最短路,图上可能有环。

解法:
   因为点数很少,所以在spfa的时候可以记录最短路的路径以避免环的出现。这样做的复杂度是O(kVE)。

代码 http://codeforces.com/contest/301/submission/3676958

D题:
给若干个区间,询问一段区间内含有多少个区间。

解法:
我的做法是F(L,R) = F(1,R) - F(1,L) - 所有经过L的区间个数。 这样需要离线做,以保证区间右端点不超过R。

http://codeforces.com/contest/301/submission/3681928

之前一直觉得树状数组没用,但是看了CLJ的做法以后,我觉得还是很有用的。。。。。。

贴一下CLJ的模板,mark一下

struct TA {
    int a[MAX_N], n;

    void init(int n) {
        this->n = n;
        memset(a, 0, sizeof a);
    }

    void upd(int p, int x) {
        for (p++; p <= n; p += p & -p)
            a[p - 1] += x;
    }

    int get(int p) {
        int r = 0;
        for (p++; p > 0; p -= p & -p)
            r += a[p - 1];
        return r;
    }
} ta;
posted on 2013-05-23 19:24 西月弦 阅读(513) 评论(0)  编辑 收藏 引用 所属分类: codeforces

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理