ACM × Touhou (ZOJ Monthly, August 2010)题解
Posted by watashi in solution, tags: solution, summer2010, ZOJ, 東方| 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)的算法，贪心帝猛犸也钻地的神题，从前往后看，先假设每天都升级，如果食物不够吃，就一直把最后一次升级改成生产，直到够吃。特别的，这样处理完后可能还要把最后一些升级改成生产得到最优解。
Entries (RSS)
大神你好，这道题，我想了很久就是想不出。如果你有空的话，能说一下思路。菜鸟跪谢.
http://acm.hdu.edu.cn/showproblem.php?pid=1598
这题m的规模这么小的话，只要先枚举min edge，再用>= min edge的边构图，求minmax的最短路就可以了吧
也可以排序后，枚举最小的边，在按大小顺序加边，用并查集判连通
还有与日志无关的留言请发到about下吧
大牛你好，我想请教个问题，是关于prim算法的。我对prim算法的理解是，它是逐步构造生成树的，假设含有n个顶点,生成树集合一开始为A,A一开始就为一个顶点v1,选v1到剩下的n-1各顶点中距离最小的，构造出两个点的最小生成树，再在剩下的n-2个顶点中选取到A距离最短的，构造出含三个顶点的最小生成树,。。以此重复直至构造出含n个顶点的最小生成树。我的疑惑是，如果用这种办法，那是否与一开始取的顶点v1有关？我取v2,v3,v4..按这种方法构造出来的最小生成树会一样吗?（如果不一样，那最小生成树的值，岂不是要分别以n个顶点为初始点，构造n次，然后取最小的？），我自己感觉，如果一开始取图里边权值最小的，构造出两个点的最小生成树，在依次按照prim的思想往集合里添加节点。。似乎跟合理。
prim算法有严格的数学证明的，不管从哪个点开始，得到的树的长度都是一样的，最小的，当然树可能是不同的
至于先取最小的边的这种思想，正是kruskal算法的
太太太和谐了，囧，这日英混杂的题目好鬼畜啊
日 英 繁体 符号 注释 动态图 斜体字 logo 就差背景音乐了 ！
其实在题解里放上人物的简介可能不适合，干脆全部放在Introduction底下好了；题目不用带日文吧
嗯，发的有点匆忙，有空的时候试着弄得更pp些
不过明天训练，后天开会，大后天训练……
题目描述好感人。#
。。。
（Problem Hanami Party 让我想起了。。去年NOIP宋神牛的那个”红警”题。#
啊啊啊。。。原来可贪心呀。。#）
占个位置膜拜一下神题……
然后利用一个线段数维护max
线段树LOL…
ym 1.2楼的两位贪心帝
-.- 抢了一个ac..
bs
sf!
ym