算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
攒了很多没有写题解的比赛。。。 真是对不起大家。。。
以后我一定认真写博客。。。

A题
有N个演员,M个明星,(M<=N<=100)。K场电影(K<=100)。
每个电影i有演员表,可惜有Ai个演员不能确定。
最好的电影是明星最多的电影。询问每个电影是否的一定是最好的,或者一定不是最好的。或者不一定是最好的。

算法分析:
   把这个乱七八糟的逻辑搞清楚就可以了。。。
   如果一个电影取最多的明星,其他电影取最少的,这个电影还不是最多的,那么就一定不是最好的。
   如果一个电影取最少的明星,其他电影取最多的,这个电影还是最多的,那么一定是最好的。
   两个事件肯定不能同时发生,不过同时不发生,那么就是不一定。

http://codeforces.com/contest/240/submission/2365084

B题
   给N(N<100)个高度不超过100的篱笆刷颜色,颜色只有两种,A和B。
   A颜色总共最多可以刷a高度,B颜色总共可以刷b高度。

   问怎么刷才能让不同颜色的连接点的和最少。

算法分析:
   DP。。。 DP[i][j][k]表示前i个篱笆,刷了j个A颜色,如果k等于0,表示最后一个颜色是A,反之表示B,的最佳答案。
   可以向后递推,这样比较快一些。

http://codeforces.com/contest/240/submission/2368522


C题
   给N个队员,每次分成两组比赛。最后让每个人都成为过对手并且让总比赛次数最少。

算法分析:
   根据ceiling(N/2)和flooring(N/2)的方案数递推。记忆化搜索。

http://codeforces.com/contest/240/submission/2367028

D题
   给两副扑克牌,大小为10^5。有些牌正面朝上,有些反面朝上。让你制定一个方案:
      1. 保持相对顺序不变,将两个牌堆合并。
      2. 将合并后的牌堆多次翻转[1,k]区间的牌,最后使所有牌面向下。

算法分析:
   贪心翻转,合并的时候判断末尾元素。

http://codeforces.com/contest/240/submission/2377116

E题
   给一个有向图G,有些边是损毁的。问最少修复那些边能让点1到达所有边。

算法分析:
   按照完好边缩点,然后广搜一点点修边。
   对于损毁边,只加拓扑序最高的联通分量的点。
   对于完好边,正常加就可以了。

http://codeforces.com/contest/240/submission/2389254

F题
   给一个字符串,支持多次询问。对于每次询问[l,r],把子串l...r交换顺序,变成字典序最小的回文串。
   输出最后的结果。

算法分析:
   26个线段树乱搞可以刚好卡过

http://codeforces.com/contest/240/submission/2383235
posted on 2012-10-17 13:47 西月弦 阅读(597) 评论(1)  编辑 收藏 引用 所属分类: 解题报告codeforces

FeedBack:
# re: codeforces #145
2013-01-08 17:35 | 匿名
E的程序错了,4 4 1 2 1 2 3 0 3 4 1 4 2 0  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理