格物致知

Qingw の Blog

ACM笔记

Posted at # Codeforces

开头

刷题的作用

训练方案

知识

数学

异或

异或线性基

给出一个数列 a1,a2,…,an，若一个序列 d1,d2,…,dk 满足以下性质：

  • 所有原数列中的元素能够异或出来的值 d 中的数也能异或出来

d[i]中非零的个数就是这个线性空间的秩(线性无关的向量的个数)

鸠巢原理

有N + 1个可能， 但是只有N个抽屉， 那么必然至少有一个会有重复的

质数筛

任何一个合数都是可以整除比他小的一个质数

矩阵加速

(AkSk)[AA01]=(Ak+1Sk+1)\begin{pmatrix} A_k&S_k \end{pmatrix} \begin{bmatrix} A&A\\ 0&1\\ \end{bmatrix} = \begin{pmatrix} A_{k+1}&S_{k+1} \end{pmatrix}

斐蜀定理

两个互质的数a和b

凑不出的最大整数为S=a∗b−a−bS = a * b - a - b, 在S之后的数都可以用a 和 b凑出来（用于路径压缩）， 所以大于S的路径直接变成S长度

概率论

  1. 逆元的计算（费马小定理（np−2n ^ {p-2} 前提是p是质数）， 扩展欧拉函数）： 适用于求单点的逆元

  2. 逆元的预处理 （阶乘预处理， 再处理逆元） ： 适用于大范围的逆元

  3. 模类Z

  4. 组合数Cnm=n!m!(n−m)!C_n^m = \frac{n!}{m!(n-m)!}

计算几何

扫描线

动态规划

定义dp数组 -> 初始化dp数组 -> 转移方程

DP数组的初始化

线性DP

dp数组的思考 : 有足够的信息, 不会破坏无后效性

最长递增子序列

tails数组 --> tails[1] = 7 代表长度为2的LIS的最小结尾数字为7

树上DP

套路： 父节点的全集信息需要靠子节点的全集信息递归来返回

数位DP

利用条件判断加递归

状压DP

dp[status][i] status == (1 << MAXN)， 用位来表示每一个东西已经选了或者还没选(状态的子集状态)

区间DP

小区间合并成大区间

一般允许O(n3)O(n^3)的复杂度

0-1背包

两个变量: 容量和价值， 依次遍历每个物品，更新dp[容量] = std::max(价值1， 价值2)， dp[i]数组定义是在容量为x的时候最大价值是多少， 可以买或者不买来更新

数据结构

链表

带版本控制的链表(可持久化)

前缀和 差分

二维前缀和公式 : a[i][j] = a[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1]

二维差分公式: d[x1][y1]++, d[x1][y2 + 1]--, d[x2 + 1][y1]--, d[x2 + 1][y2 + 1]++

BIT

a[0011] 代表以3结尾，长度为1的区间和, a[0100]代表以4结尾，长度为4的区间和

维护可差分（可减性）信息（由两个大区间得到一个小区间）

  1. 单点修改 + 区间查询（维护原数组） P3374

    1. 求逆序对 P1774
    2. 树上逆序对 P3605
    3. 离线查询 + 维护区间出现了几次 P1972 P4113

  2. 单点查询 + 区间修改（维护差分数组）P3368

  3. 区间查询 + 区间修改 （维护D和Di）P3372

  4. 二维数组 + 单点修改 + 区间查询 （维护二维数组）

  5. 二维数组 + 区间修改 + 区间查询 （维护二维差分数组）P4514

DSU

RMQ

对数组的范围静态查询， （最大值， 最小值， 最大公约数）

rmq[i][k]rmq[i][k] 可以理解成管辖[i, i + (1 << k))的一个值

线段树

区间查询 + 区间修改 + 一维数组 + （有组合律）

单调栈

找到阶段性的强者

单调队列/滑动窗口

与普通的队列不同的是，这是一个双端队列

堆/优先队列

自动维护最小值，最大值， 反悔贪心的关键数据结构

