Codeforces Good Bye 2017 解题报告

Posted by


T1

http://codeforces.com/contest/908/problem/A

题意

统计一个字符串中元音字母和\(0,2,4,6,8\)的个数。

题解

……比赛的时候读题花了老半天。

代码

T2

http://codeforces.com/contest/908/problem/B

题意

给出一个迷宫和一个只有\(0\sim 3\)的数字串,将四个数字映射到四个方向(各不相同),问有多少种映射方案使得按照数字串的形式走是合法的(不走出迷宫,不走到障碍物上且能走到终点)。

题解

搜索统计答案。

代码

T3

http://codeforces.com/contest/908/problem/C

题意

有\(n\)个直径为\(r\)的圆形,依次从\((x_i,10^{100})\)的高度向\(x\)轴落下,若在下落途中与之前的某个圆形或者\(x\)轴相切则立刻停止下落,求最后每个圆心的纵坐标。

题解

\(O(n^2)\)模拟,用勾股定理计算。

代码

T4

http://codeforces.com/contest/908/problem/D

题意

给定整数\(k,p_a,p_b\)。
初始有一个空序列,每次往末尾添加一个字符,有\(\frac{p_a}{p_a+p_b}\)的概率添加\(a\),有\(\frac{p_b}{p_a+p_b}\)的概率添加\(b\)。
当\(ab\)作为子序列出现了至少\(k\)次的时候停止,问此时\(ab\)出现次数的期望。

题解

概率DP:设\(f[i][j]\)为\(a\)出现\(i\)次,\(ab\)子序列出现\(j\)次的概率。
状态转移方程:
\[f[i][j]\cdot \frac{p_a}{p_a+p_b}\Rightarrow f[i+1][j]\]
\[f[i][j]\cdot \frac{p_b}{p_a+p_b}\Rightarrow f[i][j+i]\]
当\(i+j\geq k\)时,再往串后面添加一个\(b\)就能有\(k\)个\(ab\)子序列,于是\(ans+=f[i][j]\cdot (i+j+\frac{p_a+p_b}{p_b}-1)\)。(括号里最后一项好像是级数求和……我也不会)
在子串开头无论有多少个\(b\)都没有意义,于是边界条件\(f[1][0]=1\)。

代码

T7

http://codeforces.com/contest/908/problem/G

题意

令\(S(i)\)表示将\(i\)的数位从小到大排序后形成的数。
给定整数\(n\),求\(S(1)+S(2)\ldots +S(n)\)。

题解

数位DP:设\(f[i][j][k][l]\)为确定了前\(i\)位,有\(j\)位不小于\(k\),触碰边界情况为\(l\)的方案数,\(a[1\ldots len]\)表示\(n\)的每一位,枚举当前位填数为\(t\)。
状态转移方程:
\[f[i][j][k][l]\Rightarrow f[i+1][j+(t\geq k)][k][l|(t<a[i])]\]
统计答案时枚举每一种情况,乘对应的贡献。

代码

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注