2017-Sp334-team2

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

== 流水账 ==
=== chenjb ===
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：考虑本质不同的区间，只在区间内的答案先统计完，有可能画出区间的那个答案，看看后面有没有结束时间比自己早，没有的话加进答案。

 * B：考虑合并相同的段，然后如果枚举在一个位置插入，那显然两边对应位置要同字母且至少三个，于是只有中间可以插入。

 * C：

 * D：先把每个点看成一个需求的二进制状态mask，还有一个标记tag，每个点在收到自己需要的mask之后，可以选择在传出去之前是否&上tag，考虑从起点mask=7出发，每次拿已有的mask去扩展需求为这个mask的人，由于mask已经有了，所以新扩展的这些人一定都直接&上自己的tag，看看能不能形成新的mask，这样做完之后，枚举两个恰有一位1并且不在同位置的mask，这两个人可以共同or出一个新的mask，如果需求这个mask的人还有多个，则可以先连到第一个人身上，再从这个人出发，贯穿剩下的人。注意到这个mask的两个子集其实都已经存在了，则这些人没必要再&自己的tag，并且这样的情况最多不会超过3次，所以边数不会超过n+3，如果这样还染不出来显然无解。

 * E：枚举谁把那人干了，贪心取，更新答案即可。

 * F：显然prufer序包含恰有n-1个>n的点和m-1个<=n的点，大力猜想只要ka<=m-1且kb<=n-1则一定有解，可以随意填充，之后标准prufer构造，叶子节点是黑的时候取白的队列头，反之亦然。

 * G：猜想先rand后买，因此买可以视作用平均价获得一个随机物品，这样每个状态出现概率相同，直接dp统计k个物品代价为t的方案数，期望为Σf[k][t]/c(n,k)*min(rand1,rand2)。

 * H：考虑1填哪些位置，按照插入顺序从后往前考虑，当某个位置填了之后，显然它在自己插入时刻的相邻两个位置不能再填这个位置。考虑这样把能填的1都填了，如果只填了一个位置，肯定所有子区间满足条件，否则考虑最终状态，任意包含不止一个1的子区间，将所有的1删去之后，就是一个未填数字的序列上的子区间，所以剩下的未填序列变为一个子问题。由于这些1的任意插入时刻，任意子区间都可以把1都去掉变为新的子问题的子区间，一定是合法的，所以只需要不断的能填新的数字就填上，然后删去一些位置变为规模更小的子区间即可。显然，一个数字最多支配边上两个位置，所以一次规模至少减为原来的2/3，所以减小规模的次数大约为n对3/2取对数，(3/2)^24^>16000>n，所以数字种类足够。

 * I：n-1个人放A组，2个人放B组，每次组内找到最菜的人，然后两个最菜的人去掉更菜的，然后从外界补一个进来，重复n次，两个组的并集就是答案。

 * J：显然s<=最小值+1，最小值*数字个数是O(n)级别的，枚举暴力即可。

 * K：每一个序列唯一对应数字，注意序列末尾不能是0，直接组合数统计。

 * L：每次把目前和第k小字典序相同的人拿出来，后面按字典序加一个字母，k填完之后随便放。

流水账

chenjb

oipotato

subconscious

题解

  • A：考虑本质不同的区间，只在区间内的答案先统计完，有可能画出区间的那个答案，看看后面有没有结束时间比自己早，没有的话加进答案。
  • B：考虑合并相同的段，然后如果枚举在一个位置插入，那显然两边对应位置要同字母且至少三个，于是只有中间可以插入。
  • C：
  • D：先把每个点看成一个需求的二进制状态mask，还有一个标记tag，每个点在收到自己需要的mask之后，可以选择在传出去之前是否&上tag，考虑从起点mask=7出发，每次拿已有的mask去扩展需求为这个mask的人，由于mask已经有了，所以新扩展的这些人一定都直接&上自己的tag，看看能不能形成新的mask，这样做完之后，枚举两个恰有一位1并且不在同位置的mask，这两个人可以共同or出一个新的mask，如果需求这个mask的人还有多个，则可以先连到第一个人身上，再从这个人出发，贯穿剩下的人。注意到这个mask的两个子集其实都已经存在了，则这些人没必要再&自己的tag，并且这样的情况最多不会超过3次，所以边数不会超过n+3，如果这样还染不出来显然无解。
  • E：枚举谁把那人干了，贪心取，更新答案即可。
  • F：显然prufer序包含恰有n-1个>n的点和m-1个<=n的点，大力猜想只要ka<=m-1且kb<=n-1则一定有解，可以随意填充，之后标准prufer构造，叶子节点是黑的时候取白的队列头，反之亦然。
  • G：猜想先rand后买，因此买可以视作用平均价获得一个随机物品，这样每个状态出现概率相同，直接dp统计k个物品代价为t的方案数，期望为Σf[k][t]/c(n,k)*min(rand1,rand2)。
  • H：考虑1填哪些位置，按照插入顺序从后往前考虑，当某个位置填了之后，显然它在自己插入时刻的相邻两个位置不能再填这个位置。考虑这样把能填的1都填了，如果只填了一个位置，肯定所有子区间满足条件，否则考虑最终状态，任意包含不止一个1的子区间，将所有的1删去之后，就是一个未填数字的序列上的子区间，所以剩下的未填序列变为一个子问题。由于这些1的任意插入时刻，任意子区间都可以把1都去掉变为新的子问题的子区间，一定是合法的，所以只需要不断的能填新的数字就填上，然后删去一些位置变为规模更小的子区间即可。显然，一个数字最多支配边上两个位置，所以一次规模至少减为原来的2/3，所以减小规模的次数大约为n对3/2取对数，(3/2)24>16000>n，所以数字种类足够。
  • I：n-1个人放A组，2个人放B组，每次组内找到最菜的人，然后两个最菜的人去掉更菜的，然后从外界补一个进来，重复n次，两个组的并集就是答案。
  • J：显然s<=最小值+1，最小值*数字个数是O(n)级别的，枚举暴力即可。
  • K：每一个序列唯一对应数字，注意序列末尾不能是0，直接组合数统计。
  • L：每次把目前和第k小字典序相同的人拿出来，后面按字典序加一个字母，k填完之后随便放。