Chenyao

CF Round 309 Div2

Posted at — Jun 25, 2015

趁fst前先更blog

A. Kyoya and Photobooks

题意:给你一个字符串,长度小于等于20。问在字符串中任意一个位置插入一个字母,有多少种字符串。

随便搞一下就行。

B. Ohana Cleans Up

题意:给一个01矩阵,每次可以把一整列取反,可以操作任意次,问有最多几行完全为0。

显然操作影响所有行,如果一行变为全0那么只有和这行一样的才可以全0。

C. Kyoya and Colored Balls

题意:有$k$个数字,数字$i$有$num_i$个,一个合法的排列要求最后一个数字$i$的位置一定比最后一个数字$i+1$的位置靠前。

求出来总共和为$n$,可以发现最后一个位置一定是$k$,然后把剩下$num_k - 1$扔到剩余$n-1$个位置,接着求$k-1$的答案填补进去。所以方案数为$f(k,n) = C(n-1, num_k-1) * f(k-1, n-num_k)$。

D. Kyoya and Permutation

题意:给一个1至n的排列,求出其置换表示法,接着去掉括号,如果!@%$@$#&…细节太多自己去看原题。

理解错题意了,不知道是不是div1不发通知只有div2发。可以发现符合条件的序列第$i$个位置为$i$或者与$i+1$交换,最多交换一次。递推式发现是fibonacci数列,可以类似二分的从前往后构造下去就行了。

E. Love Triangles

题意:有$n$个节点的图,任意两点有边,边的颜色可以使红色或者黑色。一些边的颜色已经给定。求满足:任意3个点构成的三角形只有1边是红色或者3条边都是红色。

看上去挺厉害,感觉自己计数题自己有点傻逼,就在那里想啊想,然后发现还是不会统计。剩15分钟的时候突然卧槽,发现自己傻逼了。

可以发现如果已知一个点与剩下所有点之间边的颜色,那么图是确定的,所以不妨记每个点颜色为与1点的边的颜色。

对于一条红边可以确定两个点颜色一定一样,对于一条黑边可以确定两个点颜色一定不一样。先用并查集把第一个连通块缩点,接着对于一条黑边在表示两个连通块之间点连边。记连通块个数为$cnt$。二分图染色,看看是否合法,如果不合法答案为0。合法的的话一个连通块颜色有两种,但是1号点所在连通块颜色固定(其实是没有颜色),所以答案为$2^{cnt-1}$。

我再讲一个有趣的故事,写完代码后发现比赛结束1分钟了→_→。