SuperDY

分类

题解(8)

/ 注册

全部文章（共8篇）

Sumo and Robot Game

题意：给出X轴上的n个点的坐标，每一个点的位置都有一个权值，有正有负，你可以移动X步，问可以获得的最大权值和是多少。思路：这里提供一个比较容易理解的做法，比赛时写bug一直没调出来，首先我们肯定要找到最后一个小于等于0的位置t，然后用一个辅助数组b记录从t开始到1和从t+1到n的权值累加和，然...

2020-06-06

3 579

小A与小B

题意：给出一张地图和小A和小B的位置，问两个人是否能在某一个点相遇，如果能相遇，那么需要的最短时间是多少。思路：首先肯定是要搜索了，首先分析小A，小A的行走方式简单，所以可以对小A BFS一遍，用一个数组记录小A到达这个位置所需要的最短时间，那么如果小B也能走到这个位置时，取所有可以走到公共地方时...

2020-06-04

0 853

旅游

题意：给出一个无向树，每一个节点代表一个城市，问从给出的城市出发，每一次到达一个城市之后都会将距离他为1的城市访问完，第二天继续访问其它没有访问的城市，问最多可以持续多少天。思路：简单的树形dp，跟树形dp模板题没有上司的舞会一样，设dp[i][0]代表不把i作为休息点的以i为根的最大天数，dp[...

2020-06-01

0 720

Protecting the Flowers

题意：给出n头牛的运输时间和每分钟的破坏值（如果该头牛没有被运走的话，每分钟造成的损失就是该破坏值）；问将所有牛运送完造成的最小损失是多少。解题思路：我们先假设有两头牛i和j，两头牛的运送时间和破坏力为q[i].ti,q[i].val,q[j].ti,q[j].val；那么先运送i花费较小的前提是...

2020-05-27

0 651

货币系统

题意：给出一组数据，让你简化这个数组，使得原数组中任意一个元素都可以被简化后的数组表示，表示的方式为从简化后的数组抽取数组中任意元素任意次累加和等于该元素，求简化后数组的最小长度。解题思路：这道题类似于牛客的另一道题砝码，不过砝码可以相减，但是思路都差不多。首先如果一个元素能被已经选择的元素表示出...

2020-05-26

0 641

[JSOI2007]建筑抢修

题意：给出n个建筑的修复需要的时间和截止时间，建筑必须要在截止时间结束前修复才行，问最优的修复顺序下的最大修复建筑数量是多少。解题思路：首先第一印象肯定是和贪心脱不了关系了，如果可以修复，我们肯定先修复截止时间早的建筑，后修复截止时间迟的建筑。所以我们首先需要对截止时间进行排序，然后从第一个到最后...

2020-05-25

0 710

[CQOI2009]中位数图

题意：给你一个排列和一个数值k，问数组中存在多少以k为中位数且长度为奇数的连续段。解题思路：首先我们可以想到的是找到k的位置，然后对k左右两边取数的方式都check一遍看是否合法，时间复杂度肯定不允许；所以需要转换一下思路，因为是要求中位数，所以我们并不关心选择的序列每一位的实际大小，只需要找到序...

2020-05-21

0 774

图的遍历

图的遍历：[https://ac.nowcoder.com/acm/problem/52275] 解题思路：首先容易想到是如果是一个奇数环，那么该环上任意一点都可以被经过，因为gcd(2，奇数)==1,所以延申一下与奇数环连接的所有点也可以被经过，因为可以通过环上的的点来调节（可以选择后退...

2020-05-20

0 723