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:,,,

Related Posts

[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}时,进行朴素的计算。

时间复杂度 O(\sqrt{n}),空间复杂度 O(1)。

算法就是这样了,刚开始写的时候 TLE 了,原因是作为循环条件的 sqrt(n) 没有提前计算出来,于是导致了很多不必要的运算,多么低级的错误……

C++ 代码在这里

P.S. 突然想做编号是大家生日的题目,这题编号是我一个朋友的生日,自己的生日编号的题目的状态是暂不提供……

Tags:,,,

Related Posts

[OI][Vijos 1059]积木城堡

Thursday, October 16th, 2008

一年没写代码了,这周又开始拿起我那二把刀,开始切题了……

看到我们的小妹妹写了积木城堡这个题,于是我也从这题开始了……

简单的 0/1 背包,渐进时间复杂度(大概)是 O(N*n*n),渐进空间复杂度(大概)是 O(N*n*n),其中 N 为城堡数量, n 为组成每个城堡的积木数。

这题有着 Vijos 的一贯传统,就是题目描述令人 confused,就这题来说,从中间抽取积木还能使城堡不倒,不得不说是有一定功力,抽出的积木就扔在一边,不能不说是浪费。其实这都可以在题目中说清楚的。

开始做,一开始用了 bitset (在 NOIP 中允许使用),结果 TLE ;后来优化了读入,还是 TLE,后来砍掉了 bitset ,用 boolean array,提交无数次后(Vijos 最近服务器有问题,运行程序忽快忽慢,随机 TLE 的现象时有发生),终于 AC 了。

代码可以看这里,其他 vijos 的代码也在那里。

事实证明, bitset 的效率并不高,竞赛的时候应远离 bitset …… (这也可能跟 Vijos 所用编译器的实现有关)

Tags:,,,

Related Posts