Offer收割赛70题目简析

1
0

数位翻转

计算一下 nn-1 二进制下有几位不同就行了,签到题

子序列

A 中有 x00x11

因为 AB 等长,所以 B 中至少有 x0 个 0 或者至少有 x11

所以答案的下界是 min(x0,x1)

可以发现这个下界是取得到的,全 0 或者 全 1 就好了

所以输出 min(x0,x1) 就好了

三角形

考虑状态压缩 dpf[S]表示用了集合 S 中的棍子,拼出最多几个三角形

转移只要枚举选哪三根木棍来拼

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

序列

考虑矩阵乘法,现在有一个向量Tx=[ a[x] … a[x+n-1] ]

我们构造一个矩阵 A 使得 Tx * A=Tx+1

这样我们只要求 T1 * A^(m-1)就行了,可以用快速幂来做

A 的构造非常简单,直接通过输入给定的 k 来构造就行了

0 answer(s)

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


转发分享