搜索结果
查询Tags标签： AcWing，共有 179条记录-
【算法】AcWing 870. 约数个数
题 算法思想 约束的个数都加一，然后全部乘在一起。 代码： 学到了unordered_map 因为x在循环过程中会变小，所以可能x还没被完全分解就退出循环了，所以要有if(x>1)那个判断。 #include<iostream> #include<unordered_map> #define LL long long int us…
2021/5/30 1:27:45 人评论 次浏览 -
《算法竞赛进阶指南》 第二章 Acwing 139. 回文子串的最大长度
地址 https://www.acwing.com/problem/content/141/ 如果一个字符串正着读和倒着读是一样的，则称它是回文的。 给定一个长度为 N 的字符串 S，求他的最长回文子串的长度是多少。输入格式 输入将包含最多 30 个测试用例，每个测试用例占一行，以最多 1000000 个小写字符的…
2021/5/18 14:28:00 人评论 次浏览 -
[Acwing算法基础] 2.1 dfs暴力搜索
dfs深度优先搜索分析方法 dfs最重要的使搜索顺序。即使用什么顺序搜索遍历所有方案。以例题842. 排列数字 按照图中所示的顺序对所有方案进行遍历。 算法： 用 path 数组保存排列，当排列的长度为 n 时，是一种方案，输出。用 st 数组表示数字是否用过。当 state[i] 为 1…
2021/5/17 20:55:59 人评论 次浏览 -
[Acwing] 双最长上升子序列 登山
https://www.acwing.com/problem/content/1016/ 题意:你可以连续的上山然后可以连续的下山, 下山了就不能再上山 问你最多浏览的爬山数思路+问题抽象问题抽象: 就是让你在一堆数里面 挑选最长的上升子序列+最长的下降子序列 的最大值思路 因此我们可以将答案分成1~n个区间…
2021/5/13 18:29:07 人评论 次浏览 -
Acwing - 算法基础课 - 笔记（四）
文章目录 数据结构（一）链表栈和队列单调栈单调队列 KMP算法数据结构（一） 本节讲解的是 链表与邻接表栈与队列看毛片（kmp）算法 链表 使用数组模拟单链表，双链表 使用数组模拟的链表，为静态链表，对单链表，开2个数组，其中1个用来存每个链表节点的值，另1个数组用来…
2021/5/11 20:28:54 人评论 次浏览 -
AcWing 346. 走廊泼水节
原题链接 考察:最小生成树 思路:本题要求完成图的最小生成树依旧是原树.考虑Kruskal算法,每次都是选择当前边两端合并为一个集合,我们要保证为完全图的话需要让左右端点的集合两两之间连一条边,同时保证原树的边是当前集合最小的边.因为原边不能代替所以考虑取road[i].w+1…
2021/5/4 18:27:27 人评论 次浏览 -
AcWing 345. 牛站
原题链接 考察:Floyd+矩阵快速幂 思路:前面讲过Floyd算法的第一层循环是i~j的最短路,经过1~k的结点.在这里我们将Floyd的dp状态表示f[k,i,j].假设i经过a条边到达S, f[k,i,j] = f[a,i,S]+f[k-a,S,j] 我们可以发现前a条边的路径与后面的路径不相干,所以我们可以这么写.然后…
2021/5/3 10:26:48 人评论 次浏览 -
AcWing算法提高课【第二章搜索】最短路模型
1076. 迷宫问题 分析：将st数组改为pair类型，记录每个格子从那一步回来，从终点反推。代码：1 #include <cstdio>2 #include <cstring>3 #include <algorithm>4 5 using namespace std;6 7 typedef pair<int, int> PII;8 9 #define x first 10 …
2021/4/25 12:55:08 人评论 次浏览 -
AcWing算法提高课【第四章高级数据结构】并查集
1250. 格子游戏 分析：显然，当出现闭环的时候，就会出现我们当前节点和要到达的节点出现一个闭环 代码：1 #include <bits/stdc++.h>2 3 using namespace std;4 5 const int N = 210;6 7 int n, m;8 int g[N][N], tot;9 int f[N * N]; 10 11 int get(int x) 12 {…
2021/4/24 20:25:32 人评论 次浏览 -
【二维前缀和】AcWing 796.子矩阵的和
输入一个 n 行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。 对于每个询问输出子矩阵中所有数的和。 输入格式 第一行包含三个整数 n，m，q。 接下来 n 行，每行包含 m 个整数，表示整数矩阵。 接下来 …
2021/4/24 10:57:08 人评论 次浏览 -
数位DP - AcWing 338 - 计数问题
数位DP - AcWing 338 - 计数问题 注意前导0的影响 #include <bits/stdc++.h> using namespace std;int a, b; int num[10]; int dp[10][10]; // 当前填位i,tar数已经出现的次数j int dfs(int i, int j, int flag, int first, int tar){if(!i) return j;if(!flag &am…
2021/4/19 10:56:27 人评论 次浏览 -
AcWing算法提高课【第一章动态规划】数字三角形
摘花生 Hello Kitty想摘点花生送给她喜欢的米老鼠。 她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。 地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。 Hello Kitty只能向东或向南走，…
2021/4/13 12:25:11 人评论 次浏览 -
AcWing 连续子数组的最大和 Python O(n)解法
连续子数组的最大和 Python O(n)O(n)O(n)解法 题目 题目链接：https://www.acwing.com/problem/content/description/50/ 题目描述 输入一个非空整型数组,数组里的数可能为正,也可能为负。 数组中一个或连续的多个整数组成一个子数组。 求所有子数组的和的最大值。 要求时…
2021/4/8 20:29:17 人评论 次浏览 -
AcWing刷题——最长公共上升子序列（动态规划 线性DP 前缀和）
题目描述 熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。 小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们研究最长公共上升子序列了。 小沐沐说，对于两个数列 A 和 B ，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，…
2021/4/8 18:55:49 人评论 次浏览
