Solutions

解题报告

解题报告已发布,对题目/数据/解题报告有问题请留言 :D

传送门:Practice Session的解题报告

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/

10 Responses to “Solutions”
  1. Passer-by says:

    都不知道你D题在说什么,描述的不清不楚的,想要有人做还真是挺难。

  2. xo.jam says:

    求Master Spark的数据。。。WA到死。。。

    • watashi says:

      全都是生成的随机数据,你可以自己生成着对拍

      • xo.jam says:

        没有特殊数据吗?我生成了很多大随机数据都和标程输出结果一样,可还是WA。。。

        • watashi says:

          没,你多生成一些n=20的跑跑看

          • hzhua says:

            我都生成10000组数据了 都一样-_-||提交还是wa

            • watashi says:

              我生成数据的程序

              #!/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";
              }
              
  3. 552734199 says:

    先生真乃神人也

  4. 芙蕾德利卡 says:

    啊啊啊啊啊啊啊!还“油库里”地AC(泪)?

    我只过了youmu的一题啊,shiki那道题为了保证精度把除法全部换成了乘法,没想到WA了十几次还不得其解……
    sample已经过了,但这也太忽悠了(谁叫你看不懂题目)!
    还以为⑨的题最简单,没想到做的人这么少?我已经学了一年了啊混蛋!我连⑨都不如吗?

    为什么大家都用C/C++,只有寥寥无几的人用Pascal?我连除号都不适应啊。
    /*C/C++的除号和Pascal的除号有区别的,C/C++的整除也是“/”,但是Pascal的整除是“div”。*/

    • watashi says:

      做ACM的话比赛都未必支持Pascal吧,而且C++的STL优势明显啊,你是正在参加OI么?
      后来才知道shiki那题光靠sample是分不出浮点数除法还是整数除法的……失误了
      ⑨的题可不简单的啊……

  5.  
Leave a Reply