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),利用线段树,查找区间[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
建图,从根节点开始dfs,同时统计个数
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
我只是听人说过他们而已,还没有达到"认识"的程度。