10.23计算思维实训题解

百忙之中抽空写一下今天计算思维题目的简略题解。如有看不懂请谅解~

Yaoge’s Simple Math Problem

  • 推公式:
    $$b_i = a_{i + 1} - a_i$$$$b_i - b_{i - 1} = (a_{i + 1} - a_i) - (a_i - a_{i - 1}) = 2c_i$$$$a_{n + 1} - a_0 = \sum_{i = 0} ^ n b_i = (n + 1)b_0 + 2\sum_{i = 1} ^ n (n - i + 1)c_i$$$$a_1 = a_0 + b_0$$

Yaoge’s Domino

  • 从左往右dp即可:
    $dp[i]$表示第$i$个骨牌最少能被几次推到,这样$dp[n]$就是要求的结果。对于每个骨牌,先从左向右更新当前骨牌能够放倒的所有骨牌,然后从右更新(更新的骨牌为能够从右向左砸到当前骨牌的牌以及能够砸到所有能被更新的骨牌的所有骨牌)。转移方程$dp[j] = min(dp[j], dp[i - 1] + 1)$

Yaoge’s Simple Shortest Path

  • 数据很小,直接用floyd求。唯一要注意的就是,只有当$dp[i][j] = dp[i][k] + dp[k][j]$时,才要在两个实际路径中取大的。不然只要更新$i→j$的最短路,实际路径是直接更新的。

The Only Principle of Yaoge

  • 水题

Yaoge’s New Skill - Teleport

  • 数据很小。对于每个点,都有$8$个转移方向,从$(0, 0)$遍历整个图即可。随便用bfs和dfs都是一样的。

Yaoge’s Simple Data Structure Problem

  • 用带权并查集维护即可。
  • 具体就是维护$l - 1$和$r$与根结点之差。两个点如果不在一个集合就将它们合并,否则就可以确定两点间的差,从而判断信息是否出现错误。
  • 注意带权并查集路径压缩和合并时候的写法即可。
捐助作者