算法模板——线段树7(骰子翻转问题)

实现功能:首先输入一个长度为N的序列,由1-4组成(1表示向前滚一下,2表示向后滚一下,3表示向左滚一下,4表示向右滚一下,骰子原始状态:上1前2左4右5后3下6),然后输入任意多个操作,输入“1 x y”表示将序列第x个数改成y,输入“2 x y”表示输出对于原始状态的骰子,按照从x到y的序列操作可以使骰子变成什么样子

原理:还是线段树,而且只需要点修改区间访问,不过这里面区间之间的合并不再是简单的累加了,而是——置换关系,通过置换关系的合并实现及时的维护即可

 1 type
 2     cube=array[1..6] of longint;
 3 const fo:cube=(3,1,6,4,5,2);
 4       ba:cube=(2,6,1,4,5,3);
 5       le:cube=(5,2,3,1,6,4);
 6       ri:cube=(4,2,3,6,1,5);
 7       mo:cube=(1,2,3,4,5,6);
 8 var
 9    i,j,k,l,m,n:longint;
10    a:array[0..1000000] of cube;
11    a1:cube;
12 function min(x,y:longint):longint;inline;
13          begin
14               if x<y then min:=x else min:=y;
15          end;
16 function max(x,y:longint):longint;inline;
17          begin
18               if x>y then max:=x else max:=y;
19          end;
20 
21 function merge(a1,a2:cube):cube;inline;
22           var a3:cube;i:longint;
23           begin
24                for i:=1 to 6 do
25                    a3[i]:=a1[a2[i]];
26                exit(a3);
27           end;
28 procedure built(z,x,y:longint);inline;
29           begin
30                if x=y then
31                   begin
32                        read(i);
33                        case i of
34                             1:a[z]:=fo;
35                             2:a[z]:=ba;
36                             3:a[z]:=le;
37                             4:a[z]:=ri;
38                        end;
39                   end
40                else
41                    begin
42                         built(z*2,x,(x+y) div 2);
43                         built(z*2+1,(x+y) div 2+1,y);
44                         a[z]:=merge(a[z*2],a[z*2+1]);
45                    end;
46           end;
47 procedure op(z,x,y,t,v:longint);inline;
48           begin
49                if (t=y) and (x=t) then
50                   begin
51                        case v of
52                             1:a[z]:=fo;
53                             2:a[z]:=ba;
54                             3:a[z]:=le;
55                             4:a[z]:=ri;
56                        end;
57                        exit;
58                   end;
59                if t<=(x+y) div 2 then op(z*2,x,(x+y) div 2,t,v) else op(z*2+1,(x+y) div 2+1,y,t,v);
60                a[z]:=merge(a[z*2],a[z*2+1]);
61           end;
62 function res(z,x,y,l,r:longint):cube;inline;
63          begin
64               if (l>r) then exit(mo);
65               if (x=l) and (y=r) then exit(a[z]);
66               exit(merge(result(z*2,x,(x+y) div 2,l,min((x+y) div 2,r)),result(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r)));
67          end;
68 begin
69      readln(n);
70      built(1,1,n);
71      readln;
72      while true do
73            begin
74                 read(i);
75                 case i of
76                      1:begin
77                             readln(j,k);
78                             op(1,1,n,j,k);
79                      end;
80                      2:begin
81                             readln(j,k);
82                             a1:=res(1,1,n,j,k);
83                             for i:=1 to 6 do write(a1[i],' ');
84                             writeln;
85                      end;
86                 end;
87            end;
88 
89 end.
90                  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习原理

深度学习(2)——tensorflow可视化TensorFlow变量作用域TensorFlow可视化示例

1625
来自专栏有趣的Python和你

Python数据分析之pandas数据可视化折线图条形图pandas绘图乱码解决

2334
来自专栏机器学习原理

深度学习(1)——tensorflow简介什么是TensorFlow?什么是数据流图?安装基本概念示例变量的更新操作

3813
来自专栏人工智能的秘密

Tensorflow教程:GPU调用如何实现

今天,给大家分析一下Tensorflow源码之GPU调用是如何实现的?

9470
来自专栏用户2442861的专栏

Qt 学习之路 2(45):模型

http://www.devbean.net/2013/02/qt-study-road-2-model/

982
来自专栏深度学习那些事儿

在pytorch中实现与TensorFlow类似的"same"方式padding

文章来自Oldpan博客:https://oldpan.me/archives/pytorch-same-padding-tflike

2.8K7
来自专栏吉浦迅科技

DAY44:阅读Texture Reference API

fetches from the region of linear memory bound to the one-dimensional texture re...

932
来自专栏漫漫深度学习路

tensorflow学习笔记(三十四):Saver(保存与加载模型)

Saver tensorflow 中的 Saver 对象是用于 参数保存和恢复的。如何使用呢? 这里介绍了一些基本的用法。 官网中给出了这么一个例子: ...

3998
来自专栏章鱼的慢慢技术路

层层递进——宽度优先搜索(BFS)

2424
来自专栏码匠的流水账

HashedWheelTimer算法详解

George Varghese 和 Tony Lauck 1996 年的论文:Hashed and Hierarchical Timing Wheels: da...

1561

扫码关注云+社区

领取腾讯云代金券