算法竞赛杂记

仅用做提醒自己，看不懂概不负责～

LIS 和 LNDS #

int LIS(vector<int> &a) {
    vector<int> dp;
    for (auto it : a) {
        auto pos = lower_bound(begin(dp), end(dp), it);
        if (pos == dp.end()) dp.push_back(it);
        else
            *pos = it;
    }
    return dp.size();
}
 
int LNDS(vector<int> &a) {
    vector<int> dp;
    for (auto it : a) {
        auto pos = upper_bound(begin(dp), end(dp), it);
        if (pos == dp.end()) dp.push_back(it);
        else
            *pos = it;
    }
    return dp.size();
}

Maximum subarray sum #

int cur = 0, max_sum = 0; // max_sum=-1e8 if at least one element must be chosen
for (auto it : a) {
    cur = max(cur + it, it);
    max_sum = max(max_sum, cur);
}

整数三分 #

以求函数最大值为例

while (l < r - 2) {
    int m = (l + r) / 2;
    if (cal(m) > cal(m + 1)) r = m + 1;
    else
        l = m;
}
int ans = max({cal(l), cal(l + 1), cal(r)});

把 n 分成 k 组 #

int sz = n / k 有n % k组有sz + 1个，k - n % k组有sz个。

快速范围判断 #

判断是否在[0, N)，常用于 bfs/dfs 边界判断

if ((unsigned)x < N)

判断是否在 [l, r]内

if ((x - l | r - x) >= 0)

根据两数之和和异或值反推两数 #

原理：a + b == (a ^ b) + 2 * (a & b)

如果 $sum-xor$ 是奇数，那么无解。

否则 $A=(sum-xor)/2$ ，根据 A 和 xor 的每一位填就行了，注意如果某一位两数都是 1 的话也是无解。

优先队列模板参数自动推断 #

利用了类模板实参推导（CTAD），可以少写一点代码，需要 C++17。

priority_queue q(greater{}, vector<int>{});

g++11 有 bug，要写成

priority_queue q{greater{}, vector<int>{}};

精确计算 $\lceil\log_2 x\rceil$ #

x == 1 ? 0 : __lg(x - 1) + 1

用交换相邻元素的排序数组的最小操作次数 #

是数组中逆序对的数目

a 个 0，b 个 1 组成的 01 字符串字典序第 k 小 #

先预处理 i 个 0,j 个 1 的字符串个数，然后从高位到底位枚举

vector dp(a + 1, vector(b + 1, 0LL));
dp[0][0] = 1;
for (int i = 0; i <= a; i++) {
    for (int j = 0; j <= b; j++) {
        if (i > 0) {
            dp[i][j] += dp[i - 1][j];
        }
        if (j) {
            dp[i][j] += dp[i][j - 1];
        }
    }
}
auto find_kth = [&](auto &find_kth, int A, int B, ll k) {
    if (A == 0) return string(B, 'b');
    if (B == 0) return string(A, 'a');
    if (k <= dp[A - 1][B]) return "a" + find_kth(find_kth, A - 1, B, k);
    return "b" + find_kth(find_kth, A, B - 1, k - dp[A - 1][B]);
};

位运算技巧 #

可以看这

冒泡排序遍历的次数 #

创建一个复制数组 b，其中 $b[i]={a[i], i}$ ，然后排序 b，排序后 $b[i].second-i$ 的最大值就是答案， $b[i].second-i$ 本质上就是一个数向前移动的距离，不难想出每个会向前移动的数从第一轮遍历就会开始向前移动，直到到达排序后的位置，所以最大的向前移动距离就是遍历的轮数。