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