算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
div1 A
求1~2^m-1之间选择n个数,让他们的任意连续子序列的xor和不等于0的方案数。

算法分析:
假设选择 i 个数的方案数是dp(i),那么第i+1个数只有2^m-1-i种选择。所以dp(i+1) = (2^m-1-i)*dp(i)

http://codeforces.com/contest/238/submission/2499373


div1 B
大坑。。。将一个数列A分成两组,如果A(i)和A(j)属于同一组,那么定义F(i,j)=A(i)+A(j),否这F(i,j) = A(i)+A(j)+C
现在给出A和C,求分组方案让F的最大值和最小值之差最小。

算法分析:
只有两种情况可能最优,A(0)单独一组或者A(1)...A(i)单独一组。

http://codeforces.com/contest/238/submission/2499373


div1 C
在一个有向树上找到两个点u,v。更改一些边的方向让u或v能到达所有点,且让更改数最小。

算法分析:
枚举点u,以u为根遍历。
对于两个点u,v而言。对于不在路径(u,v)上的边,必须都朝向叶子,这个可以预处理。
对于在路径(u,v)上的边,存在一个点 i,让(u,i)和(v,i)都朝向i。
这就相当于求把一个线性01序列A(0,...,n)变成00...11序列的最小代价。
这个可以用DP来解,那么放到树里面就可以用treeDP来解了。

http://codeforces.com/contest/238/submission/2501450
posted on 2012-11-05 20:25 西月弦 阅读(417) 评论(0)  编辑 收藏 引用 所属分类: 解题报告codeforces

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