位运算，双指针，二分，排序算法

位运算

1. bitset< 16 >将十进制数转为16位的二进制数

int x = 25;
cout << bitset<16>(x) << endl;

二进制中1的个数

题解

1. 就是每个数与上1判断低位是否是1，是1就加，否则不加，判断完后，这个数右移1位，再判断，直到这个数变为0为止

代码

// 3  011 & 001  1 count++
//        >> 001 & 001 1 count++
#include<iostream>
#include<vector>
using namespace std;int main()
{int n;cin >> n;vector<int> v(n);for (int i = 0; i < n; i++)cin >> v[i];for (int i = 0; i < n; i++){int count = 0;int val = v[i];while (val){if (val & 1)count++;val /= 2;}v[i] = count;}for (int i = 0; i < n; i++)cout << v[i] << " ";return 0;
}

我们需要0

题解

1. 利用了x ^ x = 0和0 ^ x = x这两个性质

代码

// 1 ^ 2  ^ 3 ^ x ^ x ^ x  
// 1 ^ 2 ^ 3 ^ x = 0
// 1 ^ 2 ^ 3 ^ x ^ x == 0 ^ x
// 1 ^ 2 ^ 3 == x#include<iostream>
#include<vector>
using namespace std;int main()
{int t, n;cin >> t;int k = 0;int x = 0;while (t--){cin >> n;vector<int> v(n+1);int sum = 0;for (int i = 1; i <= n; i++)cin >> v[i];for (int i = 1; i <= n; i++)sum ^= v[i];cout << sum << '\n';}return 0;
}

排序

1. 使用unique之前要确保数组是有序的，有序的才能确保所有元素都是唯一的
2.unique会把重复的元素移动到数组的末尾，最后返回第一个重复元素的迭代器

模版排序1

题解

1. 先排序，然后用unique进行返回第一个重复元素的迭代器，最后用erase删除这些重复元素

代码

#include<iostream>
#include<vector>
#include<algorithm>using namespace std;int main()
{int n;cin >> n;vector<int> v(n);for(int i = 0;i < n;i++)cin >> v[i];sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());for(auto x : v)cout << x << " ";return 0;
}

模版排序2

题解

1. 自己写一个排序的逻辑，自定义类型的排序
2.升序的，逆置完之后就可以变为降序的了

代码

#include<iostream>
#include<vector>
#include<algorithm>using namespace std;const int N = 2e5 + 10;
struct Book
{int a;int b;int c;bool operator<(const Book& v) const{if (a == v.a && b == v.b) return c < v.c;if (a == v.a) return b < v.b;return a < v.a;}}u[N];int main()
{int n = 0;cin >> n;for (int i = 0; i < n; i++)cin >> u[i].a >> u[i].b >> u[i].c;sort(u, u + n);reverse(u, u + n);for (int i = 0; i < n; i++)cout << u[i].a << " " << u[i].b << " " << u[i].c << '\n';return 0;
}

模版排序3

题解

1. 这题用了桶排序的思想
2.记录出现数字的次数，然后用次数控制循环，输出[ ]里的数就是存进去的数，可以按顺序输出了

代码

// 桶排序#include<iostream>
#include<vector>
#include<algorithm>using namespace std;const int N = 2e5 + 10;
int v[N];int main()
{int n = 0;cin >> n;for(int i = 1;i <= n;i++){int x;cin >> x;v[x]++;}for(int i = 0;i <= 2e5;i++){// v[i] 是出现的次数for(int j = 0;j < v[i];j++){// i是出现的数字cout << i << " ";}}cout << '\n';return 0;
}

双指针

1. 一快一慢(快慢指针)
2.区间内维护某个东西(滑动窗口)

最长连续不重复子序列

题解

1. 开始的时候i = 1,j = 0
2.j向右走的条件j+1下标的数不在数组中
3. 如果出现重复的数，更新i,让i向后走
4. 代码中使用桶的思想解决

代码

#include<iostream>
#include<vector>
#include<algorithm>const int N = 1e5 + 10;
using namespace std;
int a[N],b[N];void solve()
{int n = 0;cin >> n;for(int i = 1;i <= n;i++) cin >> a[i];int ans = 0;// 初始化桶数组for(int i = 1;i <= n;i++) b[a[i]] = 0;for(int i = 1,j = 0;i <= n;i++){// j < n并且后一个数不在桶数组中while(j < n && !b[a[j+1]]) b[a[++j]]++;// 更新最大长度ans = max(ans,j - i + 1);// i之后要++,让i往后走一个,把之前在桶数组中的数删除b[a[i]]--;}cout << ans << '\n';
}int main()
{int T = 0;cin >> T;while(T--){solve();}return 0;
}

二分

1. 二分的步骤

查找

题解

1. 保证了l始终小于r, l + 1 == r
2.这样保证了a[l] < x, a[r] >= x，后续可以判断a[r] == x

代码

#include<iostream>
#include<vector>
#include<algorithm>using ll = long long;
const int N = 2e5 + 10;
using namespace std;
int a[N];void solve()
{int n = 0, q = 0;cin >> n >> q;for (int i = 1; i <= n; i++) cin >> a[i];while (q--){int x;cin >> x;int l = 0, r = n;while (l + 1 != r){int mid = l + (r - l) / 2;if (a[mid] < x) l = mid;else r = mid;}if (a[r] == x) cout << r << " ";else cout << -1 << " ";}
}int main()
{solve();return 0;
}