2012ACM-ICPC杭州站A题

发布时间:2017-2-24 21:05:24 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"2012ACM-ICPC杭州站A题",主要涉及到2012ACM-ICPC杭州站A题方面的内容,对于2012ACM-ICPC杭州站A题感兴趣的同学可以参考一下。

题目http://acm.hdu.edu.cn/showproblem.php?pid=4453 Looploop   题意: 有个循环链表,一个指针。 然后又几个操作 1: add x Starting from the arrow pointed element, add x to the number on the clockwise first k2 elements.从当前指针顺时针查k2个数,这k2个数全部加x   2: reverseStarting from the arrow pointed element, reverse the first k1 clockwise elements. 从当前指针顺时针查k1个数,这k1个数翻转   3: insert x Insert a new element with number x to the right (along clockwise) of the arrow pointed element.在指针之后插入一个数x 4: delete Delete the element the arrow pointed and then move the arrow to the right element.删除指针所指的数,指针指向顺时针的下一个   5: move x x can only be 1 or 2. If x = 1 , move the arrow to the left(along the counterclockwise) element, if x = 2 move the arrow to the right element.指针移动 x=1时逆时针移动一个位置 x=2时指针顺时针移动一个位置 6: queryOutput the number on the arrow pointed element in one line.询问当前指针所指的值     其实这道题很水的,如果想到一个数据结构的话---dequeue 当时我虽然想到了,可是当时感冒了,头很晕,或者其他原因吧,这道题被队长放弃了。 结束比赛后我一想这么水。 现在题挂出来了就编出来了。   思路:三个deque,一个方向标记,一个延迟标记。 第一个deque存0至k1个数,方向标记为正 第二个deque存k1至k2个数 第三个deque存剩下的 可以参考这个图 说到这如果熟悉deque的话就应该明白了 详细见代码吧   View Code 1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 using namespace std; 5 struct Root{ 6 deque<int>que1,que2,que3; 7 int _add; 8 bool head; 9 //初始化 10 void init(int k1,int k2,int n){ 11 _add=0; 12 head=true; 13 while(!que1.empty())que1.pop_back(); 14 while(!que2.empty())que2.pop_back(); 15 while(!que3.empty())que3.pop_back(); 16 int tmp; 17 for(int i=0;i<k1;i++){ 18 scanf("%d",&tmp); 19 que1.push_back(tmp); 20 } 21 for(int i=k1;i<k2;i++){ 22 scanf("%d",&tmp); 23 que2.push_back(tmp); 24 } 25 for(int i=k2;i<n;i++){ 26 scanf("%d",&tmp); 27 que3.push_front(tmp); 28 } 29 30 } 31 //插入一个x,由于是顺时针在指针之后插入 32 //这样插入之后整就要向顺时针移动一次 33 //如果que1的第一个在que3中,则只需把x插入que1,然后move(1)即可 34 void insert(int x){ 35 if(head){ 36 que3.push_front(que1.front()+_add);que1.pop_front(); 37 que1.push_front(x-_add); 38 }else{ 39 que3.push_front(que1.back()+_add);que1.pop_back(); 40 que1.push_back(x-_add); 41 } 42 move(1); 43 } 44 //删除一个元素整体要逆时针移动一次 45 //那我们就先逆时针移动一次,也就是move(2) 46 //然后删除que3的ront即可 47 void _delete(){ 48 move(2); 49 que3.pop_front(); 50 } 51 //翻转时只需翻转标记位即可 52 void reverse(){ 53 head=!head; 54 } 55 //加x时只需加延迟标记位即可 56 void add(int x){ 57 _add+=x; 58 } 59 //移动时比较繁琐,不过思路较简单 60 //左移相当于逆时针旋转一次 61 //右移相当于顺时针旋转一次 62 void move(int x){ 63 if(x==1){ 64 if(head){ 65 que1.push_front(que3.front()-_add);que3.pop_front(); 66 que2.push_front(que1.back());que1.pop_back(); 67 que3.push_back(que2.back()+_add);que2.pop_back(); 68 }else{ 69 que1.push_back(que3.front()-_add);que3.pop_front(); 70 que2.push_front(que1.front());que1.pop_front(); 71 que3.push_back(que2.back()+_add);que2.pop_back(); 72 } 73 }else{ 74 if(head){ 75 que3.push_front(que1.front()+_add);que1.pop_front(); 76 que1.push_back(que2.front());que2.pop_front(); 77 que2.push_back(que3.back()-_add);que3.pop_back(); 78 }else{ 79 que3.push_front(que1.back()+_add);que1.pop_back(); 80 que1.push_front(que2.front());que2.pop_front(); 81 que2.push_back(que3.back()-_add);que3.pop_back(); 82 } 83 } 84 } 85 //询问时返回实际值即可 86 int query(){ 87 if(head){ 88 return que1.front()+_add; 89 }else{ 90 return que1.back()+_add; 91 } 92 } 93 94 }root; 95 96 97 98 int main(){ 99 int m,tmp,n,k1,k2; 100 char op[10]; 101 int ca=1; 102 while(scanf("%d%d%d%d",&n,&m,&k1,&k2),n){ 103 root.init(k1,k2,n); 104 printf("Case #%d:\n",ca++); 105 while(m--){ 106 scanf("%s",op); 107 switch(op[0]){ 108 case 'a':scanf("%d",&tmp);root.add(tmp);break; 109 case 'r':root.reverse();break; 110 case 'i':scanf("%d",&tmp);root.insert(tmp);break; 111 case 'd':root._delete();break; 112 case 'm':scanf("%d",&tmp);root.move(tmp);break; 113 case 'q':printf("%d\n",root.query());break; 114 } 115 } 116 } 117 return 0; 118 }    

上一篇:JAVA获取文件MD5值
下一篇:Android利用Volley异步加载数据(JSON和图片)完整示例

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。