ACM

HDU 5527 Too Rich(贪心好题)

HDU 5527 Too Rich(贪心好题)
题意:给出你硬币价值分别为1,5,10,20,50,100,200,500,1000,2000的数量,请找出能凑成价值为p的硬币最多的方案,输出此时的硬币数量。题解:假设我们不考虑50,500这两个数,那么,其他的数都是前一个数的倍数,因此,只要前面有足够的硬币剩余,我们就可以将后面的硬币转换成前面的硬币来增加硬币数量。但是现在这里的50和500改变了这一性质,所以我们考虑改进这一贪心方法。方法一... 继续阅读 »
ACM

tenka1-2017-IntegerotS(位运算+贪心)

tenka1-2017-IntegerotS(位运算+贪心)
题意:给出n组数据,ai,bi,意味着编号为ai的物品价值为bi,求选择一些ai,他们或运算之后小于或等于k的最大价值。题解:贪心法,因为当前选择的ai或运算之后有可能会大于k,考虑到或运算的性质,假设当前选择的数或运算之后必须小于或者等于k,那么我们必须要选择这样的一个a[i],a[i]&k==a[i]。即k的二进制位上有1的地方,a[i]才能有1。然后,循环将k二进制位上有1的位减一(... 继续阅读 »
ACM

CodeForces - 626C - Block Towers(二分)

CodeForces - 626C - Block Towers(二分)
题意:给出n、m,请计算一个只有n个2的倍数和m个3的倍数构成并且没有重复的序列中最小的max(n*2, m*3)。为了接下来学习01规划找到的这个题。这个题有两种解法,一种是贪心,一种是二分。我们先来看看贪心解法:一、贪心:首先,我们考虑到2的倍数和3的倍数是有他们的最小公倍数6的倍数的重复的。所以我们只需要先假定n就是n*2,m就是m*3,这时候可能有6的重复,所以我们从6开始不断增长6的倍数... 继续阅读 »
ACM

CDOJ - 1334 郭大侠与Rabi-Ribi(stl、贪心)

CDOJ - 1334 郭大侠与Rabi-Ribi(stl、贪心)
开始一直想的是直接安时间-价值排序,然后从时间最少的开始for循环一遍找兔子,如果时间不够用则进入下一个时间段找兔子,然后就wa啊,后来想想有点不对,万一时间少的地方有比时间大的地方的兔子呢,所以这个地方要用一个优先队列来维护,和bzoj上面建筑抢修那个题一毛一样啊。地址:http://acm.uestc.edu.cn/#/problem/show/1334代码:StatusAcceptedTim... 继续阅读 »
ACM

2017湘大邀请赛 Partial Sum(贪心)

2017湘大邀请赛 Partial Sum(贪心)
题目的意思是,给你n个连续的序列,有m次操作,每次操作是求某个区间和然后减去c,求能获得的最大值。比赛的时候真的是脑子短路,这么简单的贪心竟然看不出来,每次看到区间就想到dp,然后就不想做了,心痛啊。不过还是有个坑点,就是长整型,湘大的OJ是要用%I64d输出的。代码:#include <iostream> #include <cstdio> #in... 继续阅读 »
ACM

HDU 6012 - Lotus and Horticulture(贪心)

HDU 6012 - Lotus and Horticulture(贪心)
题目意思是一个人要做研究,现在要你计算植物在特定温度下的研究价值,给定一个区间,区间以上,区间内,区间以下三个段位是不同的价值。植物很多,而且每盆植物都有自己的区间价值,然后现在要你计算出研究价值最大的那个温度。一开始也不知道自己再想什么玩意儿,虽然想到了贪心但是却在乱做,后来看了题解~我们可以从最低的温度开始慢慢往上计算。在输入数据时就要把位置设置好了,然后赋值,所以肯定需要一个结构体来存咯。要... 继续阅读 »