1. 双向搜索 Meet-in-the-middle 适用于输入数据较小, 但还没小到能直接暴力搜索的情况 双向广搜的一般步骤: 将开始结点和目标结点加入队列 q 标记开始结点为 1 标记目标结点为 2 while (队列 q 不为空) { 从 q.front() 扩展出新的 s 个结点 如果 新扩展出的结点已经被其他数字标记过 那么 表示搜索...

D. Flip and Adjust (DP) 题目: $n$ 张卡片, 正面数字 $a_i$, 背面数字 $b_i$ 你来决定每张卡片正面朝上还是反面朝上 但是最后卡片上显示的数字总和必须为 $s$ 思路: 定义 $dp[i][j]$: 是否能从 $1, 2, …, i$ 张卡片中得到总和 $j$ 转移: $dp[i + 1][j] = 0$ if $dp[i][...

D. Stones (DP) DP[n] = the number of stones that the first player can take if the game starts with a pile with n stones [dp[n] = \max (A_i + (n - A_i) - dp[n - A_i] A_i <=...

D. Letter Picking Letter Picking 题目: Alice和Bob又双叒叕在玩游戏, 有一个由小写字母组成的字符串, 长度为偶数, 两个玩家每次从字符串左边或者右边拿掉一个字符, 添加在自己字符串的头部, 问最后谁能赢 分析: 区间DP 定义 $dp[l][r]$: 只考虑区间 $[l, r]$, 两个人都在最优策略下执行完所有操作之后的结果 区间D...

线性筛 1. 素数 如何判断一个数是不是 素数? bool isPrime(a) { if (a < 2) return false; for (int i = 2; i * i <= a; ++i) if (a % i == 0) return 0; return true; } 2. 素数筛法 如果我们想要知道小于等于 $n...

D. Snuke Panic (DP) https://atcoder.jp/contests/abc266/tasks/abc266_d 定义 $dp[x][i]$: The maximum sum of size of Snukes that Takahashi captures until he reaches at the coordinate $x$ at time $t$ ...

D. 阿宁的质数 (线性筛) E. 阿宁去游玩 (Dijkstra / 分层图) #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n &...

快速幂 快速幂, 二进制取幂(Binary Exponentiation, 也称平方法), 是一个在 $O(\log{n})$ 的时间内快速计算 $a^n$ 的小技巧, 而暴力的计算需要 $O(n)$ 的时间 推荐学习链接: OI-WIKI https://oi-wiki.org/math/binary-exponentiation/ 知乎博主pecco https://zh...

E. Warp (DP) 定义 $dp[n][i][j]$: the number of paths that end up in $(x,y)$ after $n$ teleportations 复杂度: $O(N^3(\log{N} + \log{M}))$ #include <bits/stdc++.h> using namespace std; int main...

简介 珂朵莉树（Chtholly Tree）起源于 CF896Chttps://codeforces.com/problemset/problem/896/C 可以较快地实现: 区间加 区间赋值 求区间第k大值 求区间n次方和 珂朵莉树的适用范围: 有 区间赋值 操作且 数据随机 的题目 实现 珂朵莉树的思想在于: 随机数据下的区间赋值操作很可能让大量...