勤劳努力的小蜜蜂

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\) 个整数，依次 ...

A. Only Pluses 每次操作选择一个数 \(+1\)，执行五次，使得 \(a*b*c\) 最大，只需要在每次操作对 \(a,b,c\) 中最小的一个 \(+1\) 即可 code: 1234567891011121314151617181920212223242526272829303132#include <bits/stdc++.h>#define x first#define y second#define int long longusing namespace std;typedef pair<int, int> PII;const int N = 200010;int T;int a[3];signed main(){ cin >> T; while (T--) { for (int i = 0; i < 3; i++) cin >> a[i]; for (int i = 0; i < 5; i++) { ...

A. Submission Bait 博弈 当最大数的数量是奇数时，第一个选择最大数是必胜的，因此 \(Alice\) 先手选择最大数即为必胜策略 当最大数的数量是偶数时，第一个选择最大数是必败的，因此两人都要避免第一个选择最大数，这时可以考虑选择次大数，可以发现，当次大数的数量为奇数时，先手拿次大数的人会后手拿最大数，反之会先手拿最大数 从后往前递推，可以发现，当存在一个数的数量是奇数时，先手必胜，否则先手必败 code: 123456789101112131415161718192021222324252627282930313233343536#include <bits/stdc++.h>#define x first#define y second#define int long longusing namespace std;const int N = 200010;int T;int n;int a[N];signed main(){ cin >> T; while (T--) { cin & ...

A. Minimize! 输出\(b-a\)即可 code: 123456789101112131415161718#include <bits/stdc++.h>using namespace std;int T;int a, b;int main(){ cin >> T; while (T--) { cin >> a >> b; cout << b - a << endl; } return 0;} B. osu!mania 从下到上，从左到右遍历字符串，输出每个\(\#\)在当前行的位置 code: 123456789101112131415161718192021222324252627#include <bits/stdc++.h>using namespace std;const int N = 510;int T;int n;string s[N];int main(){ ci ...

A. 会赢吗？ 签到，比大小 code: 123456789101112131415#include <bits/stdc++.h>using namespace std;double a, b;int main(){ cin >> a >> b; if (a < b) cout << "YES" << endl; else cout << "NO" << endl; return 0;} B. 能做到的吧 判断是否有\(i,j\)满足\(1<=i<j<=n\)，并且\(s[i]<s[j]\)，如果有就输出\(YES\)，否则输出\(NO\) code: 1234567891011121314151617181920212223242526272829303132#include <bits/stdc++.h>using namespace std;int T;s ...

A. Dora's Set 要使三个数互质，那么一定是两个奇数\(+\)一个偶数，因此遍历\(l\)到\(r\)，每次删除相邻的奇偶奇序列即可 code: 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include <bits/stdc++.h>#define int long longusing namespace std;int T;int n, m;signed main(){ cin >> T; while (T--) { cin >> n >> m; int res = 0; while (n <= m) { if (n % 2 == 0) n ...