A 贪心,由于基地可以重复销毁，所以找出找出每架战机可轰炸基地的最大价值，排序之后贪心找一下即可 #include<iostream> #include<algorithm> using namespace std; const int N = 1e6 + 15; struct node{ int d, v; }no[N]; bool cmp(node a, node b){ if(a.d == b.d) return a.v < b.v; else return a.d < b.d; } int a[N]; int main() { int n, m; c...

A 贪心,由于基地可以重复销毁，所以找出找出每架战机可轰炸基地的最大价值，排序之后贪心找一下即可 #include<iostream> #include<algorithm> using namespace std; const int N = 1e6 + 15; struct node{ int d, v; }no[N]; bool cmp(node a, node b){ if(a.d == b.d) return a.v < b.v; else return a.d < b.d; } int a[N]; int main() { int n, m; c...

排列组合 、 逆元、快速幂 题目来源：中北大学2019年新生赛 题目：    请构造一个长度为n的非严格递增序列，序列中每个元素大小都属于[1, m]，但是这个问题太简单了，于是cy想知道有多少种合法的方案数，并且由于答案可能很大，故你需要将答案取模998244353  输入：  输出：  样例： 输入： 输出： 3 3 3  比赛时候傻了，没想到。赛后一想，这题就是个思维题，推出公式dp和排列组合都能过。 这里拿排列组合写，推出组合公式  #include<stdio.h> #define ll long long #define mod 998244353 ll mul(ll ...

二维哈希 题意：给定一个由和0组成的大小为nm的匹配对象，和T个大小为pq的匹配模式，求匹配对象中至少出现一次匹配模式的个数 思路：将每一行看成一个字符串，计算从每个位置开始长度为Q的字符串子串的哈希值，然后把得到的哈希值在列方向看成一个字符串，计算每个位置开始长度为P的字符串子串的哈希值，通过上述步骤，可以得到这个nm的匹配对象的所有的pq的子阵的哈希值*  注意：两次哈希值的计算选用不同的基数 样例： 输入： 3 3 2 2 2 *00 0** *00 ** 00 *0 ** 3 3 2 2 2 *00 0** *00 ** 00 *0 0* 0 0 0 0 0 输出： Case 1: 1...

Next 数组及KMP KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个getnext()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。其中最难理解的部分即next数组的求法以及回溯 前缀数组 **前缀数组中存储的是这个字符串前缀和后缀中相同子串的最长长度 ** next 数组考虑的是除当前字符外的最长相同前缀后缀 以 agctagcagctagctg 为例 ** start** 将next数组初始化之后为：  –>将模串依次向后移比较至此  –>回溯 此时对比，小串长为3，j=3;...

