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)

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)

### ZOJ3487. Ordinal Numbers

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

### ZOJ3488. Conic Section

source code (ZOJ3488.cpp) [if-else, yet-another-easy-problem]

```-x^2-y^2+1=0 is also circle
-x^2-2*y^2+1=0 is also ellipse
x^2+4y=0 is also parabola
y^2-x^2-1=0 is also hyperbola
```

```a==c is circle
a*c>0 is ellipse
a*c<0 is hyperbola
a*c=0 is parabola
```

### ZOJ3489. Old Labels

source code (ZOJ3489.cpp) [greedy, construction, sorting]

```for (int i = 0; i < n; ++i) {
printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');
}
```

### ZOJ3490. String Successor

source code (ZOJ3490.cpp) [simulation, string manipulation]

• 9的后继是10，而不是00；
• (z)的后继是(aa)，而不是a(a)；
• 输入虽然最长只有100，但输出最长可能有102。

### ZOJ3491. Wall-nut Bowling

source code (ZOJ3491.cpp) [simulation, data structure]

vls的标程和navi的验题程序都是按这个算法写的。而我觉得这样写的代码好长啊好长啊，于是想了另一种算法。前面的算法的主要思路是，利用数据结构来优化模拟的效率，具体还是坚果按顺序撞倒每个僵尸的。我的思路则刚好是反过来的，我按x坐标的顺序扫描所有僵尸，然后快速求出会被哪个坚果撞倒，或不会被撞倒。做法很简单，用3*n个优先队列维护不同线路的坚果。对于每个僵尸，它可能被来自三个（y=1或y=N时是两个）不同线路的坚果撞倒，而如果有多个可能，实际上应该是被标号最小的坚果撞倒了。所以如果这三个优先队列都为空，那么–ans；否则，假设k是这三个优先队列中最小的堆顶元素，那么将它从原优先队列中删除，根据规则计算出其新的线路，并加到对应的优先队列中去。这个算法的复杂度是O(m\lg k)的，实际效率比很多O(m)的实现还要好，而且写起来简单。

### ZOJ3492. Kagome Kagome

source code (ZOJ3492.cpp) [array, linear search]

### ZOJ3493. Palm Up and Palm Down

source code (ZOJ3493.cpp) [bitwise operation, dynamic programming, probability theory]

```for (int sub = (mask - 1) & mask; sub > 0; sub = (sub - 1) & mask) {
}
```

• 绝对不要算出NaN(Not a Number)来；
• 要能够处理好Inf或/0的情况；
• 比较概率需要加上eps；
• 概率该归一化的时候要归一化。

### ZOJ3494. BCD Code

source code (ZOJ3494.cpp) [Aho-Corasick, dynamic programming, counting]

### ZOJ3495. Lego Bricks

source code (ZOJ3495.cpp) [geometry, topsort]

### ZOJ3496. Assignment

source code (ZOJ3496.cpp) [greedy, parameter search, flow network]

### ZOJ3497. Mistwald

source code (ZOJ3497.cpp) [graph, dynamic programming, powers of matrices]

### ZOJ3498. Javabeans

source code (ZOJ3498.cpp) [greedy, construction]

### ZOJ3499. Median

source code (ZOJ3499.cpp) [sorting]

59 Responses to “第8届浙江省程序设计竞赛点评beta
1. wuyiqi says:

zoj 3494 的数据水了，建议增加如下数据
1
1
00
1 1000

答案应该是21
网上很多错误的都过了，包括我自己的，开始我还以为自己写对了呢。。。。

2. creepyuncle says:

palm up and palm down的ratio有可能加起来不等于100吗？看你的代码有考虑这种情况

• watashi says:

ratio, not percentage

3. Yuan says:

请问神牛
这题ZOJ3491. Wall-nut Bowling 您的标程里的那3个方向的编码是怎样的？
看的不太懂@_@

• watashi says:

[0, m) 斜的，好像是对应从(-i, 0)出发的吧
[m, m + n) 水平的，对应从(i - m, 0)出发的

4. Yuan says:

弱问神牛
vector的clear()和resize(0)哪个快呢？
还有，那个erase后面一部分跟直接resize()到目标大小哪个快呢？

• watashi says:

复杂度是一样的，差别可以忽略不计……

5. CrazyCow says:

菜人写ZOJ3496. Assignment的时候遇到一个灵异问题
当二分最大下界时，l=-1,r=INF就一直WA；然后看了大牛的飘逸程序把上界改成maxflow+1就过了，话说这个问题单调性明显，上界取INF和取maxflow+1有啥区别呀？为啥前者错后者对。。
二分不就是基于函数单调性的么，又有啥奥妙玄机呀

• watashi says:

我的程序改成INF也会WA，看了一下似乎是会死在边=0的边界case上

6. Yuan says:

请问下神牛
3493这题
是不是计算到最后，所有人的输的概率之和会为1？
表示不太懂题目说的“the maximum probability to lose ”，请问这个可不可以解释一下？
多谢了

• watashi says:

不是的，你看样例就有一个是0.0% + 0.0% < 1的
加上死循环的概率之和才是1

• Yuan says:

这题会不会很卡精度啥的？
我这样写
dp[mask] = fabs(left) < EPS ? 1e30: right / left;错了
这样dp[mask] = right / left;就可以过 T_T

• watashi says:

我觉得应该不会才是，只有最后求minimum需要考虑精度吧，中间连EPS都是多余的，直接==0就好了
你是把1e30作为INF么，那么你要注意，在判断答案是不是Infinity的时候要用小得多的数
比如(0.1*1e30+0.9*1)+1 << 1e30……

• Yuan says:

