## 250. TaroJiroGrid：

### Brief description:

一個 n*n 的 0/1 方陣。。被稱為 good 。。如果對於任意一列。。都不存在 > n/2 個連續相同的格子。。

。。。你可以對某行進行染色操作（全部染成白色或黑色）。。。

問至少幾次染色操作可以讓給定的 0/1 方陣 good。。。

### Analysis:

注意到最多只需要兩次（在對中間兩行染色。。）一定合法。。

........

0000

1111

........

因此只需要判斷 0 次和 1 次是否合法。。。暴力枚舉所要染色的行和染的顏色即可。

#define REP(i, n) for (int i=0;i<n;++i) #define FOR(i, a, b) for (int i=a;i<b;++i) #define REP_2(i, j, n, m) REP(i, n) REP(j, m) #define CPY(A, B) memcpy(A, B, sizeof(A)) const int N = int(1e2) + 9; int A[N][N], _A[N]; int n; bool ck(){ REP(j, n){ int c = 1; FOR(i, 1, n) if (A[i][j] != A[i-1][j]) c = 1; else if (++c > n/2) return 0; } return 1; } class TaroJiroGrid { public: int getNumber(vector <string> grid) { n = grid.size(); REP_2(i, j, n, n) A[i][j] = grid[i][j] == 'B'; if (ck()) return 0; int z = 2; REP(i, n) REP(b, 2){ CPY(_A, A[i]); REP(j, n) A[i][j] = b; if (ck()) return 1; CPY(A[i], _A); } return 2; } };

## 500. CatsOnTheLineDiv1:

### Brief description:

x-軸上分布著 n 堆貓，每堆貓的位置是 p[i]，數量是 c[i]。。。每個單位時間每隻貓可以向兩邊移動一格。

問 t 時間後，有兩隻及以上貓的位置最小時多少

### Analysis:

排序，貪心。

.。。計算出每堆貓，t 時間後可以到達的最左邊和最右邊的位置 (l, r)。。。顯然如果 c[i] > r-l+1。。那麼至少 res++。

。我們可以把這個 「匯聚」 (sink) 點放到最右側 r。。。這樣下次還遇到這類區間時。。如果 l <= r 那麼就可以不用 res++ 了。。
[cpp]
#define REP(i, n) for (int i=0;i<n;++i)
#define FOR(i, a, b) for (int i=a;i<b;++i)
#define fi first
#define se second
template<class T> inline T& checkMax(T &a,const T b){if (a<b) a=b;return a;}
const int INF = 0x3f3f3f3f;
class CatsOnTheLineDiv1 {
public:
int getNumber(vector <int> position, vector <int> count, int time) {
int n = position.size(); vector<pair<int, int> > I;
REP(i, n) I.push_back({position[i]-time, count[i]}); sort(I.begin(), I.end());
int res=0,l=-INF,sink=-INF; REP(i, n){
int ll = I[i].fi, r = I[i].fi+2*time;
if (ll <= sink) continue;
checkMax(l, ll);
if (r-l+1 >= I[i].se) l += I[i].se;
else ++res, sink = r;
}
return res;
}
};
[/cpp]

## 1000 TaroTreeRequests:

裸動態樹。