這場比賽發(fā)揮的不錯，rank 33，但是unrated。。。。 題目都很有意思，這里回憶一下
A題
數(shù)列A中有2*n-1個數(shù)，每次可以改變n個數(shù)正負，可以改變無數(shù)次，問最后數(shù)列加和最大是多少。
解法：
找規(guī)律，n是奇數(shù)的時候，可以改變?nèi)魏螖?shù)量的數(shù)的正負。n是偶數(shù)的時候，只能改變偶數(shù)個數(shù)的數(shù)的正負。
代碼
http://codeforces.com/contest/301/submission/3673183
B題
求不帶環(huán)的最短路，圖上可能有環(huán)。
解法：
因為點數(shù)很少，所以在spfa的時候可以記錄最短路的路徑以避免環(huán)的出現(xiàn)。這樣做的復雜度是O(kVE)。
代碼
http://codeforces.com/contest/301/submission/3676958
D題：
給若干個區(qū)間，詢問一段區(qū)間內(nèi)含有多少個區(qū)間。
解法：
我的做法是F(L,R) = F(1,R) - F(1,L) - 所有經(jīng)過L的區(qū)間個數(shù)。 這樣需要離線做，以保證區(qū)間右端點不超過R。
http://codeforces.com/contest/301/submission/3681928
之前一直覺得樹狀數(shù)組沒用，但是看了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
西月弦 閱讀(611)
評論(0) 編輯 收藏 引用 所屬分類:
codeforces