题目 题目描述： 平面上有若干个点，从每个点出发，你可以往东南西北任意方向走，直到碰到另一个点，然后才可以改变方向。 请问至少需要加多少个点，使得点对之间互相可以到达。 输入描述： 第一行一个整数n表示点数（ 1 <= n <= 100)。 第二行n行，每行两个整数xi, yi表示坐标（ 1 <= xi, yi <= 1000)。 y轴正方向为北，x轴正方形为东。 输出描述： 输出一个整数表示最少需要加的点的数目。 解析 1）知识点 一道简单的并查集，把我搞了好久，一开始的写法还是不知道为啥错了QA...

题目 题目描述： 给你一个 n 个点，m 条边的无向图，求至少要在这个的基础上加多少条无向边使得任意两个点可达~  输入描述： 第一行两个正整数 n 和 m 。 接下来的m行中，每行两个正整数 i 、 j ，表示点i与点j之间有一条无向道路。 输出描述： 输出一个整数，表示答案 解析 1）知识点 这道题是一道基础的dfs或并查集，一开始我是想这么说的。但是我发现题目吧dfs压死了。 因为dfs遍历标记用的空间在并查集的五倍，所以会MLE（代码依旧放下面了）。 2）看题目 ...

题目 题目描述： 给你一个长度为n的序列，你每次可以将一个序列分割成两个连续的的子序列， 分割的代价为原序列的总和。 现在允许你在初始时将序列重新排列一次。 问分割成n个长度为1的序列的最大总代价是多少？ 输入描述： 第一行一个数n表示原序列的长度； 接下来一行n个数a_i表示原序列的第i个数。 2<=n<=100000 0<=a[i]<=10000 输出描述： 一行一个整数表示答案。 解析 1）知识点 这道题，简单贪心。 2）看题目 题目意思就是让你找到最大花费的划分方法。 3...

题目 题目描述： 这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。 注意：选出的k个子矩阵 不能相互重叠。 输入描述： 第一行为n,m,k（1 ≤ n ≤ 100,1 ≤ m ≤ 2,1 ≤ k ≤ 10）， 接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。 输出描述： 只有一行为k个子矩阵分值之和最大为多少。 解析 1）知识点 这是一道动态规划的题目。 2）看题目 首先看题目，就是让我们在矩阵里面找k个不重叠矩...

题目 题目描述： 小A与小B这次两个人都被困在了迷宫里面的两个不同的位置，而他们希望能够迅速找到对方，然后再考虑如何逃离迷宫的事情。 小A每次可以移动一个位置，而小B每次可以移动两次位置，小A移动的方向是上下左右左上左下右上右下8个方向，小B移动的方向是上下左右4个方向。 请问他们最早什么时候能够找到对方，如果他们最终无法相遇，那么就输出”NO"。 输入描述： 第一行两个整数N，M分别表示迷宫的行和列。\\ 接下来一个N\times M 的矩阵\\其中"C"表示小A的位置,"D"表示小B的的位置，\\ "＃"表示不可通过的障碍，"."则是可以正常通过的位置...

题目 题目描述：     德玛西亚是一个实力雄厚、奉公守法的国家，有着功勋卓著的光荣军史。     这里非常重视正义、荣耀、职责的意识形态，这里的人民为此感到强烈自豪。     有一天他们想去制裁邪恶的比尔吉沃特，于是派遣了自己最优秀的战士。     结果比尔吉沃特领土太小，只有长为n宽为m共计n*m块土地，其中有些土     地标记为0表示为高山峻岭或者深海湖泊，英雄们无...

比赛靠手机码代码真累QAQ B-减成一 1）知识点 就是一道简单的动态规划。 2）看题目 就是你每次都可以让一个区间数字都-1，求最少几次全变1。 3）算法分析 一开始我以为不是连续区间，还直接就排个序来搞了。但是看到连续区间的时候我就发现这一定是个dp。 说到dp：动态规划最重要的就是递推和dp数组的含义。 首先我们讲一下dp数组的含义：这里重要的是数的位置。所以dp数组就是一个一维数组：dp[位置] = 最小次数。 ...

