某島

… : "…アッカリ~ン . .. . " .. .
September 7, 2013

SRM 508

250. DivideAndShift

Brief description:

。。求滿足以下遞歸關係的某函數的值。。
f(n, 0) = 1
f(n, m) = f(n, m%n)
f(n, m) = min(f(n, m-1), f(n, m+1), f(n/d, m%(n/d))

Analysis:

。。顯然放縮總是安排在滾動的前面比較科學。。。於是枚舉約數就行了。。放縮次數等於素因子個數。。

int fact(int x){
    int z = 0; REP(i, SZ(P)){
        while (x % P[i] == 0) ++z, x /= P[i];
        if (x == 1) break;
    }
    if (x != 1) ++z;
    return z;
}

class DivideAndShift {
public:
	int getLeast(int n, int m) {
        sieve(); --m; int res = INF; REP_1(d, n) if (n % d == 0){
            int nn = n / d, mm = m % nn;
            checkMin(res, fact(d) + min(mm, nn-mm));
        }
        return res;
	}
};

500. YetAnotherORProblem

Brief description:

。給定一個長度為 n 的數組 a[]。。求有多少滿足條件的數組 b[]。。使得。。b[i] <= a[i]。。。且 b 的和等於位或。。

Analysis:

。。和等於位或。。顯然就是每個位上至多有一個一。。於是顯然和某題一樣。。可以從高位到低位 DP。。。
dp[k][s]: 表示當前第 k 位。。s 表示當前已經不受限制的集合。。。枚舉 0 和 恰好有一個 1 這兩種決策。記憶化搜索即可。。。

const int N = 10;
int dp[61][1&lt;&lt;N]; vector&lt;long long&gt; R;
int n;

int f(int k, int s){

    if (k &lt; 0) return 1;

    int &amp;res = dp[k][s]; if (res == -1){
        int ss = s; REP(i, n) if (_1(R[i], k)) ss |= _1(i);
        res = f(k-1, ss); // 0 .. .

        REP(i, n) if (_1(s, i) || _1(R[i], k)){ // 1 .. .
            int ss = s; REP(j, n) if (j != i &amp;&amp; _1(R[j], k)) ss |= _1(j);
            INC(res, f(k-1, ss));
        }
    }
    return res;
}

class YetAnotherORProblem {
public:
	int countSequences(vector&lt;long long&gt; R){
	    ::R = R; n = SZ(R); FLC(dp, -1);
		return f(60, 0);
	}
};

1000. BarbarianInvasion2

Brief description:

。。一個 n 個點的凸包內部分布著 m 個點。。。要求將凸包的輪廓分割成等長的 m 段測度。。(。注意每段不要求在邊界上連續分布。。)。。。將這些測度和內部的點做匹配。。。最小化最遠的測度到點的距離。。。(m = 5)

Analysis:

。。首先二分答案。。

。。顯然對凸包上的每一條邊。。我們需要做線段和圓求交。。然後掃描線。。搞出每個小段可以從屬的圓的集合。。。
。。之後要判斷合法。。實際上就得到了一個完備匹配的問題。。。似乎可以跑網路流。。但是困難之處在於。。此題中的容量不是整數。。。。
。。注意到。m 非常小。。而且我們只要判斷完備匹配的存在性。。所以可以暴力使用 Hall’s marriage theorem。。。

const int M = 5;
VP B; Po C[M]; DB T; DB S[1&lt;&lt;M];
int n, m;

bool f(DB r){

    RST(S); REP(i, n){

        Seg l(B[i], B[i+1]); DB ln = l.len(); vector&lt;DB&gt; D; D.PB(0), D.PB(ln);

        REP(j, m){

            Circle c(C[j], r); if (!~c.sgn(l)) continue;
            Po p0, p1; VP P = c*l; ECH(p, P) D.PB(dist(*p, B[i]));

            /*DB b= 2*dot(B[i]-C[j],l.d()._1()), c = (B[i]-C[j]).len2() - sqr(r);
            DB d = sqr(b) - 4*c; if (d &lt; 0) continue;
            d=sqrt(d); DB d0 = (-b-d)/2, d1 = (-b+d)/2;
            if (0&lt;d0&amp;&amp;d0&lt;ln) D.PB(d0); if (0&lt;d1&amp;&amp;d1&lt;ln) D.PB(d1);*/
        }

        SRT(D); FOR(j, 1, SZ(D)){
            Po p = l.a + l.d()._1()*(D[j]+D[j-1])/2;
            int s = 0; REP(k, m) if (~sgn(r*r, dist2(p, C[k]))) s |= _1(k);
            S[s] += D[j] - D[j-1];
        }
    }

    FOR(s, 1, _1(m)){
        DB p = 0, q = T * count_bits(s);
        FOR(ss, 1, _1(m)) if (s &amp; ss) p += S[ss];
        if (sgn(p, q) &lt; 0) return 0;
    }
    return 1;
}

class BarbarianInvasion2 {
public:
	double minimumTime(vector &lt;int&gt; bX, vector &lt;int&gt; bY, vector &lt;int&gt; cX, vector &lt;int&gt; cY) {

	    n = SZ(bX), m = SZ(cX); B.resize(n+1);
	    REP(i, n) B[i] = Po(bX[i], bY[i]); B[n] = B[0]; T = getPeri(B) / m;
	    REP(i, m) C[i] = Po(cX[i], cY[i]);

		DB l = 0, r = 1e5; DO(233){
		    DB m = (l+r) / 2;
		    if (f(m)) r = m;
		    else l = m;
		}
		return l;
	}
};

External link:

https://apps.topcoder.com/wiki/display/tc/SRM+508
https://gist.github.com/lychees/6475006
www.cnblogs.com/zbwmqlw/archive/2011/06/03/2070534.html