欢迎来到Doc100.Net免费学习资源知识分享平台!
您的位置:首页 > 程序异常 >

chinese dialects_小结

更新时间: 2014-05-16 10:37:39 责任编辑: Author_N5

 

Chinese Dialects__总结

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=34629#problem/D

http://acm.timus.ru/problem.aspx?space=1&num=1964

看到这道题的时候,题目已经被贴上了容斥的标签。自己就什么都不管,一头扎到那个方向,自己最后还想出来了一个看似正确的想法,可笑至极。。。。

我的想法:分奇偶的情况,奇数:n = ∩(1) - ∩(2) + ∩(3) + ..... +∩(k)此时∩(1)>=n,式子可以分开成若干项相加,那么除过∩(n)之外的项尽可能的大。

---------华丽的分割线--------之后开始脑残。。。。。

认为∩(n+1)与∩(n)存在一个限制关系。。。。然后就一直陷入死循环,WA了两次之后才觉得应该是想的不对


这个时候应该换一种思路的,直到最后队友A了这个题,我好想也不太明白∩(n+1)与∩(n)的限制关系 (除了>=关系之外)


缅怀一下这个奇葩的思路。

容斥是考虑了多个集合相交的情况,使得问题变得更加复杂(我是这样觉得的),如果不是题目中明确告诉了多个集合相交的情况,尽量避免将题目的问题考虑成互相有影响的情况。还是按照通常的思路,将题目分解。

以后做题应该多注意思路的灵活性,不要总是一直纠结一个思路,思路还是太弱了。。。。

明显可以知道这个题目不难,已经很多人秒了的,就应该能大概估计出来这个题目的程度。。。还是需要灵活。。。。


此题目有两种解法:

1.贪心 -->   不妨设会Ki种语言的人有Xi人,那么sum = sigma(Ki * Xi ) 此时考虑一下对于会k-1种语言的人儿,他的系数除了k意外是最大的,如果都是会k-1种语言的人,即此时的人数为n * (k - 1),此时是没有会k种语言人时候总人数最多的时候,若仍小于sum,那么必然要有会k种语言的人;若直接大于sum,那么一定不用有会k种语言的人;

这个思路还是比较简单的,不用数学什么原理


2.类似小容斥+贪心 --->  每次考虑前两个种类的人,贪心一下,假如至少会前两个语言的人最少,那么结果也会减少。也就是 a[0] + a[1] - a[0] ∪ a[1]最小,即a[0] ∪ a[1] 最大,最大的情况就是总人数,那么一直贪心即可

上一篇:上一篇
下一篇:下一篇

 

随机推荐程序问答结果

 

 

如对文章有任何疑问请提交到问题反馈,或者您对内容不满意,请您反馈给我们DOC100.NET论坛发贴求解。
DOC100.NET资源网,机器学习分类整理更新日期::2014-05-16 10:37:39
如需转载,请注明文章出处和来源网址:http://www.doc100.net/bugs/t/605272/
本文WWW.DOC100.NET DOC100.NET版权所有。