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:
裸动态树。
