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)的算法，贪心帝猛犸也钻地的神题，从前往后看，先假设每天都升级，如果食物不够吃，就一直把最后一次升级改成生产，直到够吃。特别的，这样处理完后可能还要把最后一些升级改成生产得到最优解。
©2010 Zhejiang University ACM/ICPC Team
©2010 http://watashi.ws/acm_x_touhou/
Entries (RSS)
求Master Spark的数据。。。WA到死。。。
全都是生成的随机数据，你可以自己生成着对拍
没有特殊数据吗？我生成了很多大随机数据都和标程输出结果一样，可还是WA。。。
没，你多生成一些n=20的跑跑看
我都生成10000组数据了 都一样-_-||提交还是wa
我生成数据的程序
#!/usr/bin/perl @n = ((100) x 100, 0 .. 2); while ($n[-1] <= 15000) { push @n, int($n[-1] * 1.5); } push @n, (30000, 30000); for $n (@n) { $a = (1 + int(rand(10))) / (1 + int(rand(10))); print "$n $a\n"; @x = (); @y = (); for (1 .. $n) { push @x, rand(200) - 100; push @y, rand(200) - 100; } @x = map { sprintf '%0.2f', $_ } @x; @y = map { sprintf '%0.2f', $_ } @y; print "@x\n@y\n"; }先生真乃神人也
啊啊啊啊啊啊啊！还“油库里”地AC（泪）？
我只过了youmu的一题啊，shiki那道题为了保证精度把除法全部换成了乘法，没想到WA了十几次还不得其解……
sample已经过了，但这也太忽悠了（谁叫你看不懂题目）！
还以为⑨的题最简单，没想到做的人这么少？我已经学了一年了啊混蛋！我连⑨都不如吗？
为什么大家都用C/C++，只有寥寥无几的人用Pascal？我连除号都不适应啊。
/*C/C++的除号和Pascal的除号有区别的，C/C++的整除也是“/”，但是Pascal的整除是“div”。*/
做ACM的话比赛都未必支持Pascal吧，而且C++的STL优势明显啊，你是正在参加OI么？
后来才知道shiki那题光靠sample是分不出浮点数除法还是整数除法的……失误了
⑨的题可不简单的啊……