SRM 557解题报告

250:算出U和D分别有几个,然后显然应该先全U然后再histroy然后再全D。。判断一下即可。

550:求floyd传递闭包,如果f[i][i]=true那么显然选i没意义,无视掉这些点之后就是个DAG。那么就是求DAG最长反链,也就是n-最小链覆盖。

1000:我比赛的时候解方程写错了。。我是傻逼么?

注意到。。。我们实际上是要找n个互相独立的向量v1,v2,…,vn (mod 2下的向量)

他们跟输入向量A的"点积"(乘了之后xor起来)的和最大。

由于这是个拟阵,每次找一个跟之前选的向量独立的且跟A点积最大的向量就行了。

我们对A先高位到低位消一次元然后从大到小排序,

那么从i=0开始每次如果选ai更优就选,不然就不选,用解方程判断能不能选即可。

具体看我在Arena里面的代码。

这个空间最后一篇日志啦LOL。。。请岛娘帮忙开新空间xD

3 thoughts on “SRM 557解题报告

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>