最近一段时间学习算法有一点感悟，就是在从初学到掌握基础算法这个阶段，没必要涉猎太多的高阶算法，应该认真把基础打好，把精力放在 锻炼算法思维 、 提升代码实现和查错能力 、提高基础算法熟练度并熟练运用于各种变形题目 上，对应在 Codeforces 上的分数， $2000$ 分以下应该都应该属于这个阶段。
这几点需要坚持打比赛，不要在意分数，重要的是在规定时间内专注思考，尽可能多地将题目做出来。有些题目其实很简单，但对于新手来说，一开始往往不熟悉算法比赛的套路，或不知道如何下手，看题解的时候很容易怀疑自己的智商。我现在比较常用的做法是拿到一道题，首先 把题意读懂 ，知道题目是在说什么，并且结合样例有一个更直观的理解；然后 从头模拟一遍样例，样例不够就自己构造一些 ，对着样例思考是否有直接的解题思路；接着 将题目的一些要求简化、转化、分步骤 ，思考每个步骤的本质是什么，回忆之前是否见过，有没有相似的模型，或者结合之前的知识想一个办法解决它；然后 整理思路，再构造一些样例验证方法 ，尤其是特殊情况或边界；然后 检查复杂度 ，如果超出限制，则想办法进行优化；最后 实现代码 。
定期打比赛并总结一些自己的思考，每次将比赛时 有一些想法但没做出来 的题补掉。如果要求的前置知识远超目前拥有的，那就先放着，通过做题最有效的提升方式就是做那些 稍超目前能力圈 的题目，可以参考 Codeforces 的分数，大约超过自己当前分数的 $300$ 分的题目吧， AtCoder 的话，可以参考比自己当前颜色高一个 Level 的题目。
多做题目，多看高手的实现方法，实现能力和查错能力都会潜移默化地提高。一开始查一个小 bug 查个半天甚至一天都是不奇怪的，只能说查得越久，折磨得越痛苦，印象就越深刻，以后再犯相似错误的概率就越小。之后出现 bug ，大概出在什么地方，心里也都有个数了。
高阶算法要么思维非常巧妙，要么实现起来非常麻烦，要么二者兼备，所以如果思维和代码能力没有打好基础，理解和实现起来是非常困难的，而且初学阶段打比赛时几乎碰不到高阶算法的应用场景，学了之后也会很快忘记。再者，许多高阶算法其实是基础算法的结合、延伸，能够熟练运用基础算法之后，再去学比赛中遇到的新算法，这样理解起来会更快，运用起来也会更得心应手。
以上内容大家可以参考、交流，因为在算法学习中我也走过不少弯路，所以仅作为不断完善学习方法过程中的一些思考与感悟。另外关于我的码风，我觉得大概是 tourist 和 y总 的结合体吧，应该还是能看得下去的hh，那就照例写几道杂题，都不算很难。
D. Cut
题目链接： D. Cut
题意：
给定一个序列，多次询问，每次询问给定一个区间 $[l,r]$ ，问至少将这个区间分成多少个连续段，使得每一段的所有数相乘都和这些数的最小公倍数相等。
解题思路：
首先比较简单的转化就是一段内所有数相乘都和这些数的最小公倍数相等，等价于这段数的所有数互质，或者说最大公因数为 $1$ 。
因为题目要求分成尽量少的连续段，所以对于每个连续段，都尽量长即可。
然后对于某个数 $a_i$ ，将它进行因式分解，对于每个质因数，找到它在 $i$ 之后的最左边的出现过的位置 $j$ ，如果以 $i$ 为起点， 最多 只能构成 $[i,j-1]$ 这个区间，如果包含 $j$ ，那么 $a_i$ 和 $a_j$ 就不互质了，因此可以从 $i$ 向 $j$ 连一条边，从 $i$ 走一步可以到达 $j$ 。其次，还要考虑 $i+1$ 能够走到的位置，将它和 $j$ 取最小值，就是 $i$ 走一步可以走到的最右边的位置。
然后问题可以转化为倍增优化 DP 来解决，定义 $f[i,j]$ 为从 $i$ 开始，走 $2^j$ 步的方案，属性是最右边的位置，转移是比较基本的倍增方式，即 $f[i][j]=f[f[i][j-1]][j-1]$ 。初始化的话，为了实现方便，我们可以将 $n+1$ 也考虑进去，也就是如果某些方案走出界了，就规定它只能走到 $n+1$ 这个位置。
对于一个完整的序列来说，问题可以转化为：从起点出发，最少走几步可以到 $n+1$ 。对于每次询问，则可以转化为：从 $l$ 出发，最少走几步可以到 $r$ 的后面。注意处理询问的时候，先处理走到 $r$ 需要几步，最后再走多一步走出 $r$ 即可。
可以预处理每个数的最小质因子来简化代码和时间复杂度。
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = 20;
int n, m;
int a[N];
int f[N][M];
int nxt[N];
int primes[N], cnt;
int minp[N];
bool st[N];
void init(int n)
{
st[1] = true;
for (int i = 2; i <= n; i ++ )
{
if (!st[i])
{
primes[cnt ++ ] = i;
minp[i] = i;
}
for (int j = 0; primes[j] <= n / i; j ++ )
{
int t = primes[j] * i;
st[t] = true;
minp[t] = primes[j];
if (i % primes[j] == 0) break;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
init(N - 1);
cin >> n >> m;
for (int i = 0; i < N; i ++ ) nxt[i] = n + 1;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
f[n + 1][0] = n + 1;
for (int i = n; i; i -- )
{
int x = a[i], mn = f[i + 1][0];
while (x > 1)
{
int p = minp[x];
mn = min(mn, nxt[p]);
while (x % p == 0) x /= p;
nxt[p] = i;
}
f[i][0] = mn;
}
for (int j = 1; j < M; j ++ )
for (int i = 1; i <= n + 1; i ++ )
f[i][j] = f[f[i][j - 1]][j - 1];
while (m -- )
{
int l, r;
cin >> l >> r;
int res = 0;
for (int j = M - 1; j >= 0; j -- )
if (f[l][j] <= r)
{
res += (1 << j);
l = f[l][j];
}
cout << res + 1 << '\n';
}
return 0;
}
D. Rarity and New Dress
题目链接： D. Rarity and New Dress
题意：
建议直接看原题。
解题思路：
一个比较典型的图形 DP ，规律找得好可以大大简化代码，以下方法比官方题解简单多了。
比较常规的思路是一个斜正方形是上下两个三角形组成的，因此定义 $f[i][j]$ 、 $up[i][j]$ 和 $down[i][j]$ 分别为以 $(i,j)$ 为中心的最大斜正方形、最大上三角形和最大下三角形， $f[i][j]=min(up[i][j],down[i][j])$ 。然后要通过预处理每行的前缀后缀连续相同字符数来求出 $up$ 和 $down$ ，整体思路不难，但是实现的细节有点多。
下面的方式则是定义 $f[i][j]$ 为以 $(i,j)$ 为最下面的那个点的最大斜正方形，可以观察到，如果 $g[i][j]=g[i-1][j]=g[i-1][j-1]=g[i-1][j+1]=g[i-2][j]$ ，那么 $f[i][j]=min(f[i-1][j-1],f[i-1][j],f[i-1][j+1],f[i-2][j])+1$ ，所以直接转移就行了。初始化每个 $f[i][j]$ 都为 $1$ ，注意一下边界。
代码如下：
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<string> g(n);
for (auto &s : g) cin >> s;
vector<vector<long long>> f(n, vector<long long>(m, 1));
for (int i = 2; i < n; i ++ )
for (int j = 1; j < m - 1; j ++ )
{
char c = g[i][j];
if (g[i - 1][j - 1] == c && g[i - 1][j] == c && g[i - 1][j + 1] == c && g[i - 2][j] == c)
f[i][j] = min(min(min(f[i - 1][j - 1], f[i - 1][j]), f[i - 1][j + 1]), f[i - 2][j]) + 1;
}
long long res = 0;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
res += f[i][j];
cout << res << '\n';
return 0;
}
B2. Optimal Subsequences (Hard Version)
题目链接： B2. Optimal Subsequences (Hard Version)
题意：
给定一个序列，定义一个长度为 $k$ 的最优子序列为和最大的子序列，且它们在原始序列的下标序列的字典序最小。多次询问，每次询问给定 $k$ 和 $pos$ ，求长度为 $k$ 的最优子序列中第 $pos$ 个数是什么。
解题思路：
题目有点绕，但是手动模拟一下样例应该能够理解这个过程是在干嘛。
其实就是选出最大的前 $k$ 个数，并且尽量选在原始序列靠前的数，这就是最优子序列。
基于这个思路，可以先对原始序列的 下标数组 进行排列，大的数排在前面，如果数值相同，则下标小的排前面。
然后处理询问，那么就转化成了在排序后的下标数组中，前 $k$ 个数的第 $pos$ 小的值是多少。
动态求区间第几小，容易想到主席树，我之前的文章其实也分享过用树状数组静态求第几小的数的模板，可以把所有询问存下来，按照 $k$ 的大小，从小到大处理，就可以转化为静态问题了。
注意事项：
树状数组代码：
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
#define lowbit(x) (x & -x)
using namespace std;
const int N = 200010;
int n, m;
int a[N];
int order[N];
int tr[N];
int res[N];
vector<vector<pair<int, int>>> query;
void add(int x, int c)
{
for (int i = x; i < N; i += lowbit(i)) tr[i] += c;
}
int find_kth_min(int k)
{
int cnt = 0, x = 0;
const int MAX_VAL = N;
for (int i = log2(MAX_VAL); i >= 0; i -- )
{
x += (1 << i);
if (x >= MAX_VAL || cnt + tr[x] >= k) x -= (1 << i);
else cnt += tr[x];
}
return x + 1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i ++ )
{
cin >> a[i];
order[i] = i;
}
cin >> m;
query.resize(n + 1);
for (int i = 1; i <= m; i ++ )
{
int k, pos;
cin >> k >> pos;
query[k].emplace_back(pos, i);
}
sort(order + 1, order + 1 + n, [&](int x, int y)
{
if (a[x] != a[y]) return a[x] > a[y];
else return x < y;
});
for (int k = 1; k <= n; k ++ )
{
add(order[k], 1);
for (auto &[pos, id] : query[k])
res[id] = a[find_kth_min(pos)];
}
for (int i = 1; i <= m; i ++ ) cout << res[i] << '\n';
return 0;
}
主席树代码：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200010;
int n, m;
int a[N];
int order[N];
int root[N], idx;
struct Node
{
int l, r, cnt;
} tr[N * 4 + N * 17];
void pushup(int u)
{
tr[u].cnt = tr[tr[u].l].cnt + tr[tr[u].r].cnt;
}
int build(int l, int r)
{
int p = ++ idx;
if (l == r) return p;
else
{
int mid = l + r >> 1;
tr[p].l = build(l, mid);
tr[p].r = build(mid + 1, r);
return p;
}
}
int insert(int p, int l, int r, int x)
{
int q = ++ idx;
tr[q] = tr[p];
if (l == r)
{
tr[q].cnt ++ ;
return q;
}
else
{
int mid = l + r >> 1;
if (x <= mid) tr[q].l = insert(tr[q].l, l, mid, x);
else tr[q].r = insert(tr[q].r, mid + 1, r, x);
pushup(q);
return q;
}
}
int query(int p, int q, int l, int r, int k)
{
if (l == r) return r;
else
{
int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
int mid = l + r >> 1;
if (cnt >= k) return query(tr[p].l, tr[q].l, l, mid, k);
else return query(tr[p].r, tr[q].r, mid + 1, r, k - cnt);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i ++ )
{
cin >> a[i];
order[i] = i;
}
sort(order + 1, order + 1 + n, [&](int x, int y)
{
if (a[x] != a[y]) return a[x] > a[y];
else return x < y;
});
root[0] = build(1, n);
for (int i = 1; i <= n; i ++ ) root[i] = insert(root[i - 1], 1, n, order[i]);
cin >> m;
while (m -- )
{
int k, pos;
cin >> k >> pos;
cout << a[query(root[0], root[k], 1, n, pos)] << '\n';
}
return 0;
}
D. Cut and Stick
题目链接： D. Cut and Stick
题意：
给定一个序列，多次询问，每个询问给定区间 $[l,r]$ ，求至少将它们分成多少个子序列（不必连续），使得每个子序列中每个相同的数的数量都不超过这个子序列的长度除以 $2$ 上取整。
解题思路：
设某个询问的区间的长度为 $len=r-l+1$ ，出现数量最多的数为 $val$ ，出现了 $mx$ 次，其实就是要求 $mx\leq \lceil \frac{len}{2} \rceil=\lfloor \frac{len+1}{2} \rfloor$ ，假如本身就满足，那么输出 $1$ ；否则需要分成若干个子序列，如果 $mx>\lfloor \frac{len+1}{2} \rfloor$ ，那么就用 $len-mx$ 个其它数以及 $len-mx+1$ 个 $val$ 形成一个子序列，剩下的 $2\times mx-len-1$ 个 $val$ 分别单独成为一个长度为 $1$ 的子序列，总共形成 $2\times mx-len$ 个子序列。
剩下的问题就是如何求出 $[l,r]$ 这个区间内出现最多的数以及出现了多少次了，用一些数据结构如莫队、主席树都可以搞出来，但是这里学到了一个巧妙的方法，就是用随机化来做。
因为我们如果要将这个区间分成多个子序列，那么某个数一定出现了超过这个区间长度的一半的次数，粗略地算 $\frac{1}{2}$ ，假如从这个区间内取 $n$ 次，取不到这个数的概率是 ${\frac{1}{2}}^n$ ，如果 $n$ 取 $40-50$ ，这个概率就非常趋近于 $0$ 了。
再说一下主席树的做法，有一种是常规的主席树上二分求众数的思路，另一种其实可以发现，本题有用的众数要求是出现次数大于 $\lfloor \frac{len+1}{2} \rfloor$ 的，因此如果有这样的数存在，那么这个数肯定也是这个序列的中位数。
随机化代码：
#include <vector>
#include <random>
#include <chrono>
#include <iostream>
#include <algorithm>
using namespace std;
mt19937 rng((unsigned int)chrono::steady_clock::now().time_since_epoch().count());
const int N = 300010;
int get_rand(int d)
{
return rng() % d;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, q;
cin >> n >> q;
vector<int> a(n);
vector<vector<int>> idx(N);
for (int i = 0; i < n; i ++ )
{
cin >> a[i];
idx[a[i]].emplace_back(i);
}
while (q -- )
{
int l, r;
cin >> l >> r;
l -- , r -- ;
int mx = 0, len = r - l + 1;
for (int i = 0; i < 50; i ++ )
{
int val = a[l + get_rand(len)];
int L = lower_bound(idx[val].begin(), idx[val].end(), l) - idx[val].begin();
int R = upper_bound(idx[val].begin(), idx[val].end(), r) - idx[val].begin();
mx = max(mx, R - L);
}
if (mx <= (len + 1) / 2) cout << "1\n";
else cout << 2 * mx - len << '\n';
}
return 0;
}
主席树上二分求区间出现次数超过一半的数：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 300010;
int n, q;
int a[N];
int root[N], idx;
struct Node
{
int l, r;
int cnt;
} tr[N << 5];
void pushup(int u)
{
tr[u].cnt = tr[tr[u].l].cnt + tr[tr[u].r].cnt;
}
int build(int l, int r)
{
int p = ++ idx;
if (l == r) return p;
else
{
int mid = l + r >> 1;
tr[p].l = build(l, mid);
tr[p].r = build(mid + 1, r);
return p;
}
}
int insert(int p, int l, int r, int x)
{
int q = ++ idx;
tr[q] = tr[p];
if (l == r)
{
tr[q].cnt ++ ;
return q;
}
else
{
int mid = l + r >> 1;
if (x <= mid) tr[q].l = insert(tr[q].l, l, mid, x);
else tr[q].r = insert(tr[q].r, mid + 1, r, x);
pushup(q);
return q;
}
}
int query(int p, int q, int l, int r, int len)
{
if (l == r) return tr[q].cnt - tr[p].cnt;
int sum_l = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
int sum_r = tr[tr[q].r].cnt - tr[tr[p].r].cnt;
int mid = l + r >> 1;
int limit = (len + 1) / 2;
if (sum_l <= limit && sum_r <= limit) return 0;
else if (sum_l > limit) return query(tr[p].l, tr[q].l, l, mid, len);
else if (sum_r > limit) return query(tr[p].r, tr[q].r, mid + 1, r, len);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
root[0] = build(1, n);
for (int i = 1; i <= n; i ++ ) root[i] = insert(root[i - 1], 1, n, a[i]);
while (q -- )
{
int l, r;
cin >> l >> r;
int len = r - l + 1;
int cnt = query(root[l - 1], root[r], 1, n, len);
if (cnt <= (len + 1) / 2) cout << "1\n";
else cout << 2 * cnt - len << '\n';
}
return 0;
}
主席树求中位数出现的次数：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 300010;
int n, q;
int a[N];
int root[N], idx;
struct Node
{
int l, r;
int cnt;
} tr[N << 5];
void pushup(int u)
{
tr[u].cnt = tr[tr[u].l].cnt + tr[tr[u].r].cnt;
}
int build(int l, int r)
{
int p = ++ idx;
if (l == r) return p;
else
{
int mid = l + r >> 1;
tr[p].l = build(l, mid);
tr[p].r = build(mid + 1, r);
return p;
}
}
int insert(int p, int l, int r, int x)
{
int q = ++ idx;
tr[q] = tr[p];
if (l == r)
{
tr[q].cnt ++ ;
return q;
}
else
{
int mid = l + r >> 1;
if (x <= mid) tr[q].l = insert(tr[q].l, l, mid, x);
else tr[q].r = insert(tr[q].r, mid + 1, r, x);
pushup(q);
return q;
}
}
int query(int p, int q, int l, int r, int k)
{
if (l == r) return tr[q].cnt - tr[p].cnt;
else
{
int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
int mid = l + r >> 1;
if (cnt >= k) return query(tr[p].l, tr[q].l, l, mid, k);
else return query(tr[p].r, tr[q].r, mid + 1, r, k);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
root[0] = build(1, n);
for (int i = 1; i <= n; i ++ ) root[i] = insert(root[i - 1], 1, n, a[i]);
while (q -- )
{
int l, r;
cin >> l >> r;
int len = r - l + 1;
int cnt = query(root[l - 1], root[r], 1, n, len / 2);
if (cnt <= (len + 1) / 2) cout << "1\n";
else cout << 2 * cnt - len << '\n';
}
return 0;
}
谢谢大佬，学到了
谢谢hh
写的真好
谢谢hh
orz 写得真好 ，很有帮助！~
谢谢hh
提高课属于基础还是高阶算法呢
在基础课的知识都理解了并能够运用模板的前提下，以文中提到的 Codeforces $2000$ 分为目标的话，建议 cover 提高课中以下内容：
一些不算很难，不过这个阶段比较少见的知识：欧拉路径、最近公共祖先、负环、最小生成树、数位 DP 。
好的，谢谢。