TCO Onsite rounds 2012 solutions

LOL。。。开个坑。。。

本来说要换新空间的但是在太懒了就拖一会儿吧。。。

目前已经在Arena里做完了Semi1 Semi 2 和Wildcard。。。

代码见Arena room

慢慢填吧。。。 

Semi 1:

250:我们不妨计算白色格子的数量,注意到一个联通块显然是一个矩形,如果我们确定了S[i]=T[j]=U[k]的这个字符x,那么比如说S中a1..a2是全是x,T中b1,..b2全是x,U中c1…c2全是x,那么显然这就是一个白色的长方体,同时只要a1..a2,b1..b2,c1..c2中有一个贴着边缘,那么就全最后生下来的白色格子。

分析到这里,只要枚举是S,T,U中的哪个贴边了,然后计算答案即可。

500:注意到说白了我们得到的信息pi是说i的前面是哪一个。

那么图论化一下就是说要建立一个最小字典序的pi序列使得i->pi这个图形成一个环。

显然只需要满足2点,这个问题就是有解的:

1:图中没有长度小于N的环。

2:图中没有出度和入度大于1的点。

我们只需要用个并查集维护连通性,然后注意不要违反了这两个条件一位位给pi填上去就行了。

1000:看起来很难。。。

题目的意思实际上是要求所有连续k个都在xor下线性相关。

我们不妨倒过来求"存在连续k个在xor下线性不相关"的序列的数量。 

我们注意到到实际上只需要记最后有几个数是线性不相关的就行了。

比如最后有k个数线性不相关么,那么有m-(1^k)+1种可能性新的数跟他们线性不相关

k->k+1

否则跟他们线性相关的话,实际上就是从这k个中选几个xor起来,不妨说选的最后一个是倒数第i个,

那么之后就只有i个线性不相关的数了,有2^(i-1)种可能性。

那么状态是k,用矩阵乘法加速即可。

 

5 thoughts on “TCO Onsite rounds 2012 solutions

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>