ZOJ Monthly, June 2010,也是今年ACM-ICPC集训选拔赛的一部分。赛前hhanger放出话:

史上最easy的一次月赛,believe me :mrgreen:

这也是atouSk, Bzu, CError和Django奉献的最后一次Monthly了。没题啊,没题啦……


ZOJ Monthly, June 2010
[A]ZOJ3343 Accident Tree 12.00% (3/25)
[B]ZOJ3344 Card Game 36.73% (18/49)
[C]ZOJ3345 Language 28.90% (61/211)
[D]ZOJ3346 Number Game 12.87% (26/202)
[E]ZOJ3347 Picture Handling 26.15% (68/260)
[F]ZOJ3348 Schedule 14.21% (30/211)
[G]ZOJ3349 Special Subsequence 18.09% (76/420)
[H]ZOJ3350 Strange Calender 21.21% (7/33)
[I]ZOJ3351 Washing Clothes 18.64% (110/590)

ZOJ3343 Accident Tree

downloadsource code (ZOJ3343.cpp) [bitwise, tree, parser, scanf]

计算中心218原因不明地起火了,据专家Frozen的表示,起火原因可用一棵XML树表示:

  • 非叶子节点有两种:”and”代表的条件成立当且仅当其所有的子条件都成立;而”or”节点只要有一个子条件成立,这个节点就成立;
  • 叶子节点都表示一个元条件,包含名字和概率。注意具有相同名字的叶子节点总是同时成立或不成立的。

要求这棵树(根节点)成立的概率。最多只有10种不同名字的元条件。

由于只有10种不同名字的元条件,很容易想到2^10枚举所有情况,再判断根节点是否成立。最后的答案就是所有成立情况的加权和,复杂度为2^10*200。题目的麻烦之处再于读入XML并parse成树,其实灵活运用scanf的话,还是比较轻松的,具体看代码。

ZOJ3344 Card Game

downloadsource code (ZOJ3344.java) [counting, BigInt]

其实问题的本质是求将n个数的排列分解为不超过k的奇数个环的方案数。把n个数的排列分解为恰好k个环的方案数就是第一类斯特林数

\left[{n\atop k}\right] = (n-1) \left[{n-1\atop k}\right] + \left[{n-1\atop k-1}\right].

当然还要求n的阶乘。需要大数。

ZOJ3345 Language

downloadsource code (ZOJ3345.cpp) [string]

给定一些语言的模板和一些单词在某些语言中的类型,判断一个句子是什么语言的。

由于模板非常简单,数据规模也非常小,暴力匹配就好了。不过还是洋洋洒洒写了上百行。

ZOJ3346 Number Game

[number theory, game theory]

还是用Alice和Bob好了。对于一个数n,Alice可以把它变成[n, n^2]的任意一个数,而Bob可以把它变成n/(p^k),其中p是素数,k>0。如果n变成1990则Alice胜,n变成1则Bob胜,给定一个初始的n,Alice先手,问谁必胜。

下面来证明:如果n≥45,则Alice必胜。如果45≤n≤1990,那么n≤1990≤n^2,Alice一步就可以胜了,否则记m=ceil(sqrt(n))。由于任意k和2k之间都有一个素数,所以存在两个不同素数p和q落在m和n之间,于是Alice取p*q,这样Bob只能把它变成p或q,不妨设为p,那么Alice新的可选区间就是[p, p^2],显然p<n且p^2>n,按照这个策略,n最终将会满足45≤n≤1990,所以Alice必胜。得证。其它自己用力搞吧,结论就是:n<6,Bob胜,n>7,Alice胜。

ZOJ3347 Picture Handling

downloadsource code (ZOJ3347.cpp) [simulation]

给你一系列对矩阵子阵的操作,包括negative, –, ++, 水平翻转和垂直翻转。最后问某个位置的元素的值。

由于只问一个位置的元素的值,所以只要简单的对其进行模拟操作就可以了,注意这个位置是最终位置,不是初始位置,所以操作的时候要逆序。

ZOJ3348 Schedule

downloadsource code (ZOJ3348.cpp) [FlowNetwork]

乒乓球比赛中,胜利最多的人就是冠军,并列不可。给定已结束的比赛结果和未来的比赛安排,问DD能夺冠否?

