hnust_yangyanjun

分类

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

/ 注册

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

每日一题题解

30篇文章 895人学习

全部文章（共9篇）

Microtransactions (hard version) 来自专栏

题意：有i种物品，每种物品需要买k[i]个，然后商店会有m次特价出售，第j次为在di天出售第ti种物品，物品原价2元，特价1元，你每天上午可以获得一元，下午可以进行交易，求获取所有物品花费的最少时间为多少天？思路：如果第i天满足条件，则i+1天一定满足，所有二分答案.如何判断答案x是否符合：按贪心...

二分贪心

2021-02-28

1 591

Train Hard, Win Easy 来自专栏

题意：有n个参赛者，每个参赛者在做第一题和第二题都有一个罚时，两个人组成一队，每个人负责一题，该队罚时为两人罚时之和（队内会取最优策略），求该参赛者在所有可能的组队中总罚时为多少？思路：我们发现可以按照前一个写第一题，后一个写第二题最优来排序：既：A.a+B.b<A.b+B.a先求该参赛者与...

贪心前缀和

2021-02-10

1 798

[HAOI2006]均分数据来自专栏

题意：将n个数分成m组，求最小均方差？思路：随机打乱数组，然后贪心求结果，取最小值。(double)clock()/CLOCKS_PER_SEC得出程序运行的时间，单位为S。random_shuffle(a+1,a+n+1);打乱数组。贪心策略：前m个数每个数单独为一组，然后将剩余数分给当前最小数...

贪心

2021-01-26

1 632

黑白树

题意：有一颗n个节点的树，每个节点有一个权值k[i]，一开始树上节点全是白色的，你可以选择一个白色的节点进行染色，使该节点到根节点路径上的点距离该节点小于k[i]的节点染成黑色。求使该树所有节点变黑的最少操作次数。思路：树形结构+贪心由于染色的节点在你选择的节点和根之间，所以叶子节点你一定会选择，...

贪心树状结构

2020-08-21

1 788

矩阵消除游戏

题意：有一个n*m的矩阵，你可以进行k回合的游戏，每一回合将矩阵的一行或者一列的值置零并将分数加上。求你最后最多能得多少分？思路：由于消除行对列有影响，所以不能简单的贪心，但你n和m小于15，所以我可以枚举消除列的状态，然后对每一种合理状态再对行进行贪心操作，然后取最大分数值。代码： #incl...

枚举贪心

2020-08-10

1 867

Protecting the Flowers

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

贪心

2020-05-28

0 494

[JSOI2007]建筑抢修

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

贪心优先队列

2020-05-26

0 573

模拟战役

题意：给出一个整数m,再给出8行字符串，前4行为司机基地情况，后四行为齐齐基地情况，求齐齐在摧毁司机全部大炮后最多剩多少门大炮？（无法全部摧毁司机大炮则输出-1）思路：dfs求出司机基地有多少个大炮连通块，再用dfs求出齐齐每一个大炮连通块的大炮个数并保存，由于保存最多的大炮，使用的大炮所在连通块...

dfs 贪心

2020-05-18

0 551

美味菜肴

题意：有n种食材，m种菜肴，每种菜肴给出所需食材和美味值和制作时间，因为每种食材以a[i]的速率变得不新鲜，求在t秒总美味值最大为多少？注意：最大总美味值可能为负。思路：贪心+01背包贪心：设二种相邻菜肴，第一种所需食材变的不新鲜的速率为w[i].a,美味值为w[i].b，制作时间为w[i].c...

贪心 dp

2020-05-04

0 917