TuringJudge monthly 图灵姬月赛 2019.12【解题报告】

phython 2019-12-07 22:48:26 2019-12-09 11:42:57

参赛人数再创新低!

作为命题人,我很伤心,嘤嘤嘤。

A 环套树计数

不难看出,具有n个点n条边的环套树实际上就是一个圈。 实际上,这道题等价于对一个具有n个点的环进行黑白染色,黑色不能相邻,问有多少种染色方案。

注意到n <= 20,于是我们可以dfs,枚举每个点染成黑色或者白色,相邻不能都染成黑色,且最后一个点和第一个点不能都是黑色即可。

其实这道题是2016年提高组初赛第21题变体,对应地,这道题也有动态规划的解法,大家可以想一想,形式与斐波那契数列非常相似。

B 简单的求和

询问q的答案: ans(q) = q * a1 + (q-1) * a2 + (q-2) * a3 + ... + 1 * aq

询问q+1的答案: ans(q+1) = (q+1) * a1 + q * a2 + (q-1) * a3 + ... + 2 * aq + aq+1

我们发现ans(q+1) - ans(q) = a1 + a2 + ... + aq + aq+1 = sum(q+1)

其中sum(q)是a数组的前缀和。

由此可知,ans(q)是a数组的二阶前缀和。

O(n)预处理出a数组的二阶前缀和即可O(1)回答每个询问。

C 路径最优化

注意到,从s点到t点,要么全部步行以速度v走,要么先步行以速度v走,再中途在某个点骑上自行车,随后以2v走到终点t。

情况1:只需求出从s到t的最短路,然后用长度除以速度v。

情况2:求出从s出发到其他任意点的最短路d1,再建立反图,在反图上求出从t点出发到其他点的最短路。 枚举中间有自行车的点u,对式子(d1[u]/v + d2[u]/2v)取最小值即是答案。

D 三角形染色

这是一道较难的动态规划问题。

考虑最靠右侧两个三角形的上下边的颜色是否相等,并以此作为状态,进行转移即可。

dp[i][0]表示已经考虑了i个三角形,且第i个三角形与第(i-1)个三角形的上下边"相同",边染色方案数。

dp[i][1]表示已经考虑了i个三角形,且第i个三角形与第(i-1)个三角形的上下边"不同",边染色方案数。

那么状态转移方程可以写为:

dp[i][0] = (m-2) * dp[i-1][1]

dp[i][1] = (m-3) * (m-3) * dp[i-1][0] + (m-4) * (m-3) * dp[i-1][1]

初始化条件是:

dp[2][0] = m * (m-1) * (m-2) * (m-2)

dp[2][1] = m * (m-1) * (m-1) * (m-3) * (m-3)

最后的答案即为 dp[n][0] + dp[n][1]

专一的时候画图看一下即可,注意n = 1的情况。

这次来了就给奖

下次月赛无须提前注册,来了就行,以及,会考虑延长时间。

别划了啊来打月赛啊

共 3 条回复

FiLaReTKuN

orz

Qipeng

orz

lu_ruo_kuan

orz

AMAZE UI
Hello world!