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

External link:

Posted by xiaodao
Category: 线上比赛