Difference between revisions of "2018 Multi-University, HDU Day 4"

From EOJ Wiki
Jump to navigation Jump to search
Line 13: Line 13:
 
那么怎么筛掉呢?如果用原有的性质,即逐一检查比它小的所有数的因子个数,在这个数据规模下肯定是来不及的。其实有下面的结论:$x$ 有不超过 $K$ 个比它小的数因子数比它多,那么这些比它小的数肯定每个都在候选列表里。我们可以使用反证法证明这个结论:如果不在列表里,有一个不在列表里的数 $y<x$ 满足因子比 $x$ 多,又因为不在列表里,它有超过 $K$ 个比它小的数因子数比 $y$ 多,那么至少有 $K+1$ 个数小于 $x$ 且因子比 $x$ 多,矛盾。所以我们进行筛选的时候,就只依赖于这个列表中的数了。从小到大枚举这个列表中的数,然后维护因子数前 $K+1$ 大的,如果 $x$ 的因子数比第 $K+1$ 大的因子数都小,那么就跳过,否则把 $x$ 加入下一轮的答案,并将 $x$ 的因子数加入集合。
 
那么怎么筛掉呢?如果用原有的性质,即逐一检查比它小的所有数的因子个数,在这个数据规模下肯定是来不及的。其实有下面的结论:$x$ 有不超过 $K$ 个比它小的数因子数比它多,那么这些比它小的数肯定每个都在候选列表里。我们可以使用反证法证明这个结论:如果不在列表里,有一个不在列表里的数 $y<x$ 满足因子比 $x$ 多,又因为不在列表里,它有超过 $K$ 个比它小的数因子数比 $y$ 多,那么至少有 $K+1$ 个数小于 $x$ 且因子比 $x$ 多,矛盾。所以我们进行筛选的时候,就只依赖于这个列表中的数了。从小到大枚举这个列表中的数,然后维护因子数前 $K+1$ 大的,如果 $x$ 的因子数比第 $K+1$ 大的因子数都小,那么就跳过,否则把 $x$ 加入下一轮的答案,并将 $x$ 的因子数加入集合。
  
几个细节:质因子大概加到 350 左右就不再有用了,可以直接退出;乘的时候要注意经典的防爆 LL;实现还是比较紧的,全部用 set 实现的话可能会超时,建议能开数组的地方全部开数组,由于质因子是从小到大枚举的,所以不会有去重的问题;刚开始直接算 233 的答案,最后存答案的时候,从大到小枚举 $K$,逐步筛选,用 234 个 vector 记录所有答案,由于 $K$ 的时候的答案集合一定是 $K+1$ 的时候的答案集合的子集,所以这样做是正确的。
+
几个细节:质因子大概加到 350 左右就不再有用了,可以直接退出;乘的时候要注意经典的防爆 LL;实现还是比较紧的,全部用 set 实现的话可能会超时,建议能开数组的地方全部开数组,由于质因子是从小到大枚举的,所以不会有去重的问题,新加进来的数直接存在后面,然后 sort 就好了;刚开始直接算 233 的答案,最后存答案的时候,从大到小枚举 $K$,逐步筛选,用 234 个 vector 记录所有答案,由于 $K$ 的时候的答案集合一定是 $K+1$ 的时候的答案集合的子集,所以这样做是正确的。
  
 
另外回答询问的时候,std 采用了某种技巧,往答案里填数的时候减去了一个下标,可以一个 log。但是直接二分套二分两个 log 也能过(这不是瓶颈)。
 
另外回答询问的时候,std 采用了某种技巧,往答案里填数的时候减去了一个下标,可以一个 log。但是直接二分套二分两个 log 也能过(这不是瓶颈)。

Revision as of 02:46, 3 August 2018

Problem A

Upsolved by ultmaster.

题意:一个数是好数当且仅当比它小的且因数个数比它多的数不超过 $K$ 个。求第 $n$ 个不好的数。

题解:此题是一个之前没补的题:2015-2016 Makoto rng_58 Soejima Сontest 4 的 A 的加强版。一石二鸟把两个题都补了。

首先这个好数是不多的,大概在导致即使询问在 $10^{18}$,答案也就在 $10^{18}+10^5$ 的规模。所以考虑用一种快速的暴力求出所有的好数。

其次考虑一个数一旦不是好数,这个数所有的倍数也不是好数(因为所有比它小的,害它不是好数的数,同样也会加倍)。基于这点考虑,增加很多质因子是没有好处的,我们可以维护一个已经找到的好数的集合,然后从小到大枚举质因子,不断扩充这个集合。当然这个扩充完的集合肯定不是每个数都合法的,我们每次扩充完毕之后,还要从这个集合里面筛掉一点。

那么怎么筛掉呢?如果用原有的性质,即逐一检查比它小的所有数的因子个数,在这个数据规模下肯定是来不及的。其实有下面的结论:$x$ 有不超过 $K$ 个比它小的数因子数比它多,那么这些比它小的数肯定每个都在候选列表里。我们可以使用反证法证明这个结论:如果不在列表里,有一个不在列表里的数 $y<x$ 满足因子比 $x$ 多,又因为不在列表里,它有超过 $K$ 个比它小的数因子数比 $y$ 多,那么至少有 $K+1$ 个数小于 $x$ 且因子比 $x$ 多,矛盾。所以我们进行筛选的时候,就只依赖于这个列表中的数了。从小到大枚举这个列表中的数,然后维护因子数前 $K+1$ 大的,如果 $x$ 的因子数比第 $K+1$ 大的因子数都小,那么就跳过,否则把 $x$ 加入下一轮的答案,并将 $x$ 的因子数加入集合。

