搜索结果
查询Tags标签： AcWing，共有 179条记录-
AcWing算法提高课 最小生成树
一般使用kruskal(克鲁斯卡尔)(mlogm) 对于稀疏图，用朴素prim(n^2) prim:每次选择和当前已经构建出的连通块相连，且权重最小的边，加入当前连通块。 一共需要扩展(n-1)次 kruskal:基于并查集。先将所有边从小到大排序，然后枚举每条边，如果边的两个端点还不联通，则将当…
2022/9/14 1:19:09 人评论 次浏览 -
AcWing 860.染色法判断二分图
题目链接：https://www.acwing.com/problem/content/862/ 放AC代码1 #include<bits/stdc++.h>2 using namespace std;3 const int N = 1e5+10, M = 2e5+10;//因为是无向图所以边的数量*24 int e[M], ne[M], h[N], cnt;5 int color[N];6 7 void add(int u, int v)8 {…
2022/9/8 23:54:37 人评论 次浏览 -
[AcWing 258] 石头剪刀布
带扩展域的并查集点击查看代码 #include<bits/stdc++.h>using namespace std;typedef long long LL;const int N = 1e6 + 10;int n, m; int p[N];struct Node {int a, b;char op; } s[N];int find(int x) {if (p[x] != x)p[x] = find(p[x]);return p[x]; }void merg…
2022/8/16 23:29:46 人评论 次浏览 -
[AcWing 3409] 这是一棵树吗
点击查看代码
2022/8/16 23:24:27 人评论 次浏览 -
AcWing-4507. 子数组异或和
异或的一个性质：如果对一个数异或了两次就相当于不异或。 所以我们可以用前缀和预处理 \(a[i]\oplus =a[i-1]\) \(i\) 至 \(j\) 的异或和为 \(a[j]\oplus a[i-1]\) 该连续子数组的前一半元素的异或和等于其后一半元素的异或和。 即该连续子数组的异或和为 \(0\) 。 暴力的…
2022/8/13 23:28:40 人评论 次浏览 -
AcWing 798. 差分矩阵
二维差分 我们已经知道了一维差分如何去做，那么如果扩展到二维呢？这里就要引入二维差分了。 定义给定一个数组 \(a\)，构造一个数组 \(b\)，使得 \(a\) 数组是 \(b\) 数组的前缀和数组，那么称 \(b\) 数组是 \(a\) 数组的差分数组。作用在 \(O(1)\) 的复杂度内将原矩阵中…
2022/8/11 6:26:53 人评论 次浏览 -
[AcWing 340] 通信线路
二分 + 双端队列广搜 复杂度 \(m \cdot log(r - l) = 1 \times 10^4 \times log(10^9) = 3 \times 10^5\)点击查看代码 #include<bits/stdc++.h>using namespace std;typedef long long LL;const int N = 1e6 + 10; const int M = 1e3 + 10; const int INF = 0x3f3f…
2022/8/11 6:23:01 人评论 次浏览 -
[AcWing 1127] 香甜的黄油
选一个起点，到其他点的最短距离之和最小 堆优化 dijkstra （太慢） 复杂度 \(O(n \cdot log(m) \cdot p) = 500 \times log(1450) \times 800 = 1.2 \times 10^7\)点击查看代码 #include<bits/stdc++.h>using namespace std;typedef long long LL; typedef pair<…
2022/8/9 23:22:46 人评论 次浏览 -
AcWing算法基础课 手写哈希表
开放地址法 M一般是N的十倍左右 find用于查找，看返回值是否为INF find用于插入，直接将待插入的值放到find返回的位置 会比unordered_set快5-10倍。
2022/8/9 1:25:26 人评论 次浏览 -
[AcWing 197] 阶乘分解
点击查看代码 #include<bits/stdc++.h>using namespace std;typedef long long LL;const int N = 1e6 + 10;int n; vector<int> primes; bool st[N];void get_primes(int x) {for (int i = 2; i <= x; i ++) {if (!st[i])primes.push_back(i);for (auto p …
2022/8/8 6:25:25 人评论 次浏览 -
Acwing 1053 修复DNA
Acwing 1053 修复DNA 题意: 给出\(n\)个字符串，这些字符串为致病因子，给出一个字符串，求将这些字符串处理成没有致病因子，最少需要改变多少个字符数量 请问，其中有多少个单词在文章中出现了。 思路: 利用AC自动机来实现多字符串匹配，设f[i][j]为，前i个字符，当前匹…
2022/8/7 23:27:51 人评论 次浏览 -
Acwing 1282 搜索关键词
Acwing 1282 搜索关键词 题意: 给定 \(n\) 个长度不超过 \(50\)的由小写英文字母组成的单词，以及一篇长为\(m\)的文章。 请问，其中有多少个单词在文章中出现了。 思路: AC自动机模板题目 但是由于匹配到的是和当前的的字符串最长的字符位置，但是可能里面包含则其他单词…
2022/8/7 23:26:24 人评论 次浏览 -
[AcWing 179] 八数码
A* 算法点击查看代码 #include<bits/stdc++.h>using namespace std;typedef long long LL; typedef pair<int,string> PIS;const int N = 1e6 + 10;string start; int dx[] = {-1, 0, 1, 0}; int dy[] = {0, 1, 0, -1}; char op[] = {u, r, d, l};int f(strin…
2022/8/7 23:23:47 人评论 次浏览 -
Acwing 3540.二叉搜索树（指针+前中后序遍历）
https://www.acwing.com/problem/content/description/3543/ 输入一系列整数，利用所给数据建立一个二叉搜索树，并输出其前序、中序和后序遍历序列。输入格式 第一行一个整数 n，表示输入整数数量。第二行包含 n 个整数。输出格式 共三行，第一行输出前序遍历序列，第二行…
2022/8/4 23:27:24 人评论 次浏览 -
Acwing 798.差分矩阵
题目链接：https://www.acwing.com/problem/content/800/ 要睡觉了今早要早起，今晚再写关于二位差分的内容吧 放AC代码1 #include<bits/stdc++.h>2 using namespace std;3 int a[1005][1005],b[1005][1005];//a前缀和数组，b差分数组4 int n,m,q;5 6 void insert(…
2022/7/26 6:52:58 人评论 次浏览
