Archive for category TopCoder

TC SRM416

Posted by twcai in TopCoder on September 4, 2008

虽然一直都被虐，但真的越来越喜欢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的，递归函数代码如下：

  1. int digui(int x,int y)    //x,y分别为用二进制表示的男孩和女孩的选中情况
  2.     {
  3.         int i,j;
  4.         if(ret[x][y]!=-1) return ret[x][y];
  5.         ret[x][y]=0;
  6.         for(i=0;i<n;i++)
  7.             if(x&(1<<i)) break;
  8.         for(j=0;j<m;j++)
  9.             if(y&(1<<j))
  10.                 if(ma[i][j]==1)
  11.                     ret[x][y]+=digui(x^(1<<i),y^(1<<j));
  12.         return ret[x][y];
  13.     }

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

No Comments

SRM415

Posted by twcai in TopCoder on August 27, 2008

这是最近难得的一次早起哈，为了topcoder完全是值得的。
250分和500分的都是简单题，可惜我头脑更简单，500分那题没有注意坐标的变化，sample都思考了很久才过，等我交上去就只剩220多分了，最后一题，看了下，ms跟置换群有点类似，不过又不太一样，看懂题目后时间已经没了，思绪还都还理清，只好直接放弃了。。。
还好最后前两题都过了system test，这次估计也能涨一点点rating

No Comments

SRM413

Posted by twcai in TopCoder on August 7, 2008

第一次涨rating，主要是都是数学题，代码比较好写。
做500的时候，检查实验室的人来门口晃了一下，吓死我们，屏气吞声躲了10分钟左右。我们都是偷偷躲在实验室过夜的，寝室里没得上网了，好可怜啊~~~~
感觉这次SRM是不是TC在怜悯我这样的小菜鸟呢。。。。

No Comments

TC初次

Posted by twcai in TopCoder on July 11, 2008

初次听说TopCoder是在大一的时候去ZJU的ZJG校区听薛在岳大牛的ACM讲座，时隔那么久，我还是小菜菜一个，不过今晚和一起参加ACM的室友一起注册了TC的SRM409。
C++还没学好，250分的题目我花了20分钟左右才写好，交了一下，147.93分。
challenge phase阶段，我成功cha掉房间里最菜的250，不过又失败了两次，就收手了，呵呵
发现Topcoder很有意思

No Comments