暑期笔记 | 近期杂类笔记 (位运算和高精等)
位运算
运用位运算，能简化一些问题。
基本概念
&按位与 同为1则得出1，否则为0|按位或 同为0则得出0，否则为1^按位异或 相同为0，不同为1，相当于不进位加法^优先级高于|和&a ^ a = 0, a ^ 0 = ax ^ y = (x | y) - (x & y)
~取反<<左移 $x « k = x \times 2^{k}$>>右移 $x » k = \lfloor x\div 2^k\rfloor$
十进制的位运算都要先转换成二进制，再按位进行。每一位的规则与逻辑运算类似。
$e.g.$
$5 \& 6=(101)_2\&(110)_2=(100)_2=4$
$7 \& 13=(111)_2\&(1101)_2=(101)_2=5$
常用技巧
lowbit = (x&(-x))$lowbit(x)$获得一个数二进制的最后一个为 $1$ 的 $bit$n&(n-1)==0判断一个数是否为$2$的幂n&((1<<x)-1)求$n \mod 2^x$(x^y)>=0判断两个数符号是否相同
例如，可以用来统计一个数的二进制形式中$1$的个数：
int cntBit(int x){
int ret = 0;
while(x){
ret++;
x -= x&(-x);// x&(-x)即lowbit
// x &= x-1 也可以代替上一句求出lowbit
}
return ret;
}
生成n位格雷码：
int n;
for(int i=0;i<(1 << n);i++){
int code = (i >> 1) ^ i;
print_2(code, n); //假设print_2可以输出n位二进制形式
}
习题1
输入一个长度为$n$的数组，考虑所有不同的数字，有且只有一个数字出现了奇数次。
输出这个出现了奇数次的数字。
代码
int n, num, ans=0;
cin >> n;
for(int i=1;i<=n;i++){
cin >> num;
ans ^= num;
}
cout << ans;// 出现偶数次的数一定会被异或变成0，留下的就是要求的数字
习题2
给出区间$[a,b]$，求$a\ xor\ (a+1)\ xor\ (a+2) ….. \ xor\ b$。
题解
设$f(x)$为从$1$到$x$的前缀异或。那么原式等于$[f(b)\ xor f(a-1)]$。
对于任意的$f(x)$，考虑到$0\ xor\ 1=1;\ 2\ xor\ 3=1;\ 4\ xor\ 5=1…$
所以有：
\[f(x)=\begin{cases} 1 & (x\mod 4=1)\\ 0 & (x\mod 4=3)\\ f(x-1)\ xor\ x & (其他情况) \end{cases}\]直接写成代码即可。
习题3
给出两个数$a$，$b$。问$a$能否只通过位移运算（ >>和 << 可以多次使用）变成$b$。
题解
如果可以变成$b$，那么可以说$b$的二进制删除了前导和后缀$0$后，是$a$的子串。
#include <iostream>
using namespace std;
int main(){
int t, a, b;
cin >> t;
for(int i=1; i<=t; i++){
bool flag = 0;
cin >> a >> b;
while(b%2==0 && b) b /= 2; // 去除b尾部的所有0
while(a>0){
if((a&b)==b){ //a&b运算后为b本身，可知b的所有1的位置 a都是1，其他不确定
int t = a ^ b;
int lowbit = t & (-t);
if(t==0 || lowbit>b) flag = 1;
//t==0 : 完全一样则异或为0；lowbit>b ： 异或后的1的位置大于b的
//同时满足即可
}
a >>= 1;
}
if(flag) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
高精度基础
高精度这块就是模拟。其中压位的思想可以省一些时空，但是其实大部分题不压位也能过，所以直接拿十进制模板写就够了。
模板（无压位）
以下给出高精度加减的模板。
这些函数都有一些局限，所以如果不知道给出的两个数的正负，需要先判断：两个数同正负，可处理成高精加；两个数一正一负，可处理成高精减。
int ta[10001], tb[10001];
// add 假定a与b同正负,返回a+b
string add(string a, string b){
memset(ta,0,sizeof(ta));
memset(tb,0,sizeof(tb));
string ans;
bool flag = 0;//是否需要加负号
if(a[0]=='-'&&b[0]=='-'){
flag = 1;
a.erase(a.begin());
b.erase(b.begin());
}//a,b同负时，抹负号，最后加负号
int len_a = a.length(), len_b = b.length();
int len = max(len_a, len_b);
for(int i=1; i<=a.length(); i++) ta[i] = a[len_a-i]-'0';
for(int i=1; i<=b.length(); i++) tb[i] = b[len_b-i]-'0';
int cnt=0;
for(int i=1; i<=len; i++){
cnt += ta[i] + tb[i];
ans = char(cnt%10 + '0') + ans;
cnt /= 10;
}
if(cnt) ans = "1" + ans;
if(flag) ans = "-" + ans;
return ans;
}
//sub 假定a与b同正，返回a-b
string sub(string a, string b){
memset(ta,0,sizeof(ta));
memset(tb,0,sizeof(tb));
string ans;
bool flag = 0;//是否需要加负号
int len_a = a.length(), len_b = b.length();
if((len_a<len_b)||(len_a==len_b&&a[0]<b[0])){
swap(a, b);
flag = 1;
}//a<b时交换，最后加负号
int len = max(len_a, len_b);
for(int i=1; i<=a.length(); i++) ta[i] = a[len_a-i]-'0';
for(int i=1; i<=b.length(); i++) tb[i] = b[len_b-i]-'0';
for(int i=1;i<=len;i++){
int tmp = ta[i]-tb[i];
if(tmp < 0){
tmp+=10;
ta[i+1]--;
}
ans = char(tmp + '0') + ans;
}
while(ans[0]=='0') ans.erase(ans.begin());
if(flag) ans = "-" + ans;
return ans;
}
给出高精乘的模板：
int ta[100001], tb[100001], ts[100001];
string mult(string a,string b){
memset(ta,0,sizeof(ta));
memset(tb,0,sizeof(tb));
memset(ts,0,sizeof(ts));
string ans;
ta[0]=a.length();tb[0]=b.length();
int len=ta[0]+tb[0];
for(int i=1;i<=ta[0];i++) ta[i]=a[ta[0]-i]-'0';
for(int i=1;i<=tb[0];i++) tb[i]=b[tb[0]-i]-'0';
for(int i=1;i<=ta[0];i++) for(int j=1;j<=tb[0];j++) ts[i+j-1]+=ta[i]*tb[j];// 对于a的第i位乘b的第j位，它贡献在答案的 i+j-1 位
for(int i=1;i<=ta[0]+tb[0];i++){
if(ts[i]>9){
ts[i+1]+=ts[i]/10;ts[i]%=10;//进位，每一位只留下个位
}
}
while(ts[len]==0&&len>1) len--;
for(int i=1;i<=len;i++) ans=char(ts[i]+'0')+ans;
return ans;
}
复杂度
时间复杂度
$O(n^n)>O(n!)>O(k^n)$（指数复杂度，基本无法接受）
$O(n^k)>O(n\sqrt n)>O(n\log n)>O(n)>O(\sqrt n)>O(\log n)>O(1)$ （多项式复杂度）
部分算法的时间复杂度
| 算法 | 复杂度 |
|---|---|
| 遍历 | O(n) |
| 冒泡排序 | O(n^2) |
| 快速排序 | O(n log n) |
| 全排列 | O(n!) |
习题
小b喜欢和为K的倍数的序列。
现在有一个长度为n的序列A，请问A有多少个非空连续子序列是小b喜欢的。
题解
思路0 $O(n^3)$
枚举每一个序列，循环求和，判断合法序列数。
思路1 $O(n^2)$
用前缀和来代替循环求和的过程。
思路2 $O(n)$
使用前缀和$sum_i$来维护某个区间的和。
则问题转化为有多少对$(i, j)$，使得$k \mid (sum_j - sum_i)$。
也就是有多少对$(i, j)$，使得$sum_i \equiv sum_j(\mod\ k)$。只需要用 $cnt$ 数组统计同余的数量。其中$cnt_i$记录的 是有几个$sum\mod k=i$。
则答案为$\sum\limits_{i=0}^{k-1}\binom{cnt_i}{2}$。
离散化
把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率叫做离散化。
对于某些只关心数之间大小关系，不关心数的具体值的题目，可以使用离散化的手法，缩小数据范围，简化算法。
习题1(离散化与计数)
这个世界上有很多叫小明的人，他们在不同的国家，不同国家有不同的语言，每一种语言有一个语言编号。
我们给出所有语言的编号，需要注意的是：每个国家的人除了可以懂自己国家的语言，也能懂编号相邻国家的语言，例如：语言编号为：1,7,10,5，其中：
母语编号为 1，懂编号为 1,5 的语言 母语编号为 5，懂编号为 1,5,7 的语言 母语编号为 7，懂编号为 5,7,10 的语言 母语编号为 10，懂编号为 7,10 的语言
这个相邻编号指的并不是输入顺序，而是按照数字大小。同时我们还会告知每一个小明的母语是什么，按照上面的例子，如果小明的母语是 7，那么小明懂的语言编号是：5,7,10。
有一天世界上的小明突然想要聚集在一起看电影，现在有 m 部电影，每部电影的声音对应的语言编号是 a[i]，字幕对应的语言编号是 b[i]。如果小明可以听懂电影声音的话他会非常满意，如果小明可以看懂字幕的话他会比较满意，否则它很不满意。
现在问看哪部电影会使得 n 个小明满意最高，输出这部电影非常满意人数和较满意人数（如果两部电影使得 n 个小明非常满意的人数相同时，选比较满意的最多的那部电影）。
题解
最重要的就是用map来实现离散化。其他不解释，比较简单。
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
const int MAXN = 200005;
int langs[MAXN];
map <int, int> lti;//id to rank
int cnt[MAXN];
int movies[MAXN];
int main(){
ios::sync_with_stdio(false);
int l, m, n, tmp;
cin >> l >> m >> n;
for(int i = 1; i <= l; i++) cin >> langs[i];
sort(langs+1, langs+l+1);
for(int i = 1; i <= l; i++) lti[langs[i]] = i;
for(int i = 1; i <= m; i++){
cin >> tmp;
int p = lti[tmp];
cnt[p-1]++; cnt[p]++; cnt[p+1]++;
}
int mx_g = 0, mx_l = 0, cur_g = 0, cur_l = 0;
for(int i = 1; i <= n; i++){
cin >> cur_g >> cur_l;
cur_g = cnt[lti[cur_g]];
cur_l = cnt[lti[cur_l]];
if(cur_g > mx_g){
mx_g = cur_g;
mx_l = cur_l;
}
else if(cur_g == mx_g && cur_l > mx_l){
mx_l = cur_l;
}
}
cout << mx_g << " " << mx_l;
return 0;
}
习题2(离散化与枚举)
平面上有n个金矿点。现在可以选择一块边长为L的正方形的土地，四边要求和坐标轴平行。请计算一下最多有多少金矿落在（在边界上也算）所选择的土地中。
已知1 <= n <= 100，1 <= L<= 100000，每个金矿的坐标(x,y)满足-100000<=x,y<= 100000。
题解
由于正方形本身是任意的，所以要考虑怎样才能枚举到最优情况。
考虑正方形的一角$(tx,ty)$。最优解的情况下，经过平移让$tx$与边界上的某个金矿的$x$重合，$ty$与边界上的某个金矿的$y$重合，可以使得最终覆盖数量不变。
所以枚举每一个金矿的$x$和$y$组成一组$(tx, ty)$，维护覆盖到的点数的最大值即可。
时间复杂度稳定$O(n^3)$，使用了离散化的思想。
#include <iostream>
using namespace std;
int c[101][2];
int main(){
int n, l;
cin >> n >> l;
for(int i = 1; i <= n; i++){
cin >> c[i][0] >> c[i][1];
}
int mx_p = 0, p, lx, ly, x, y;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
p = 0;
lx = c[i][0];
ly = c[j][1];
for(int k = 1; k <= n; k++){
x = c[k][0];
y = c[k][1];
if(x >= lx && x <= lx+l && y <= ly && y >= ly-l) p++;
}
mx_p = max(mx_p, p);
}
}
cout << mx_p;
return 0;
}
ST表
简单来说，ST表是用于解决 可重复贡献问题(如RMQ问题) 的数据结构。
写ST表时，注意：
- 由于数据量可能较大，使用快速读入会优化一些
- 可以通过$\log_{2}{n} = \log_{2}{\frac{n}{2}} + 1$来预处理查询时需要的log数据，代替
std::log2
习题(模板)
给定一个长度为 $N$ 的数列，和 $M$ 次询问，求出每一次询问的区间内数字的最大值。
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2000005;
const int MAX_LOG = 22;
int f[MAX_N][MAX_LOG], log_2[MAX_N];
//快速读入
inline int read() {
char c = getchar();
int f = 1, x = 0;
while(c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
//预处理log_2
void pre() {
log_2[1] = 0;
log_2[2] = 1;
for(int i = 3; i < MAX_N; i++) log_2[i] = log_2[i/2] + 1;
}
int main() {
int n = read(), m = read();
pre();
for(int i = 1; i <= n; i++) f[i][0] = read();
for(int j = 1; j <= MAX_LOG; j++)
for(int i = 1; i + (1 << (j-1)) - 1 <= n; i++)
f[i][j] = max(f[i][j-1], f[i+(1<<(j-1))][j-1]); //实现st表
for(int i = 1; i <= m; i++) {
int l = read(), r = read();
int s = log_2[r-l+1];
printf("%d\n", max(f[l][s], f[r-(1<<s)+1][s]));
}
return 0;
}
有序化
习题1
小b有一个数n，现在她想把n的每一位重排列，使得得到的结果为2的幂次。
请问小b能得到2的幂次吗？
题解
直接看代码。
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e9;
vector <string> powers;
void pre() {
for(int i = 0; (1 << i) <= MAX_N; i++) {
powers.push_back(to_string(1 << i));
sort(powers[i].begin(), powers[i].end());
}
}
int main() {
pre();
int n;
cin >> n;
string s = to_string(n);
sort(s.begin(), s.end());
for(int i = 0; i < powers.size(); i++) {
if(s == powers[i]) {
cout << "true";
return 0;
}
}
cout << "false";
return 0;
}
其他小知识点
判断一个点在直线的哪边
我们有直线上的一点 $P$ 的直线的方向向量 $\vec{v}$ ，想知道某个点 $Q$ 在直线的哪边。
我们利用向量积的性质，算出 $\vec{PQ}\times \vec{v}$ 。如果向量积为负，则 $Q$ 在直线上方，如果向量积为$0$ ，则$Q$ 在直线上，如果向量积为正，则 $Q$ 在直线下方。
nth_element
nth_element(a, a+k, a+n, cmp) 是 algorithm库中提供的一个方法。
它可以将数组 a 中第 k 小的数放在排序后正确的位置 a[k]，且使得它左边的数都比 a[k]小，右边的数都比 a[k]大。
时间复杂度：$O(n)$
- 上一篇 暑期笔记 | 刷题题解
- 下一篇 OI笔记 | 二分与双指针优化
♥