线段树 线段树是一种二叉搜索树。它将一段区间划分为若干个单位区间，每一个节点都储存着一个区间。 线段树可做 区间求和，区间最值，区间更新，单点更新等操作 以区间和为例来做介绍： 建树 const int maxn=1000000+5; struct Tree{ int l,r; int val; int lazy,tag;//标记，需要区间更新时使用 }tree[maxn*2]; //把子节点的信息汇总到了父节点上，根据题目要求可做修改，比如可以更改为区间最值 void pushup(int cur) { tree[cur].val = tree[2 * cur].val + tree[2 *...

简单DP的小见解（入门背包） n为个数，m为大小，v[]为单个物品体积，w[]为此物品的价值 01背包（每种物品只能选0件或者1件） 引例：假设小偷去珠宝店***，他的背包容量为C=10，珠宝店里有3件珠宝可以***，问可以装入背包的最大价值是多少。 想要求装入背包的最大价值，肯定要在尽量装满背包的情况下拿走价值尽可能高的物品，使得最后的总价值最大化 dp[n] [m]为第n件物品剩余m空间 第i件物品是否可以拿，存在两种情况： （1）剩余空间不能装下此物品，那么问题转化为将前i-1件物品放入背包中所获得的最大价值.。 （2）剩余空间可以装下此物品，想要求i件物品最优解，对于此物品又面临拿与不...

归并排序 归并排序是建立在归并操作上的一种有效的排序算法，是采用分治法的一个典型应用。其时间复杂度为O(n log n) 归并排序的步骤如下：  划分求解：将序列分成元素个数尽量相等的两半。 递归求解：将两半元素分别排序。 合并问题：将两个有序表合并在一起 当我们要排序一个数组的时候，归并排序法首先将这个数字分成一半，然后给左边的数组排序，右边的数组给排序，之后将它们归并起来，而我们在对左边和右边的数组排序的时候，又可以将它们继续划分成一半，然排序，归并，如此递归，到一定程度的时候，我们就将这个数组分成了一个又一个的元素，此时不用排序，对它们进行一次简单的归并就可以 例；将8,6,2,3,1,...

最小生成树 一个有n个节点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点，并且有保持图连通的最少的边。最小生成树可以用Kruskal算法或者prim算法求出。 kruskal 算法的过程为不断对子图进行合并，直到形成最终的最小生成树。prim 算法的过程则是只存在一个子图，不断选择顶点加入到该子图中，即通过对子图进行扩张，直到形成最终的最小生成树。  https://www.jianshu.com/p/cf21443b3838  此网址对着两种算法做了详细介绍 prim算法 最小生成树的一个典型问题 poj-1258 题意：要在n个城市之间铺设光缆，主要目标是要使这 n 个城...

快速幂||快速乘 求(a^b)%p或(a*b)%p 例如：因为7 = 4 + 2 + 1，那么 5^7 = 5^(4 + 2 + 1) = 5^4 * 5^2 * 5^1 ​    幂： 57=5×56=5×(52)3… ​    乘： 5×7=5+5×6=5+(5×2)×3… #include<stdio.h> #define ll long long ll quick_pow(ll a,ll b,ll p){ if(!b) return 1%p; ll ans=1%p; //ans=0 while(b){ if(b%2==1) b--,ans=(ans*a)%p; //ans=...

可持久化线段树不是一颗完全二叉树，所以不能用层次序编号，而应该直接记录每个节点的左、右子节点的编号。可持久化线段树维护了每次操作后线段树的历史形态。 下面举个简单的例子来理解一下： 以poj-2104为例；这棵树是一颗不用修改的线段树 题意：即多次查询，查询区间第K大的数。 POJ-2104 (区间第k大) //主席树的学习--区间第k大 //区间第k大又可以用整体分治算法，归并树，线段树套平衡树，主席树来做 //以主席树为例来做 #include<iostream> #include<algorithm> using namespace std; const int ...

回顾并查集。 题意：给定N个商品，每个商品有利润pi和过期时间di，每天只能卖一个商品，过期商品不能在卖，求如何安排每天卖的商品，可以使收益最大。（1 <= N, pi, di <= 10000） 样例： 4 50 2 10 1 20 2 30 1 7 20 1 2 1 10 3 100 2 8 2 5 20 50 10  思路：把商品按照利润从大到小排序，并建立一个关于“天数”的并查集，起初每一天各自构成一个集合。对于每个商品，若它在d天之后过期，就在并查集中查询d的树根，标记为d。如果d大于0，则把该商品安排在第d天卖出，合并d和d-1，答案累加该商品的利润。 #include...

A. Mezo Playing Zoma 题目大意：给你两个操作L和R，分别表示当前坐标-1和+1，当然，这些操作可以视为无效，即不移动它的坐标点。现在给你一个操作的字符串，然后进行一系列操作，让你算出有多少种可能的坐标。 思路：计算出它的左右边界，这个区间内的所有点即他可能到达的点。 #include<iostream> #include<bits/stdc++.h> using namespace std; int main() { int n; cin >> n; string str; cin >> str; int l = 0, r =...