随笔

zrzring 2021-01-25 PM 56℃ 2条

可重集合的无嵌套子集的数量的最大值

2020夏令营的一个题

当时正解是一个DAG,但是这个题目应该有巧妙的性质,场上很多大佬都猜到了一个结论

记该可重集合大小为$n$,答案为大小为$\lfloor \frac{n}{2} \rfloor$的子集的数量

这个结论并没有得到证明,我也只是感性理解,通过几个性质并不是严格的证明这是对的

  • 性质1:最大无嵌套子集集合中的子集大小一致

对于任意一个子集,我们想通过它去扩展无嵌套子集集合,那必然是删掉该子集中的元素再加入该子集的补集中的元素

考虑如果我们通过一次操作删掉或加入了复数个元素,那仅仅扩展了$1$个新的子集,而我们每次删掉或加入这复数中的1个元素的话,我们可以扩展多次,而且对其它的元素并没有影响,于是我们每次扩展必定是删掉并加入单个元素,我们把这个过程表示为$(+1,-1)$

这样一来,如果我们得到了一个大小为$k$的初始子集,去用$(+1,-1)$扩展出整个子集集合,那整个子集集合中的元素一定和初始子集大小一致,且我们扩展出的子集集合为原集合的全部大小为$k$的子集组成的集合

由于其不可扩展,所以其为极大解,于是只要找到一个初始子集大小$k$使得答案最大即可解决该问题

  • 性质2:无嵌套子集中每个子集的补集组成的集合也是无嵌套子集

因为我们在构造无嵌套子集的时候用的策略是去掉一个子集中的元素加入一个子集中不在的元素,那么对于其补集来说这一过程也一样,所以该性质成立

只能推出这两个性质,还不够,不过感性理解的话,因为要找到一个子集大小$k$使得答案最大,一个集合能扩展的方案数取决于该集合内的元素数量和该集合的补集的元素数量的最小值,$k$越大则集合外的元素少,$k$越小则集合内的元素少,这样扩展出去的状态数就越少,于是我们取$k$为$n/2$

目前只能感性理解它是对的,如果我能发现更多的性质来严格证明的话再写吧

装备收集期望

给定一种怪物,等概率随机掉落n个职业的m类装备,问收集任意一个职业的全部m类装备期望需要打死这只怪物多少次

空间里看到的一道题,然后写了个3^3的dp,最后发现需要把一些状态合并,但并不好合并,于是只能换个思路

qwaszx说了一个min-max容斥,还不是很理解,改日填坑

NIM游戏

ZR的一道题 [#1541. [2020提高组十连测day2] 小W与屠龙游戏](http://www.zhengruioi.com/problem/1541)

想一种理解博弈论的方法,对于这个题,是任意两堆任意数量,推广一下

双方轮流从n堆石子中取x堆石子的任意数量,把每一堆的数量用二进制数表示,对应位相加并对x+1取模,每一位都为0即为先手必败状态

证明其正确性,考虑一个状态是必败状态当且仅当它的所有后继状态均为必胜状态,那么如果堆石子数满足上面的性质的话,应该是它的后继状态不会满足这个性质,才使命题正确

如果我们要对这x堆二进制下某一位集体-1的话,是不会在x+1取模下继续为0的,但是对于该位如果对某些堆-1并对某些堆+1的话,在更高的位是一定会被减的(NIM游戏只能石子),也就是我们一定会存在一个极多-1的位的,而这个极多-1的位置不可能达到减去x+1,于是他的后继状态不可能有满足上述性质的状态

评论



共 2 条评论


  1. cc攻击
    cc攻击

    网站是自己写的吗?

    回复 2021-02-05 08:01
    1. zrzring
      zrzring 博主

      每个页面最下面写了驱动和主题来源

      回复 2021-02-10 23:58
Title - Artist
0:00