usx21145328

题解

/ 注册

全部文章 / 题解（共15篇）

题解 | #炮兵阵地#

思路：题目要求求出最多的炮兵数，对于一个位置可以选择放也可以不放，而之后可以根据这次的选择更新下一步的选择。考虑状态压缩dp。一行一行的放炮兵，因为题目中给出的炮兵攻击范围是一个十字，所以在判断这个炮兵能不能放的时候需要知道上一行炮兵和上上行放在哪了，也要知道此时放的炮兵所在的这一行里左边的放炮兵...

2022-02-11

0 415

题解 | #栈和排序#

思路：在a数组中，如果a[i]后面没有比它还大的数，那就直接把这个数输出,否则这个位置输出的数就会比a[i]小，那么字典序就会更小。用一个数组maxn来记录每个数后面的最大值，从后往前循环，求出a[i]到a[n]的最大值代码： #include<bits/stdc++.h> u...

2022-02-06

2 677

题解 | #免费馅饼#

题意：一个能向左移动1格或两格，向右能移动1格或两格，也能移动0格的人，在水平宽为W，高度为H的区域内，能接到的馅饼的分值最大为多少。馅饼给出了它掉落的初始时刻、水平位置、掉落速度、分值。思路：和数塔类似，把饼落到人高度的时间算出来（人占一格高），然后以时间为横坐标，水平位置为纵坐标，创建一个...

2022-01-31

0 833

题解 | #[SCOI2010]游戏#

题意：你有n种装备，每种装备有两个属性值，你要在这两个属性值里选一个，使得这些属性值是1、2、3、4......这些从1开始连续的数，题目求最多能连续到多少。思路：假设这些连在一起的数都在一个连通块里，那么如果这个连通块内有大于n-1条边，连通块内里的数就都能用上，否则就只能用到这个连通块内第...

2022-01-27

0 470

题解 | #模拟战役#

题意：司机的大炮是前四行，小齐的大炮是后四行，小齐先开炮，然后司机开炮，小齐可以打司机任意一个大炮，但司机只能打小齐打自己的大炮的大炮，问小齐把司机的大炮打完最多能剩几个大炮。思路：因为一个大炮被打完后会产生一个 3 * 3 的波及范围，所以可以用一个dfs来搜索这个大炮的周围是否还有大炮...

2022-01-24

0 514

题解 | #tokitsukaze and Soldier#

题意：在每个士兵都有一个对团队人数的限制下，选出战斗力最高的一个团队思路：根据每个士兵对团队人数限制的大小，从人数多的到少的，枚举一下对每个人的判断，看一下这个人要不要进来，进来后要不要把一些人删掉。如果人数超了，肯定是要把队里战力最小的拿出去，就可以用一个小根堆来维护。这样维护只要每次删除一...

2022-01-20

0 406

题解 | #Largest Rectangle in a Histogram#

题意：求出最大的可以用矩形覆盖的面积思路：这题和[USACO 2009 Mar S]Look Up类似，我们只要找到每个矩形左边第一个比它矮的地方和右边第一个比它矮的地方，然后这两个距离之差 * 矩形高就行了，从左往右走，如果遇到一个比之前遇到的最高的矮，那就说明那个最高的矩形的面积最大也...

2022-01-18

7 544

题解 | #装备合成#

思路：三分，三分要满足函数是先增后减或者先减后增的，这里可以三分用第一个方案的次数，假设第一个方案用了n次，那么第二个方案的个数就是min( (x-2n)/4 , y-3n )，对于单调性的证明，参考下面的博客。 https://blog.csdn.net/RunningBeef/article...

2022-01-16

0 362

题解 | #位数差#

题意：求出a[i]后面的数+a[i]与a[i]的位数差的和思路：可以整体二分，然后分治。假设这个数组长度为n，把它分成两半，就是[1，mid]和[mid+1,n]，我们可以先求出[1，mid]和[mid+1,n]各自的位数差，然后求出[1，mid]里的数作为a[i]，[mid+1,n]里的数...

2022-01-16

2 796

题解 | #完全平方数#

二分条件要想清楚，题目是找到l到r里的平方数的个数，其实就是在l到r里找0、1、2、3、4.....到31622这些数的平方，可以找左边界假设是x1，要找到满足x1 * x1>=l的第一个数，然后找右边界假设是x2，要找到满足x2 * x2<=r的最后一个数，那么x1到x2之间的数就是l...

2022-01-14

2 566