Posts Tagged “FlowNetwork”

这是第8届浙江省大学生程序设计竞赛(The 8th Zhejiang Provincial Collegiate Programming Contest)的比赛点评。这不是官方的解题报告,裁判组也将不会提供官方的解题报告和测试数据。


第8届浙江省大学生程序设计竞赛
A ZOJ3487 Ordinal Numbers 39.24% (312/795)
B ZOJ3488 Conic Section 21.27% (160/752)
C ZOJ3489 Old Labels 2.00% (1/50)
D ZOJ3490 String Successor 10.86% (88/810)
E ZOJ3491 Wall-nut Bowling 0.00% (0/12)
F ZOJ3492 Kagome Kagome 38.00% (233/613)
G ZOJ3493 Palm Up and Palm Down 0.00% (0/1)
H ZOJ3494 BCD Code 18.75% (3/16)
I ZOJ3495 Lego Bricks 8.33% (2/24)
J ZOJ3496 Assignment 11.11% (2/18)
K ZOJ3497 Mistwald 16.66% (13/78)
L ZOJ3498 Javabeans 28.44% (225/791)
M ZOJ3499 Median 30.47% (263/863)

原定的题目只有A-L,比赛前一周姐姐看过题目后表示还是太难,于是又加了一道M。13道题,是姐姐的吉利数字(参考试机赛B题Lucky Number)。其中水题有5道,结果开场对于OJ来说压力实在太大,ZOJ上一长排的Queuing,直到90min后system load才降下来。由于省赛专科和本科在一起比,实力跨度也很大,所以难度控制一直是比较困难的。这次简单题稍微多了一些,而原本我们以为只是中等题的K和I似乎对于很多队伍来说还是太难了。最主要的是,除了冠军队HDU-Knuth外,其它队伍的跳坑顺序完全出乎裁判们的预料= =b 有很多队伍都热衷于折腾赛前被认为是不适合在中期搞的题,而悲剧的是,他们也确实没有搞出来……


The 8th Zhejiang Provincial Collegiate Programming Contest (online)
A ZOJ3487 Ordinal Numbers 51.24% (413/806)
B ZOJ3488 Conic Section 29.45% (291/988)
C ZOJ3489 Old Labels 5.26% (6/114)
D ZOJ3490 String Successor 15.50% (198/1277)
E ZOJ3491 Wall-nut Bowling 0.00% (0/13)
F ZOJ3492 Kagome Kagome 55.55% (345/621)
G ZOJ3493 Palm Up and Palm Down 10.52% (4/38)
H ZOJ3494 BCD Code 15.90% (7/44)
I ZOJ3495 Lego Bricks 10.20% (5/49)
J ZOJ3496 Assignment 12.19% (10/82)
K ZOJ3497 Mistwald 10.97% (46/419)
L ZOJ3498 Javabeans 46.88% (339/723)
M ZOJ3499 Median 51.83% (381/735)

赛前vls曾预测冠军会有10~11题,而我表示今年题目虽然和去年相当,但冠军只有9题,最后还是我猜对了。六年之后,浙大又一次省赛丢杯,不过这一次丟得毫无意外,虽然如此,我还是很看好现在这一批集训队或有意进入集训队的xpies的。比较意外的是我原以为同步赛会有11题的,结果是只有4个10题的。也许是由于我们的失误,J题赛后rejudge了,影响了某些队伍向11题进发的脚步吧。

ZOJ3487. Ordinal Numbers

downloadsource code (ZOJ3487.cpp) [if-else]

输入基数词,输出序数词。为了降低难度,还直接把规则给你了,题目描述里还附带无数测试数据。

Comments 59 Comments »

ZOJ Monthly, July 2009

[F]ZOJ3227 Perfect Cherry Blossom 0.00% (0/13)
[H]ZOJ3229 Shoot the Bullet 12.12% (4/33)

ZOJ Monthly, November 2009

[E]ZOJ3263 Immaterial and Missing Power 0.00% (0/8)

标题是照着vls的《我出过的题目》取的,确切的说是我出过的以東方Project为背景的,已经公开的题目。因为今年Summer2010暑期集训新手上路选拔和七月校队选拔中,我又出了11道东方系列的题目,以在这个月办好一场东方专场ZOJ月赛(详情:acm_x_touhou),用把力,把去年暑假的yy变成现实。去年出的这三题当然离办一场Monthly还有无限远,不过今年提前准备,再加上vout和猛犸的强力支持,现在已经有了充足的各种难度,各种类型的东方系列备选题目能够支援ZOJ八月的月赛了。届时希望广大acmer和touhou fans捧场 :D

