搜索结果
查询Tags标签： AcWing，共有 179条记录-
[AcWing 900] 整数划分
类比完全背包 复杂度 \(O(n^{2})\) 总体复杂度 \(1000^{2} = 1 \times 10^{6}\)点击查看代码 #include<iostream>using namespace std; const int N = 1010, mod = 1e9 + 7; int n; int f[N];int main() {cin >> n;f[0] = 1;for (int i = 1; i <= n; i +…
2022/5/24 23:53:03 人评论 次浏览 -
AcWing 903. 昂贵的聘礼
y总做法:建立一个虚拟原点，到所有物品的距离为物品原本价值，物品之间的价值为交易价值，枚举等级范围跑最短路即可 我的做法：以女儿为原点反向建图，物品之间的距离为交易价值，到每个物品的最短路加上这个物品的原本价值即为总花费，取最小 时间复杂度均为O(n^2*logn)…
2022/5/22 23:05:38 人评论 次浏览 -
[AcWing 844] 走迷宫
BFS 使用STL中的queue点击查看代码 #include<iostream> #include<cstring> #include<queue> using namespace std; typedef pair<int, int> PII; const int N = 100 + 10; int n, m; int g[N][N], d[N][N]; queue<PII> q; int bfs() {q.pus…
2022/5/5 6:15:44 人评论 次浏览 -
AcWing 802.区间和
AcWing 802.区间和 题目描述 假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。 现在，我们首先进行 n次操作，每次操作将某一位置 x 上的数加 c。 接下来，进行 m次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。 输入格式 第一行包…
2022/5/4 23:16:13 人评论 次浏览 -
[acwing]第1天
2.1.3 BFS中的双向广搜和A-star：https://www.acwing.com/video/455/ ps：为了督促自己学习新算法，开启每日acwing，如果顺利的话，暑假前可以把提高课刷完，然后暑假继续学习进阶课，学习过程中可以顺便看oiwiki，其他的算法学习方式感觉就没必要了，先把acwing搞定再说…
2022/5/4 6:13:57 人评论 次浏览 -
[AcWing 841] 字符串哈希
点击查看代码 #include<iostream>using namespace std; typedef unsigned long long ULL; const int N = 1e5 + 10; const int P = 131; int h[N], p[N]; char str[N]; ULL get(int l, int r) {return h[r] - h[l - 1] * p[r - l + 1]; } int main() {int n, m;cin …
2022/5/3 23:12:54 人评论 次浏览 -
[AcWing 3302] 表达式求值
点击查看代码 #include<iostream> #include<stack> #include<cstring> #include<unordered_map>using namespace std;stack<int> nums; stack<char> op; unordered_map<char, int> h{ {+, 1}, {-, 1}, {*, 2}, {/, 2} }; void …
2022/4/30 6:14:57 人评论 次浏览 -
[AcWing 829] 模拟队列
点击查看代码 #include<iostream>using namespace std; const int N = 1e5 + 10; int q[N]; int l = 0, r = 0; void push(int x) {q[r] = x;r ++; } void pop() {l ++; } bool empty() {return l == r; } int query() {return q[l]; } int main() {int m;cin >&…
2022/4/30 6:14:37 人评论 次浏览 -
AcWing 854. Floyd求最短路
模板题 解释一下第36行 判断两点间是否有路径 为什么是 INF/2 而不是INF？ 题目所说“边权可能为负数”，虽然我们可能无法到达那个点，但是那个点的权值可能会被更新掉。如图所示 因为4到5的边权值为负的，那么1到5的距离是INF，这个点可能经过了4，也就是经过了负边，到…
2022/4/29 23:18:48 人评论 次浏览 -
AcWing 456. 车站分级 拓扑排序
车站分级 今日份DAG呈上 题目 https://www.acwing.com/problem/content/458/ 思路 题意：同一趟车次内，停靠的车站\(a\)的等级严格大于未停靠的车站\(b\)的等级 所以可以根据\(a>b\)来建边（即，所有未停靠站建边指向所有停靠站） 优化：对于两个点集之间，可以在中间…
2022/4/27 23:42:52 人评论 次浏览 -
[AcWing 790] 数的三次方根
点击查看代码 #include<iostream>using namespace std;int main() {double x;scanf("%lf", &x);double l = -1e5, r = 1e5;while (r - l > 1e-8) {double mid = (l + r) / 2;if (x <= mid * mid * mid) r = mid;else l = mid;}printf(&quo…
2022/4/25 6:17:32 人评论 次浏览 -
[AcWing 35] 反转链表
点击查看代码 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:ListNode* reverseList(ListNode* head) {if (!head || !head->next) …
2022/4/22 6:16:43 人评论 次浏览 -
AcWing 2. 01背包问题（01背包）
题目链接题目描述 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi，价值是 wi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。 题目模型01背包：每个物品只能选或不选 集合表示：f(i，…
2022/4/21 23:17:56 人评论 次浏览 -
Floyd
#include <bits/stdc++.h> using namespace std; const int N = 210, INF = 0x3f3f3f3f; int d[N][N], n, m, q; void Floyd(){for (int k = 1; k <= n; k ++ )for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )d[i][j] = min(d[i][j], d[i][…
2022/4/19 6:16:07 人评论 次浏览 -
AcWing 【算法提高课】笔记02——搜索
搜索进阶 22.4.14 (PS：还有 字串变换 A*两题 生日蛋糕 回转游戏 没做) 感觉暂时用不上 BFS 1. Flood Fill在线性时间复杂度内，找到某个点所在的连通块 思路 统计连通块个数（多个连通块）：逮着一个就开搜 连通性问题（能走多远，迷宫性问题，一个连通块）；起点…
2022/4/14 14:13:08 人评论 次浏览
