NOIP 2014民間題解
Day1
T1
這個題其實就是考你會不會編程。
T2
題目有坑點，說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的可能
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)。
取P在nm???√附近。總復雜度O(nnm???√)。
