這場比賽發揮的不錯，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
西月弦 閱讀(622)
評論(0) 編輯 收藏 引用 所屬分類:
codeforces