某島

… : "…アッカリ~ン . .. . " .. .
April 22, 2012

TCO 2012 Round 2A

Brief description:

300: SwitchesAndLamps:
。。給定 n 組開關和燈泡,以及 m 組開關與燈泡的對應關係,(以子集的方式給出)。。
問至少再添加多少組,可以一一確定開關與燈泡的對應關係.. .
.. .( .. n, m ≤ 50 .. ) .. .

450: CucumberWatering
。。某人要按照順序經過數軸上的 n 個點 ( 有返回現象,不保證遞增)。。
。問在可以安置 m 個傳送門的情況時的最小代價。。( 經過一個傳送門可以選擇從任意一個傳送門出來。。)
.. .( .. n, m ≤ 50 .. ) .. .

1000: EvenPaths
。。給定一個 有 n 個點的 DAG 。。其中有 m 個點是可以封閉的。。
。。當從 0 出發到 1 的路徑總數是偶數的時候那麼稱之為 Nice 的。。。問 Among 這 2^m 種狀態中,有多少種是 Nice 的。。

Analysis:

這盤按照 450->300->1000 的順序。。

首先 450 出了很大的問題。。。首先我也意識到了解的離散性。。但我犯的錯誤是。。總是糾結對數軸上的 n 個點是保留排序後的,還是不排序的。。。
。。。( 但其實是兩個都要保留。。) 再之後就是對 w 數組錯誤認識。。。(。。一直認為要從每對傳送門的角度。。來鬆弛路徑導致無法書寫狀態轉移方程。。)

另外犯的錯。。在明明知道是動態規劃但是不會動態規劃的時候還去想了個貪心。。。( 居然還調對了樣例。。。但是明顯是錯的。。不願交。。Orz。)。。。其實總的說來 450 是一個比較常規的 2D/1D DP。。(。。狀態兩維, 枚舉狀態轉移 1 維。。另外 w 數組好像可以 O(n2) 預處理。。。)。。。

最後留了 25 分鐘做 300。。其實 300 想的方法其實還是比較好的。。寫了一個很優美的遞歸。。( 避免了二分圖匹配。。)。。
(。。現場生代碼 胡亂 yy 了一個對稱的位運算表達式調過了樣例居然就交了。。。)。。其實正確的方法只要判斷 count_bits(s) != count_bits(l) 就行了。。。= =。。。

const int MOD = 1000000007;
const int INF = 0x7fffffff;

const int N = 50;

inline bool _1(LL x, int i){return x & 1LL<<i;}
inline LL _1(int i){return 1LL<<i;}
inline LL _U(int i){return _1(i) - 1;};

vector <string> S, L; int n, m;
int res; bool Bad;

int count_bits(LL mask){
    int res = 0; REP(i, n) if (_1(mask, i)) ++res;
    return res;
}

void Gao(int k = 0, LL s = _U(n), LL l = _U(n)){

    if (Bad) return; if (count_bits(s) != count_bits(l)){Bad = true; return;}
    if (count_bits(s) <= 1) return;

    if (k == m) checkMax(res, count_bits(s));
    else {
        LL _s = 0, s_ = 0, _l = 0, l_ = 0; REP(i, n){
            if (S[k][i] == 'Y') _s |= _1(i);
            if (L[k][i] == 'Y') _l |= _1(i);
        }

        s_ = ~_s, l_ = ~_l;

        Gao(k + 1, s & _s, l & _l );
        Gao(k + 1, s & s_, l & l_);
    }
}

class SwitchesAndLamps {
public:
  int theMin(vector <string> switches, vector <string> lamps) {
        S = switches, L = lamps, n = SZ(L[0]), m = SZ(L);
        res = 1; Bad = false; Gao();
        return Bad ? -1 : int(ceil(log2(res)));
  }
};
const LL INF = (1LL << 60);
const int Null = -1;

struct CucumberWatering{

    vector<LL> P; vector<pair<LL, LL> > L;
    LL _F[52][51], _W[50][50]; int n;

    LL w(int l, int r){
        LL &W = _W[l][r]; if (W == Null){
            LL a = P[l], b = P[r]; W = 0; ECH(q, L) {
                LL c = q->first, d = q->second;
                if ((a <= c && c <= b) && (a <= d && d <= b)) W += min(d - c, (c - a) + (b - d));
                else if (a <= c && c <= b) W += min(c - a, b - c);
                else if (a <= d && d <= b) W += min(d - a, b - d);
            }
        }
        return W;
    }

    LL f(int l, int remK){
        LL &F = _F[l][remK]; if (F == Null){
            F = w(l, n+1);
            if (remK != 0) FOR_1(i, l+1, n)
                checkMin(F, w(l, i) + f(i, remK-1));
        }
        return F;
    }

    LL theMin(vector <int> X, int K){
        n = SZ(X); ECH(it, X) P.PB(*it); P.PB(-INF), P.PB(+INF), SRT(P);
        FOR(i, 1, n) L.PB(MP(min(X[i], X[i-1]), max(X[i], X[i-1]))); FLC(_F, _W, -1);
        return f(0, K);
    }
};

。。。。。2B 再來過吧。。。。 /$:o~o