2012 ACM-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.現在のポインタから時計回りにk 2個の数を調べ、このk 2個の数はすべてxを加える.
 

2: reverseStarting from the arrow pointed element, reverse the first k1 clockwise elements.
現在のポインタから時計回りにk 1個の数を調べ、このk 1個の数を反転
 

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で反時計回りに1箇所移動
x=2でポインタが時計回りに1つ移動

6: queryOutput the number on the arrow pointed element in one line.現在のポインタの値を尋ねる

 
 
実はこの問題はとても水のようで、もし1つのデータの構造を思い付くならば---dequeue
その时私は思いついたが、その时は风邪を引いて、头がくらくらして、あるいはその他の原因でしょう、この问题は队长に放弃されました.
試合が終わった後、私はこのような水を考えた.
今問題が出てきたら編み出した.
 
構想:3つのdeque、1つの方向タグ、1つの遅延タグ.
最初のdequeは0からk 1の数を保存し、方向は正とマークします.
2番目のdequeメモリk 1~k 2の数
3番目の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:
",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
",root.query());break;
114             }
115         }
116     }
117     return 0;
118 }