某島

… : "…アッカリ~ン . .. . " .. .
April 29, 2013

North America – Greater NY 2012

。\省賽訓練第一彈/。。。
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=22824#overview

Problem D. Maximum Random Walk

Brief description:

。。一維隨機遊動系列問題,向右的概率為 r,向左的概率為 l,靜止的概率為 s。
詢問 n 步後 rightmost (歷史上的最右位置) 的期望。

Analysis:

… 比賽時只想到 O(n3) 的做法。。(dp[第i步][rightmost 位置][current 位置]。。。
。看到 n = 1000。。沒敢敲。。。賽後發現 HDU 的數據是 n = 100。。。
。。交上去發現 UVa O(n3) 也是可過的。。。

倒推。。)
我傻逼了。。順推明顯更好做一點。。)

const int N = 1009;

DB dp[2][N][2*N], l, r, s;
int n;

DB f(int n){
    int p = 0, q = 1; RST(dp[p]); dp[p][0][0+N] = 1;

    REP(i, n){
        swap(p, q); RST(dp[p]);
#define v dp[p]
#define u dp[q][j][k+N]
#define jj (j==k?j+1:j)
        FOR_1(j, 0, i) FOR_1(k, -i+2*j, j) if (u){
            v[j][k+N] += u * s;
            v[j][k-1+N] += u * l;
            v[jj][k+1+N] += u * r;
        }
    }
    swap(p, q);
    DB res = 0; REP_1(j, n) FOR_1(k, -n+2*j, j) res += u * j;
    return res;
}

Problem F. The King’s Ups and Downs

Brief description:

A001250: Number of alternating permutations of order n.
(n <= 20)

Analysis:

。。。直接分析 A000111 吧。。。
… 。。。比賽時當然是 SCDP 交了個表。。
。。。(。。然後這個序列是非常優美的。。指數生成函數就是 sec x + tan x 。。|| )。。。

—————— UPD ————————
。。。niuox 剛剛告訴我這題根本不用狀態壓縮。。直接 O(n2) DP 就好。。。。(

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1117603

F[長度][末尾] 。。末兩位遞增的方案數。。末兩位遞減的方案數可以鏡像得到。。。
。。然後在推 F[][] 的過程中之所以只需要知道末尾的數字是多少。。因為前面大於等於末尾數字的值。。都可以 +1。。然後結構不變。。

dp[i][j] 表示長度為i以j結尾的合法的排列個數(由1…i組成的排列)。
還要清楚一個結論:
給定一個長度為i-1的字元串,由{1,2,…,i}組成的合法排列數和由{1,2,…,j-1,j+1,…,i+1}
組成的合法排列數是相同的。

—————— http://blog.csdn.net/morgan_xww/article/details/6847305

。。(。。這不就是 2011 Dalian Regional Onsite 的 Problem E 么= =。。。

const int N = 22;

LL A[N], F[N][N];
int n;

int main(){

#ifndef ONLINE_JUDGE
    freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);
    //freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);
#endif

    A[1] = F[1][0] = 1; FOR_1_N(n, 2, 20){
        REP(i, n) A[n] += F[n][i] = F[n-1][n-i-1] + F[n][i-1];
        A[n] *= 2;
    }

    Rush{
        RD(Case, n);
        printf(&quot;%d %lld\n&quot;, Case, A[n]);
    }
}

Problem G. Mad Veterinarian

Brief description:

。。。給定一些物質轉換機器。。
{S1} <=> {S2}。。 ( 可以反過來用。。
。。。問從初始集合到目標集合的最短路徑長度。。並輸出方案。。(多重集。。。

Analysis:

。。。數據範圍很小。。。 bfs() 即可。。
(雖然這種題上界不好估計。。只能盡量取的大一些。。= =。。
(然後一直沒讀出來。。是要恰好達到目標集合。。還是 >= 就行。。跑出樣例才能知道。||。。。

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1112918
比賽時交了八九發。。。賽後交到 HDU 就過了。。。好像 UVa 這題的數據是有問題的。。||

External link: