。\省赛训练第一弹/。。。
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 这题的数据是有问题的。。||
