同一骨架 2009 年河南预赛 第 14 题 · P010221
有序底集上的子集条件,可先选一个能唯一恢复原对象的端点或切口骨架,再数其间的自由选择。最终若有权重,应按每个原对象的贡献累加,不能把相同极值去重或让空对象产生虚假切口。
前题固定最小偶数后按最大元素分类,内部任取并乘最大值权重;后题选择两个严格分离非空集的并集,再在有序并集中选择切口,权重来自可选切口个数。
(14 分)已知集合 ,集合 ,且集合 中的最小元素是偶数。
若集合 中的最小元素是 ,最大元素是 ,求满足条件的集合 的个数;
求所有满足条件的集合 中的最大元素之和。
这是解答题,请在纸上写出完整过程。写完后对照解答给自己评分。
第一问固定两端后中间任取;第二问按最小偶数分类,再对每类的最大值加权求和。
先回想这道题的想法,再试试当前题。
(1)二与十三必选,其间三至十二的十个数任意选,所以有 个。 (2)固定最小元素为 ,。单点集贡献最大值 ;若最大元素为 ,其中 ,中间 个数任取,共 个。故此类最大值之和为
这里用了 与 。再对所有最小偶数求和,得
单点偶数集合不能漏掉;同一最大值出现在多个不同集合中,应按各集合分别贡献,不能先把最大值去重。按最小元素的50类互斥并覆盖所有题给集合。
对子集的极端元素求加权和,可固定一个端点作为骨架,再按另一个端点留下的自由区间计数。
第二问不是数集合而是按各集合最大元素加权,须双端点分类、保单点集并算有限加权等比和。
同一骨架 2009 年河南预赛 第 14 题 · P010221
有序底集上的子集条件,可先选一个能唯一恢复原对象的端点或切口骨架,再数其间的自由选择。最终若有权重,应按每个原对象的贡献累加,不能把相同极值去重或让空对象产生虚假切口。
前题固定最小偶数后按最大元素分类,内部任取并乘最大值权重;后题选择两个严格分离非空集的并集,再在有序并集中选择切口,权重来自可选切口个数。
已记下,谢谢!