Acwing
AcWing 903. 昂贵的聘礼 (超级源点 + 等级限制 + 抽象建图
package 算法提高课; import java.util.Arrays; import java.util.Scanner; public class acw903 { static int m, n; static int[] dis, level; static boolean[] st; ......
AcWing 180. 排书 (IDA*算法 = A* + 迭代加深, 感觉其实之所以IDA*可以过就是因为利用迭代加深和估价函数做了一步类似于剪枝的操作
要是有疑问就再看一遍视频 package 算法提高课; import java.util.Arrays; import java.util.Scanner; public class acw180 { static Scanner sc = new Scanner(System.in); stati ......
对acwing193的解释
首先是估价函数的解释 由于\(x\)较大，所以\(x\)一直平方是最快的能到达\(p\)及以上的方法，所以这个估价函数比实际代价小（或等） 再看\(gcd\)这个剪枝 把八种情况列出，如果\(x\)和\(y\)都是\(gcd=d\)的倍数，那么加减或翻倍之后的新的\(x\)和\(y\)一定也是\(d ......
acwing 第 130 场周赛 (前缀和，dfs，对不同边的处理)
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<climits> using namespace std; typedef long long LL; const int N = 5 ......
AcWing 算法基础课week 1 总结(万字长文)
AcWing 算法基础课week 1 总结 总结点 1：快速排序（分治思想） 题1：从小到大排序 主体思路：定义一个数x属于数组s，利用双指针，将数组分为大于等于x和小于等于x的两部分，然后递归处理。（具体步骤如下） 1. 如上图所示，我们定义一个数组s用来储存n个数据，然后定义两个指针i j,分别 ......
AcWing 768. 忽略大小写比较字符串大小
题目链接： #include <iostream> using namespace std; string get(string s) { string res; for (auto c : s) res += tolower(c); return res; } int main() { strin ......
Acwing.第130场周赛
Acwing.第130场周赛 比赛链接 A.最大数和最小数 题目链接 思路： 简单模拟，使用max()和min()函数就可以了 代码： #include<bits/stdc++.h> using namespace std; void solve(){ int a,b,c; cin>>a>>b>>c ......
AcWing 1017. 怪盗基德的滑翔翼——最长上升子序列
最长上升子序列 1、\(O(n^{2})\) 简单DP做法 \[dp[i]=\max_{h[j] < h[i]} [dp[j] + 1] \]#include<bits/stdc++.h> using namespace std; const int N = 105; int h[N]; int d ......
acwing276机器任务的证明
假设我们已经给每一个任务分配了一种模式了 那么相同模式的任务排在一起的时候肯定重启次数最小 对涉及到的模式，我们还原回二分图上 就是在二分图上尽量选择少的节点（一种模式代表一次重启次数，因为相同模式都是放在一起的），使每一个任务都可以被安排 就可以转换为最小点覆盖问题 ......
acwing374导弹防御塔分析
二分是怎么想到的？ 我们假设已经找到了最终的方案，那么每一座防御塔都被分到了一些敌人去攻击 那么这个方案的时间是多少呢？就是每个防御塔的时间的最大值 每个防御塔的时间是他所分配的这些敌人里面所需要花费最长的时间去攻击的敌人的时间 相当于最大值最小，所以想到二分 acwing上的打卡代码换了一种实现方 ......
AcWing785
AcWing785. 快速排序 一、题目描述 给定你一个长度为 n的整数数列。 请你使用快速排序对这个数列按照从小到大进行排序。 并将排好序的数列按顺序输出。 输入格式 输入共两行，第一行包含整数 n。 第二行包含 n 个整数（所有整数均在 1∼1091∼109 范围内），表示整个数列。 输出格式 ......
ACwing 334 K匿名序列
首先这道题很容易发现如果已经知道了最后的答案序列，那么操作顺序是无所谓的 所以我们可以假设从头操作到尾 由于题目给的是非严格递增序列，我们猜想最后的答案一定是一段一段的，段与段之间单调递增 比如1 1 1 2 2 2 2 2 3 3 4 5 5 反证：如果最终的答案序列存在\(a_{i}\)和\(a ......
Acwing.第 129 场周赛
Acwing.第 129 场周赛 比赛地址 A.字符串 题目 思路: 只需要用到reverse()反转函数就可以 代码: #include<bits/stdc++.h> using namespace std; void solve(){ string s; cin>>s; reverse(s.be ......
AcWing785
AcWing785. 快速排序 一、题目描述 给定你一个长度为 n的整数数列。 请你使用快速排序对这个数列按照从小到大进行排序。 并将排好序的数列按顺序输出。 输入格式 输入共两行，第一行包含整数 n。 第二行包含 n 个整数（所有整数均在 1∼1091∼109 范围内），表示整个数列。 输出格式 ......
AcWing785
AcWing785. 快速排序 一、题目描述 给定你一个长度为 n 的整数数列。 请你使用快速排序对这个数列按照从小到大进行排序。 并将排好序的数列按顺序输出。 输入格式 输入共两行，第一行包含整数 n。 第二行包含 n 个整数（所有整数均在 1∼1091∼109 范围内），表示整个数列。 输出格式 ......
快速排序——acwing算法基础课笔记
课堂内容+个人思考，个人笔记，但是欢迎补充、批评、指正。 快速排序基于分治的思想 平均时间复杂度O（nlogn） 已知数组q[] 步骤： 1、确定分界点（x）： （1）首元素q[l]; （2）尾元素q[r]; （3）中值q[(l+r)/2]; (4)随机; 2、调整区间 将区间通过x值划分为两部分（ ......
Acwing.第128场周赛
Acwing.第128场周赛 比赛地址 A长方体 题目 思路： 知道长方体的体积计算公式即可，就是一个比较简单的模拟 代码： #include<bits/stdc++.h> using namespace std; void solve(){ int a,b,c; cin>>a>>b>>c; cou ......
acwing300任务安排1对“费用提前计算”的解释
我们考查对任意一种方案答案的构成 假设最终方案只有这三段 那么很显然，答案为$$(S+sumT_[i])\cdot sumC_{i}+(2S+sumT_[j])\cdot (sumC_{j}-sumC_{i})+(3S+sumT_[n])\cdot (sumC_{n}-sumC_{j})$$ 我们换 ......
归并排序 Acwing 787
归并排序最重要的一部便是归并，我们的模板顺序为： 定义一个中间值，将我们的区间范围一分为二，我们将 这两部分看成两个数组，我们分别将这两个数组进行归并 排序，并且定义一个新的数组，将这两个数组排序好后导入 到这个新数组中，并最后将这个定义的数组输出为原数组，即可 实现归并排序。 1 #include ......
二分模板 Acwing 789 数的范围
二分一定有解，若出现无解，一定是题目中无解二分步骤：定义check函数，先找到一个x，使得区间左边满足条件区间右边不满足条件， 定义mid = l + r >> 1去判断于x的关系，此时需要判断边界关系，例如当a[mid]小于x时，说明二分值在x的左边，此时缩小范围为【mid，r】， 即令 l = ......
AcWing 3559. 围圈报数
考点：约瑟夫环问题，环形链表，队列 #include <bits/stdc++.h> using namespace std; const int N = 55; int ne[N];//链表指针数组 int main() { ios::sync_with_stdio(false), cin.tie ......
Acwing127周赛第三题 构造矩阵 （套路）
题目链接：构造矩阵 题目描述 我们希望构造一个 n×m 的整数矩阵。 构造出的矩阵需满足： 每一行上的所有元素之积均等于 k。 每一列上的所有元素之积均等于 k。 保证 k 为 1 或 −1。 请你计算，一共可以构成出多少种不同的满足条件的矩阵。 由于结果可能很大，你只需要输出对 109+7 取模后 ......
Acwing.第126场周赛
Acwing.第126场周赛 比赛链接 之前忘记整理上传了，不能有遗留问题 A.蜗牛爬井 蜗牛在 n米深的井底往上爬，每天清晨到傍晚向上爬 5米，夜间又滑下来 4米，请问像这样从某天清晨开始，第几天爬到井口？ 输入格式 一个正整数 n。 输出格式 一个整数，表示爬到井口的天数。 思路： 就是一个比较 ......
acwing367证明
首先，\(max(p,q)\)是下界，因为连一条边最多只能减少一个零入度点和一个零出度点，而最终的图不可能有哪怕一个零出度点或者零入度点（最后的图刚好就是一个点） 根据这个下界，我们也很容易可以构造出来一种方法，让零出度点和另一个SCC的零入度点相连即可，就像下面一样（红色边是添加的边） ......
acwing318 划分大理石
有价值分别为 1..6 的大理石各 a[1..6] 块，现要将它们分成两部分，使得两部分价值之和相等，问是否可以实现。 其中大理石的总数不超过 20000 。 输入格式 输入包含多组数据！ 每组数据占一行，包含 6 个整数，表示 a[1]∼a[6] 。 当输入为 0 0 0 0 0 0 时表示输入结 ......
对acwing355异象石引理的证明
首先我们抽象一下这道题的模型，然后把引理记住 模型：对于一棵树上选定的一些点，把他们连通起来的最小边数 我们先考虑一种朴素做法，对于任何一种方案，任取其中两个点，那么这个方案一定包含这两个点之间的路径 就是说，我们依次添加每个点，对于每一个新添加进来的点，让这个点与其已经添加的点求路径，然后把路径上 ......
Acwing 最长上升子序列
题目 给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。 输入格式 第一行包含整数 N。 第二行包含 N 个整数，表示完整序列。 输出格式 输出一个整数，表示最大长度。 数据范围 1≤N≤1000 −10^9≤数列中的数≤ 10^9 输入样例： 7 3 1 2 1 8 5 6 ......
Acwing 800.数组元素的目标和，双指针初步
Acwing 800.数组元素的目标和 给定升序的有序数组A（长度为n），B（长度为m）以及目标值x，求出满足\(A[i] + B[j] = x\)的数对\((i,j)\)，题目保证仅有 唯一解 输入样例： 4 5 6 1 2 4 7 3 4 6 8 9 输出样例： 1 1 双指针来做 定义指针i， ......
题解 AcWing 1272. 与众不同
题目描述 定义完美序列：若一个序列内没有重复的数，称这个数列为完美数列。 每次给定一个区间 \([l,r]\)，求这个区间内最长的完美序列长度。 具体思路 设 \(len_i\) 表示从 \(i\) 出发往右的最长完美序列长度。 我们定义一个指针 \(st\)，表示当前枚举的区间左端点，同时定义多一 ......
Acwing.第125场周赛
比赛链接 数量 给定一个正整数 n，请你计算[1,n]范围内一共有多少个正整数满足能被 2整除，但不能被 3整除。 输入格式 一个正整数 n。 输出格式 一个整数，表示满足条件的整数的数量。 数据范围 前 3个测试点满足 1≤n≤100。 所有测试点满足 1≤n≤10000。 思路: 一个比较简单的 ......