首页 > 代码库 > SRM 631 DIV1
SRM 631 DIV1
SRM 631 DIV1
A:最多肯定只需要两步,中间的两行,一行黑,一行白就可以了,这样的话,只需要考虑一开始就满足,和枚举一行去染色满足的情况就可以了,暴力即可
B:贪心,一个记录当前有猫的位置和当前超过一只猫的位置,然后位置排序从左往右找,如果当前能移动到之前超过两只的位置,就全部移动过去,不增加,如果不行,那么考虑当前这个能不能铺成一条,如果可以,相应更新位置,如果不行,就让猫全部堆到右边右边去,然后堆数多1
代码:
A:
#include <iostream> #include <string> #include <vector> #include <set> #include <map> using namespace std; class TaroJiroGrid { public: bool judge(vector<string> 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<string> grid, int cnt) { if (cnt == 0) if (judge(grid)) return true; else if (cnt == 1) { for (int i = 0; i < grid.size(); i++) { vector<string> 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<string> grid) { for (int i = 0; i < 2; i++) { if (solve(grid, i)) return i; } return 2; } };
B:
#include <vector> #include <algorithm> using namespace std; typedef pair<int, int> pii; #define MP(a,b) make_pair(a,b) const int INF = 0x3f3f3f3f; class CatsOnTheLineDiv1 { vector<pii> g; public: int getNumber(vector<int> position, vector<int> 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; } };
SRM 631 DIV1
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。