。\省賽訓練第一彈/。。。
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("in.txt", "r", stdin); //freopen("out.txt", "w", 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("%d %lld\n", 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 這題的數據是有問題的。。||