bitset

题目选讲

• ADACOINS：http://www.spoj.com/problems/ADACOINS/ ⭐⭐
  • 题意：给n个数，q个查询，每个查询有l，r，求n个数的子集和在[l,r]区间的不同和的个数。
  • 题解：因为这里限制了大小为1e5，所以可以维护1e5的bitset，那么对于前i个数所有能组成的子集和的状态为bs，那么前i+1个数的所有子集和为bs |= bs << a[i+1]，再维护个前缀和即可。
  • 代码：https://github.com/phonism/notes/blob/master/AlgorithmQuestions/BlueBook/spojADACOINS.cpp
• Count The Rectangles：https://codeforces.com/contest/1194/problem/E ⭐⭐⭐⭐
  • 题意：给n个垂直或者水平的线段，问所有井字形的4元组有多少个。
  • 题解：预处理每条垂直的线段和哪些有交集，用bitset存储，然后枚举左右垂直的线段l，r，那么和l和r有交集的水平线段个数为bitset[i] & bitset[j]。这题用树状数组也行，也是枚举l，r，然后维护个树状数组，扫的过程中扫到每个水平的线段i左端点，第i位+1，扫到右端点第i位-1。需要提前排好序，一边遍历水平，一边遍历垂直。
  • 代码：bitset：https://github.com/phonism/notes/blob/master/AlgorithmQuestions/BlueBook/cf1194E.cpp
• Substrings in a String：http://codeforces.com/contest/914/problem/F ⭐⭐⭐⭐⭐
  • 题意：给一个长度1e5的string，然后有1e5次操作，操作1修改某一位的字符，操作2，输入l，r，x，问l到r中substring是x的个数。注意所有的查询x的长度和<1e5。
  • 题解：所有的查询x的长度和<1e5是个关键信息，那么我们可以维护26个bitset，表示每个字母在string的位置。操作1直接修改bitset就行，对于操作2，要查询的x比如是abcb的话，那其实就是(bs[a] >> 0) & (bs[b] >> 1) & (bs[c] >> 2) & (bs[b] >> 3)后在l到r-(y.size()-1)中1个个数，这个等价于l到末尾1的个数减去r - l + 1 - (y.size() - 1)到末尾1的个数。好题！
  • 代码：https://github.com/phonism/notes/blob/master/AlgorithmQuestions/BlueBook/cf914F.cpp