弱菜只能围观了。。）。。

250. SimilarSequences

Brief description:

… 两个序列被认为是相似的，当前仅当从两个序列中各删除一个元素后相等。（这里相等指相同位置上的元素相同。。
。。给定长度为 n 的初始序列 A 和上界 up。。。。问存在多少序列与之相似。。（每个元素取自 [1, up]…
( n <= 40 .. )

Analysis:

… 暴力美学。。。。
。枚举 A 序列中删除的元素。。再枚举要补上的元素位置。（用 -1 标记之。。）。。把这个 token 放进 set 里。。记之 h。。
那么答案就是 SZ(h) * up ？。。。

。。。。明显这样会重复计数。。。

。。。因此我们用 SI B(ALL(A)) 记录 A 数组中出现过的元素。。。
。。再建一个 set 。h2。（之前的现在记作 h1。。
。。用以保存那些所有可能会被重复计数的 token 。。(既在 h1 中原先用 -1标记的那个位置。。现在依次用 B 中的元素填上。。。

那么总的答案就是 SZ(h1) * (up - SZ(B)) + SZ(h2)。。。

//}/* .................................................................................................................................. */

class SimilarSequences {
public:
	int count(vector <int> A, int up) {

	    SI B(ALL(A)); set<VI> h1, h2; int n = SZ(A); REP(i, n){
	        VI AA = A; ERS(AA, i); REP(j, n){
	            INS(AA, j, -1); h1.insert(AA);
	            ECH(it, B) AA[j] = *it, h2.insert(AA);
	            ERS(AA, j);
	        }
	    }

	    return sum(pdt(SZ(h1), (up - SZ(B))), SZ(h2));
	}
};

450. AntlerSwapping

Brief description:

。。一对数被称为是平衡的。。如果它们的差 ＜ 给定的 cap。
… 给定 n 对数。。问至少多少次交换可以使它们全部平衡。。（交换在某对数的任意一项和另一对数的任意一项之间进行。。。
..( n <= 16 .. )

Analysis:

。。很容易想偏。。。但是这个数据范围的话似乎应该是 SCDP？。。。

dp[s] 表示只考虑 s 集合中的数对的话。。要让他们平衡至少需要几次交换。
那么显然有…

..
	        REP_SS(i, s) checkMin(dp[s], dp[i] + dp[s^i]);
..

这里 REP_SS 是枚举子集。。（参见 [技巧]枚举子集的飘逸写法 by 柯神小天使

。。。考虑赋初值。。

。。对于单元素集合。。那么如果这两个元素的差 < cap 那么显然代价是 0 否则是无穷大。。。 。。对于双元素集合。。如果可以凑成 2 对的话。。。那么初值设为 1 次。。（。。当然也有可能是 0 次。。0 次的话将会由上面的转移得到。。。。 。。一般的。。对于 n 个元素的集合。。如果可以凑成 n 对的话。。那么初值设为 n-1。。（至少可以通过 n-1 次交换使之平衡。。。 [cpp collapse="false" firstline="1" highlight=""] //}/* .................................................................................................................................. */ int dp[1<<16]; int n; class AntlerSwapping { public: int getmin(vector <int> L, vector <int> R, int C) { n = SZ(L); FLC(dp, 0x3f); REP_1(s, _U(n)){ VI A; REP(i, n) if (_1(s, i)) A.PB(L[i]), A.PB(R[i]); SRT(A); int j; REP_N(j, SZ(A)){ if (A[j+1] - A[j] > C) break; ++j; } if (j == SZ(A)) dp[s] = count_bits(s) - 1; REP_SS(i, s) checkMin(dp[s], dp[i] + dp[s^i]); } return dp[_U(n)] == INF ? -1 : dp[_U(n)]; } }; [/cpp]

1000. ToastJumping

Brief description:

。。问从 (0, 0) 跳到 (x, y) 至少需要跳几步。。。
。。。跳跃只能在整点之间进行。。且每次跳跃的 欧几里得距离^2 不得超过 d。。
…

Analysis:

.. 一图流。。。

。。。k 步后的可达区域是凸的。。而且就是 1 步可达区域的那个凸包每个点乘以 k。。。因此算法就是构造出最里层的那个凸包。。然后枚举每条边。。checkMax 。。
。。实际根据对称性。。。构造出第一象限的一半就够了。。

const int N = 50;
VP P;

int f(int x0, int y0, int dd){
    if (!x0 && !y0) return 0;

    LL t = sqr((LL)x0)+sqr((LL)y0);

    CLR(P); int d = sqrt(dd), y = d, x = 0;
#define xx sqr(x)
#define yy sqr(y)
    while(1){
        while (xx+yy>dd) --y; Po p(x, y);
        while (SZ(P)>=2 && dett(P[SZ(P)-2], P.back(), p) >= 0) P.pop_back();
        P.PB(p); if (x>=y) break; ++x;
    }

    x0 = abs(x0), y0 = abs(y0); if (x0 > y0) swap(x0, y0);

    int k = 0; Po p0(x0, y0); FOR(i, 1, SZ(P)){
        Po p1(P[i]-P[i-1]); LL p = det(p1, p0), q = det(p1, P[i-1]);
        //cout << p << " " << q << endl;
        checkMax(k, int(ceil(p, q)));
    }

    return k;
}

class ToastJumping {
public:
    vector <int> minJumps(vector <int> x, vector <int> y, vector <int> d){
        VI res; int n = SZ(x); REP(i, n) res.PB(f(x[i], y[i], d[i]));
        return res;
    }
};

External link:

https://apps.topcoder.com/wiki/display/tc/TCO+2013+Round+3B
https://gist.github.com/lychees/5843231

Posted by xiaodao
Category: TopCoder
Tags: 凸包, 暴力美学