ZOJ3229 Shoot the Bullet (文花帖)

downloadsource code (ZOJ3229.cpp) [FlowNetwork, 上下界最大流]

在未来的n天中,文文要强拍幻想乡的mm们为《文々。新闻》增加8g素材。但是每天她只能对某些mm拍照,并且所拍照片数不能过多或过少,每天总的照相数也有上限,而n天内她所拍某个mm的相片也有最低要求。在满足所有这些要求的前提下,希望最后拍的照要尽量多,求任意一个最优方案。

很裸的上下界最大流,构图算法都没什么需要多说的了,有模块就直接秒杀了。ZOJ上就这题的AC数到了三位数,不知道有没有人用来测模块。

ZOJ3227 Perfect Cherry Blossom (妖々夢)

downloadsource code (ZOJ3227.cpp) [DP, SegmentTree]

 暖和的季节结束了,边境被银白色的幻想所封闭。
 人们在这不知道什么时候结束的漫长冬天中,也变得安分起来了。
 

Comments 5 Comments »


Andrew Stankevich’s Contest #3
ZOJ2361 SGU209 Areas 18.12% (62/342)
ZOJ2362 SGU210 Beloved Sons 45.40% (173/381)
ZOJ2363 SGU211 Strange Counter 28.12% (63/224)
ZOJ2364 SGU212 Data Transmission 11.95% (104/870)
ZOJ2365 SGU213 Strong Defence 36.40% (83/228)
ZOJ2366 SGU214 Weird Dissimilarity 13.31% (84/631)
ZOJ2367 SGU215 PL/Cool 22.91% (33/144)
ZOJ2368 SGU216 Royal Federation 24.80% (64/258)
ZOJ2369 SGU217 Two Cylinders 15.71% (94/598)

还是先推荐两道构造题2363 Strange Counter2368 Royal Federation2361 Areas是一道coding量很大的计算几何题,而2367 PL/Cool是一道考验基本功的蘑菇题。2363 Data Transmission是一个值得再研究的分层图的阻塞流问题。

ZOJ2361/SGU209 Areas

downloadsource code (ZOJ2361.cpp) [geometry, 计算几何, dfs]

题目描述很简单,问给定的n条线把平面分出了几个有限的区域。

规模为80,不得不ym那些用优化的半平面交轻松AC这道题的牛人们,但我觉得这不能算a right approach。

我的算法是O(n^2lg(n))的。

Comments 10 Comments »


Andrew Stankevich’s Contest #4
ZOJ2559 The Smart Bomb 53.76% (321/597)
ZOJ2560 I Just Called … 21.05% (76/361)
ZOJ2561 Order-Preserving Codes 18.28% (126/689)
ZOJ2562 More Divisors 30.14% (322/1068)
ZOJ2563 Long Dominoes 37.94% (148/390)
ZOJ2564 The Magic Wheel 17.11% (83/485)
ZOJ2565 Cracking SSH 50.25% (98/195)
ZOJ2566 Periodic Tilings 33.81% (47/139)
ZOJ2567 Trade 16.66% (97/582)
ZOJ2568 Counting Triangulations 16.31% (101/619)
ZOJ2569 Unfair Contest 28.57% (64/224)

这套题居然有11道,还是有不少好题的,尤其是ZOJ2566 Periodic Tilings,非常好的一道题,利用数学结论,可以转换为美丽的图论。还有ZOJ 2568是非常不错的计算几何模型动态规划;ZOJ 2561也是动态规划,用到了四边形不等式优化;ZOJ 2567,上下界最小流。

ZOJ2559 The Smart Bomb

downloadsource code (ZOJ2559.cpp) [math]

给定三个圆的圆心,要求圆不能相交,但可以相切,要使三个圆的半径和最大,问三个圆的半径各应该是多少。

显然要使三个圆两两相切,设三角形三边为a, b, c,三个圆半径为x, y, z就有
\left\{\begin{array}{l}x+y=c\\y+z=a\\z+x=b\end{array}\right.
有唯一解。

Comments 6 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 »