雅礼NOIP2018集训 day5
联
题面
由于出题人懒所以没有背景。
一个无限长的 01 序列，初始全为 0，每次选择一个区间 [l,r] 进行操作，有三种操作：
• 1 l r 将 [l,r] 中所有元素变成 1。
• 2 l r 将 [l,r] 中所有元素变成 0。
• 3 l r 将 [l,r] 中所有元素异或上 1。
每次操作后询问最左边的 0 在哪个位置。
下标从1开始。
大概思路
把所有点和点与点的区间离散化
然后线段数即可
赛
题面
由于出题人思维枯竭所以想不出好玩的背景。 有 n 个物品，第 i 个物品的价格是 vi，有两个人，每个人都喜欢 n 个物品中的一些物 品。 要求选出正好 m 个物品，满足选出的物品中至少有 k 个物品被第一个人喜欢，k 个物 品被第二个人喜欢。并求出最小的价格和。
大概思路
把物品分为4类 A类:两个人都喜欢的物品 B类:只有第一个人喜欢的物品 C类:只有第二个人喜欢的物品 D类:所有物品
先把四个数组先从小到大排序
我们先全部选A类 然后从大到小枚举A类选的个数 每少选一个A类就分别B、C类从小到大选一个数 把选过的数在D类标记然后用二分查询 D类需要用树状数组或线段数维护
题
题面
由于出题人赶时间所以没办法编故事来作为背景。
一开始有 n 个苹果，m 个人依次来吃苹果，第 i 个人会尝试吃 ui 或 vi 号苹果，具体 来说分三种情况。
• 1、两个苹果都还在，那么这个人将随便选一个苹果吃了。
• 2、只有一个苹果，那么这个人将吃掉这个苹果。
• 3、都不在了，这个人吃不到苹果就走了。
请问有多少对苹果 (i, j)（i < j）满足它们两个都幸存下来的概率 > 0。
大概思路
我们一个苹果最后存活，需要哪些苹果
设定一个需要被保护的苹果的集合{S}
一开始将最后存活的那一个苹果放进集合里
接着我们从后往前看
如果一个人要吃的两个苹果，都不在保护集合内，我们就让他吃，不用理他
如果一个人要吃的两个苹果，一个在保护集合内，另一个不在保护集合内，我们就会吃掉不在保护集合内的苹果。
不在保护集合内的苹果，只能现在被吃掉，否则最后存活的那一个苹果无法存活。
因此我们将在保护集合内的苹果放在保护集合内。
如果一个人要吃的两个苹果，都在保护集合内，很遗憾，最后存活的那一个苹果无法存活。
每一个苹果都作为最后存活的那一个苹果一次
然后枚举两个苹果，如果它们都能活到最后且它们需要保护的苹果没有交集的情况下，它们都可以活到最后。
标签：存活,一个,day5,NOIP2018,雅礼,苹果,物品,集合,保护 From： https://www.cnblogs.com/blln/p/16616471.html