2017-Codeforces-team2

从 Trac 迁移的文章

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

原文章内容如下：

 == 914F Substrings in a String ==
  * 题意：长度不超过100000的小写字母字符串，1操作修改一个字母，2操作询问区间[l,r]有多少个t串，t串长度总和不超过100000，操作个数不超过100000。
  * 题解：开26个大小为N的bitset，维护每个字符出现的位置，对于每个询问，开一个bitset全部置为1，枚举t串长度依次把相应字符的bitset右移i-1位 &到相应的起点，就得到了所有合法的起点，再取出属于[l,r]的即可。

 == 914G Sum the Fibonacci ==
  * 题意：给定一个数组s，定义合法的下标五元组(a,b,c,d,e)如下：1.s[a]&s[b]=0 2.(s[a]|s[b])&s[c]&(s[d] xor s[e])=2^i^，求所有五元组的贡献和。某一五元组(a,b,c,d,e)的贡献为fib[s[a]|s[b]]*fib[s[c]]*fib[s[d] xor s[e]]，其中fib[I]定义为斐波那契数列的第i项，且f[0]=0,f[1]=1。要求答案对1E9+7取模。数组长度范围为10^6^，数字大小为[0,2^17^)。
  * 题解：记录s中每一种数字分别出现了几次，记为数组vc。对于任意x=s[a]|s[b]，由于s[a]&s[b]=0，显然s[a]和s[b]为x的两个互补的子集，对于所有的x，枚举子集便可统计出对于每一种x有多少对合法的(a,b)满足条件，记为数组vab。对于x=s[d] xor s[e]，只需做一次xor下的FWT即可得到每一种x有多少对(d,e)，记为数组vde。将vab，vc，vde数组的每一个值分别乘上下标所对应的fib值，并对三个数组做一次and下的FWT，将结果中2^i^的贡献都取出来即可。

 == 911F Tree Destruction ==
   * 题意：给出一棵树，每次你选择两个叶子节点，将其简单路径累积到答案，然后选择其中一个叶子节点删掉，进行n-1次操作直到剩下一个点，要求给出一种方案，使得答案最大，n<=200000。
   * 题解：找到一条直径，然后直径外的所有子树从叶子一步步收缩，其另一端一定是直径的某一端，收缩完之后将直径收缩即可。因为每个点在树上的最远点一定是直径的某一端，所以每次都取到了该点被删掉时取的上限，因此最优。

914F Substrings in a String

  • 题意：长度不超过100000的小写字母字符串，1操作修改一个字母，2操作询问区间[l,r]有多少个t串，t串长度总和不超过100000，操作个数不超过100000。
  • 题解：开26个大小为N的bitset，维护每个字符出现的位置，对于每个询问，开一个bitset全部置为1，枚举t串长度依次把相应字符的bitset右移i-1位 &到相应的起点，就得到了所有合法的起点，再取出属于[l,r]的即可。

914G Sum the Fibonacci

  • 题意：给定一个数组s，定义合法的下标五元组(a,b,c,d,e)如下：1.s[a]&s[b]=0 2.(s[a]|s[b])&s[c]&(s[d] xor s[e])=2i，求所有五元组的贡献和。某一五元组(a,b,c,d,e)的贡献为fib[s[a]|s[b]]*fib[s[c]]*fib[s[d] xor s[e]]，其中fib[I]定义为斐波那契数列的第i项，且f[0]=0,f[1]=1。要求答案对1E9+7取模。数组长度范围为106，数字大小为[0,217)。
  • 题解：记录s中每一种数字分别出现了几次，记为数组vc。对于任意x=s[a]|s[b]，由于s[a]&s[b]=0，显然s[a]和s[b]为x的两个互补的子集，对于所有的x，枚举子集便可统计出对于每一种x有多少对合法的(a,b)满足条件，记为数组vab。对于x=s[d] xor s[e]，只需做一次xor下的FWT即可得到每一种x有多少对(d,e)，记为数组vde。将vab，vc，vde数组的每一个值分别乘上下标所对应的fib值，并对三个数组做一次and下的FWT，将结果中2i的贡献都取出来即可。

911F Tree Destruction

  • 题意：给出一棵树，每次你选择两个叶子节点，将其简单路径累积到答案，然后选择其中一个叶子节点删掉，进行n-1次操作直到剩下一个点，要求给出一种方案，使得答案最大，n<=200000。
  • 题解：找到一条直径，然后直径外的所有子树从叶子一步步收缩，其另一端一定是直径的某一端，收缩完之后将直径收缩即可。因为每个点在树上的最远点一定是直径的某一端，所以每次都取到了该点被删掉时取的上限，因此最优。