topcoder

SRM div1 easy 版切！

• SRM706：MovingCandies ⭐⭐⭐
  • 题意：给一个矩阵，'#'表示可以走，'.'表示不能走，每次走可以走上下左右，现在可以移动'#'，问最少需要移动几个'#'可以从左上走到右下。
  • 题解：用vis[i][j][k][l]表示到达[i,j]点，走了k步，其中经过了l个ones。注意到k<h*w，l<n+m，这样状态就能保存下了，因为最多只需要移动n+m-1个'#'一定可以达到目的，所以对于l>n+m-1的结果没必要保存。
  • 代码：https://github.com/phonism/notes/blob/master/AlgorithmQuestions/TopCoder/SRM706_DIV1_EASY.cpp
  • Highlight：搜索的状态设计。
• SRM709：Xscoregame ⭐⭐⭐
  • 题意：给一个数组A，对于A的某个排列，执行下列操作。x初始化为0，x = (x + (x ^ a_i))，问如何排列A使得最终的x值最大，最大值是多少。
  • 题解：注意到直接状压dp不行，因为当前最大的不代表转移到下一个状态还是最大。但是考虑到数字大小最多50，操作是异或，对于超过1<<6的部分其实不会有变化，所以可以用dp[s][t]来表示状态s的时候，且结果后6位是t的最大的x是多少，然后直接转移。
  • 代码：https://github.com/phonism/notes/blob/master/AlgorithmQuestions/TopCoder/SRM709_DIV1_EASY.cpp
  • Highlight：dp的状态设计。