位運算

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;
}