贪心法 – Tgotp-Blog

1691: [Usaco2007 Dec]挑剔的美食家

将每次满足条件价格最小的w放入对应的。

用set维护即可

c++代码如下:

 

1629: [Usaco2007 Demo]Cow Acrobats

已知:对于 两个相邻的牛,他们交换只会改变他们两个的相互关系,不会影响其余的条件。

那么只用比较a.w - b.s 与b.w - a.s即可。

c++代码如下:

 

F. New Year and Rainbow Roads

GoodBye2017 F题。

最后一分钟被绝杀,被手速坑了。。。

容易发现,R,B都必须与G相连,分下面三种情况

1.对于在最左边G的左边的点,一定会连这个G

2.那么也就是在某两个G中间,求得如何连接使得两个黑点(经过R,B )花费最小

3.对于在最右边G的右边的点[......]

Read more

2697: 特技飞行

直接贪心,按价值分别放在两边。

c++代码如下:

 

1110: [POI2007]砝码Odw

因为每两个数之间都是倍数关系,那么一定大的数可以被小的替换掉,且数字最多有log个,然后贪心就好了。

c++代码如下:

 

NOIP2013D2T1 积木大赛

贪心,比较巧妙。

也就是说,我们搭建一层,一定会将他延伸至他能延长的最长处。

所以,如果当前比前面的高的话,才需要单独去弄,不然一定会在之前的时候弄好。

具体见代码。

c++代码如下:

 

T7951 排序

贪心搞搞就好了。

观察,我们发现要把大数尽可能靠前输出。

所以可以用队列维护。

我们先从后往前扫一遍最大值。

然后再从前往后枚举。

对于当前位置 i ,如果后面有比此时更大的数,当然要继续往后找到这个maxNum,

如果没有我们就不断 pop ,直到后面有比前面大[......]

Read more

疫情控制 NOIP2012 T6

二分答案 + 贪心;

你会发现,其实对于每个点,我们只要能往上(不是根节点)一定是更优的,如果是根节点,我们先看看这个点通不通,不通的话这个点判通,返回,不然的话进入根节点找最小不通的点。

最后一个点恶心的菊花图,所以对于这道题的极限数据,你倍增不倍增都没卵用,我也懒得帖我倍增+桶排的代[......]

Read more

BZOJ1046: [HAOI2007]上升序列 Luogu 2215

思路:lis + 二分答案 + 贪心?

过程:之前一直在纠结字典序输出,后来一想,从最前面开始,向后枚,肯定是最优的,还有一个坑点,严格按照格式输出;

另外就是 lis  要注意从后向前找,即f[i]代表从 i 开始,最长的上升序列长度吗,其他的就是基础lis过程。

over[......]

Read more

Educational Codeforces Round 22 A

题面

A. The Contest
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

s[......]

Read more

2017年6月6日 Educational Codeforces Round 22 A已关闭评论 / /
Tag: