hihoCoder Challenge 30题解

0
1

最短的 Nore0061

用 dp[i][j][k] 表示 S 枚举到 i，第一个串匹配到 j，第二个串匹配到 k 时最晚开始能是哪个位置。转移 O(1)，复杂度 O(|S||A||B|)。

四次方根

记 f(n) 为所求结果，则我们有：

f(n + 1) = - f(n) * a - f(n - 1) * b - f(n - 2) * c - f(n - 3) * d

利用递推式矩阵加速即可，复杂度 O(logN)。注意下边界的 f(0)，f(1)，f(2)，f(3) 要特别处理下。

躲闪鱼雷

计算几何题。考虑船运行的角度，容易发现，会撞到某个鱼雷的角度是连续的一（或二）段，于是算出所有非法角度取个并看下是否是全集即可。

Toffoli 门

注意下，如果记 T(a, b, c) = (a, b, (a & b) ^ c)。

则我们有T(T(a, b, c)) = (a, b, c)。

于是题目最后的要求就可以将运算反过来即可。

下面给出一些运算符的构造：

a & b   ->      T(a, b, 0) = (a, b, a & b)  
~ a     ->      T(a, 1, 0) = (a, 1, ~a)  
a ^ b   ->      T(a, 1, b) = (a, 1, a ^ b)  
a | b   ->      ~T(~a, ~b,0) = T(T(T(a, 1, 0), T(b, 1, 0), 0), 1, 0)

3 answer(s)

1

update:
根据大佬的提示，一元四次方程与系数的关系，可得。。。

f(0) = 4
f(1) = -a
f(2) = a^2 - 2*b
f(3) = f(2)*f(1) + b*a  - 3*c
0

A直接暴力不行么？求个样例QAQ

0

比练习赛难好多QAQ
第二题的f(0)...f(3)需要求出4个根吗，卡这了，不会求这四个值。

  • 一元四次方程根与系数的关系...

  • f（0）=4，f（1）=x1+x2+x3+x4,f(2)=x1^2+.....以此类推，所以还是要求四个解= =

  • 楼上是大佬

  • 一元四次方程根与系数的关系也是必须要掌握的嘛。。。

  • 添加评论
  • ✖reply

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

转发分享

▲