题目链接  大致思路： 刚开始做的时候怎么也做不对。在寻找最短路的过程中会对如何降低山的高度有影响。一直在想如何找出两者之间的联系。 所以就一直错。后来经过一位学长提醒，我们只需要关注比1号山高k的山。因为我们有可能降低这些山的高度。比1号山低 的山我们其实是不需要关注的，因为虽然下山增加体力，但是在上山的过程中有抵消了。所以是没有影响的。 具体的做法是，我们可以把所有比h1 + k高的山都降到h1 + k,在寻找最短路的过程中，如果我们需要经过这条路就减去对应 代价 

为了方便结构体的初始化我们需要在结构体内写构造函数； 如下：  #include<stdio.h> struct node { int x,y; node(){}; node(int a,int b) : x(a), y(b) {}; }; int main() { node data[100]; //注意如果没有无参的构造函数这行代码会出错的 node a = node(1,2); return 0; }   

在写题中经常遇到一些需要用到二分策略的题。 这些题有些简单有些比较难。但是他们都遵循一些简单的原则。 1.大部分题都是二分答案。 2.将答案带入问题过程，由这个过程产生的信息与题目中给出的已知信息比较，确定下次的二分的区间。 3.确保在这个过程中区间能不断缩小。 例题讲解： POJ-3258 POJ-3122  

题目链接  题目大意： 有n个蛋糕，每个蛋糕有个半径。我们需要把这些蛋糕分给F + 1个人。F+1个人分得得蛋糕的大小必须 是一样的(形状可以不一样)。分得的蛋糕可以由原来的蛋糕切割下来的，但不能是由几个蛋糕拼凑而成。 求如何切才能使分得的蛋糕大小最大。只用输出最后分得的蛋糕的面积即可 大致思路： 我们可以二分这个最大对蛋糕面积。然后把它带入切蛋糕的过程。 求出如果这个面积是正确答案，我们能切出几块蛋糕。 如果切出的蛋糕比F+1大，说明这个值小了。 如果切出的蛋糕比F+1小，说明这个值大了。 代码如下：  #include<stdio.h> #include<math.h&g...

题目链接   题目大意： 在一条河的起点和终点之间有N块石头，起点和终点上也有石头。农夫可以移走M块石头（不包括起点和终点）使得 移走的每两块石头(包括起点和终点)的最短距离最大。求这个值。 大致思路： 我们可以二分这个最短距离，然后求出如果这个是最短距离，我们需要在原来的基础上去掉几个石头。 去掉石头的个数如果比M大，说明我们枚举的最短距离比真正的最短距离大了。 去掉的石头个数比M小，说明我们枚举的最短距离比真正大最短距离小了。 代码：  #include<stdio.h> #include<string.h> #include<algorithm> #d...

题目链接 题目大意：给你n * k 个木板，让你组成有n个木桶，每个木桶有k个木板。每个木桶的体积 是这个木桶的木板中最短的那个。并且任意两个木桶的体积的差必须<=l。 求如何组装才能使n个木桶的体积和最大。输出体积和。 解题思路： 首先我们先将所有的木板从小到大分成n个块。如果我们想要实现体积最大化，我们需要选出 每个块最短的那个木板作为由本块木板组成得木桶的体积。 但是题目上限制了任何两个木桶的体积的差必须小于l,所以如果本块最短的那个木板如果不符合 条件就往前面找到符合条件且最长的那个木板作为本块木桶的体积即可。 代码如下：  #include<stdio.h> #in...

题目链接   题目大意： 给你一个树，你可以通过切割某多条边来制造多个连通块。问你最多到可以切几条边使得偶数大小的连通块最多且剩下 的连通块的大小都为偶数； 解题思路： 用dfs遍历每一颗子树，如果这颗子树大小是偶数，说明可以切这棵子树和它父亲结点相连的那条边。如果是奇数则不切 代码如下：  #include<stdio.h> #include<string.h> #include<algorithm> #include<vector> #define ll long long #define mmset(a,b) memset(a,b,size...

