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]

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

熟悉对偶线性规划的话应该会有帮助,不过不熟悉也完全不要紧,线性规划的格式在不同文献里都可能不一样,在这里就得按大妈的规矩。注意>还是<的变化在min/max是不一样的,而sample只有min的。对偶线性规划的对偶线性规划应该是自己,所以把sample input和sample output对换一下又是两组case。

ZOJ2591 DVD

downloadsource code (ZOJ2591.cpp) [DP]

Johnie从他的uncle那继承了一大堆片,不知哪的规矩,看片居然一定要按年份的顺序,更悲剧的是每个片都有个region,DVD要设置成相应的region才能看,DVD只能改5次region。问最多能看多少片,要求输出方案。

动态规划,可以用dp[i][j][k]表示看到第i年,DVD的region最后设为j,改过k次region的情况下,所能看的最多片数。注意一年可以看超过两个region的,但是dp的时候不能一个片看多次……所以转移时,需要枚举这一年DVD都设置成过哪些region,然后贪心的把这些region的片都看了。DP不难想,但不是很好写。

ZOJ2592 Think Positive

downloadsource code (ZOJ2592.cpp) []

s_{jk}=\left\{\begin{array}{l}\sum_{i=j}^k{a_i},\text{ if }k\ge j;\\\sum_{i=j}^n{a_i}+\sum_{i=1}^k{a_i},\text{ if }k<j;\end{array}\right.
问有多少不同的j,使得对任意k,sjk恒为正。

我最初的做法就是对j=1的情况,求出所有s0k,并令s00=0,记xj=min{s0k|k<=j},yj=min{s0k|k>=i},那么对0<i<n如果有s0i<yi+1,且s0i<s0n+xi,那么答案++。不过显然有更漂亮的做法,因为答案其实就是1的个数减去-1的个数!所以甚至可以这么写:

scanf("%d ", &n);
n *= 5;
gets(s);
n = n - 2 * strlen(s) - 2;
printf("%d\n", n > 0 ? n : 0);

ZOJ2593 Ranking

downloadsource code (ZOJ2593.cpp) [simulation]

略。

dead do | 死做

ZOJ2594 Driving Straight

downloadsource code (ZOJ2594.cpp) [Graph]

本质上是求最短路,不过输入和输出比较奇怪。

先从右上角开始bfs出每个点到右上角的最短距离,再从左下角出发,每次都从距离为d的点走到相邻距离为d-1的点,模拟并输出答案就可以了。

One Response to “Andrew Stankevich’s Contest #5解题报告”
  1. Xuanwo says:

    n *= 5;
    gets(s);
    n = n – 2 * strlen(s) – 2;

    这个姿势好优越= =,看不懂。

  2.  
Leave a Reply