bits

题目选讲

• a^b ⭐
  • 题意：求a的b次方对p取模的值，其中1<=a,b,p<=10^9
  • 题解：将b用二进制表示，然后根据a^(d+e)=a^d * a^e，这样对b的二进制从右到左遍历即可，判断每一位是否是1
  • 代码：https://github.com/phonism/notes/blob/master/AlgorithmQuestions/BlueBook/CH0101.cpp
• 64位整数乘法 ⭐
  • 题意：求a乘b对p取模的值，其中1<=a,b,p<=10^18
  • 题解：可以将b表示成二进制，那么对于每个2^k的系数要么是0，要么是a，类似于快速幂思想，a2^k-1 -> a2^k递推
  • 代码：https://github.com/phonism/notes/blob/master/AlgorithmQuestions/BlueBook/CH0102.cpp
• 最短Hamilton路径 ⭐⭐⭐
  • 题意：给定n个点的带权无向图，求0到n-1的最短hamilton路径。n<=20（hamilton路径定义是0到n-1不重不漏的恰好经过每一个点）
  • 题解：朴素做法复杂度O(n!)，可以用状态压缩dp来求解，用二进制表示当前状态已经经过哪些点，然后转移的时候，就遍历所有可以再次经过的点？ dp[i][j]，i是二进制表示当前经历了哪些点，j是最后一个经历的点。那么dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][k] + weight[j][k])
  • 代码：https://github.com/phonism/notes/blob/master/AlgorithmQuestions/BlueBook/CH0103.cpp
• 起床困难综合症 ⭐⭐
  • 题意：给定n个位运算操作，每个有op（操作类型）和t，然后给一个m，问0-m的所有数中经过这n个操作后最大值是多少
  • 题解：显然，按二进制去枚举每一位0或者1，在经历n次操作后，这一位变成多少，然后从高位去贪心就行。
  • 代码：https://github.com/phonism/notes/blob/master/AlgorithmQuestions/BlueBook/CH0104.cpp
• Short Program：http://codeforces.com/contest/879/problem/C ⭐⭐
  • 题意：给n个二进制操作，让构造小于等于5个二进制操作，使得无论输入是多少，经过这些操作后，结果是一样的。
  • 题解：按位去枚举0或者1的情况，根据n个操作后每一个是0还是1来决定这一位用什么操作。注意&|^的操作顺序。
  • 代码：https://github.com/phonism/notes/blob/master/AlgorithmQuestions/BlueBook/cf879C.cpp
• Pretests：https://codeforces.com/gym/102006/problem/F⭐⭐⭐⭐⭐
  • 资料：SOS Dynamic Programming [Tutorial]
  • 题意：给你t个测试样例，n道题目，给出每道题目对于每个测试用例是否会通过，求测试样例的顺序，使得n个题目测试的次数最少。（题目测试遇到失败后就不会向后测试）。
  • 题解：将t个测试用例用二进制表示，定义dp[s]是当前测了s的状态的测试样例，最少需要的测试次数，那么对于所有s & i != i的情况（即所有没测试过的状态），dp[s ^ (1 << i) = min(dp[s] + cnt[s])，其中cnt[s]，表示至少可以通过状态为s的题目个数。这个cnt需要通过上述资料处理出来。
  • 代码：https://github.com/phonism/notes/blob/master/AlgorithmQuestions/BlueBook/cf102006F.cpp
• KOMPICI：http://www.spoj.com/problems/KOMPICI/⭐⭐
  • 题意：给n个数，求有多少个pair至少有一个数字是一样的。
  • 题解：对于每个数，用10位的二进制表示0-9每个数字是否出现，然后遍历n个数字，对于新加的数字，枚举1<<10所有的状态，如果s&i>0，表示两个状态有相同数据，pal += cnt[i]。复杂度O(n * (1 << 10))
  • 代码：https://github.com/phonism/notes/blob/master/AlgorithmQuestions/BlueBook/spojKOMPICI.cpp