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

Posted by xiaodao
Category: TopCoder