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)

0

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

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

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

  • 楼上是大佬

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

  • 添加评论
  • reply
0

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

1

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

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

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


转发分享