SRM 631 DIV1

A：最多肯定只需要两步，中间的两行，一行黑，一行白就可以了，这样的话，只需要考虑一开始就满足，和枚举一行去染色满足的情况就可以了，暴力即可

B：贪心，一个记录当前有猫的位置和当前超过一只猫的位置，然后位置排序从左往右找，如果当前能移动到之前超过两只的位置，就全部移动过去，不增加，如果不行，那么考虑当前这个能不能铺成一条，如果可以，相应更新位置，如果不行，就让猫全部堆到右边右边去，然后堆数多1

代码：

A：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
       using namespace std; class TaroJiroGrid { public: bool judge(vector
       
         grid) { for (int i = 0; i < grid.size(); i++) { int cnt = 1; for (int j = 1; j < grid.size(); j++) { if (grid[j][i] == grid[j - 1][i]) { cnt++; } else { if (cnt > grid.size() / 2) return false; cnt = 1; } } if (cnt > grid.size() / 2) return false; } return true; } bool solve(vector
        
          grid, int cnt) { if (cnt == 0) if (judge(grid)) return true; else if (cnt == 1) { for (int i = 0; i < grid.size(); i++) { vector
         
           tmp = grid; for (int j = 0; j < grid[i].length(); j++) tmp[i][j] = 'B'; if (judge(tmp)) return true; tmp = grid; for (int j = 0; j < grid[i].length(); j++) tmp[i][j] = 'W'; if (judge(tmp)) return true; } } return false; } int getNumber(vector
          
            grid) { for (int i = 0; i < 2; i++) { if (solve(grid, i)) return i; } return 2; } };

B：

#include 
  
   
#include 
   
     using namespace std; typedef pair
    
      pii; #define MP(a,b) make_pair(a,b) const int INF = 0x3f3f3f3f; class CatsOnTheLineDiv1 { vector
     
       g; public: int getNumber(vector
      
        position, vector
       
         count, int time) { int n = position.size(); for (int i = 0; i < n; i++) g.push_back(MP(position[i] - time, count[i])); sort(g.begin(), g.end()); int le = -INF, sink = -INF, ans = 0; for (int i = 0; i < n; i++) { int l = g[i].first; int r = l + 2 * time; if (l <= sink) continue; le = max(le, l); if (r - l + 1 < count[i]) { ans++; sink = r; } else { le += count[i]; } } return ans; } };


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：HDU 1260 Tickets（简单DP）	下一篇：[ACM] hdu 3037 Saving Beans (Lu..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: