Posts Tagged “数论”


ZOJ Monthly, November 2010
A ZOJ3427 Array Slicing 21.05% (56/266)
B ZOJ3428 Bug Races 25.00% (2/8)
C ZOJ3429 Cube Simulation 22.94% (131/571)
D ZOJ3430 Detect the Virus 8.23% (40/486)
E ZOJ3431 Escape! 9.90% (21/212)
F ZOJ3432 Find the Lost Sock 18.38% (257/1398)
G ZOJ3433 Gu Jian Qi Tan 17.41% (39/224)
H ZOJ3434 Hiiragi’s Sticks 23.68% (9/38)
I ZOJ3435 Ideal Puzzle Bobble 4.87% (2/41)
J ZOJ3436 July Number 13.15% (15/114)

因为这一段时间考试、作业、Project实在忙不过来。所以原定的三题比较难的题目都没有挂出来,所以平凡的题目好像多了一点。最近事情好多好烦,希望快点应付过去……

ZOJ3427. Array Slicing

downloadsource code (ZOJ3427.cpp) [regex, simulation, slice, splice]

其实就是要实现一个list的__getslice__和__setslice__操作(pretty solution in python),或者说splice(more pretty solution in perl)操作。题目关于slice只贴了wiki上一段话,没有详细解释,不过sample给得很强,我以为slice是common sense,可是我错了。

输入有点小麻烦,其实scanf可以轻松搞定的啦,规模非常小,所以暴力什么的就好了。STL里的vector::insert和list::splice都可以直接做题目中的操作。题目说数字都是100,不过list的长度可是可以长到很长的哦,xe一点倒是可以让用数组的TLE,不过这是签名题,没有那么坏啦,sample应该是非常强的了 :-)

ZOJ3428. Bug Races

downloadsource code (ZOJ3428.cpp) [Number theory, Pythagorean triple, Euclid's formula, counting]

Comments 19 Comments »

这套体中推荐ZOJ 2674, ZOJ 2673, ZOJ 2676, ZOJ 2675。其中2674是欧拉函数,但模型非常赞;2673是非常不错的DP问题;2676是0-1分式规划与网络流相结合的经典中的经典。

ZOJ2670 Nonoptimal Assignments

downloadsource code (ZOJ2670 .c) [构造]

给定n,构造一个n*n的矩阵,使得按题目所给的“贪心”算法,不能得到正确解。

构造非常简单,下面是我的一种构造
\begin{pmatrix}0&1&1&\cdots&1\\0&2&2&\cdots&2\\0&0&2&\cdots&2\\\vdots&\vdots&\vdots&\ddots&\vdots\\0&0&0&\cdots&2\end{pmatrix}

ZOJ2671 Cryptography

downloadsource code (ZOJ2671.c) [math, SegmentTree]

有n<30000个2×2矩阵,m<30000次查询,每次查询需要快速回答区间[i, j]内矩阵的积(mod r)。

如果把矩阵换成整数,把求矩阵积换成求区间和(或最大/小值),那么这就是线段树一个经典的应用,而且是结构最为简单的一种线段树。而矩阵的乘积运算同样满足结合律((A*B)*C=A*(B*C)),符合应用线段数优化的条件,所以通过线段树,问题能在O(mlg(n))内解决。

ZOJ2672 Fibonacci Subsequence

downloadsource code (ZOJ2672.c) [DP, hash]

给定一个长度为n<=3000的序列,要求满足Fibonacci性质(c[i]=c[i-1]+c[i-2])的最长的子序列。

枚举c[1]=a[i]和c[2]=a[j],那么可以依次在序列中查c[3]=a[k], c[4], …其中k显然应该取满足a[k]==a[i]+a[j]&&k>j中最小的。但可能有很多比较长的序列,而对一个最大长度为m的Fibonacci序列,会被枚举到O(m)次,总的处理复杂度是O(m^2)的,会TLE。为了避免这种重复计算,引入动态规划,dp[i][j]表示c[1]=a[i], c[2]=a[j]的序列的最大长度,那么有dp[i][j]=dp[j][k]+1,DP复杂度为O(n^2)。最后问题的关键是已知i和j,如何得到k,一个map<a[k], k>可以满足要求,但是这里它太慢了,O(n^2lg(n))的复杂度将会超时。所以需要用O(1)的hash_map代替O(lg(n))的map,也可以自己实现哈希。

ZOJ2673 Hexagon and Rhombic Dominoes

downloadsource code (ZOJ2673.c) [DP, bitwise]

问用两个正三角形组成的棱形覆盖变长为n<=7的正六边形三角网格的方案数。

mp.2673

Comments 20 Comments »