ACM × Touhou (ZOJ Monthly, August 2010)
akyu ZOJ3373 Gensokyo Forbidden Words 19.70% (27/137)
cirno ZOJ3374 ⑨ Adjacent Numbers 11.36% (5/44)
furan ZOJ3375 Imperishable Night 23.12% (68/294)
hatate ZOJ3376 Safest Points 100.00% (3/3)
inaba ZOJ3377 Ancient Duper 23.50% (51/217)
kaguya ZOJ3378 Attack the NEET Princess 9.80% (103/1050)
marisa ZOJ3379 Master Spark 6.64% (20/301)
pache ZOJ3380 Patchouli’s Spell Cards 15.68% (8/51)
reimu ZOJ3381 Osaisen Choudai! 19.51% (193/989)
sakuya ZOJ3382 Luna Dial 28.57% (2/7)
shiki ZOJ3383 Shiro? Kuro? 22.94% (355/1547)
youmu ZOJ3384 Yuyuko and Youmu 50.31% (398/791)
yuyuko ZOJ3385 Hanami Party 0.91% (1/109)

基本上这套题都是红魔馆和白玉楼的天下了,风神录/地灵殿/星莲船都没什么出场机会。然后不多说了,下面是每题简要的解题报告,详细会放在http://watashi.ws/blog/touhou-monthly/touhou-monthly-solutions/

ZOJ3373. Gensokyo Forbidden Words

tag: 通配符(glob), 正则表达式(regex), 字符串(string), if-else
详细解题报告和标程
根据题目描述给定的规则,对”.”, “?”, “*”, “[]“里的第一个”!”变化一下就好了。输入可能有很长很长的一行,getchar推荐。

ZOJ3374. ⑨ Adjacent Numbers

tag: 动态规划(DP), 计数(counting)
详细解题报告和标程
先考虑,从站成一列的n个人里选m个人,不出现9连号的方案数,这个动态规划可解。然后确定一个位置,把环剪开成链,枚举剪开的地方到底是几连号,就可以求出围成一个圈的n个人里选m个人,不出现9连号的方案数。

ZOJ3375. Imperishable Night

tag: 动态规划(DP), 贪心(greedy)
详细解题报告和标程
首先要知道part内的顺序只对本part有影响,而part的顺序可以2^15进行DP。part内也可以DP,不过事实上贪心就好了。

ZOJ3376. Safest Points

tag: 几何(geometry), 宽度优先搜索(bfs)
详细解题报告和标程
先根据定义求出危险点,然后从这些危险点出发bfs求出其余点到危险点的距离,于是就求出了最安全点,不知道为什么没人写@,@

ZOJ3377. Ancient Duper

tag: 博弈(game theory)
详细解题报告和标程
博弈论暴搜即可。似乎题目说的不够清除,我以为直接copy ZOJ1815的描述没什么问题,我错了……

ZOJ3378. Attack the NEET Princess

tag: 图论(graph), 连通性(connectivity), 割边/桥(cut-edge/bridge), Tarjan
详细解题报告和标程
求两点之间的必经之路,注意重边。方法是求桥,不过dfs要加一个对起终点是否是祖先的判断,我比较暴力,把求出来桥的集合和最短路的集合求一个交就是答案。

ZOJ3379. Master Spark

tag: 解析几何, 排序+扫描线
详细解题报告和标程
先求出每个妖精会被击中的极角范围,然后就是极角排序+关键极角扫描了,复杂度O(nlgn)。

ZOJ3380. Patchouli’s Spell Cards

tag: 动态规划(DP), 组合计数(counting)
详细解题报告和标程
出得最为失败的一道题,原本应该是要把n放到10000的,标程的复杂度就与n无关……现在的话,只要记dp[i][j]表示用了1到i这些数字把j个位置填好了,于是dp[i][j]=sum{dp[i-1][j-k]*choose[m-(j- k)][k] | k≤j && k<l}就好了。

ZOJ3381. Osaisen Choudai!

