题目链接：https://www.acwing.com/problem/content/102/给定一个序列，只能对一个区间加一或者减一，问至少需要多少步使得所有数都变成一致的？有多少种一致序列？利用差分，对一个区间进行加一或者减一的话，一定是一个差分+1加上另一个差分-1。代码如下：#include<bits/stdc++.h> usingnamespace std; typedef unsigned int ui; typedef longlong ll; typedef unsigned longlong ull; #define pf printf #define mem(a,b) memse...
题目链接：https://www.acwing.com/video/472/给定n门课，存在先修关系，构成一个森林，修一门课之前他的先修课程一定要完成，问在选m门课的情况下最多能获得多少学分？如果没有先修规则就是一个裸的01背包问题。但这个问题不能用01背包解决。而是一个分组背包问题，设f[x,j]为x为根的子树中修j门的最大学分数，从结点x出发，子树的数量就是分组的数量，背包的容量从0-j-1，每个分组中第k个物品的体积是k。在每个点的子树处理完之后...
改进版本1??舍去一边的快速排序，该边的快速排序用自身的排序代替。def quick2(li,left,right):while left<right:mid=partition2(li,left,right)#索引的中间值quick2(li,left,mid-1)#单边递归法left=mid+1return lidef partition2(li,left,right):pivot=li[left]#定位左边的元素while left<right:#还没有搜索完# 从右边开始，将大于中间索引所在元素的元素放在左边while left<right and pivot<li[right]:right-=1li[left]=li[right...
题目要求：给一个n*m的矩阵，求从左上角到右下角的两条路径，使得两条路径上的值只和最大。从左上角往右下角走的时候只能向下或者向右。在这个问题中阶段就是步数，步数与坐标点的横纵坐标之和相差一个常数，所以可以通过坐标只和以及两个点的横坐标来确定当前的状态集合。此时通过一个点的所有入边更新一个点即可。一共有四种状态，代价可以先计算出来。其中坐标枚举的范围要综合考虑横纵坐标的范围。代码：#include<iostream> #i...
题目链接：https://www.acwing.com/problem/content/276/题目给出m个地点，n个任务，每两个地点之间有距离，有三个服务员，初始时刻服务员在1,2,3位置，每个服务必须且只有一个人到指定的地点，问完成这些服务的最小移动距离之和，决策集合是所有完成了i个任务并且另外两个人在x,y位置的方案，属性是距离之和的最小值，在DP中有两种常见的更新方式，分别是通过依赖的状态来更新当前的状态和通过当前的状态去更新以来的状态本问题中...
一般的dijkstra算法利用贪心的思想，每次找出最短边，然后优化到该点的的距离，我们还采用贪心思路，但在寻找最短边进行优化，之前是双重for循环，现在我们用优先队列来实现。代码解释：//样例程序采用边表储存。 #include<cstdio>#include<queue>#include<cstring>#include<cmath>#include<iostream>using namespace std;int head[100000]={0},next[200000]={0},aa[200000]={0},size,s,tt,m,n;struct bb { int x,y; }a[1000...
《算法竞赛进阶指南》 二分篇 学习1二分的原理其实很简单整数集合上的二分复习一下c++ STL库 lower_bound upper_bound :利用二分查找的方法在一个排好序的数组中进行查找 lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。 upper_bound( begin,end,num)：从数组的beg...
题目链接：https://www.acwing.com/problem/content/246/线段树合并线段的时候要更新结点中的ans值，但是这个值的更新依赖于lmax与rmax，这两个值的更新又依赖于sum，故查询的时候需要返回的是一个结点，返回代表的区间的信息。代码：#include<iostream> #include<cstdio> usingnamespace std; constint maxn = 500010; constint inf=0x3f3f3f3f; int n,m; struct node{int l,r,s,lx,rx,ans; }t[maxn*4]; void pushup(int rt){t[rt...
题目链接：https://www.acwing.com/problem/content/199/分解N！的质因数，因为N!的质因数不超过N，所以可以先预处理出[1,N]的质数，然后就是简单的求和计算了。筛法采用的是优化之后的艾式筛法的优化了，算法的时间复杂度是O(n*loglogn)，十分接近线性。代码：#include<iostream> #include<vector> #include<cstring> usingnamespace std; #define maxn 1000010 vector<int>primes; bool v[maxn]; void get_primes(int n){memset...
题目链接：https://www.acwing.com/problem/content/description/151/给定长度为n的序列，代表一个单词的出现次数，要求构造k叉哈夫曼树使得总权值最小，并且在权值最小的情况下问最小的高度是多少？我们可以考虑不断取k个数组成一个新的结点放入优先队列，但是根节点可能不满k叉，所以可以考虑在其中不超过k-1个零来上调权值比较大的结点，权值为零的结点肯定在最深层的一个父节点上。也只有这一个父节点是不满k叉的，这个可以通过...
题目链接：http://poj.org/problem?id=3635题目和最短路算法的形式很像，只要对每个状态确定转移的分支即可，其中每次油量只加一，因为后续一定会在队列中被取出来重新加一（如果可以的话）代码：#include<iostream> #include<cstring> #include<queue> usingnamespace std; #define maxn 1005 int head[maxn],nxt[maxn*20+10],ver[maxn*20+10],len[maxn*20+10]; int d[maxn][105]; int n,m,q; bool vis[maxn][105]; int price[max...
第一章 算法竞赛概述 算法竞赛（程序设计竞赛）是培养杰出程序员的捷径。 在国内众多竞赛中，面向中学生的程序设计竞赛有全国青少年信息学奥林匹克竞赛（NOI），最具影响力的面向大学生的程序设计竞赛有ACM-ICPC（国际大学生程序设计竞赛），CCPC（中国大学生程序设计竞赛）培养杰出程序员的捷径：1.编写大量代码； 2.丰富的算法知识； 3. 计算思维和逻辑思维； 4. 团队合作精神。算法竞赛入门： 1. 竞赛队员主要的学习方法就是“刷...
题目链接：https://www.acwing.com/problem/content/149/题目中给出一些点在x轴上的位置，问选出k对位置的情况下，他们的两两距离之和的最小值是多少？容易直到，选中的位置一定是相邻的而且没有交集，我们对原始序列求差分之后问题就变成了在这个差分序列中寻找k个不相邻的数，使得和最小。当选中了其中的k个两两间隔为1的位置之后，如果下一次从剩下的区间里面选出一个最小的区间跟这k个点相邻就破坏了性质，这k个点一定会被周围...
一、 数据结构和算法关系为什么要学数据结构和算法？通常，计算机解决问题的步骤如下： 在数学模型中，计算机处理的对象之间通常存在着一种最简单的线性关系，这类数学模型就是线性的数据结构。著名计算机科学家沃斯（Nikiklaus Wirth）提出一个公式：程序=数据结构+算法。数据结构就是编程的思维，编程的灵魂，算法的精髓所在，没有了数据结构，程序就好像一个空核，是低效率的。算法与数据结构是紧密联系不可分割，必须在一起才...
题目链接：http://poj.org/problem?id=1190剪枝的常用思考策略：优化搜索顺序（从决策数量越少的位置开始决策）、排除冗余的等效的操作、可行性剪枝、最优性剪枝、上下界剪枝，其中在可行性剪枝方面可以利用“未来期望进行剪枝”要充分利用不等式关系进行放缩，将不可能的状态进行剪枝，也是一个对“未来状态的估计”。代码：#include<iostream> #include<cstdio> #include<math.h> usingnamespace std; #define maxn 25 constint ...