Offer收割赛64题目简析

1
0

题解

公平划分

设这n个数的异或值为 X ,集合 B 的异或值为 Y

相当于要满足 X xor Y=Y,于是可得X=0

于是只需要判断下读入的 n 个数的异或值是否为 0,如果是 0 输出2^n-2,否则输出 0

配对

考虑状态压缩dp,令f[S][i]表示配对了前 i-1 个男生,用的女生的集合为 S 的方案数,直接转移即可。

字符串问题

考虑第二种操作每次肯定能加多长就加多长,于是只要维护串 S 的子序列自动机,每次贪心跳就行了。

公共山峰

定义f[i][j][type]表示考虑了x[1..i]y[1..j],且x[i]y[j]配对,当前山峰的类型是 type的情况的最长公共山峰长度。

朴素的转移是枚举下一个 k 是啥,然后进行转移,时间复杂度:O(n^3)

但是我们可以令g[i][j][type]=Max_{k=1}^{i}f[k][j],然后只要考虑k=i+1就行了

时间复杂度:O(n^2)

1 answer(s)

0

又想了想,发现不会啊,出来个人讲解一下

  • g[i][j][type]=Max_{k=1}^{i}f[k][j]这公式啥意思

  • 我好像知道怎么做了

  • 添加评论
  • reply

write answer 切换为英文 切换为中文


转发分享