LCA（最近公共父节点）

作用：

  1. 求树上两点的距离
  2. 树上差分（点差分[diff[u]++,diff[v]++,diff[lca]—, diff[fa[lca]]]—，边差分 diff[u]++,diff[v]++,diff[lca]-2)

算法

搜索

每个节点都是状态(位置， 颜色…), 我们需要找到一条从起点到终点的有效边

分治法

把大问题分成两半， 再递归合并

CDQ分治

倍增

图论

DFS

父节点给子节点初始化信息， 先操作，后递归

子节点给父节点更新消息，先递归， 后操作

BFS

洪水填充

二分图

哈夫曼树

高频短码， 低频长码， 从底至上

dji算法

优先队列维护的是全局的最近的点

算法复杂度 O(N+M)log(N)O(N + M)log(N) N+M是遍历了图中的所有点和边, logN是优先队列比较每个点

floyd

求全局任意两点的最短路, O(n3)O(n^3)

剪枝很重要， 很有可能不剪枝过不了hdu_1704

// abc_416_E 动态增加新路 O(n^2)
dist[i][j] = std::min({dist[i][j],
                       dist[i][x] + dist[x][y] + dist[y][j],
                       dist[i][y] + dist[y][x] + dist[x][j]});

spfa

用来判断图中是否有负环,初始的时候要把所有点入队(防止图不连通), 所有dist都为0

如果没有负环, 起始节点到目标节点的走过的边数应该是<= V - 1(整个图的总点数)

如果是从0号点出发,则其他的dist应该为INF(这种是求最短路顺便判断负环)

算法复杂度: 最坏是O(NM)O(NM) 菊花图

johnson

求全源最短路 O(NMlog(M))O(NMlog(M))

先用spfa求势能,再跑n个dij算法

tarjan

SCC: 强连通分量, 一个有向子图(不是树)中任意两个点连通

dfnndfn_n: dfs顺序遍历的编号

lownlow_n : u为根的子树的所有节点能够到达的最小dfn序

割边: 如果删掉这条边, 图中的连通块(分量)变多

割点: 如果删掉这个点, 图中的连通块(分量)变多

字符串

马拉车

解决回文问题

KMP

找到S1中的S2的位置 , S2∈S1S_2 \in S_1

nxtnxt数组是在[0, i)的前缀中的最长公共前后缀

n−nxt[n]==xn-nxt[n] == x 则s[i]==s[i+x]s[i] == s[i+x] 则x为最小循环字串的大小

字符串哈希

判断字符串是否相等

字典树（前缀树）

记录多个字符串的前缀

  1. 维护字符串的字典树
  2. 0-1 Trie 求路径最大异或和 P4551

杂项

CF思考角度

从局部思考推到整体

旋转操作

// 顺时针
vector<string> ns(n);
for (int i = N - 1; i >= 0; --i) {
    for (int j = 0; j < N; ++j) {
        ns[j] += s[i][j]; 
    }
}
// 从最后一行向上从左到右发牌
// 1 2 3       7 4 1
// 4 5 6 ====> 8 5 2
// 7 8 9       9 6 3

// 逆时针
vector<string> ns(n);
for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
        ns[N - 1 - j] += s[i][j];  
    }
}

// 
// 1 2 3      3 6 9
// 4 5 6 ===> 2 5 8
// 7 8 9      1 4 7

位运算

// 取一位数n的最高位1的位置
int high_bit = 63 - __builtin_clzll(n);
// 制作一个数前i位都是1 (11111100000)
-(1 << i) + 1;
// 取一个数的最小的一位1
x & -x
// 取x的第i位
(x >> i) & 1
// 取反x的第i位
x ^= (1 << i)
// 将x的第i位取0
x &= ~(1 << i)

贪心

反悔贪心

在一维数组上进行要或者不要（这个值）， 带有前缀条件，用优先队列

先无脑入队列

最大子段和

