NOIP 2014民间题解 - c++编程基础

Day1

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

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

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

我们要做的是对于一个数组 a1,a2,a3,…,am ，要求 aiaj,i≠j 的Σ与max

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

至于Σ，我们知道 ∑i=1n∑j=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的可能

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

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

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

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) 。

取 P 在 nm???√ 附近。总复杂度 O(nnm???√) 。