程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> SRM 631 DIV1

SRM 631 DIV1

編輯：C++入門知識

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;
		}
};