T1 【NOIP2017模拟】Fibonacci
题解:
本以为这道题是一个类似的之前做的一道斐波那契的\(DP\),一看数据范围就知道应该是乱搞差不离了\(,,,\)
我们预处理前\(45\)项\(Fibonacci\)数列,发现已经突破\(1e9\)了,于是我们直接每次询问扫一遍即可,时间复杂度\(O(T*45*45)\)
\(code\):
#include
#include
#include
#include
#include
#include
#include
#include
T2【NOIP2017模拟】一样远
题解:
很显然,当两点之间的点数为奇数时,此时有解,否则显然无解,而有解时,显然我们应该去找中点;
我们对有解的情况分情况讨论:
\(1.dep[x]==dep[y]:\)
这时候只用将x、y上提到中点的前一个点就好,\(N-Sz[xx]-Sz[yy]\)即可;
\(2.dep[x]!=dep[y]:\)
我们假设\(dep[x]>dep[y]\),那么我们先找到他们的中点,再用中点的子树大小减去包含了\(x\)的子树的大小就行了;
\(code:\)
#include
#include
#include
#include
#include
#include
#include
#include
T3 【NOIP2017模拟】拆网线
题解:
贪心,显然两两相连接是最优的情况,如果不能满足就往里面加点,每加一次答案就多一条边;
\(code:\)
#include
#include
#include
#include
#include
#include
#include
#include