tag: 动态规划(DP), 线段树(SegmentTree)
详细解题报告和标程
显然有O(n^2)的动态规划dp[i] = s[i] + max{dp[i + j] | x[i] ≤ j < y[i]},然后利用一个线段数维护max就可以把复杂度降到O(nlgn)了。

ZOJ3382. Luna Dial

tag: 表达式解析(parser), 树形DP
详细解题报告和标程
先把表达式解析成一个二叉树,这是关键,然后问题就是很简单的树形DP了。

ZOJ3383. Shiro? Kuro?

tag:
详细解题报告和标程
死做,似乎有人没有注意到是整数除法,然后就是一定要过sample啊……

ZOJ3384. Yuyuko and Youmu

tag: 贪心(greedy)
详细解题报告和标程
O(n)的算法,从后往前做,如果食物不足就往前要,要不到就”Myon”。

ZOJ3385. Hanami Party

tag: 贪心(greedy)
详细解题报告和标程
还是O(n)的算法,贪心帝猛犸也钻地的神题,从前往后看,先假设每天都升级,如果食物不够吃,就一直把最后一次升级改成生产,直到够吃。特别的,这样处理完后可能还要把最后一些升级改成生产得到最优解。

17 Responses to “ACM × Touhou (ZOJ Monthly, August 2010)题解”
  1. 菜鸟 says:

    大神你好,这道题,我想了很久就是想不出。如果你有空的话,能说一下思路。菜鸟跪谢.
    http://acm.hdu.edu.cn/showproblem.php?pid=1598

    • watashi says:

      这题m的规模这么小的话,只要先枚举min edge,再用>= min edge的边构图,求minmax的最短路就可以了吧

      • watashi says:

        也可以排序后,枚举最小的边,在按大小顺序加边,用并查集判连通
        还有与日志无关的留言请发到about下吧

  2. 菜鸟 says:

    大牛你好,我想请教个问题,是关于prim算法的。我对prim算法的理解是,它是逐步构造生成树的,假设含有n个顶点,生成树集合一开始为A,A一开始就为一个顶点v1,选v1到剩下的n-1各顶点中距离最小的,构造出两个点的最小生成树,再在剩下的n-2个顶点中选取到A距离最短的,构造出含三个顶点的最小生成树,。。以此重复直至构造出含n个顶点的最小生成树。我的疑惑是,如果用这种办法,那是否与一开始取的顶点v1有关?我取v2,v3,v4..按这种方法构造出来的最小生成树会一样吗?(如果不一样,那最小生成树的值,岂不是要分别以n个顶点为初始点,构造n次,然后取最小的?),我自己感觉,如果一开始取图里边权值最小的,构造出两个点的最小生成树,在依次按照prim的思想往集合里添加节点。。似乎跟合理。

    • watashi says:

      prim算法有严格的数学证明的,不管从哪个点开始,得到的树的长度都是一样的,最小的,当然树可能是不同的
      至于先取最小的边的这种思想,正是kruskal算法的

  3. 木子日匀 says:

    太太太和谐了,囧,这日英混杂的题目好鬼畜啊

    • However says:

      日 英 繁体 符号 注释 动态图 斜体字 logo 就差背景音乐了 !

      • 芙蕾德利卡 says:

        其实在题解里放上人物的简介可能不适合,干脆全部放在Introduction底下好了;题目不用带日文吧

  4. xiaodao says:

    题目描述好感人。#
    。。。
    (Problem Hanami Party 让我想起了。。去年NOIP宋神牛的那个”红警”题。#
    啊啊啊。。。原来可贪心呀。。#)

  5. Dumbear says:

    占个位置膜拜一下神题……

  6. MatRush says:

    然后利用一个线段数维护max
    线段树LOL…

  7. shǎ崽 says:

    ym 1.2楼的两位贪心帝

  8. Navi says:

    -.- 抢了一个ac..

  9. 猛犸也钻地 says:

    sf!

  10.  
Leave a Reply