【水题合集】7.13贪心考试

ljh大爷的贪心题真是太神辣

1.战役

这题是防AK题

然而被我骗分骗过了= =

正解是数学推一推会得到神奇的东西

我一开始用错误的程序打表得到是单峰函数。。然后写了个三分过了大样例自信提交就A了

然而还是能卡掉的吧 虽然不是很好卡

2.jump的树

首先任意两点之间的异或和可以表示为两个端点分别到根节点的异或和的异或和 这是异或带来的神奇性质

那么把所有点到根节点的异或和都求出来 问题就转化为在这些数中找出两个数使得它们的异或和最大

考虑对于任意一个数,要找到其它数中与它异或和最大的数,可以贪心地从高位往低位尽可能找有没有当前位与它不同的数

这个就可以用trie来实现

那么就可以用31次找出与某个数异或和最大的数

3.团结的队伍

普及组水题

4.llg的农场

能覆盖某个庄稼的圆心是在一段区间里的

所以就转化成一堆区间的问题了

按右端点排序贪心地放稻草人

说点什么

  Subscribe  
提醒