1. 位运算

应用

  1. 一些有限状态集合可以通过位运算来快速表示，如状态压缩DP。
  2. 进行乘方和乘法的快速计算，如快速幂，慢速乘。

代码模板
最短Hamilton路径：从起点到终点，每个点只经过一次的最短路径

  1. memset(dp, 0x3f, sizeof dp);
  2. dp[1][0] = 0;
  4. for(int i = 1; i < 1 << n; i++) {
  5.     for(int j = 0; j < n; j++) {
  6.         if(i >> j & 1) {
  7.             for(int k = 0; k < n; k++) {
  8.                 if(k != j && i >> k & 1) {
  9.                     dp[i][j] = min(dp[i][j], dp[i & ~(1 << j)][k] + d[k][j]);
  10.                 }
  11.             }
  12.         }
  13.     }
  14. }
  16. printf("%d\n", dp[(1 << n) - 1][n - 1]);

快速幂、慢速乘（大数乘法）

  1. int qmi(int a, int b, int p)
  2. {
  3.     int ans = 1;
  4.     for(; b > 0; b >>= 1) {
  5.         if(b & 1) ans = (ll) ans * a % p;
  6.         a = (ll) a * a % p;
  7.     }
  8.     return ans % p;
  9. }
  11. ll qadd(ll a, ll b, ll p)
  12. {
  13.     ll ans = 0;
  14.     for(; b > 0; b >>= 1) {
  15.         if(b & 1) ans = ((__int128)ans + a) % p;
  16.         a = ((__int128)a + a) % p;
  17.     }
  18.     return ans;
  19. }

2. 排序

快排模板

  1. void qsort(int l, int r) {
  2.     if(l >= r) {
  3.         return;
  4.     }
  6.     int i = l - 1, j = r + 1, x = a[l + r >> 1];
  7.     while(i < j) {
  8.         do i++; while(a[i] < x);
  9.         do j--; while(x < a[j]);
  10.         if(i < j) {
  11.             swap(a[i], a[j]);
  12.         }
  13.     }
  14.     qsort(l, j), qsort(j + 1, r);
  15. }

3. 贪心

贪心的题目没有特定的框架，需要具体问题具体分析，尽量分类清楚。
目前有这几种类型：

  1. 根据特定规则排序类：给你一个数组，一个规则，回答怎么对该数组排序，使得结果最优。这类问题通常是先假定结果已经按最优情况排好了，如果交换两个相邻的项（在不影响其他前后元素的基础上），结果会变差，然后推出排序规则。
  2. 有多个限制条件，然后不断地维护一个最优决策。这类题目通常有多个限制条件，我们需要先在满足一个条件地基础上，尽可能满足第二个条件，使得结果最优。解法通常是先按照条件一排序，然后贪心地选择条件二对结果更有利的项。一般需要仔细想想按照哪个条件排序，可以更方便维护当前的最优决策。

经典场景：

  1. 超市

有N个物品，每个物品都有一个价值和一个过期时间。假如每天只能卖一个物品，如何安排使得超市的收益最大。这道题可以先按照过期时间排序，先卖快过期的，然后对于每个物品，我们可以看当前合法决策下的最优物品集合，它的过期时间是不是比集合总数大，是的话可以直接作为候选项（可以安排最后卖这个物品），否则需要和集合中的物品的价值进行比较，如果比集合中价值最小的物品要大，那么把集合中价值最小的去掉，把这个物品加进入。
这道题还有另一种解法，按价值排序，优先放价值最大，然后对于新物品，查看有没有空闲日期放。维护空闲日期通过并查集来解决，使用掉一个日期，将该日期的父节点指向父节点的前一个结点。这样，对于任意一个过期时间，它的根都对应最近可选的空闲时间。下面是解法一的代码。

  1. #include<cstdio>
  2. #include<queue>
  3. #include<algorithm>
  4. using namespace std;
  6. typedef pair<int,int> pii;
  8. const int N = 1e4 + 10;
  10. pii a[N];
  12. int main() {
  13.     int n;
  15.     priority_queue<int, vector<int>, greater<int>> pq;
  16.     while(scanf("%d", &n) == 1) {
  17.         for(int i = 0; i < n; i++) {
  18.             scanf("%d%d", &a[i].second, &a[i].first);
  19.         }
  21.         sort(a, a + n);
  23.         for(int i = 0; i < n; i++) {
  24.             int d = a[i].first, v = a[i].second;
  25.             while(pq.size() >= d && (int)pq.top() < v) {
  26.                 pq.pop();
  27.             }
  28.             if(d > (int)pq.size()) {
  29.                 pq.push(v);
  30.             }
  31.         }
  33.         int ans = 0;
  34.         while(pq.size()) {
  35.             ans += pq.top();
  36.             pq.pop();
  37.         }
  39.         printf("%d\n", ans);
  40.     }
  42.     return 0;
  43. }
  1. 耍杂技的牛（相似题：国王游戏）

有N头牛垂直站，每个牛都有一个重量和强壮值，每个牛的风险是在它之上所有牛的重量减去它自己的强壮值的结果，求这N头牛如何排列，使得每头牛最大的风险值最小。这道题是第一种类型的贪心题，我们发现在一种排序里，交换两头牛不会对其他牛的风险值产生影响，因此可以比较交换相邻两头牛，比较前后的最大值变化，推导出排序的规则。

  1. #include<cstdio>
  2. #include<algorithm>
  3. using namespace std;
  5. const int N = 5e5 + 10;
  7. int a[N], b[N], c[N];
  9. bool cmp(int i, int j) {
  10.     return a[i] + b[i] < a[j] + b[j];
  11. }
  13. int main() {
  14.     int n;
  15.     scanf("%d", &n);
  17.     for(int i = 0; i < n; i++) {
  18.         scanf("%d%d", &a[i], &b[i]);
  19.         c[i] = i;
  20.     }
  22.     sort(c, c + n, cmp);
  24.     int ans = -1e9, sum = 0;
  25.     for(int i = 0; i < n; i++) {
  26.         ans = max(ans, sum - b[c[i]]);
  27.         sum += a[c[i]];
  28.     }
  30.     printf("%d\n", ans);
  32.     return 0;
  33. }