2011年03月 存档

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

2011年03月20日,星期日

今天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 (二分查找)

2011年03月20日,星期日

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)

2011年03月20日,星期日

UVA 103 Stacking Boxes

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

(更多…)

ZOJ 2059 The Twin Towers (DP)

2011年03月19日,星期六

ZOJ 2059 The Twin Towers

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

ZOJ 2402 Lenny’s Lucky Lotto Lists (DP)

2011年03月15日,星期二

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)

2011年03月15日,星期二

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物品所需花费的最少量。。。 好好想想。。好好想想。。。
(更多…)

UVA 11408 Count DePrimes (线性筛法)

2011年03月11日,星期五

UVA 11408 Count DePrimes

看到大牛的空间上有贴这个题的,我最近在看数论,所以就看了看O(n)线性筛法,没有花太长时间,不过感觉挺神奇的,我在内层循环里加了个count++来计算它的计算次数,没想到筛200万的素数count只有185万,好神奇。这个算法的思想就是避免重复筛,比如35=5*7,就被筛了两次,我们只让一个和数只被他最小的素因子晒到。1Y了,好高兴~

(更多…)

近期被虐,不爽~

2011年03月6日,星期日

昨天晚上做codeforces,第一题因为条件判断错误,WA了,比赛一完就A了。。第二题应该用贪心的方法,我的超时了。。。然后就什么都不会了。。

做了十几次的CF,第一次剃光头,其余每次出2 + 1题,rating始终是绿色范围,看来是一点进步都没有。

寒假看了好多东西,数学方面的,一开学就一直在刷数论题,收获还是蛮大的,不过进步并没有地方体现出来,而且现在看题做题头都晕了,干点其他事吧,又怕路后,哎。。。。

今天下午,做ustc的题目,少了个二分而超时。。。

不由地感觉菜到无助。。

ZOJ 2964 Triangle (非常好的一个数论题)

2011年03月4日,星期五

ZOJ 2964 Triangle

题目的描述我感觉有点问题,是看了shi哥空间才知道的.三角形的三边l>m>n,a^l=a^m=a^n(modz),由于三边不等,所以说要使边权和最小,就要找到a生成的子群规模.由于我们知道他肯定是euler(z)的约数,所以枚举约数进行寻找,这个题就亮在这个寻找约数的过程.


(更多…)