勤劳努力的小蜜蜂

A. Letter Song ~ 致十年后的我们 处理出来年份，\(+10\) 后输出 code: 1234567891011121314151617181920#include <bits/stdc++.h>using namespace std;string s;int main(){ cin >> s; int x = 0; for (int i = 0; i < 4; i++) x = x * 10 + s[i] - '0'; x += 10; cout << x; for (int i = 4; i < s.size(); i++) cout << s[i]; return 0;} B. 简单图形问题 - 0123 手动模拟可以发现，边长为整数的等边三角形面积不可能是整数，因此只需要判断 \(s\) 是否是平方数即可 code: 123456789101112131415161718192021222324252627282930#in ...

A. Soccer 只有一种情况会导致两队的分持平，就是前后两队比分出现反超 code: 123456789101112131415161718192021222324252627282930313233#include <bits/stdc++.h>#define int long long#define x first#define y second#define endl '\n'using namespace std;typedef pair<int, int> PII;const int N = 200010;int T;int n;int x1, yl, x2, y2;signed main(){ ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> T; while (T--) { cin >> x1 >> yl >> x2 >> y2; ...

A. Zhan's Blender 搅拌机一秒最多能搅拌 \(min(x,c)\) 个水果，因此搅拌的总时间为 \(\lceil\frac{n}{min(x,c)}\rceil\) code: 1234567891011121314151617181920212223242526272829303132#include <bits/stdc++.h>#define int long long#define x first#define y second#define endl '\n'using namespace std;typedef pair<int, int> PII;const int N = 200010;int T;int n, x, y;signed main(){ ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> T; while (T--) { cin >> n & ...

ST 表 (Sparse Table，稀疏表) 主要用来解决 \(RMQ\) (区间最大/最小值查询)问题。应用倍增思想，可以实现 \(O(nlogn)\) 预处理、\(O(logn)\) 查询。 预处理 ST 表 倍增法递推：用两个等长的小区间组合成大区间 以区间最大值为例：\(f[i][j]\) 表示以第 \(i\) 个数为起点，长度为 \(2^j\) 的区间最大值 \(f[i][j]=max(f[i][j-1],f[i+2^j-1][j-1])\) 查询 对查询区间 \([l,r]\) 进行分割 设 \(k=log_2(r-l+1)\) 则区间 \([l,r]\) 可以分割成 \([l,l+2^k-1]\) 和 \([r-2^k+1,r]\)，用预处理的 \(f\) 数组进行查询即可，中间的重叠部分无需理会 例题 Luogu P3865 【模板】ST 表 && RMQ 问题 题目描述 给定一个长度为 \(N\) 的数列，和 \(M\) 次询问，求出每一次询问的区间内数字的最大值。 输入格式 第一行包含两个整数 \(N,M\)，分别表示数列的长度和询问的个数。 第二 ...

A. Simple Palindrome 可以发现，两个相同的字母产生的回文子串与它们之间间隔的字母个数有关，因此考虑把 \(n\) 个字母分配给 \(aeiou\)，并且相同的元素相邻 code: 123456789101112131415161718192021222324252627282930313233343536373839#include <bits/stdc++.h>#define int long long#define x first#define y secondusing namespace std;typedef pair<int, int> PII;const int N = 200010;int T;int n;int a[N];signed main(){ cin >> T; while (T--) { cin >> n; string s = "aeiou"; int x = n / 5, ...

A. Catch the Coin 不难发现，只有硬币的 \(y\) 坐标大于等于 \(-1\) 时，\(Monocarp\) 才有可能收集到该硬币 code: 123456789101112131415161718192021222324252627#include <bits/stdc++.h>#define x first#define y secondusing namespace std;typedef pair<int, int> PII;const int N = 200010;int T;int x, y;signed main(){ cin >> T; while (T--) { cin >> x >> y; if (y >= -1) cout << "YES" << endl; else cout << "NO" << ...

缩点 每个环都缩成一个点，把有环图变为无环图 变量 \(scc[u]\)，节点 \(u\) 所在环的编号 例题 Luogu P3387 【模板】缩点 题目描述 给定一个 \(n\) 个点 \(m\) 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。 允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。 输入格式 第一行两个正整数 \(n,m\) 第二行 \(n\) 个整数，其中第 \(i\) 个数 \(a_i\) 表示点 \(i\) 的点权. 第三至 \(m + 2\) 行，每行两个整数 \(u,v\)，表示一条 \(u→υ\) 的有向边。 输出格式 共一行，最大的点权之和。 数据范围 \(1 \leq n < 10^4, \ 1 \leq m \leq 10^5, \ 0 \leq a_i < 10^3\) code: 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535 ...

强连通 若一张有向图的节点两两互相可达，则称这张图是强连通的。 强连通分量(Strongly Connected Components，SCC)： 极大的强连通子图。 搜索树： 对图深搜时，每一个节点只访问一次，被访问过的节点与边构成搜索树。 有向边按访问情况分 4类: 树边(tree edge):访问节点走过的边。图中的黑色边。 返祖边(back edge):指向祖先节点的边。图中的红色边。 横叉边(cross edge):右子树指向左子树的边。图中的绿色边。 前向边 (forward edge):指向子树中节点的边，图中的蓝色边。 边返祖边与树边必构成环，横又边可能与树边构成环。前向边无用 如果节点 \(u\) 是某个强连通分量在搜索树中遇到的第一个节点，那么这个强连通分量的其余节点肯定是在搜索树中以 \(u\) 为根的子树中。节点 \(u\) 被称为这个强连通分量的根。 tarjan算法 变量 时间戳 \(dfn[u]\)，节点 \(u\) 第一次被访问的顺序 追溯值 \(low[u]\)，从节点 \(u\) 出发，能访问到的最小时间戳 判断栈中元素 \(instk[ ...

可持久化线段树是支持访问历史版本的线段树 内存空间 初始建树需开 \(2n-1\) 个节点，\(n\)次修改，每次修改最多开 \(logn+1\) 个节点，所以节点总数为 \(2n-1+n(logn+1)\) 动态开点 不再用 \(u<<1\)和\(u<<1|1\) 记录左儿子和右儿子，而是使用 \(ls[u]\) 和 \(rs[u]\) 来表示，每个版本的根节点用 \(root\) 数组来维护 例题 Luogu P3919 【模板】可持久化线段树 1（可持久化数组） 有了可持久化数组，便可以实现很多衍生的可持久化功能 题目描述 如题，你需要维护这样的一个长度为 \(N\) 的数组，支持如下几种操作 在某个历史版本上修改某一个位置上的值 访问某个历史版本上的某一位置的值 此外，每进行一次操作(对于操作2，即为生成一个完全一样的版本，不作任何改动)，就会生成一个新的版本。版本编号即为当前操作的编号(从1开始编号，版本0表示初始状态数组) 输入格式 输入的第一行包含两个正整数 \(N,M\)，分别表示数组的长度和操作的个数。 第二行包含 \(N\) 个整数，依次 ...