首页 > 代码库 > NOIP 2014民间题解

NOIP 2014民间题解

Day1

T1

这个题其实就是考你会不会编程。

T2

题目有坑点,说n个点的无向图上有n-1条边,很明显这是棵树。
因为是树,所以我们没必要跑最短路,而且世界上还没这么快的最短路算法能A掉这个题。
下面是ydc的思路

考虑距离为2的点对,可以理解为枚举ii能走到的点集两两之间距离为2

我们要做的是对于一个数组a1,a2,a3,,am,要求aiaj,ij的Σ与max

max是个很简单的事情,你只要求a数组的最大值与次大值即可

至于Σ,我们知道i=1nj=1naiaj=(i=1nai)2,于是容易推出我们要求的就是(i=1nai)2?i=1na2i

当然你也可以令s=i=1nai,求i=1nai(s?ai)

复杂度应该是O(n)

还有我的思路:

枚举树上的n个点,每个点枚举他们的孙子节点,统计每个点和其孙子节点的乘积最大值和乘积之和。

按理说每个点只被统计过一次,复杂度应该是O(n),有同学说可能会出现O(n^2)的情况,有个别点TLE的可能

T3

类完全背包问题。有O(nm)的算法,我用O(nm^2)的记忆化搜索方法,预计得分50~70

Day2

T1

还是考你会不会编程,注意题目要求路由器在路口处

T2

根据题意,我们首先建一个反向图,所有边和原图方向相反,在这个图上跑BFS或者SPFA,得到所有与终点联通的点,然后预处理筛掉那些不符合题意的点,最后正向跑BFS或SPFA就行了

T3

1、O(nm)算法,就是m次枚举x,代入方程计算答案,高精度或者用多个大素数取模处理,高精度的话如果高精度位数太长会卡常数T掉很多点,没办法我只能开长度200的高精度,取模不存在这个问题,可以卡时得到70分,如果高精度带压位也可以拿到70分。
2、策爷的做法:

暴力做法是对[1,m]的所有整数在模意义下验证,复杂度O(nm)

取一个质数P,对[0,P?1]的整数进行验证(模P意义下),复杂度是O(Pn)。(注意挑选的P需要保证f(x)在模P意义下不会变成零多项式)

然后可以知道模P意义下有不超过n个解。(拉格朗日定理)

那么对应地,在[1,m]中至多只有n??m/P?个解,对这些解进行验证即可。复杂度O(n2m/P)

Pnm???附近。总复杂度O(nnm???)


NOIP 2014民间题解