台湾菜

TC SRM416

twcai • topcoder

虽然一直都被虐,但真的越来越喜欢TC了,嘿嘿。
前端时间曾经感觉没做题的热情,现在也恢复嘞,加油AC!!

我参加的是DIV2区的比赛,250的题目就不说啦。

500分有些人用全排列做,其实没这个必要,找出规律简单模拟就可以了。

N先化为二进制,然后从低位往高位找第一段连续的1,比如这里有t个1(从低位到高位1…t),那么把第t个1往高位移动一位,原地址用0替代,1到(t-1)个1,移动到最低的t-1位,原位用0替代,就好了。

做掉1000分前先YM和学习了下windy大牛的代码。具体先求出1's-counting sequence,之后枚举binary weight为K的男孩和女孩数量,然后进行状态DP。我使用一个递归的过程来进行状态DP的,递归函数代码如下:
int digui(int x,int y) //x,y分别为用二进制表示的男孩和女孩的选中情况
{
int i,j;
if(ret[x][y]!=-1) return ret[x][y];
ret[x][y]=0;
for(i=0;i if(x&(1< for(j=0;j if(y&(1< if(ma[i][j]==1)
ret[x][y]+=digui(x^(1< return ret[x][y];
}

P.S. 发现SRM变成了日期的另一种形式啦,呵呵。

comments powered by Disqus