几个细节:质因子大概加到 350 左右就不再有用了,可以直接退出;乘的时候要注意经典的防爆 LL;实现还是比较紧的,全部用 set 实现的话可能会超时,建议能开数组的地方全部开数组,由于质因子是从小到大枚举的,所以不会有去重的问题,新加进来的数直接存在后面,然后 sort 就好了;刚开始直接算 233 的答案,最后存答案的时候,从大到小枚举 $K$,逐步筛选,用 234 个 vector 记录所有答案,由于 $K$ 的时候的答案集合一定是 $K+1$ 的时候的答案集合的子集,所以这样做是正确的。

另外回答询问的时候,std 采用了某种技巧,往答案里填数的时候减去了一个下标,可以一个 log。但是直接二分套二分两个 log 也能过(这不是瓶颈)。

Problem B

Solved by zerol. 03:24 (+2)

题意:求 $f(n,m)=\sum_{i=0}^m \binom{n}{m}$ 范围和询问都是 1e5。

题解:$f(n,m)$ 可以 $O(1)$ 转移到 $f(n\pm 1,m)$ 和 $f(n,m\pm 1)$,然后莫队。

zerol:为了防止零贡献,抢了这题来写,然后犯了愚蠢至极的错误,模意义下我竟然写了 /2,(手动自裁)。

Problem C

Upsolved by ultmaster.

题意:给一棵树,边上有权值 1,2,3。在树上走路必须遵循 (1*3)?[12]* 的模式。每次操作先令 $w(a,b) = \max(1, w(a,b)-1)$,然后求 $s$ 到 $t$ 有没有路,$s$ 到多少点有路。

题解:初一看并查集似乎很显然,维护 1 的块,维护 1 和 2 的块,维护 1 的块相邻的 2 的块的大小总和。但是很显然不会维护。。。看了 dls 的讲解(内容就是反复强调这个题真的简单)之后发现没有利用到树的性质。其实对于每个节点只需要维护孩子的信息即可。父亲的信息在询问的时候另外算(这和一般图是不一样的)。树上并查集也是多校中第二次碰到了。保持并查集的结构和树的结构的一致性,并查集合并的时候要有向合并,使得合并之后节点的父亲仍然可查(没有注意方向 WA1)。

ultmaster: WA 了好久,又犯了修 bug 修一半的错误,并查集的信息永远维护在根节点上,查询的时候一定要传根。后来写了个函数如果发现不是根就再调用一次 find。用到两个有一点点不一样的并查集(写了个继承)。有数据也因为规模太大,完全没有帮助调试,最后还是对了拍(捂脸)。注意查父亲的时候一定要检查跟父亲连的那条边是不是 3(有一发 WA 在这里)。

Problem D

Solved by ultmaster. 01:02 (+2)

题意:有 $n$ 道题目,每道题目有 $a_i$ 个正确答案和 $b_i$ 个错误答案。现在有 $n$ 个人,设计合理策略使得最高分最大。

题解:简单地认为策略是笛卡尔乘积。出了个假算法过了。

zerol: 必须要喷,___出题人,出假题导致 WA 到怀疑人生(虽然也不一定是正解),发现不对 std 假了就魔改题面,然后还是假的就加样例解释。好在队友 ultmaster 与出题人心有灵犀,一下子就 A 了。

ultmaster: 和 ___出题人 心有灵犀,我也是 ___?

Problem E

Solved by kblack. 02:32 (+)

题意:按斜角在一个无限矩阵中放置一个数列,求子矩阵的和。

题解:循环节为 $2L$,求前缀和以后分区域求和即可。

Problem G

Solved by zerol. 04:53 (+5)

题意:问一棵树的所有可能的 dfs 序中有多少比给定序列小。

题解:类似于数位 dp 的想法,每次固定给定序列的一位,然后下一位比给定序列小,计数后累加入答案。一棵树 dfs 序总数是 $\prod_u son[u]!$($son[u]$ 表示 u 的儿子个数),如果 dfs 序的前若干个已经确定了(也就是一些点已经访问了),那么在这个状态下的 dfs 序总数就是————访问过的点不计入父亲的儿子总数中,然后带入公式。维护一个全局变量 S,表示当前的 dfs 序总数,然后按照给定序列进行访问,每次访问都会使 S 除以访问的点的父亲当前儿子数,然后需要计算有几个儿子比给定序列中下一个位置的元素小,这一部分用个数据结构就好了(推荐 pb_ds)。如果有已访问结点的儿子没访问完,那么剩下的给定序列已经无法构成合法 dfs 序了,那么退出。由于根是任意的,所以那一部分要分开算,然后以给定序列的第一项为根进行 dfs 计数。

zerol:比官方题解简单的体现就是不用从父亲计算贡献。也就是不用维护每棵子树的 dfs 序数量,而是维护一个全局的当前 dfs 序数量,因为这个计数是可减而且和顺序无关的。

Problem J

Solved by ultmaster. 02:13 (+)

题意:给一个每一块都有可能转坏了的 16 进制数独,让你把它转回来。

题解:送温暖的简单模拟题。由于题目没读清楚(只看了图)顺时针和逆时针搞反了调了半天,浪费半小时。

Problem K

Solved by ultmaster. 00:48 (+1)

题意:填 ? 使得表达式合法。

题解:把符号归成三类:1-9,0,+*。大概有三条规则:1. 刚开始和最后不能是 0;2. 0 后面必须是 +*;3. +0/*0/刚开始的 0 后面必须是 +*。使用这三条规则可以计算出每一位上可能的符号。然后一位一位填即可。注意好像不会发生冲突所以不用迭代到收敛;另外填的时候要注意不能篡改原式(没考虑到 WA1)。

Problem L

Solved by ultmaster. 00:07 (+)

温暖的签到题。(今天签的这么多一定是因为 kblack 迟到了。)