搜索结果
查询Tags标签： AcWing，共有 179条记录-
AcWing 1902. 马拉松
题目链接 每次路程改变只对前后两点间距离有影响，因此每次都判断当前三个点之间的距离之和与去掉中间点的距离哪个更优即可，最后取最大值作为结果输出。 #include<iostream> #include<cmath>using namespace std;const int N = 100010;int x[N], y[N];int d…
2022/4/13 23:22:50 人评论 次浏览 -
AcWing第8场周赛题解
A. 3770. 最小消耗 题目链接：https://www.acwing.com/problem/content/description/3773/ 题目大意：按照题目要求消灭两种类型怪兽（可以消耗 c 转换）的最小消耗。 解题思路：循环记录 0 和 1 出现的次数，消灭一个 0 的最小消耗为 min(a, b+c)，消灭一个 1 的最小消耗…
2022/4/9 6:20:41 人评论 次浏览 -
AcWing 10. 有依赖的背包问题
题目链接 https://www.acwing.com/problem/content/10/ 题解 需要注意的点就是，f[u][j]实际上是优化过第第二维后的状态表示，原状态表示应该是f[u][i][j]：对于根结点u，考虑其前i个子树，总体积不超过j的最大价值 dfs(root)的递归含义是：以root为根，考虑其所有子树，…
2022/4/4 23:19:08 人评论 次浏览 -
Acwing_4394 最长连续子序列
题目来自：https://www.acwing.com/problem/content/4397/ 笔者做的时候想着能不能去动态调整记录表，但最终的简化策略其实是往维护双指针区间上面靠的，以下是答案代码； 循环再动态维护一个从l到r的区间，将移动过的地方取消标记并判断是否产生 异值 数量的变化，对于向…
2022/4/3 0:03:44 人评论 次浏览 -
AcWing 1047. 糖果
题目链接题目描述： 由于在维护世界和平的事务中做出巨大贡献，Dzx被赠予糖果公司2010年5月23日当天无限量糖果免费优惠券。 在这一天，Dzx可以从糖果公司的 N 件产品中任意选择若干件带回家享用。 糖果公司的 N 件产品每件都包含数量不同的糖果。 Dzx希望他选择的产品包含…
2022/4/2 23:21:15 人评论 次浏览 -
[Acwing蓝桥杯数学知识] 扩展欧几里得线性同余方程
扩展欧几里得用于求解方程 ax+by=gcd(a,b)的解 当 b=0时 ax+by=aax+by=a 故而 x=1,y=0x=1,y=0当 b≠0 时因为gcd(a,b)=gcd(b,a%b) 而bx′+(a%b)y′=gcd(b,a%b) bx′+(a−⌊a/b⌋∗b)y′=gcd(b,a%b)ay′+b(x′−⌊a/b⌋∗y′)=gcd(b,a%b)=gcd(a,b)故而x=y′,y=x′−⌊a/b⌋…
2022/3/31 6:23:55 人评论 次浏览 -
AcWing 113. 特殊排序（交互题）
有 N 个元素，编号 1,2..N，每一对元素之间的大小关系是确定的，关系具有反对称性，但不具有传递性。 注意：不存在两个元素大小相等的情况。 也就是说，元素的大小关系是 N 个点与 N(N−1)/2 条有向边构成的任意有向图。 然而，这是一道交互式试题，这些关系不能一次性得…
2022/3/30 23:21:14 人评论 次浏览 -
Acwing单调栈
1 题目描述 2 思路 1.用一个栈保存当前元素以前的序列，栈用一个数组来表示 2.栈中序列是单调递增的 当i<=j a[i]>=a[j]时,delete(a[i]) 保证剩余的序列一定是单调的 3 代码 package chapter02;import java.io.IOException; import java.util.Scanner;/*** @author…
2022/3/21 23:33:19 人评论 次浏览 -
背包四讲 (AcWing算法基础课笔记整理)
背包四讲背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在…
2022/3/18 22:28:05 人评论 次浏览 -
acwing-特别数的和
小明对数位中含有 2、0、1、92、0、1、9 的数字很感兴趣（不包括前导 00），在 11 到 4040 中这样的数包括 1、2、9、101、2、9、10 至 32、3932、39 和 4040，共 2828 个，他们的和是 574574。 请问，在 11 到 nn 中，所有这样的数的和是多少？ 输入格式 共一行，包含一个…
2022/3/6 23:16:24 人评论 次浏览 -
acwing 4310. 树的DFS
目录题目描述输入格式输出格式数据范围输入样例：输出样例：dfs算法求解分析代码时间复杂度参考文章 题目传送门 题目描述给定一棵 nn 个节点的树。 节点的编号为 1∼n1∼n，其中 11 号节点为根节点，每个节点的编号都大于其父节点的编号。 现在，你需要回答 qq 个询问。 …
2022/3/5 23:20:00 人评论 次浏览 -
AcWing 847. 图中点的层次| 学习图存储
目录题目描述输入格式输出格式数据范围输入样例：输出样例：图的链表存储+ bfs算法求解分析图的链表存储图的邻接矩阵存储代码时间复杂度参考文章 题目描述给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。 所有边的长度都是 1，点的编号为 1∼n。 请你求出 1 号…
2022/2/26 23:28:45 人评论 次浏览 -
acwing数论笔记
筛法求质数时间复杂度 质数定理:1-n中有n/(lnn)个质数 线性筛
2022/2/23 6:23:42 人评论 次浏览 -
Acwing 170. 加成序列(迭代加深算法)
170. 加成序列 - AcWing题库 以1开头以n结尾，且每个数是前面任意两数之和的序列的最短长度 这里迭代加深的层数实际上就是序列的长度，由于求的是最短长度，正好就是迭代加深的目的（解在比较浅的层）在处理第u个数时，从前u-1个数找两数之和，由于序列是递增的，…
2022/2/20 14:26:35 人评论 次浏览 -
【模拟】AcWing 155. 内存分配
有点毒瘤的模拟。 我用 \(\texttt{set}\) 乱搞编写了一个数据结构来维护，发现比很多人的代码跑得快，甚至在洛谷最优解前列，但是码量大了不少。 分析 实现的思路比较明显：记一共有 \(m\) 个进程。我们从 \(1\to m\) 枚举每个进程并进行处理。 在处理到第 \(i\) 个…
2022/2/17 7:13:12 人评论 次浏览
