Canan

分类

题解(31)

/ 注册

全部文章（共31篇）

字符串（尺取法）

https://ac.nowcoder.com/acm/problem/18386 题意：给定一字符串s，找到其包含所有小写字母的最短子串。分析：枚举区间，首先想到尺取法。尺取法：先初始化区间[0,-1]，尺取移动右端点至区间[l,r]为合法区间，然后在满足条件的情况下不断向右移动左端点，缩小合法...

2020-06-15

1 787

A supermarket（优先队列）

https://ac.nowcoder.com/acm/problem/50995 题意：超市有n件物品，已知它们的利润p和过期时间d，每天只能卖一件一件物品，过期的物品不能售卖，合理安排每天售卖的物品，问最大利润是多少？~多组数据输入输出分析：最大价值中先要保证物品不过期，先按日期正序排序，排序...

2020-06-13

0 608

失衡天平（dp）

https://ac.nowcoder.com/acm/problem/19158 题意：有一个天平，每次只要放上去的东西重量相差不超过m即可拿走，问最多能带走物品的重量为多少？分析：在这个问题中，我们关心的只有两边的差值，如果两边差值小于等于m，那么天平就是等价的，那么对于当前差值j，你再加一...

2020-06-09

1 742

扔硬币（组合数数学+分数取模）

链接：https://ac.nowcoder.com/acm/contest/5758/D来源：牛客网题意：有n枚硬币，正反概率相同，已知至少有m枚硬币是反面，问恰好有k枚硬币是正面的概率是多少。分析：首先很容易，当正面硬币数+反面硬币数大于总硬币，即m+k>n时，结果不存在，概率为0...

2020-06-09

0 1142

小A与小B

https://ac.nowcoder.com/acm/problem/23486 题意：有一迷宫，小A每秒移动1次，方向为上下左右左上左下右上右下8个方向，小B每秒移动2次，方向为上下左右四个方向，问他们最早什么时候能够相遇？分析：迷宫问题，求最短相遇时间，优先考虑用bfs。因为小B每秒运动...

2020-06-04

0 783

[CQOI2010]扑克牌

https://ac.nowcoder.com/acm/problem/19916 题意：给n种牌，每种牌有a[i]张，m张万能牌，问能组成多少套牌。（每套牌只能使用一次万能牌）分析：可以考虑二分答案，贪心进行判断。二分思路：假设答案为x，即最多能够构成x套牌，那么每种牌至少x张，所以但c[i]&...

2020-06-04

0 563

“科林明伦杯”哈尔滨理工大学第十届程序设计竞赛BCEFHJ

https://ac.nowcoder.com/acm/contest/5758B：减成一分析：1.如果前面那个数比这个数大，那直接跳过，因为前面一个数可以带它躺成1。2.如果前面那个数比这个数小，那区间是只能扩到前一个数这么大，因此还要进行多余的操作使自己变成1，于是产生了(a[i]-a[i-1...

2020-06-01

0 718

旅游

https://ac.nowcoder.com/acm/problem/15748题意：有n个节点n-1条边，由s节点开始，之后每次选择的节点不能选择之前的选择过的节点及其相邻节点。分析：n个节点，n-1条边，由s节点开始选择，很明显是一颗以s节点为根节点的树，这是一道树的最大独立集问题，由于n数...

2020-06-01

0 616

contest

题意：有n支队伍参加n3场比赛，一支队伍x认为自己比另一支队伍y强当且仅当x在至少一场比赛中比y的排名高，也就是互相赢过对方，这样算一组（x,y），试问存在多少组？分析：我们首先想到的思路是将第一场比赛进行排序，保证i自认为比i+1强，然后寻找后面比赛存在多少组j比j+1强，这样暴力下来复杂度要O...

2020-05-30

0 697

Protecting the Flowers

https://ac.nowcoder.com/acm/problem/25043题意：有n头牛要***漂亮的花朵，已知每头牛迁回牛舍的时间以及每分钟***花的数量，问最少要损耗多少花才能遏制这种行为。分析：出于保护美的渴望，这种止损的行为下意识贪心了起来，脑瓜不够用先简化一下问题，假设只有2头牛...

2020-05-27

0 695