

ZOJ Monthly, June 2010 解题报告
Posted by watashi in solution, tags: solution, summer2010, ZOJZOJ Monthly, June 2010,也是今年ACM-ICPC集训选拔赛的一部分。赛前hhanger放出话:
史上最easy的一次月赛,believe me
![]()
这也是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
source 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
source code (ZOJ3344.java) [counting, BigInt]
略
其实问题的本质是求将n个数的排列分解为不超过k的奇数个环的方案数。把n个数的排列分解为恰好k个环的方案数就是第一类斯特林数:
当然还要求n的阶乘。需要大数。
ZOJ3345 Language
source 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
source code (ZOJ3347.cpp) [simulation]
给你一系列对矩阵子阵的操作,包括negative, –, ++, 水平翻转和垂直翻转。最后问某个位置的元素的值。
由于只问一个位置的元素的值,所以只要简单的对其进行模拟操作就可以了,注意这个位置是最终位置,不是初始位置,所以操作的时候要逆序。
ZOJ3348 Schedule
source code (ZOJ3348.cpp) [FlowNetwork]
乒乓球比赛中,胜利最多的人就是冠军,并列不可。给定已结束的比赛结果和未来的比赛安排,问DD能夺冠否?
显然,DD在未来的所有比赛都应该赢了,并且就可以推算出所有人未来最多能赢的比赛场次,于是我们要找一个可行方案。这可以用网络流来做,先假设未来A与B的比赛都是A赢,那么可以连一条A到B的容量为1的有向边,如果有流量,表示其实是B赢了。增加源和汇,如果A还能赢更多的比赛,连一条到汇的边,容量为对应的场次;如果A需要输掉某些比赛,从源连一条边,容量也是对应的比赛。求最大流,如果所有源出去的边都满流,也就是可以输掉所需场次的比赛,那么输出”Yes”。
ZOJ3349 Special Subsequence
source code (ZOJ3349.cpp) [SegTree, DP]
一个长度为n的序列,要求一个长度最大的子序列,满足相邻两个元素的差不超过给定的d。
从左到右扫描,并维护一个线段树,记录当前以某个数结尾的最长子序列的长度,每次都update_max(a, query_max(a – d, a + d) + 1)就好了,最后答案是query_max(-inf, inf)。由于元素的值的范围很大,要离散化。
ZOJ3350 Strange Calender
source 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); }
不解释……
求3351的代码
为什么Number Game用力搞了半天还是搞不懂~~~~(>_<)~~~~
Watashi…
[...] something about watashi[...]…
老大救救我吧,有zoj 3185 的代码吗?请发我邮箱1044805330@qq.com////////谢谢
……这里是ZOJ Monthly, June 2010
于是atouSk, Bzu, CError和Django剩下的那些题不要了?
差不多都用掉了,剩下来的可能还会救急用,但明显下场月赛开始就是新生力量的出场时间了^ ^
也对,下一场月赛开始的时候估计已经出了不少题了,刚好可以拿来用^_^
F那道网络流用您的程序对拍了10000组14个人的,2000组28个人的都一样…zoj上就wa…….有什么恶心数据(⊙_⊙)?
靠,发现了….原来存在只有一个人的情况~~~~(>_<)~~~~
patpat
A 题好多 assert 啊 = =…
加assert可以区分是数据问题还是自己程序问题……
尤其是内部比赛的时候assert是经常要用的……
^_^
于是又要开始出题了-__-
ym 学长什么时候回来?可能周五傍晚版聚
其实我不明白,为什么最后一道题不用判断是否 n/k>b , 不是说洗完之后,会有b 个unit的水留在衣服上吗?
是的,但是这不表示每一份都要大于b啊,假设每份是a<b
那几份后总会有xa>=b的,然后每次加入a的水,变成b+a,再挤掉a,留下b
我开始也是这样认为的,提交了很多次都WA
后来仔细看题目发现有这么一句:Assume there are b units of water on the clothes before what you are going to do and despite water evaporation,就是说最初就已经有b单位的水了。。。
我觉得上个月的简单多了,555
momo 用力
momo~上个月只会2题~
终于能访问shi哥的blog了~来拜一下~Orzzzzzzzz~
ym 学长 前途无量
ps: blog支持ipv6的
bs最后一题不解释的…
靠您了
那你怎么写出来的…
靠您啊
悲剧地发现被很多人用二分水过了……于是准备加强数据-.-
Andrew Stankevich’s Contest #2 ?
555 手抖了 忘改了