数位翻转
计算一下 n
和 n-1
二进制下有几位不同就行了,签到题
子序列
设 A
中有 x0
个 0
和 x1
个 1
因为 A
和 B
等长,所以 B
中至少有 x0
个 0 或者至少有 x1
个 1
所以答案的下界是 min(x0,x1)
可以发现这个下界是取得到的,全 0
或者 全 1
就好了
所以输出 min(x0,x1)
就好了
三角形
考虑状态压缩 dp
,f[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
来构造就行了