题目链接    题目大意： 公交车有n排座位，每排的座位有两个，且这两个座位的宽度一样。任何两排座位的宽度度都不一样。 首先给你一个n，接下来给你n个数字代表第i排座位的宽度。然后给你一个01字符串代表乘客上车的 顺序。0和1分别代表内向的人和外向的人。内向的人会从没有人坐的那几排选出一个宽度最小的那排 座。外向的人会从有一个人坐的那几排选出宽度最大的那排座。 题目要求你根据上车的顺序输出他们应该坐第几排。 解题思路： 我们如果只考虑内向的人，发现内向人的选择只跟上车顺序和座位的宽度有关。 观察外向的人，我们发现外向的人会从内向人的座位挑出一个宽度最大的坐，如果不存在这样的座位，就 挑选出当前...

题目链接  题目大意是： 给你三个整数，p,q,b。其中p/q是个分数。该题目要求你给出p/q在b进制下是否是个无限小数。 解题思路： 首先我们需要知道小数转化为二进制。假定有分数a/b(a<b),要将它转化为k进制。我们需要取a * k / b为第 一位。然后让a = a * k % b.重复以上步骤，直到a* k % b == 0; a * k % b 一直不等于0那么就说明这个分数是无限小数。 如果判断 a * k % b 一直不等于0在代码层面是可行的，但是时间复杂度复杂度会比较高，而且从逻辑上说 也比较麻烦。 我们可以换一种思路，我们只要判断a * k % b 在小数转化为二进...

题目链接 大意： 有一个长度为m的圆形桌子，有n支队伍。然后有p次ac。每次ac给出ac的队伍编号和ac的时间。 有一个专门发放气球的机器人，他按照顺时针的方向绕着圆形桌子，一秒移动一个座位。当他移动 到第i个位置的时候，他会给下一个位置发放气球。发放气球的数量是该座位上次放气球的时间到 这次发放气球的时间中ac的数量。当一个队伍ac后，如果不能立即得到气球，这支队伍就会产生 怒气值。怒气值会累加。直到机器人给这次ac发放气球为止。（也就是说如果一支队伍在第t秒ac 了一道题，如果这次ac的气球是在第t1秒发放的，那么这次ac的怒气值就是t1 - t）。 给你每支队伍坐的位置编号和每次ac的队...

题目链接 题意就是给你一个a,b。并且有x + y = a 且 lcm(x,y) = b, 让你求x,y; 大致思路就是根据规律推出公式： 设g = gcd(a,b) 那么有g * K1 = x,  g * K2 = y, 且 k1 和 k2 互质； 由K1 和 K2 互质可得  K1 * K2 和 K1 + K2 也互质。 又lcm(x,y) * gcd(x,y) = x * y 可得 lcm(x,y) / gcd(x,y) = K1 * K2 即：K1 *  k2 = b / g; 又 x + y = a 可得 K1 + K2 = a / g; 由以上加粗部分可得：gcd(a,b) = g...

题意要求a/b的最大值。 其中a是任意两点的点权和，b是除去这两点剩下的最小生成树的值。 我们可以先求出最小生成树，然后不断删边，然后求出删去这条边后的剩下的点的最小生成树的值（联想到次小生成树）。 删边的过程可以用dfs枚举。 代码如下啊：  #include<stdio.h> #include<math.h> #include<algorithm> using namespace std; const int N = 1005; int INF = 99999999; int connect[N][N], data[N][3], Dres[5]; int...

整体思路就是将没有用过的边插入最小生成树中，会形成一个环，我们去掉这个环中最大的那个边，会得到一个新的 生成树，次小生成树就是新的生成树中最小的那个。我们用一个数组maxx来记录最小生成树中两点之间最大的权值。 用connect数组表示边是否加入最小生成树中，代码如下：  #include<stdio.h> #include<algorithm> using namespace std; const int N = 105, M = 10005; int INF = 99999999; int map[N][N], connect[N][N], maxx[N][N], ...

通过dfs枚举所有点集合的情况，然后对这些点进行prim求的最小生成树。 然后将边权和点权的比以及点集合存在到一个结构体数组里面，然后先对边权和点权的比进行排序， 如果相等的话就按点集合的字典序排序即可； 代码如下：  #include<stdio.h> #include<string.h> #include<algorithm> #define mmset(a,b) memset(a,b,sizeof(a)) using namespace std; const int N = 20; struct node { double num; int data[...