题目 题目描述： 小T是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有n个矿石，从1到 n 逐一编号，每个矿石都有自己的重量wi以及价值vi。 检验矿产的流程是： 1、给定m个区间[Li，Ri]； 2、选出一个参数W； 3、对于一个区间[Li，Ri]，计算矿石在这个区间上的检验值 Yi ： 且wj≥W，j是矿石编号 这批矿产的检验结果Y为各个区间的检验值之和。即： 若这批矿产的检验结果与所给标准值S相差太多，就需要再去检验另一批矿产。 小T不想费时间去检验另一批矿产，所以他想通过调整参数W的值，让检验结果尽可...

题目 题目描述： SUM问题可以表示为：给定四个具有整数值的列表A，B，C，D。 计算多少个四元组（a，b，c，d）∈A x B x C x D使得a + b + c + d = 0。在下文中，我们假定所有列表的大小均相同。 输入描述： 输入文件的第一行包含列表n的大小（该值可以最大为4000）。然后，我们有n行包含四个分别属于A，B，C和D的整数值（绝对值最大为2 28）。 输出描述： 对于每个输入文件，您的程序必须使四个数的总和为零。 解析 1）知识点 这道题是一道简单二分，但是思路就很重要。 ...

题目 题目描述： 你有n种牌，第i种牌的数目为ci。另外有一种特殊的牌：joker，它的数目是m。 你可以用每种牌各一张来组成一套牌，也可以用一张joker和除了某一种牌以外的其他牌各一张组成1套牌。 比如，当n=3时，一共有4种合法的套牌：{1,2,3}, {J,2,3}, {1,J,3}, {1,2,J}。 给出n, m和ci，你的任务是组成尽量多的套牌。 每张牌最多只能用在一副套牌里（可以有牌不使用）。 输入描述： 第一行包含两个整数n, m，即牌的种数和joker的个数。 第二行包含n个整数ci，即每种牌的张数。 输出描述： 输...

题目 题目描述： 给一个数组{a}，定义 h(a,b)为在十进制下 a + b 与 a 的位数差，求 ，0的位数为1。 输入描述： 第一行读入一个正整数 n (1 <= n <= 105)。 第二行读入 n 个非负整数，第 i 个表示a[i] (0 <= a[i] <= 108)。  输出描述： 一行表示答案。 解析 1）知识点 这道题包含了分支递归和二分思想。 2）看题目 首先我们理解题目的话，...

题目 题目描述： 小咪是一个土豪手办狂魔，这次他去了一家店，发现了好多好多（n个）手办，但他是一个很怪的人，每次只想买k个手办。 而且他要让他花的每一分钱都物超所值，即：买下来的东西的总价值/总花费=max。请你来看看，他会买哪些东西吧。 输入描述： 多组数据。 第一行一个整数T，为数据组数。 接下来有T组数据。 对于每组数据，第一行两个正整数n，k，如题。 接下来n行，每行有两个正整数ci，vi。分别为手办的花费和它对于小咪的价值。 输出描述： 对于每组数据，输出一个数，即能得到的总价值/总花费的最大值。精确至整数。 解析 1）知识点...

题目 题目描述： 有不等式y⋅x3≤ n，已知y为正整数，x为大于1的正整数，问当x和y的解数量刚好为m的时候n的最小值，如果不存在输出 -1。 输入描述： 多组数据读入。 每组数据一个数字m，如题所示。 输出描述： 每组数据输出一行，输出答案。 解析 1）知识点 这道题是一道二分的题目。 2）看题目 首先看题，就是说我们给定解的数量，求最小的n。 3）算法分析 我们求解，首先写成函数的形式y = n / x3。 然...

题目 题目描述： 多次查询[l,r]范围内的完全平方数个数。 定义整数x为完全平方数当且仅当可以找到整数y使得y*y=x 输入描述： 第一行一个数n表示查询次数 之后n行每行两个数l,r 输出描述： 对于每个查询，输出一个数表示答案 解析 1）知识点 这道题不难，完全就是一道简单的数学题。但是按题目上面说的搞二分，也完全可以。 2）看题目 这道题目就是叫我们查询一个区间内的平方数个数。 3）算法分析 因为数据范围大小有1e9的大小，所以不可能开个...