[NOI2007 day2 项链工厂]线段树、维护相对位置**

【题目】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1493

【算法分析】

这题一开始被那个翻转给吓到了,但是画了个图以后发现只是将顺时针变成逆时针,位置全变成n+2-i而已。假如我们都当成是未翻转前去看的话,就很容易想到维护方法。

定义一个偏移量pyl(拼音= =),表示向右旋转了多少格。在搞一个bool型表示是否翻转。

然后翻转前的R操作,直接偏移量+x

如果是翻转后的话,那么就是-x,因为数字变逆时针了,你要全部当成翻转前的情况的话,就相当于逆时针转动。(画了图就比较好理解)

然后有了这些性质,就维护一棵线段树即可。

另外注意数组里的color和线段树里的同步问题。

总之就是一些细节的东西。

【其它】1A,居然垫底了

Rank Run ID User Memory Time Language Code Length Submit Time 1 5318 root 18164K 2839MS Pascal 5.70K 2009-07-08 11:37:16 2 8949 oimaster 29172K 3514MS Pascal 5.26K 2010-01-30 11:57:51 3 5545 pyf 24144K 3948MS Pascal 5.17K 2009-07-10 20:11:20 4 9596 sadness 26860K 4107MS G++ 6.31K 2010-02-18 20:57:45 5 5942 tracyhenry 37808K 4342MS Pascal 4.89K 2009-08-04 15:24:39 6 9366 lilymona 41140K 4592MS G++ 2.69K 2010-02-11 02:14:30 7 5547 xlmj531 17064K 4608MS Pascal 5.92K 2009-07-10 20:14:23 8 5544 tclsm1991 23176K 4686MS Pascal 7.96K 2009-07-10 20:09:27 9 5542 tclsm 23168K 4840MS Pascal 7.96K 2009-07-10 20:08:04 10 5828 wu3412790 44288K 4871MS Pascal 3.55K 2009-07-18 22:11:15 11 9641 edward_mj 30800K 4873MS G++ 4.13K 2010-02-19 21:25:25

【CODE】

#include

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注