• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

2021NOIP模拟赛【题解】

开发技术 开发技术 3小时前 2次浏览

由于大佬们都去参加了 noip,所以剩下的蒟蒻在机房做 noip 模拟赛。

本次比赛难度:个别题目为普及组难度,其余为提高组签到题(?)

无线网络发射器选址

这是一道水题,出题人娘心,暴力可过。然鹅某些打前缀和的同学没注意边界却挂”坟”了。

思路:枚举每一个点(安装地点),然后在这个点的范围内求出答案。

特别注意:范围在 ([0,128]) 以内!

代码: https://pastebin.ubuntu.com/p/YWPgVrX7wf/

子串

一看就是一道 dp 题对吧,但是就是不会做

关于状态

  • 状态一: A串第 i 位字符
  • 状态二: B串第 j 位字符
  • 状态三: 当前使用的子串数 p(注意(pleq k)
  • 状态四:(a_i) 是否能匹配得上 (b_j)
  • 还有状态五,但是这个稍作悬念,下一栏再进一步分析

关于决策

但是由于状态四的不确定性,得分两种情况

  • (a_i=b_j)

    • 决策一:使用该字符匹配
    • 决策二:不使用该字符匹配
  • (a_inot= b_j)

    只能不使用该字符匹配。由此可见,状态五便华丽丽地登场了,那就是 是否会使用该字符

    我们可以用 0 表示不使用,1 表示使用


综上所述,得出动态转移方程:

1.(a_i= b_j)

决策一:(f[i][j][p][1]=f[i-1][j-1][p][1]+f[i-1][j-1][p-1][0]+f[i-1][j-1][p-1][1])

  • 对于上述的数组解释如下

(f[i][j][p][1]): A串前i个使用了 k 个子串匹配到B串前 j 个,并且使用了当前 (a_i) 的种数

(f[i-1][j-1][p][1]): 将当前字符纳入前一个子串,并使用前一个字符的种数

(f[i-1][j-1][p-1][0]): 将当前字符纳入新子串,但不使用前一个字符的种数

(f[i-1][j-1][p-1][1]): 将当前字符纳入新子串,并使用前一个字符的种数

  • 对于上述方程的解释:

将该字符纳入前一个子串算一种情况(因为纳入前一个子串,故肯定是使用)

将该字符单独看成一个新子串算一种,而看成一个新子串,又分两种:第一种是不使用前一个字符,第二种是不使用前一个字符。(因为是新子串,所以前一个字符与当前字符是独立的,所以有两种)

决策二: (f[i][j][p][0]=f[i-1][j][p][1]+f[i-1][j][p][0])

未使用该字符,故B子串匹配数仍为 j,子串仍为 k.

未使用该字符的种数即前一个字符使用的种数+前一个字符未使用的种数(继承上一阶段的)

2.(a_inot= b_j)

(f[i][j][p][1]=0),不能使用该字符,所以为 0

(f[i][j][p][0]=f[i-1][j][p][1]+f[i-1][j][p][0]),因为不能使用该字符,所以便继承上一阶段的值


程序员灯塔
转载请注明原文链接:2021NOIP模拟赛【题解】
喜欢 (0)