这场比赛发挥的不错，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
西月弦 阅读(595)
评论(0) 编辑 收藏 引用 所属分类:
codeforces