hnust_yangyanjun

题解

大数加法(1) 尺取法(1) 面经(4)

/ 注册

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

管道取珠

题意：链接：https://ac.nowcoder.com/acm/problem/17621来源：牛客网管道取珠是小X很喜欢的一款游戏。在本题中，我们将考虑该游戏的一个简单改版。游戏画面如图1所示：游戏初始时，左侧上下两个管道分别有一定数量的小球（有深色球和浅色球两种类型），而右侧输出管道为空。...

dp

2020-06-03

1 674

Protecting the Flowers

题意：有n只奶牛在吃花，为了减少花的损失，将奶牛放回谷仓去，每只奶牛距离各自的谷仓ti分钟时间的距离，并且每只在花园的奶牛每分钟吃di朵花，一次只能放一只奶牛回去，由于回去回来，所以需花费2*ti的时间，求奶牛最少吃多少花？思路：当AB二只奶牛回去顺序相邻时,我们可以发现AB前面的奶牛和AB后面的...

贪心

2020-05-28

0 494

货币系统

题意：有n种货币，每一种货币面值为a[i]，并且每种货币有无穷个，请问只需多少种货币可以达到和这n种货币一样的支付范围？思路：多重dp，将a数组按升序排列，如果第i种货币的值可以被前i-1种货币组成，则该面值的货币可以不要，计算不能被组成的货币种类数即可。代码： #include<bits...

dp

2020-05-27

0 727

港口

题意：有n个物品，每个物品重w[i],每一次操作可以将[l,r]区间的物品重量加一或减一。求最少多少次操作可以使每一个物品重量相等？思路：差分，每一个操作作用于差分数组为一个数加一一个数减一，第一个数与第0个数的差和第n个数与第n+1个数的差用于调节，所以只需计算第2个数到第n个数与它前一个数的差...

差分

2020-05-26

0 510

[JSOI2007]建筑抢修

题意：有n个建筑需要抢修，给出这n个建筑的抢修时间和截止时间，求最多可以抢修多少建筑？思路：按截止时间升序排列，用优先队列维护可维修的建筑的持续时间，因为截止时间是升序的，所以当遇到无法及时维修的建筑时，如果小于优先队列中最大的持续时间，可以替换，这样优先队列中数据量不变，总时间减少，相当于优化了...

贪心优先队列

2020-05-26

0 573

小AA的数列

题意：给出一个长度为n的序列，要求区间长度在[L,R]之间且为偶数的区间异或和之和？思路：参考：https://blog.nowcoder.net/n/4dacd8e372de4199a30442b4eee1849asum[i][j]为前i个数在第j位为1的个数pre[i][j][0]为在sum[...

2020-05-23

0 600

[CQOI2009]中位数图

题意：给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。思路：如果我们把比大于k的值变成1，比k小的值变成-1，那么计算从左边到k区间的值，并记录个数，加上为0的个数，再计算从右边到k区间的值，加上相反数的标记个数，如果值...

2020-05-22

0 562

图的遍历

题意：有一个n个点节点m条边的无向图，从点1开始遍历，按照每次“走两步”遍历整个图。可以发现按照每次走两步的方法，不一定能够遍历整个图，所以最少加几条边，可以完整的遍历整个图？思路：如果一个连通块中有奇数环，则该连通块可以全部遍历到，加一条边可以使二个连通块合在一起，最后在一个大于等于3的连通块中...

图

2020-05-21

0 581

简单瞎搞题

题意：一共有n个数，第i个数是xi, xi可以取 [li , ri] 中任意的一个值。设 S = ,求S种类数? 思路：bitset,01背包bit[i]为前i个数中能得到的值的那一位为1，否则为0；当加上x[i+1]的平方时相当于bit[i]向左平移了x[i+1]的平方个位置所以bit[i...

bitset

2020-05-21

0 533

比赛

题意：一场比赛总共有12个题，对于第i个题，有a[i]的几率解决它，如果不能解决，则你有b[i]的概率从左边那个队那里听会这个题的做法，有c[i]的概率从右边那个队那里听会这个题的做法，请问最终你们队伍解出0-12题的概率分别是多少？思路：每一题单独的解决概率的d[i]=a[i]+(1-a[i])...

dp

2020-05-21

0 466