ZOJ 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);
}

不解释……

This entry was posted on Monday, June 14th, 2010 at 4:56 pm and is filed under solution. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.