ZOJ 3195 Design the city (lca + st )

ZOJ 3195 Design the city

给出n个区域,有n-1条路去连接这些区域,显然他是一个带权无根树。首先把它以0为根看成有根树,对于给出的三个点,每两个点之间的距离是固定的,因为他们之间只有一条路,但是对于这么多查询(at most 70000 ),直接找距离代价太大,找出每两个点的LCA,这样就可以两个点之间的距离了,(需要知道从0点开始到这两个点的距离)。 我们把这三对点的距离加起来再除以2,就能得到连接着三个点的最短路径。

(更多…)

继续阅读 →

ZOJ 2067 White Rectangles (greedy)

ZOJ 2067 White Rectangles

好久没有更新博客了,突然间想做几个贪心题目,于是就照着大黄的贪心题目分类开始刷。

题目描述的很清楚,给出n*n的地图,需要找出全部由白色点组成的矩形的个数。刚开始想到的是枚举,不过这个复杂度也太高了。需要做一个预处理,需要统计处从某一点开始向右最长的连续白点个数,保存在rightt中。然后进行枚举每个点,统计以他为左上角的矩形的个数,其间还要枚举高度。。时间复杂度O(N^3)

(更多…)

继续阅读 →

第三届郑州轻工业学院校赛流水帐~

A.水题..注意从两个门开始搜

B.矩阵快速幂求第n个fibnacci数,但是当时比赛的时候不知道这个算法阿…依稀记得算法导论的视频上有个矩阵运算,然后我就坐在那里一直YY……最后……居然yy出来了,我了个汗阿…..但是不会求时间复杂度,但是我好像感觉比那个幂预算稍微慢点…..附上代码,路过的大牛,指导下把..
(更多…)

继续阅读 →

有点小高兴

在uva上刷题前看了看status版,看到了suneast牛,我想,uva上牛人众多,像我这样的小菜菜应该没有机会挤到第一版了吧。。。。。经过几次tle之后ac了,到第一版一看,我竟然排到了suneast前面,十分激动啊~ 💡

继续阅读 →

ZJU集训选拔分数判定器 (dt了..= =)

今天edward_mj说到浙大的集训选拔分数统计有点难搞,我就萌生写个py脚本来统计分数的想法,正好最近py手生,说搞就搞~

统计标准在这里:

狗狗40题(这里的1001-1040) 2.5分/题
Andrew Stankevich’s Contest 1.5分/题
其余ZOJ中所有题号的质数的题 1分/题
其余题目 0.3分/题

这是关于zoj题目的统计,我主要就是搞这个,主要框架就是一个if else 语句,难点就是提取那几个题的题号,一步一步来:

一、提取狗狗40题题号:

shi哥的blog有现成的题号,但是还需要分离,复制网页html代码,然后通过文件找出题号,我用的是很笨的方法,找到那一行,再找到那一个数字= =

f = open("40.txt","r")
fp = open("out.txt","w")
for i in range(1,241):
    a = f.readline();
    if i%6 is not 4:
        continue
    fp.write(a[4:8]+",")

(更多…)

继续阅读 →

ZOJ 2029 The Intervals (二分查找)

ZOJ 2029 The Intervals

给出数组a,求的最小的一个[ a[i], a[j] )使得b[m]在这个区间内,简单的方法就是排序,然后查找范围。为了练习二分,我学习了lower_bound和upper_bound,哈哈stl好强大,以后做题时不能因为不会用二分而超时了。lower_bound(a.begin(),b.end(),x)返回一个迭代器,使得这个位置的元素>=x,用upper_bound则表示>x

(更多…)

继续阅读 →

UVA 103 Stacking Boxes (DP)

UVA 103 Stacking Boxes

看到了这个题之后思路就无比清晰。矩形嵌套问题,不过这个是多维的。我们判断两个序列a,b的关系的时候,需要枚举a的各种排列,看看有没有可能a的每一个位置上的元素都比b中对应元素小,如果真枚举的话太麻烦了。可以把a和b都排下序,然后再比较。确定元素间的关系之后,就很好构造LIS了。在这道题中,我学会了sort和max_element的用法。。感觉stl挺方便的。

(更多…)

继续阅读 →

ZOJ 2059 The Twin Towers (DP)

ZOJ 2059 The Twin Towers

被成为经典的双塔问题。痛恨死了,我搞了好多天,我真是对dp一点都不开窍啊。。怎么办?看了大黄的思路,dp[i]表示高度差为i时候低的塔的最大值,这个状态定义的很纠结,也不是很好理解。就先拿我的代码来说吧,每输入一个水晶,就更新一下dp。。。这个时候我们需要一个额外的t数组来保存前边所有物品所产生的状态,因为只用一个dp来保存的话,当前物品所产生的状态有可能叠加。。对状态的更新产生影响。。t数组每次更新完就再赋给dp。。dp[0]表示高度相等时的高度。。。
(更多…)

继续阅读 →

ZOJ 2402 Lenny’s Lucky Lotto Lists (DP)

ZOJ 2402 Lenny’s Lucky Lotto Lists

用1-M之间的数,组成一个长度为N的序列,使得每一个数是之前那个数的二倍以上,如对于N=4,M=10:

1 2 4 8
1 2 4 9
1 2 4 10
1 2 5 10

有四种选择,题目给出的范围是N<=10,M<=2000。

设DP[i][j]表示长度为i的序列结尾为j的情况数,从小往大递推就行了。。

(更多…)

继续阅读 →

ZOJ 1524 Supermarket (DP)

ZOJ 1524 Supermarket

Mr. Jones得到一份购物清单,清单上按顺序写出了需要购买的物品,在买东西的时候要按照顺序弄。。。。另外,题目还给出了,超市中的物品排列情况,买东西的时候还要按照物品的顺序进行购买,显然,可能会有各种不同的购买方案,同时花费也是变化着的,要求输出最少的花费。

设一个V[i]表示,购买前i+1件物品所需要的最少费用,L[i]表示列表上商品的类型 ,K[i]表示超市里的商品类型,P[i]商品价格price。由于要随着商品的排列情况进行选择,从第一件商品开始进行选择,层循环因为用到滚动数组,所以要从M-1开始循环。。。。每找到一个便宜的价格就更新,最终V[M-1]就是结果。。。。      如果这样不好理解的话,可以这样V[i][j]表示用超市中前i个物品,买清单上前个j物品所需花费的最少量。。。 好好想想。。好好想想。。。
(更多…)

继续阅读 →