re: 容斥原理(翻譯) vici 2012-02-05 20:39
@forget~
Ak和Ap代表兩個不同的“xk>=9并且其他xi>=0的集合”,那么Ak與Ap的交集可以理解為“在Ak中xp>=9并且其他xi>=0的集合”,其中9個位置已被xp占用,那么最后結果就是C(7, 5)
@IwfWcf
先將邊按左端點排序(如果左端點相同再按右端點排序)。然后從小到大枚舉邊(a,b),利用線段樹,查找區(qū)間[b+1,n+1]的最大值t,再將b點賦為t+1。最后總的最大值就是結果。有點類似逆序數的求法,具體原因可以畫個圖來思考。
@mo
比如對于1 2 3 2 1序列 預處理之后得到
res[MAXN][2] = { {3,1}, {2,3}, {1,5} };
即表示>=3的最大長度為1, >=2最大長度為3, >=1最大長度為5
處理詢問時在res里二分查找x的值
代碼
http://www.ideone.com/ef3Y1
re: 容斥原理(翻譯) vici 2011-09-07 00:08
@e-maxx
I feel flattered by your rapid reply.
I knew your site through codeforces.com by chance, and then immediately I was attracted by the articles. The thoughts of the articles are very clear and clever. Therefore I was able to translate it, although it's hard to read Russian=>English translation.
And it's very religious of you to do the correction works.
re: 比賽總結12.11-12.21 vici 2011-06-14 21:17
@power
對 我這個算法錯了...我改一下
實在抱歉~暫時還沒有很好的想法
re: 比賽總結12.11-12.21 vici 2011-06-14 19:13
@power
題是一樣的 不過數據似乎有點不一樣 hust的數據弱了
re: 比賽總結12.11-12.21 vici 2011-06-14 17:32
@power
建圖,從根節(jié)點開始dfs,同時統(tǒng)計個數
void dfs(int u){
int v;
for(int i=p[u];i!=-1;i=e[i].next){
v=e[i].u;
dfs(v);
cnt[u]+=cnt[v]+1;
}
}
re: 比賽總結12.11-12.21 vici 2011-01-01 20:32
@Sosi
我只是聽人說過他們而已,還沒有達到"認識"的程度。