Posts Tagged “DP”

这是第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, January 2011
A ZOJ3457 Absence Number 19.32% (23/119)
B ZOJ3458 A Simple Math Problem 8.33% (7/84)
C ZOJ3459 Extraordinary 24-Point Game 0.00% (0/0)
D ZOJ3460 Missile 21.73% (20/92)
E ZOJ3461 Money Transfer 30.43% (7/23)
F ZOJ3462 Nobita’s New Filesystem 11.53% (3/26)
G ZOJ3463 Piano 40.74% (11/27)
H ZOJ3464 Rugby Football 42.37% (114/269)
I ZOJ3465 The Hive 28.51% (71/249)
J ZOJ3466 The Hive II 11.11% (1/9)

因为学校忙完才到家,所以monthly的准备显得有些仓促,结果原本推迟安排在这个月的几道题还是没有整理出来,转而挑了几道不那么需要fix的题。下个月的monthly在两周后,寒假应该有些闲暇去整理他们了,争取能放出来。J题有人过了,但C题没人提交,原本以为I题是最水的,结果比较意外,没被圆满,值得庆幸。已经是2011年了,summer2010的题也用了过大半了,之后就是校赛和省赛了,然后离summer2011也不远了^ ^

ZOJ3457. Absence Number

downloadsource code (ZOJ3457.cpp) [misc]

给定一个两位数N,求最小的m,使得1/m的十进制表示中恰好包含除N以外的所有两位数。

最大的解是N=0时m=76344。题目的输入只有100种,所以可以暴力跑表,1/m十进制表示是循环小数,且在m步内开始循环,所以很容易求得其包含的所有两位数,最后判断一下是否满足条件就好了。注意不要漏数了两个循环节头尾组成的那个两位数,否则有几个数据会WA。更简单的方法是不判断循环节,直接循环m+1步。加上一些优化后,这个表实际可以在1s之内跑出。

ZOJ3458. A Simple Math Problem

downloadsource code (ZOJ3458.py) [math]

find \lfloor(\sqrt{a}+\sqrt{b})^n\rfloor \mod 2(a+b) , where 0 < b - a < 1 + 2\sqrt{a} \text{ and } n \text{ is even}

Comments 23 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 #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 »


Andrew Stankevich’s Contest #5
ZOJ2587 Unique Attack 21.20% (263/1240)
ZOJ2588 Burning Bridges 23.92% (410/1714)
ZOJ2589 Circles 18.57% (120/646)
ZOJ2590 Linear Programming Dual 30.65% (42/137)
ZOJ2591 DVD 13.78% (79/573)
ZOJ2592 Think Positive 40.56% (527/1299)
ZOJ2593 Ranking 21.93% (84/383)
ZOJ2594 Driving Straight 19.64% (168/855)

好像是最水的一套,推荐ZOJ 2589欧拉公式太妙了;再则推荐一下ZOJ 2591的DP吧,还是很值得一写的。

ZOJ2587 Unique Attack

downloadsource code (ZOJ2587.cpp) [FlowNetwork]

恐怖分子计划用最小的代价破坏网络,以阻断AB之间的通信,问其方案是否唯一。

用最小的代价破坏AB间的网络,这就是网络流的最小割问题,于是这题就是问网络流的最小割是否唯一。判断最小割割是否唯一,我的方法是这样的,先求最大流,如果在残留网络中,从A出发bfs得到的割边和从B出发得到的一样,那么割就是唯一的。

ZOJ2588 Burning Bridges

downloadsource code (ZOJ2588.cpp) [Graph]

M个桥连通者N个岛屿,现在一些桥将被烧毁,但岛屿连通性不变,问那些桥一定不会烧毁。

题目要求的正是无向图的割边),dfs可解,可参考黑书2.4.4,注意重边的处理。

ZOJ2589 Circles

downloadsource code (ZOJ2589.cpp) [geometry, math, Euler's formula]

给定平面上的N个圆,问整个平面被分成了几个部分。

如果用圆离散化来解就太大自然了。这里可以用传说中的欧拉公式(Euler’s formula),χ=V-E+F来计算,V-vertices表示顶点数,E-edges表示边数,F-faces表示围成的面数。于是面的个数可以这样计算:对于几个相连的圆,其内有F=E-V+1个面,其中1是平面图情况的欧拉欧拉示性数(Euler characteristic);对于一个独立的圆,显然F=1;最后答案还要加上外部那个无穷大的面。通过求圆与圆的交点可以很容易的得到顶点数,边数和圆与圆是否相连,从而求得答案。

ZOJ2590 Linear Programming Dual

downloadsource code (ZOJ2590.cpp) [simulation]

输入线性规划,输出其对偶线性规划。

Comments 1 Comment »