NOIP第7场模拟赛题解

时间:2023-11-13 10:07:38

NOIP模拟赛第7场题解:

题解见:http://www.cqoi.net:2012/JudgeOnline/problemset.php?page=13

题号为2221-2224.

1.car

边界要当做建筑物。

只需要判断是否存在一个'.',至少三面都是建筑。那么这个点就是所谓的“死胡同”.

2.gcd

利用整数唯一分解定理,求出A,B的所有质因数和该质因数出现的次数。

对A,B的公共质因数取其出现次数的最小值,再将该质因数的最小值次幂累乘起来即可。

3.pair

这是一道非常有质量的题,很考思维。

暴搜的时间复杂度是O(N^2).只能处理n较小的数据。30分应该没有问题。

一般会想到容斥原理。

要统计num和之前的多少数形成一个pair,可以这样计算:与num有一个共同数字的数之和-与num有两个共同数字的数之和+与num有三个共同数字的数之和-……

如何计算与num有k个共同数字之和呢?可以这样做:

利用一个数组bit[2^10],如果当前数包含了数字i(出现多次算一次),则bit[1<<i]++;如果同时出现了i,j,则bit[1<<i]++,bit[1<<j]++,bit[(1<<j)|(1<<i)]++,如果包含i,j,k等多个数字,依次类推。

这样,要计算与num有一个共同数字的数的个数:sum(bit[1<<i])(0<=i<=9 &&num包含数字i)

这种方法很麻烦,而且时间复杂度为O(N*2^10).程序肯定会超时。

注意到bit[2^10]。为什么我们可以用这么小的一个数组来记录所有数“包含哪些数字”的信息?

思考后你会发现,其实对于一个数num,我们只关心它包含哪些数字,至于这些数字出现的顺序,出现的次数,都可以不用考虑。

所以我们把一个数num,转换为一个小于1024的数k。转换规则很简单,如果num包含数字i,则k中右数第i位设为1,否则第i位为0.

这样所有的数既可以映射到1个1024的区间,这样,相当于缩小了n的范围。现在可以用暴搜了解决了。

结果由两部分组成:

第一部分:设cnt[i]表示转换后得到的数i出现的次数。i和其他数形成的pair,即为cnt[i]*cnt[j].(j表示其他数,且i&j!=0)。最后将这些乘积累加,再除以2.(因为每个pair都计算了两次。)

第二部分:

i代表的是相同的一类数num,这些数对应同一个i,它们是两两成pair的,一共可以形成C(cnt[i],2)个pair。(组合计数,从cnt[i]个元素中取出两个,所以为C(cnt[i],2))。所有的i都可以得到一个C(cnt[i],2),这部分全部累加起来。

两部分的和即为答案。

第四题:如果26层循环相互之间没有关系,则是一个连乘即可解决的问题。

现在有些循环变量的边界是外层循环变量,我们称这两层循环有对应关系。

我们把每个循环变量看做一个节点,有对应关系的节点连一条边。具体说:题目说了,任意一个变量的两个边界中,至少有一个为常量,

也就是说之多只有一个边界为变量。如果v2的一个边界为v1,则v1向v2连一条边。这样会得到一个森林,即多棵树。

树中的节点即一个循环变量,所有循环变量给res带来的贡献即该树的结果。

树与树之间是互相独立的。最后的res值等于每棵树代表的结果的乘积。

如何计算一棵树的结果。

设f[root]为以root为根的子树的结果,g(node,number)表示节点node表示的变量取值为number时,其子树的结果。则有下列式子

注意下式中,g(node,number)只给出了一种情形,node所表示的变量的上界为常数;还有另一种情形,即node所表示的变量的下界为常数,g(node,number)的表达式要稍作修改,但其实本质都差不多的。下面的式子中,类似于pi的符号表示取乘积。

NOIP第7场模拟赛题解

这个时间复杂度是O(nm2)的,只能过70%的数据。

注意到,g(node,number)的计算是可以递推得到的,即

NOIP第7场模拟赛题解

这样,时间复杂度为O(nm)了。