搜索结果
查询Tags标签: AcWing,共有 179条记录-
2022.7.24周学习总结
一.本周学习进度1.本周复习了背包模型+单调队列优化DP2.打了两场牛客3.打了一把Atcoder+两把cf 二.本周cf和atcoder情况1.Atcoder261 2.cf809div2 3.cfedu132 三.下周学习计划1.开始狂刷DP章节2.尽量多补一写牛客的题3.CF从1600-2000分的题每天刷两道 四.本周列题总结1.单…
2022/7/24 6:23:51 人评论 次浏览 -
AcWing 2022.7.20
链表模拟 + 队列模拟 可以用队列模拟,维护未弹出的数据和顺序。 也可以直接按题目要求维护循环队列,只需要单链表就够了。 队列: #include <bits/stdc++.h> using namespace std;const int N = 60;int T; int n; int ne[N];int main() {cin >> T;while (T-…
2022/7/20 23:26:29 人评论 次浏览 -
[AcWing 95] 费解的开关
2022/7/12 6:22:20 人评论 次浏览 -
AcWing 356. 次小生成树
分析 这题做法很简单:跑一遍 \(\texttt{MST}\)(最小生成树),把这棵树建立起来,上面的边标记为树边。枚举非树边 \((u, v)\),记边权为 \(w\),考虑这条边能够提供的增量 \(del\)。 具体来说:只需要求出树上 \(u\to v\) 的路径上的边的最大值 \(mx_1\) 和严格次大值 …
2022/7/10 23:54:51 人评论 次浏览 -
[AcWing 321] 棋盘分割
点击查看代码 #include<iostream> #include<cstring> #include<cmath>using namespace std;typedef long long LL;const int N = 10, M = 20; const double INF = 1e9;int n, m = 8; int s[N][N]; double f[N][N][N][N][M]; double xx;int front_sum(in…
2022/7/9 23:20:25 人评论 次浏览 -
[AcWing 1069] 凸多边形的划分
点击查看代码 #include<iostream> #include<cstring>using namespace std;typedef long long LL;const int N = 60, M = 50;int n; int w[N]; LL f[N][N][M];void add(LL a[], LL b[]) {LL c[M];memset(c, 0, sizeof c);LL t = 0;for (int i = 0; i < M; i…
2022/7/9 6:21:37 人评论 次浏览 -
AcWing 工程课 Linux 第一讲 文件管理命令
工程课的概述: 工程的基础:服务器。后端服务器(server)有:Linux、windows等。同一个后端的框架可以同时服务多个应用。市面上90%以上的服务器为Linux服务器。Linux常用的两个版本 :Ubuntu、CentOSLinux也是一种操作系统。 文件系统: 进入根目录后,常见的文件夹:bin:存储…
2022/7/8 5:21:36 人评论 次浏览 -
AcWing 算法提高课 二维单调队列优化dp
单调队列可以求出,区间内的最值。 对于二维的情况,可以先在每一行,用单调队列求出,行方向上的最值。 然后在行方向上的最值的基础上,在每一列,用单调队列求出列方向上的最值。 即可得到二维区间的最值。 例题:1091. 理想的正方形 代码:#include<bits/stdc++.h&…
2022/7/4 1:21:16 人评论 次浏览 -
【图论/基环树】AcWing 392. 会合
分析 这题就是一道需要分类讨论的图论。。 注意到题目中每个点只有一条出边,也就是说给出的图是一个内向的基环树森林。 首先进行预处理:开一个并查集,这能够将两个点不在同一棵基环树的情况筛掉。 利用内向树随便找一个点跳到基环树的环(环上所有点记为“根”)。然后…
2022/7/1 6:49:46 人评论 次浏览 -
2022暑假训练日志01
6月25日 上午恢复手感,写了一下abc256。找到了一个题解,可以补题用。 下午刷了几道题 AcWing 1927. 自动补全 AcWing 1944. 记录保存 AcWing 1842. 牛奶桶 AcWing 2003. 找到牛! AcWing 1788. 牛为什么过马路 晚上就打了一场 abc 6 月 27 日 补了一下前天晚上 abc 的题…
2022/6/29 23:26:31 人评论 次浏览 -
AcWing 100. 增减序列
题目传送门 一、试题分析 因为题意要求,每次都一个区间加上1或者减去1,所以想到了差分。 首先,先对数组\(a\)差分一下,求出差分数组\(b\),接下来我们的任务就是对\(b[2\sim n]\)全部变成\(0\)(所有的数和\(b[1]=a[1]\)一样)即可。 我们对差分序列\(b\)直接操作,因为…
2022/6/28 23:25:10 人评论 次浏览 -
[AcWing 1058] 股票买卖 V
点击查看代码 #include<iostream> #include<cstring> #include<algorithm>using namespace std;const int N = 1e5 + 10;int n; int a[N]; int f[N][3];int main() {cin >> n;for (int i = 1; i <= n; i ++)cin >> a[i];memset(f, -0x3f…
2022/6/24 23:21:34 人评论 次浏览 -
AcWing 199. 余数之和
题目传送门 零、参考资料 总结与思考:数论分块 【数学】数论分块(整除分块) 一、数论分块的相关概念 “数论分块”这个名词,其实比较模糊,没有一个广泛认同的严格定义。这里讲一下我个人的理解: 令\(\displaystyle f(i)=\lfloor \frac{n}{i} \rfloor\) \(f(i)\)的值…
2022/6/18 23:20:56 人评论 次浏览 -
[AcWing 901] 滑雪
记忆化搜索点击查看代码 #include<iostream> #include<cstring>using namespace std;const int N = 310; int n, m; int h[N][N]; int f[N][N]; int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; int dp(int x, int y) {int &v = f[x][y];if (v != -1)…
2022/6/3 23:20:19 人评论 次浏览 -
AcWing 2003. 找到牛!
题意 给定一个括号字符串,连续的两个(可以表示牛的前脚,连续的两个)可以表示牛的后脚,前脚必须在后脚的左侧,求牛的可能位置有几个,牛的可能位置由他的前后脚表示。 数据范围 \(1 \le N \le 50000\) 解题思路正解是\(O(n)\)的做法,记一下当前位置及以前的"((&q…
2022/5/28 23:21:27 人评论 次浏览