Kadane 算法 ： 通过维护历史最值来判断是继续加，还是清零

破环成链

如何调代码

#include <bits/stdc++.h>
#define _CLR_CYAN   "\033[1;36m"
#define _CLR_GREEN  "\033[1;32m"
#define _CLR_RESET  "\033[0m"
using i64 = long long;
using i128 = __int128;
inline std::ostream& operator<<(std::ostream& os, __int128 n) {
    if (n == 0) return os << "0";
    if (n < 0) { os << "-"; n = -n; }
    std::string s;
    while (n > 0) { s += (char)('0' + (n % 10)); n /= 10; }
    std::reverse(s.begin(), s.end());
    return os << s;
}

template <typename T>
void dbg_out(const T& val) { std::cerr << val; }

template <typename A, typename B>
void dbg_out(const std::pair<A, B>& p) { std::cerr << '(' << p.first << ", " << p.second << ')'; }

template <typename T>
requires requires(T t) { t.begin(); t.end(); }
void dbg_out(const T& v) {
    std::cerr << '[';
    bool first = true;
    for (const auto& x : v) {
        if (!first) std::cerr << ",";
        first = false;
        dbg_out(x);
    }
    std::cerr << ']';
    std::cerr << "Total:" << v.size() << '\n';
}
template <typename T, std::size_t N>
void dbg_out(const T (&a)[N]) {
    std::cerr << '[';
    for (std::size_t i = 0; i < N; ++i) {
        if (i > 0) std::cerr << ",";
        dbg_out(a[i]);
    }
    std::cerr << "]";
    std::cerr << "Total:" << N << '\n';
}
template <typename T>
requires requires(T t) { t.begin(); t.end(); }
void dbg_out_range(const T& v, int L, int R) {
    std::cerr << '[';
    bool first = true;
    auto it = std::next(v.begin(), L);
    for (int i = L; i < R && it != v.end(); ++i, ++it) {
        if (!first) std::cerr << ",";
        first = false;
        dbg_out(*it);
    }
    std::cerr << "]";
    std::cerr << "Range: [" << L << ", " << R << "), Total: " << v.size() << '\n';
}
template <typename T, std::size_t N>
void dbg_out_range(const T (&a)[N], int L, int R) {
    std::cerr << '[';
    for (int i = L; i < R && i < (int)N; ++i) {
        if (i > L) std::cerr << ",";
        dbg_out(a[i]);
    }
    std::cerr << "]";
    std::cerr << "Range: [" << L << ", " << R << "), Total: " << N << "\n";
}
#define debug(x) \
    std::cerr << _CLR_CYAN << "[" << #x << "]" << _CLR_RESET << '\n'; \
    std::cerr << _CLR_GREEN; dbg_out(x); std::cerr << _CLR_RESET << '\n';

#define debug_range(x, L, R) \
    std::cerr << _CLR_CYAN << "[" << #x << "]" << _CLR_RESET << '\n'; \
    std::cerr << _CLR_GREEN; dbg_out_range(x, L, R); std::cerr << _CLR_RESET << '\n';

字符串的stl操作

string text;
text.find(word, pos) // ==> string::npos;
text.replace(pos, len, str)

    // 输入
    std::cin // 会留下一个换行符, 忽略空格换行符
    std::cin.ignore(); // 吃掉一个字符
    std::cin.get(c)
    std::getline(std::cin, s); // 读取,直到换行符,会吃掉换行符

	// 标准流程(读取多行字符串)是
	int n;
	std::cin >> n;

	// 坚决清空第一行数字后面的所有残留物
	std::string dummy;
    std::getline(std::cin, dummy); 

    for (int i = 0; i < n; ++i) {
        std::string s;
        std::getline(std::cin, s); // 干净清爽地读取每一行
        // 处理字符串 s ...
    }

天梯赛的阴函数

// 补全前导零
os << std::setfill('0') // 全局有效i
os << std::setw(5) // 只对后面一个数有效

sort的元素满足传递性

较难知识点