kickstart 18 roundB Sherlock and the Bit Strings(状压dp/计数)

[TOC]

题目链接

kickstart 18 roundB Sherlock and the Bit Strings

大意

寻找一个长度为 $n$ 的字符串,满足以下条件:

  1. 满足 $k$ 个条件: $\sum_{j=A_i}^{B_i}s_j=C_i,i\in {1,2,\dots,k}$
  2. 并且是字典序第 $p$ 大

分析

因为small所满足的限制是 $A_i=B_i$,
所以,
small 有一个非常简单的做法:

将所有的 $A_i$ 固定住,那么剩余位置第 $p$ 大 就相当于是求 $p-1$ 的二进制表示。

不过,这种做法有一个缺点就是无法扩展到 large 的情况。

因此我们直接分析 large:

首先 $B_i -A_i \le15$, 也就是说对于任意一个 position $i$, 我们如果知道他的前 $16$ 位字符,那么我们一定能判断到目前为止位置 $i$ 是否 valid 因此一个简单的做法就是我们对于 位置 $i$ 枚举所有的 $2^{16}$ 种情况,计算以这种前缀在 $i$ 结尾的种类的个数(显然,前缀相同种类数一定是相同的),即计算 $dp[prf][i]$,在 i位,包含 $i$,前缀状态是 $prf$ 的种类个数

状态转移

接下来我么你来看状态转移:

$dp[prf][i] = \sum dp[left_shift(prf)and\ append 0][i+1]+dp[left_shift(prf)and\ append 1][i+1]$

对于每一个位置 $i$ 我们 check 所有 $B_j=i$ 的条件,如果有一个不满足,那么 $dp[prf][i]=0$

构造解

构造解的过程很简单,如果 dp[prf][i],如果 prf&1==0,即第 i位为 $0$ 的状态 $\ge p$ 种,那么显然这一位取 $0$, 否则取 $1$,

如果第 $i$ 位取的是 $1$, 那么我们后续计算的时候应该用 $p-dp[prf][i]$,即减去所有 $i$ 位为0 的情况总数

code

github

总结小技巧

builtin_popcount 这个函数能很快的在位级计算有多少个1,显然要计算前 $l$位有多少个1可以如下计算

int cnt = popcnt(mask) - popcnt(((ui(-1)) <<l) & mask);
© 著作权归作者所有
这个作品真棒,我要支持一下!
这里是个人google kickstart 2018,2019年题目解析,希望对渴望参加Google 招聘或者大厂...
1条评论

什么时候继续更新呢?

top Created with Sketch.