。\省賽訓練第一彈/。。。
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 這題的數據是有問題的。。||