显然,DD在未来的所有比赛都应该赢了,并且就可以推算出所有人未来最多能赢的比赛场次,于是我们要找一个可行方案。这可以用网络流来做,先假设未来A与B的比赛都是A赢,那么可以连一条A到B的容量为1的有向边,如果有流量,表示其实是B赢了。增加源和汇,如果A还能赢更多的比赛,连一条到汇的边,容量为对应的场次;如果A需要输掉某些比赛,从源连一条边,容量也是对应的比赛。求最大流,如果所有源出去的边都满流,也就是可以输掉所需场次的比赛,那么输出”Yes”。

ZOJ3349 Special Subsequence

downloadsource code (ZOJ3349.cpp) [SegTree, DP]

一个长度为n的序列,要求一个长度最大的子序列,满足相邻两个元素的差不超过给定的d。

从左到右扫描,并维护一个线段树,记录当前以某个数结尾的最长子序列的长度,每次都update_max(a, query_max(a – d, a + d) + 1)就好了,最后答案是query_max(-inf, inf)。由于元素的值的范围很大,要离散化。

ZOJ3350 Strange Calender

downloadsource code (ZOJ3350.cpp) [counting, integer]

Bzu行星一年长T1,一个月长T2,一天长T3,T1是T3的倍数,可惜T2是个任性的数。规定满月出现的那一天为新的一个月的第一天,如果是新年到来,也将开始新的一个月,而每年第一次满月出现的那个月是1月,所以有0月这种东西存在。现在要求某年某月有多少天。

一旦不整除,这个世界就不太平了,估计作者也嫌麻烦,所以T1才是T3的倍数,否则就真的大自然了。把思路理清了其实核心代码也只有十几行,首先计算当年第一个满月出现的时间(first_full),然后就可以算出不考虑年时这个月开始(begin)与结束(end)的时间,最后求出这个月的长度,具体看代码吧……因为我也描述不能= =b。此类问题最好全部使用整数运算。

ZOJ3351 Washing Clothes

[yet-another-easy-problem]

while (scanf("%*d%*d%d", &answer) != EOF) {
	printf("%d\n", answer);
}

不解释……

29 Responses to “ZOJ Monthly, June 2010 解题报告”
  1. ygb says:

    求3351的代码

  2. jing says:

    为什么Number Game用力搞了半天还是搞不懂~~~~(>_<)~~~~

  3. Watashi says:

    Watashi…

    [...] something about watashi[...]…

  4. wyf says:

    老大救救我吧,有zoj 3185 的代码吗?请发我邮箱1044805330@qq.com////////谢谢

  5. icyrhyme says:

    于是atouSk, Bzu, CError和Django剩下的那些题不要了?

    • watashi says:

      差不多都用掉了,剩下来的可能还会救急用,但明显下场月赛开始就是新生力量的出场时间了^ ^

      • icyrhyme says:

        也对,下一场月赛开始的时候估计已经出了不少题了,刚好可以拿来用^_^

  6. YY says:

    F那道网络流用您的程序对拍了10000组14个人的,2000组28个人的都一样…zoj上就wa…….有什么恶心数据(⊙_⊙)?

  7. xpycc says:

    A 题好多 assert 啊 = =…

    • watashi says:

      加assert可以区分是数据问题还是自己程序问题……
      尤其是内部比赛的时候assert是经常要用的……
      ^_^

  8. Fancy says:

    于是又要开始出题了-__-

  9. liangjiaxing says:

    其实我不明白,为什么最后一道题不用判断是否 n/k>b , 不是说洗完之后,会有b 个unit的水留在衣服上吗?

    • watashi says:

      是的,但是这不表示每一份都要大于b啊,假设每份是a<b
      那几份后总会有xa>=b的,然后每次加入a的水,变成b+a,再挤掉a,留下b

    • whitedeath says:

      我开始也是这样认为的,提交了很多次都WA

      后来仔细看题目发现有这么一句:Assume there are b units of water on the clothes before what you are going to do and despite water evaporation,就是说最初就已经有b单位的水了。。。

  10. vout says:

    我觉得上个月的简单多了,555

  11. Navi says:

    bs最后一题不解释的…

  12. Qinz says:

    Andrew Stankevich’s Contest #2 ?

  13.  
Leave a Reply