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的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---