hnust_yangyanjun

分类

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

/ 注册

TA的专栏 30篇文章 0人订阅

每日一题题解

30篇文章 895人学习

全部文章（共125篇）

德马西亚万岁

题意：有一个n*m的地图，为0不可以站人，为1可以站人，二个人不能相邻，求合理的方案数？思路：状压dpdp[i][j]为第i行状态为j的方案数（状态为第i行二进制转化为十进制的值，既一个二进制为该行的整数）。d[i]表示地图中第i行这m位取反表示的十进制。如果该状态合法，则j&(j-1)=...

dp

2020-06-09

0 527

Sumo and Electricity(easy)

题意：n个核电站，m条电缆，每个核电站有一个耗电量，电缆传输功耗为两个核电站耗电量之间的异或值。其中有一个核电站为耗电量为-1，表示我们可改变该核电站的耗电量，求总最低传输功耗，并求在此基础上的最低总耗电量？思路：我可以改变的只有一个核电站，所以我能决定的传输功耗为与该核电站相连的电缆，所以将于该...

2020-06-09

0 609

旅游

题意：有一个n个城市有（n-1）条道路的无向图，有二人打算旅游，第一天住在s市，并浏览了周围距离不大于1的城市，每天会选择一个城市住，他们不想住在已经浏览过的城市，并且他们想旅游时间尽可能长.求最长旅游多少天？思路：树状dp,dp[v][0/1]表示以v为根节点的树，根节点分是否住的的最大旅游天数...

树状dp

2020-06-04

1 689

Contest

题意：有n支队伍一共参加了三场比赛。一支队伍x认为自己比另一支队伍y强当且仅当x在至少一场比赛中比y的排名高。求有多少组(x,y)，使得x自己觉得比y强，y自己也觉得比x强（既互相觉得比对方强），(x, y), (y, x)算一组。思路：当x自己觉得比y强，y自己也觉得比x强，只有这二种情况，第一...

树状数组

2020-06-04

1 699

管道取珠

题意：链接：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