杂项算法 - sdjasj的博客

找树的直径

定义:树中距离最远的两点

1.任取一点作为起点，找到距离该点最远的一个点u

2.再找到距离u最远的一点v

u和v之间的路径就是一条直径

单调栈

核心思想:遇到一个数，如果该数性质比栈顶元素更优，则将栈顶元素出栈，直到该数比栈顶元素性质不优为止，将该数入栈

常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

单调队列

核心思想:首先判断队头是否滑出窗口，遇到一个数，如果该数比队尾元素更优，则队尾元素出队，直到该数比队尾元素不优为止，将该数入队

常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
    while (hh <= tt && check(q[tt], i)) tt -- ;
    q[ ++ tt] = i;
}

龟速乘

把a*b转化为a+a+a+…+a(b个a相加)，利用快速幂的思想，计算出a,2*a,4*a,…2^k*a，根据b的二进制位(比如9 = 0b10001),a*9 = 2⁰a+2⁴a,可以省去高精度乘法

枚举子集

for(int i=1;i<(1<<n);i++)
{
    f[i]=0;
    for(int s=i;s;s=(s-1)&i) //i是集合二进制表示,s是i的子集
        if(cover[s]==all)   
            f[i] = max(f[i],f[i^s]+1);
}	

取整

a / b向上取整

int c = (a + b - 1) / b;

字符串哈希

核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

康托展开

康托展开可以用来求一个$1\sim n$ 的任意排列的排名

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long LL;
const int N = 1e6 + 7, MOD = 998244353;
int t[N];
int n;
LL f[N];
int lowbit(int x) {
    return x & -x;
}

void add(int x) {
    for (int i = x; i <= n; i += lowbit(i)) {
        t[i]++;
    }
}

int query(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) {
        res += t[i];
    }
    return res;
}


int main() {
    cin >> n;
    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        f[i] = f[i - 1] * i % MOD;
    }
    LL ans = 0;
    for (int i = 0; i < n; i++) {
        int a;
        scanf("%d", &a);
        add(a);
        int tt = a - query(a);
        ans += f[n - i - 1] * tt;
        ans %= MOD;
    }
    cout << ans + 1 << endl;
    return 0;
}

逆康托定理，求n的全排列中排名第k的排列

class Solution {
public:
    string getPermutation(int n, int k) {
        string ans = "";
        int f[11] = {0};
        int jc[11] = {0};
        jc[0] = 1;
        for (int i = 1; i <=n; i++) {
            jc[i] = jc[i - 1] * i;
        }
        k -= 1;
        for (int i = 1; i <= n; i++) {
            int t = k / jc[n - i];
            int cnt = 0, num = -1;
            for (int j = 1; j <= n; j++) {
                if (f[j] == 0) {
                    cnt++;
                }
                if (cnt == t + 1) {
                    f[j] = 1;
                    num = j;
                    break;
                }
            }
            ans += '0' + num;
            k -= t * jc[n - i]; 
        }
        return ans;
    }
};

对顶堆 + 懒删除堆

对顶堆动态维护滑动窗口内的中位数，懒删除堆用来删除非堆顶元素。

例题：滑动窗口中位数

#include <bits/stdc++.h>
using namespace std;

class DualHeap {
private:
  priority_queue<int> small;
  priority_queue<int, vector<int>, greater<>> large;
  unordered_map<int, int> delayed;
  int k, smallsize, largesize;

public:
  DualHeap(int k) : k(k), smallsize(0), largesize(0) {}

private:
  template<typename T>
  void prune(T& heap) {
    while(!heap.empty()) {
      int num = heap.top();
      if (delayed.count(num)) {
        heap.pop();
        delayed[num]--;
        if (!delayed[num]) {
          delayed.erase(num);
        }
      } else {
        break;
      }
    }
  }

  void makeBalance() {
    if (smallsize > largesize + 1) {
      large.push(small.top());
      small.pop();
      --smallsize;
      ++largesize;
      prune(small);
    } else if (smallsize < largesize) {
      small.push(large.top());
      large.pop();
      ++smallsize;
      --largesize;
      prune(large);
    }
  }

public:
  void insert(int x) {
    if (small.empty() || x <= small.top()) {
      small.push(x);
      ++smallsize;
    } else {
      large.push(x);
      ++largesize;
    }
    makeBalance();
  }

  void erase(int x) {
    delayed[x]++;
    if (x <= small.top()) {
      --smallsize;
      if (x == small.top()) {
        prune(small);
      }
    } else {
      --largesize;
      if (x == large.top()) {
        prune(large);
      }
    }
    makeBalance();
  }

  double getMedian() {
    return k & 1 ? small.top() : ((double)small.top() + large.top()) / 2;
  }
};


class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
      DualHeap heap(k);
      vector<double> ans; 
      for (int i = 0; i < nums.size(); i++) {
        if (i >= k) {
          heap.erase(nums[i - k]);
        }
        heap.insert(nums[i]);
        if (i >= k - 1) {
          ans.push_back(heap.getMedian());
        }
      }
      return ans;
    }
};

折半搜索

对一些题需要$O(2^{n})$枚举子集时，可以将数据分成两半，以$O(2^{\frac{n}{2}})$的时间分别枚举两个子集，进行相应操作，然后再用双指针遍历两个子集

例题:

https://leetcode.cn/problems/closest-subsequence-sum/description/

https://leetcode.cn/problems/partition-array-into-two-arrays-to-minimize-sum-difference/submissions/427521414/

杂项知识点

区间平均数

看到这种和区间平均数有关的题目可以考虑把每个数减去平均数M，一段区间的平均数大于M等价于减完数后区间的区间和大于零

一个正整数n被拆分为k个正整数，k>=2，求这k个整数乘积最大是多少

尽可能多分解3

https://leetcode.cn/problems/integer-break/solutions/352875/zheng-shu-chai-fen-by-leetcode-solution/

如何比枚举n的约数更快求出n的所有约数

如果直接枚举，那么时间复杂度是根号N。可以先求出2~n内的素数，然后枚举素数判断是否是n的约数，时间复杂度是$\frac{n}{\ln(n)}$，然后dfs将{素数,出现次数}还原为n的约数

https://www.acwing.com/problem/content/description/202/

相同元素的不同排列，如何通过对一个排列进行最少次数的邻位交换得到另一个排列？

同时遍历两个排列S1,S2，如果S1[i] != S2[i]，那么找到大于i的j使得S2[i] = S1[j]，进行j-i次交换将S1[i]和S1[j]互换

位运算性质

1.a^b<=a+b