SRM 631

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:

裸動態樹。

HDU 4010. Query on The Trees

SPOJ.com - Problem DYNALCA