这个注意神奇丫，学到东西了
Orz

• Yuan says:

在您的代码
150 dp[popcnt[j] < popcnt[k] ? j : k] += u[j] * d[k] / x * dp[i];
请问为什么求概率时要除以x？
那种“该轮没人离开”的事件不用考虑？

厄。。。还有就是算期望时，请问转移不考虑 黑与白相等、全黑或全白 是为什么呢？

• Yuan says:

请问下：
假设在运算中浮点数a是除0得到的，如a = 1.0/0.0
这样计算机是将a赋为无穷大吧？
那么即使a * 1e-300 ，最后输出的结果还是无穷大吧？
而手动搞一个INF的话，会因为后面参与运算有可能不再保持INF？

• watashi says:

是的，所以这种情况你可能需要几个不同大小的”INF”，或者pair<double, Flag>
用浮，点数中的±Inf要注意Inf*0=NaN, +Inf+-Inf=NaN ……所以还是要小心的

• Yuan says:

请问下，为什么算期望，算概率时不用考虑“没有人离开”的事件？

• watashi says:

归一化不就是对“没有人离开”的处理么……

• Yuan says:

原来那个是归一化…厄。。。。土了

• Yuan says:

厄。。。还有一个问题
您的代码那里
150 dp[popcnt[j] < popcnt[k] ? j : k] += u[j] * d[k] / x * dp[i];
请问为什么需要除一个x，那种该轮没有人退出的事件不用考虑吗？

• Yuan says:

厄。。。还有一个问题
150 dp[popcnt[j] < popcnt[k] ? j : k] += u[j] * d[k] / x * dp[i];
您的代码里，请问为什么求概率时还要再除以x?
那种该轮没有人离开的事件不用考虑吗？

7. Hi says:

在这里可以求比赛那天拍的傻照片不？网上各种搜不到。。。

• watashi says:

姐姐那里这几天回慢慢贴出来吧，我这里没有……

• Hi says:

跪求姐姐博客地址~~~~

• Hi says:

求姐姐博客地址~

• Hi says:

唉呀呀~看文不仔细的结果呀~
果然是因为我直接跳过了题解部分的结果。。

8. xiaoshua says:

为什么javaman和你在K题上的解释不一样呢。。。 javaman说：从起点出发，走一条长度为P的路径，路径中间点不能经过终点（但可以反复经过其他点）。如果从起点出发P步后，不能到达终点，就是False，如果可以到达终点也可以到其他别的点，就是Maybe，如果P步后只能到达终点（到别的点没有长度为P的路径），则是Yes。
比如
1 2
1 3
2 4
3 6
4 5，p=2这样的图，按你的解释应该是输出True，但javaman的理解却是输出Maybe，求解释。

• javaman says:

我是按我的理解做的，并且能过数据。。。不知道watashi是怎么理解的。。。

• xiaoshua says:

背景略过。以奇怪的输入格式给你一个有向图。如果所有到终点的线路长度都是p，输出True；如果存在这样的线路，输出Maybe；否则，输出False.
这个就是watashi和我一致的理解么。。。。

• guinao says:

我觉得如果输出是True的话说明一定不存在环，这样的话两种理解得到的结果就是一样的了，所以应该没有矛盾。

• javaman says:

怎么可能所有到终点的路径长度都是P 到终点的路径长度可以很多啊……

• guinao says:

我错了。。。。

• watashi says:

在cc98也有人指出了这点
ms结论是数据比较弱，两种理解都能AC

9. no!no!no! says:

在比赛时终于见到watashi本人了。= =无心恋战了

• watashi says:

木有看出这之间因果关系 @,@

10. javaman says:

我也干活了。。。。
Assignment如果给每条边一个费用的话，就直接转线性规划了。用单纯形慢慢算吧……

• watashi says:

我错了……还有欧阳也帮慢修改了描述
但是线性规划怎么做minmax或maxmin？或者怎么转换？

• javaman says:

先求出最大流值f，把它作为已知
然后给每条边上的流量设一个未知数
约束方程是
流量平衡并且到汇点的那些边流量之和等于f
目标函数是 那个费用最小？
这不是线性规划么。。。

• watashi says:

费用不需要设未知数么？
如果要的话，这样不关是minmax了，连线性都不是了……

• javaman says:

我以为费用是给定的。。。。

• Navi says:

线性规划
AX = b
max/min y = C^TX
这里一个人要决策X一个人要决策C，然后一个要最大化y一个要最小化… 这个怎么线性规划…

• javaman says:

我错了。。。
如此说来只能枚举要用的边了。。。

11. tracyzhu says:

今年的金奖竟然多了…

• watashi says:

嗯，我也觉得挺不容易的
今年的金奖刚好发到7题，所以增加到了13个，不过结果奖牌不够了，我们学校有两个队似乎没有拿到奖牌……

12. 原来我们146分钟就1Y了J….
浙大年年出题已属不易…百密一疏..我们理解…

• watashi says:

momo
感谢理解
没有及时发现比较遗憾，好在定奖之前处理好了

13. Navi says:

我错了…

• watashi says:

ym 100% rejudge
幸亏只对一个队有影响……

14. daizhenyang says:

赞解题报告

15. YN!ngC says:

赞美，其实题目应该都蛮好的，但是感觉有些题目描述的晕乎乎的，应该还是有很多队伍能做出后面的那些题目的~可惜大家开坑的位置不好~

16. VegetableB says:

3493的复杂度写错了

• watashi says:

我错了……
vls v5

17. xpycc says:

18. liangjiaxing says:

占个首页看代码

• liangjiaxing says:

代码看不了404

• watashi says:

555 搞定了，多分

19.