algorithm « Leaf Duo

Posts Tagged ‘algorithm’

[OI][Vijos 1107]环游大同 80 天

Sunday, October 26th, 2008

话说这题是一个搜索题。

我采用的是两次 DFS 的方法，也就是任意取一个点开始 DFS，找到这次 DFS 时深度最深的点（也就是从所选点开始最长路径的终点），然后从这一点（可以证明，这一点是最长路径的端点）开始再进行 DFS，这次 DFS 的深度就是要求的路径长度。

算法就是这样了，不过这个算法的正确性我一开始也不太确定，下面来证明一下：

大家看图：

设最长路径为 AB ，一开始任选的点为 P。取路径 PB 上的一点 Q，使得 AQ 与 PQ 只有一个公共点 Q（也就是使得从 A 走到 Q 再走到 B 不会走回头路）。设 AQ=a，QB=b，QP=s，不妨设 a<b。

要证明这个算法的正确性，也就是要证明从 P 开始的最长路径的终点一定是 A 或 B。假设从 P 开始的最长路径的终点是 C ，设 CP=c。

由假设知， c>s+b。由于从从 P 开始的最长路径的终点是 C，所以第二次 DFS 将从 C 开始，所得最长路径为 CB=c+s+b>s+b+s+b，又因为 a<b，故CB>s+b+s+b>s+a+s+b>a+b=AB，这与 AB 是最长路径矛盾，故假设不成立，命题得证。

时间复杂度 O(CR)，空间复杂度 O(CR)。

代码还是非常 ugly，偷了很多懒，改一下的话应该能更快些。

P.S. 停止切题，准备期中考试。（其实这个星期就没做题）

Tags:algorithm,C++,OI,Vijos

Related Posts

Tags: algorithm, C++, OI, Vijos
Posted in Information Technology | 2 Comments »

[OI][Vijos 1214]伤心的AsukaNoKaze

Sunday, October 19th, 2008

这题算是个数论题。

其实也没用到什么数论结论，首先手算找找规律。发现，对于 $\forall x\in (\frac{n}{i+1},\frac{n}{i+1}],x\in {\mathbb Z}$ 有 $n ~{\mathtt div}~ x$ 为常数 i - 1 ，于是这一区间内的数就可以只算一次，然后将结果乘以区间内整数的个数就行了。但当 $i>\sqrt{n}$ 时，每个区间的长度 $\frac{n}{i}-\frac{n}{i-1}<1$ ，这样就得不偿失了，所以当 $i<=\sqrt{n}$ 时每个区间处理一次，当 $i>\sqrt{n}$ 时，进行朴素的计算。

div 运算就这样解决了，剩下的取余可以由整除的结果生成，对于 $\forall x\in {\mathbb Z}$ ，有 $n ~{\mathtt mod}~ i = n - i(n ~{\mathtt div}~ i)$ ，每个区间内， $n ~{\mathtt div}~ i$ 为定值，所以令 $first=\frac{n}{i+1},last=\frac{n}{i},k=n ~{\mathtt div}~ i=i-1$ ，则对于区间 (first,last] ，有 $\sum\limits_{i=first}^{last}{n ~{\mathtt mod}~ i}$ $=\sum\limits_{i=first}^{last}{n- i(n ~{\mathtt div}~ i)}$ $=\sum\limits_{i=first}^{last}{n-i\cdot{}k}$ $=n\cdot{}(last-first)-k\sum\limits_{i=first}^{last}{i}$ $=n\cdot{}(last-first)-k\frac{\cdot{}(first+1+last)(last-first)}{2}$ $=n\cdot{}(last-first)-\frac{(first+1+last)(last-first)(i-1)}{2}$ 。同样地，当 $i>\sqrt{n}$ 时，进行朴素的计算。