模版前导： struct Point{ double x,y; }p[N]; //点积代码 //a*b=0,两向量垂直 //a*b==|a||b|,两向量平行 double dot(Point a,Point b){ return a.x*b.x+a.y*b.y; } //求模长 double len(Point a){ return sqrt(a.x*a.x+a.y+a.y); } //a*b/|a||b|,计算夹角 double angle(Point a,Point b){ return acos(dota,b)/len(a)/len(b)); } //>0,点在...

初步接入：Balanced Lineup G（原题链接） 题意：      给出长度为n的静态数组和q次询问，接下n行为数组a的值，q行每次给你两个数a和b，求[a,b]区间内的最大值。 做题思路：      本题是倍增区间最值的模版题，依旧先讲倍增区间的使用条件：只能使用于数组查询可以重复贡献的数组。即当查询数组时出现重叠，但依旧满足题意的数组，如下图所示，选中的两个区间中出现了重叠的数组，但此时总区间长度中，最大的值依旧是2      所以本题是可以使用区间最值求解本题的，接下来是代码实现，首先是题目数据预处理，为了方便计算结果，我们需要先预处理数据，方便在询问时，直接得出需要的结果。 ...

国旗计划：原题链接 题意：      输入：第一行给你一个n和m，n代表边防战士的人数，m代表总共有几个站点，接下来有n行，每行给你两个站点C和D，战士行走的区间为[C,D]，区间会重叠，但不会完全覆盖。      输出：输出每个战士，在以他自身的区间为起点的前提下，至少需要多少人可以使战士之间行走的区间形成一个环。 做题思路：      初步入手本题，可以想到如果要判断成环，最好的办法是将环拆分成链，即当右边的点小于左边的点时，说明该点跨过了环，因此将右边的点加上站点总数，即可生成假设在一条链上的两点间的距离。 初始输入代码： cin >>n>>m; fo...

最短？路径：原题链接 题意：      有n个点m条边和不休息次数k，希望你从点1出发到达点n。当你抵达一个点时，你有两种选择：1.休息，消耗ai的时间，2.不休息，消耗1的时间。 注：当不休息次数达到k时，此时必须在该点休息。 做题思路：      从点出发到达某点，很显然是最短路问题，但考虑到存在休息这一条件，因此使用分层最短路进行求解。（是不是做过...链接【|||--】)。      分层最短路，将最短路原先的二维地图，转变为三维，其中多出的z轴通常会是最短路多出的变量条件，本题设置k，作为分层的层数。      首先对每个点消耗的时间和能够建立的桥梁（边）进行读取。 cin &g...

使用例题：最长公共子序列（原题链接） 题意：      给你两个字符串text1，text2，求两串字符串中的共有最长字序列。 代码详解： int longestCommonSubsequence(string text1, string text2) { const int N=1e3+10; //初始化为0 int dp[N][N]={0}; int n=text1.size(); int m=text2.size(); for (int i=1;i<=n;i++) { for (int j=1;j<=m;...

最长递增子序列（普通版/暴力版） 使用例题：最长上升子序列******。 题意：      给你n个正整数组成的序列，求从原序列中按顺序取出一些数字排在一起，取出的数字必须是逐渐增大的。 数据量为5000。 代码详解：      想要求解本题，最原始的思路即双重循环搜索，先遍历数组，再遍历每个值前的所有值（1~i-1），看当前值可以放在多少值的后面，利用dp数组记录每个数的最长长度，最后遍历循环，找出dp数组中的最大值。 #include<bits/stdc++.h> using namespace std; const int N=1e3+10; int n; int maxn...

lxy的通风报信：原题链接。 题意：      给你n*m的地图，地图上有a个军队和b个敌人，求怎么样花费最少的总路径，将地图上所有的军队连接，如果能的话，输出最小花费，不能则输出No。 注：题目只给出n*m的地图，a和b均未给出 名称 含义 * 我方军队：要连接的点 # 敌方军队：该点不可以通过 . 可通行的点 做题思路：      本题的数据很小加上要求最短路径总量，解决方法很显然是生成最小树，但用二维做最小生成树很麻烦，所以先找出军队并给予每个军队编号，转为一维...

A*BBBB：原题链接 题意：      给你两个值a和b，b的每一位都相同，求它们相乘后的结果。 注意：a和b的长度有1e6。 做题思路：      很显然本题需要用到高精度，但普通高精度并不能解决本题，所以要针对本题做出优化。      首先根据题意我们可以知道b的每一个值都是相同的，我们用个样例，看看可以得出什么。 样例假设：a=1234,b=111      我们列出计算公式后，可以发现每...

适用样例：      给出长度为n的数组a,求数组中每个节点左右出现的第一个比该节点小的下标。 样例输入：n:5，a={1,4,2,3,5}。 输出结果： 编号（点） 左端 右端 1 0 0 2 1 3 3 1 0 4 3 0 5 4 0 代码详解：      本题用单调栈进行求解，当进行遍历时，可知当出现栈顶比当前节点大时，说明当前节点就是右边第一个比栈顶小的，用样例模拟： 编号（点） 状态 1 1 2 1,4 3 1,4,2 弹出...

滑动窗口最大值：****。 题意：      给你一个数组nums，并给你值为k的滑动窗口，现在将窗口从数组左端到右端，每次移动一格，问每次移动的窗口内的最大值为多少。      样例：数组nums={1,2,3,4,5}，k=3 状态 最大值 [1,2,3],4,5 3 1,[2,3,4],5 4 1,2,[3,4,5] 5      所以最大值数组为{3,4,5}。 做题思路：   &nbsp...

去除重复字母：原题链接。 题意：      给你一个字符串s，删除字符串中重复的字符，使新字符串的字典序最小（不能打乱字符串原顺序），且原字符串中出现的字符都要有且仅有一个。 做题思路：      通过题目，我们可以得知想要拿到字典序最小的字符串，只要遍历字符串并用栈读入，便利点时重复循环：当栈顶的字符大于当前字符时，就删除该字符，直到当前字符不大于栈顶或栈为空时，停止循环。这样就可以得到最小的字典序字符串。      但题目要求，每个出现在字...

获取所有钥匙的最短路径原题链接 题意：      给你一个二维数组grid其中： 符号 意义 '.' 代表可走的空房间 '#' 代表不可走的墙壁 '@' 代表出发的起点 'A'~'F' 代表锁 'a'~'f' 代表钥匙      求最少用几步可以拿完所有钥匙，如果无法拿到钥匙请输出-1。 做题思路：      本题很明显是最短路问题，但不同的是，多了钥匙这一条件，所以转变为多层图最短路问题。  &n...

C题：小红的数字对对碰(原题链接) 题意：      给你一个长度为n的数组a，并给你任选无次数限制的两种方法，求怎么样可以使数组长度尽可能短。 方法：      方法一：当i<j时，ai+aj<=0时，可以消去ai和aj。      方法二：当i<j时，ai^aj<=0时，可以消去ai和aj。 做题思路：      首先我们需要先了解方法一，二是什么意思，有哪些特定条件可...

最大食物链计数原题链接 题意：      给你一个食物网，请求出这个食物网中最大食物链的数量。n代表物种的种类，m代表食物链有几条边，接下来m行，每行a，b代表被吃者a和捕食者b。 注：最大食物链，链的最左边和最右边的端点已经不能再扩展了，最左边的端点一定是食物链的最低层，最右边的端点一定是食物链的最高层。 做题思路：      本题运用了两个知识点，1.累加法，2.拓扑排序。      首先，累加法怎么引用于本题，这里做个假设图： //可能有...