Codeforces Round #125

Brief description:

Problem A. About Bacteria
… 培養皿中的 x 只細菌下一秒會繁衍出 kx+b 只細菌。。(。。。
問如果初始培養皿中有 t 只細菌,至少多少秒才可以繁衍出不少於 z 只細菌。
。。。z 為初始為一隻細菌時,繁衍 n 秒的細菌總數。。。(。。。
(略,算術題。。不要把 z 真給算出來即可。。

Problem B. Jumping on Walls
一個忍者在一個坑裡, 左右各有一面牆,牆上有一些障礙,初始在最下角。
每秒鐘可以上下移動一格,或者跳到對面牆的恰好 +k 位置。。
。。問最終能出跳出這個坑。。
(略, Hash Dp 或者 BFS() 都行。。。。

Problem C. Delivering Carcinogen
給定一顆行星坐標 (xp, yp),軌道半徑 R,圍繞恆心運轉的線速度 vp,
以及一個飛船坐標 (x, y),飛船速度 v。。問到達 p 星球的最少時間。。
。。飛船運行過程中距恆星的距離不得低於 r。。(r ≤ R) …

Problem D. Cube Snake
給定一個 n 階立方體,要求構造滿足下列性質的路徑:
對任意的 k < n, 存在至少 2 個 k 階子立方體, 滿足其中的數字取自一段連續區間。 Problem E. Gripping Story 空間中有一堆吸盤。 。。每個吸盤用 (xi, yi, mi, pi, ri) 表示。。。 。。自身坐標,重量。。。能抓起來的最大物品的重量,以及作用範圍。。。。 。。現給定飛船初始坐標。。(x0, y0)。。初始吸盤(p0, r0)... 問最多可以收集多少個吸盤。。。 (。。一旦得到一個吸盤以後以後就可以無限更換使用。。 (。。。注意注意飛船本身不動不動不動!。。並且吸盤吸到飛船里才能使用。。。OOrz。。

Analysis:

Problem C. Delivering Carcinogen
先避免討論旋轉過程。。。二分答案 x 。。然後行星 p 直接瞬移到它該出現的位置。。。然後判斷 d(p’) <= x*v .. 然後子問題 d(p') 就是構造飛船繞道這個位置的最短路徑。。根據兩條切線產生的夾角分情況討論。。( 大概有2種情況。。一種是直線。。第二種是 2 條切線 + 1段圓弧。。。

。。。先旋轉 s 點到 x 軸上。。。考慮邊界情況、把 p 點移動到距離 s 點最遠的仍可直線訪問的位置。。(稱為臨界情況。
那麼這裡的 ∠sOp 是一個重要的常數。。(p 點在更靠左位置的話就是 2條切線 + 1段圓弧的情況了。。
可以解 △pOm 和 △sOm 這兩組直角三角形得到。。。(m 是切點。。
。。(同時注意到 2條切線 + 1段圓弧情況時 2條切線 的長度固定不變,就是圖中的 pm + ms 。

(代碼中的 alpha 是初始旋轉角,beta 是臨界情況時的 ∠sOp 。。
。。 theta 是當前 p 點具體所在位置。。。delta 是扇形的弧度。。)

const int N = 100009;

Po s, p, o;
DB R_, R, r, ss, vs, vp;
DB alpha, beta, theta, delta;

inline void _R(DB &x){
    x = fmod(x, 2*PI); if (x < 0) x += 2*PI;
}

DB d(){
    if(theta <= beta || theta >= 2*PI - beta) return sqrt(sqr(R_) + sqr(R) - 2*R_*R*cos(theta));
    else{
        delta = PI - beta - fabs(PI - theta);
        return ss + delta * r;
    }
}

bool f(DB x){
    //cout << x << endl;
    theta = x * vp + alpha, _R(theta);
    return d() <= vs * x;
}


int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    p.input(), RD(vp), s.input(), RD(vs, r);

    R_ = s.length(), R = p.length(), vp /= R;
    ss = sqrt(sqr(R_) - sqr(r)) + sqrt(sqr(R) - sqr(r));
    alpha = p.atan() - s.atan(), _R(alpha);
    beta = acos(r / R_) + acos(r / R), _R(beta);

    DB ll = 0, rr = (ss + PI*R) * vs;
    REP(i, 100){
        DB m = (ll + rr) / 2;
        if (f(m)) rr = m; else ll = m;
    }
    OT(ll);
}

Problem D. Cube Snake
給定一個 n 階立方體,要求構造滿足下列性質的路徑:
對任意的 k < n, 存在至少 2 個 k 階子立方體, 滿足其中的數字取自一段連續區間。 個人認為是這套題裡面思維複雜度最高的一道。。嘛。。(雖然題目一讀就明白。。。 首先對解做一定的猜測: 。。最終解是美的。。(。。大概至少也要是遞歸的、對稱的這樣。。)。。 。。可能要奇偶討論。(。甚至更複雜的討論。。總之比較理想的構造方案可以盡量避免討論。或者討論前後共同的部分比較多。)。。 大概就是這類題的一個方向。。需要討論的地方越多。。甚至最終解不是對稱的話這類題的難度就會大大增加。。。 比較科學的方法還是歸納二維情況。。 定義紅線和藍線。分別為兩個活動端點。(一個遞增一個遞減。。 假設現在前面小於等於 k 階情況已經全部滿足,現在得到一個 k*(k+1) 的矩形,並且活動端點處在對角位置。 那麼互相向相反方向繪一段線即可得到 (k+1) 階的情況。。。、 最後到 n 以後隨便砍掉一次就能得到結果。。。 二維的代碼好像不太難實現。。0w0。 [cpp collapse="true" firstline="1" highlight="" title="我是⑨我只能理解低維世界.cpp"] const int N = 109; int A[N][N], ox, oy; int n, p, q; const int Red = 0, Blue = 1; const int Right = 0, Down = 1, Left = 2, Up = 3; void spin(int n, int c, int d){ if (c == Red){ switch (d){ case Right: REP(i, n) A[ox][oy + i] = q--; break; case Down: REP(i, n) A[ox + i][oy + n] = q--; break; case Left: DWN(i, n, 0) A[ox + n][oy + i] = q--; break; default: DWN(i, n, 0) A[ox + i][oy] = q--; } } else { switch (d){ case Right: REP(i, n) A[ox + 0][oy + i] = p++; break; case Down: REP(i, n) A[ox + i][oy + n] = p++; break; case Left: DWN(i, n, 0) A[ox + n][oy + i] = p++; break; default: DWN(i, n, 0) A[ox + i][oy] = p++; } } } void gao(){ ox = n, oy = n, q = 0; A[ox + 0][oy + 0] = 1, A[ox + 0][oy + 1] = 4; A[ox + 1][oy + 0] = 2, A[ox + 1][oy + 1] = 3; if (n == 2) return; A[ox + 0][oy + 2] = 5; A[ox + 1][oy + 2] = 6, p = 7; FOR_1(cur, 3, n){ if (cur&1) --ox; else --oy; spin(cur, Red, (Down + cur) % 4); spin(cur, Blue, (Up + cur) % 4); } } void print(){ if (n % 4 == 0) ++oy; else if (n % 4 == 1) ++ox; REP(x, n){ REP(y, n) printf("%d ", A[ox + x][oy + y] - q); puts(""); } } int main(){ #ifndef ONLINE_JUDGE //freopen("in.txt", "r", stdin); #endif while (scanf("%d", &n) != EOF && n){ if (n == 1) puts("1"); else gao(), print(); } } [/cpp] 。。。那麼從二維到三維情況稍稍複雜了一點。。。 比較值得考慮的問題是如何讓前後兩階的活動端點都處在相同的位置。。或者至少也處在同一個面彼此互換個位置。。。) (。。三維的情況如果寫腦殘的話比較難以 Debug。。我後來寫一個函數來觀察某個角度的視圖。。) [cpp collapse="true" firstline="1" highlight="" title="Problem D. Cube Snake.cpp"] const int N = 109; int A[N][N][N], ox, oy, oz; int n, p, q; void watchFront(){ n += 2; REP(i, n){ REP(j, n) printf("%d ", A[ox + i][oy][oz + j] - q); puts(""); } } void gao(){ ox = n, oy = n, q = 0; A[ox + 0][oy + 0][oz + 0] = 1, A[ox + 0][oy + 0][oz + 1] = 4; A[ox + 0][oy + 1][oz + 0] = 2, A[ox + 0][oy + 1][oz + 1] = 3; A[ox + 1][oy + 0][oz + 0] = 6, A[ox + 1][oy + 0][oz + 1] = 5; A[ox + 1][oy + 1][oz + 0] = 7, A[ox + 1][oy + 1][oz + 1] = 8; if (n == 2) return; A[ox + 2][oy + 0][oz + 0] = 11, A[ox + 2][oy + 0][oz + 1] = 12; A[ox + 2][oy + 1][oz + 0] = 10, A[ox + 2][oy + 1][oz + 1] = 9; p = 13; int x, y, z; bool rev = false; #define Blue (rev ? q-- : p++) #define Red (rev ? p++ : q--) FOR_1(cur, 3, n){ if (cur & 1){ --oy; REP(i, cur-1) A[ox][oy][oz + i] = Red; DWN(i, cur-1, 0){ if (i&1) DWN_1(j, cur-1, 1) A[ox + j][oy][oz + i] = Blue; else REP_1(j, cur-1) A[ox + j][oy][oz + i] = Blue; } x = 0, y = 0, z = cur - 1; A[ox + x][oy + y][oz + z] = Red; REP_1(i, cur - 1){ if (i&1){ ++x; --y; REP(j, i+1) A[ox + x][oy + ++y][oz + z] = Red; REP(j, i) A[ox + --x][oy + y][oz + z] = Red; } else { ++y; --x; REP(j, i+1) A[ox + ++x][oy + y][oz + z] = Red; REP(j, i) A[ox + x][oy + --y][oz + z] = Red; } } --oz; x = cur - 1, y = 0, z = 0; A[ox + x][oy + y][oz + z] = Blue; REP_1(i, cur - 1){ if (i&1){ --x; --y; REP(j, i+1) A[ox + x][oy + ++y][oz + z] = Blue; REP(j, i) A[ox + ++x][oy + y][oz + z] = Blue; } else { ++y; ++x; REP(j, i+1) A[ox + --x][oy + y][oz + z] = Blue; REP(j, i) A[ox + x][oy + --y][oz + z] = Blue; } } } else{ --oy; REP(i, cur) A[ox][oy][oz + i] = Red; DWN(i, cur, 0){ if (i&1) DWN_1(j, cur-2, 1) A[ox + j][oy][oz + i] = Blue; else REP_1(j, cur-2) A[ox + j][oy][oz + i] = Blue; } x = cur - 1, y = 0, z = 0; A[ox + x][oy + y][oz + z] = Blue; REP_1(i, cur - 1){ if (i&1){ --z; ++y; REP(j, i+1) A[ox + x][oy + y][oz + ++z] = Blue; REP(j, i) A[ox + x][oy + --y][oz + z] = Blue; } else { ++z; --y; REP(j, i+1) A[ox + x][oy + ++y][oz + z] = Blue; REP(j, i) A[ox + x][oy + y][oz + --z] = Blue; } } --ox, x = 0, y = 0, z = cur - 1; A[ox + x][oy + y][oz + z] = Red; REP_1(i, cur - 1){ if (i&1){ ++y; ++z; REP(j, i+1) A[ox + x][oy + y][oz + --z] = Red; REP(j, i) A[ox + x][oy + --y][oz + z] = Red; } else { --z; --y; REP(j, i+1) A[ox + x][oy + ++y][oz + z] = Red; REP(j, i) A[ox + x][oy + y][oz + ++z] = Red; } } rev = !rev; } rev = !rev; } } void print(){ if (n % 4 == 3) ++oz; else if (n % 4 == 0) ++ox; REP(x, n){ REP(y, n){ REP(z, n) printf("%d ", A[ox + x][oy + y][oz + z] - q); puts(""); } puts(""); } } int main(){ #ifndef ONLINE_JUDGE //freopen("in.txt", "r", stdin); #endif while (scanf("%d", &n) != EOF && n){ if (n == 1) puts("1"); else gao(), print(); } } [/cpp] Problem E. Gripping Story 。。。坐標信息在這題里沒有幾何意義的。。於是抽象以後就成了維護一堆數列的問題。。。 。。可以樹狀數組套平衡樹裸搞。。。。

Code:

A B C D E

External link:

http://codeforces.com/contest/198/room/2