hdu 4286 Data Handler-白红宇

hdu 4286 Data Handler

阅读量：7180 次

发布时间：2019-06-29

本文共 4771 字，大约阅读时间需要 15 分钟。

　　到了大型比赛，就算是再水的模拟题都是神模拟。。。这是2012天津网络赛的模拟题。

　　这题是模拟一个链表的指针移动，插入或删除结点，以及倒置指针间的数据顺序。直接一个双向链表就解决问题了！

　　这道模拟还算简单，虽然打了快300行，不过是很容易1y的题。

代码如下：

View Code

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
           5 #include 
          
             6   7 using namespace std;  8 const int maxn = 1000001;  9  10 int lnk[maxn][2], val[maxn]; // lnk[0][1] is the end of left 11 int L, Ln, R, Rn, cntNode; // the pointer is between L & Ln / R & Rn 12 map
           
             OP; 13 14 void pre(){ 15 OP.clear(); 16 OP["MoveLeft"] = 1; 17 OP["MoveRight"] = 2; 18 OP["Insert"] = 3; 19 OP["Delete"] = 4; 20 OP["Reverse"] = 5; 21 } 22 23 void init(){ // make list 24 scanf("%d", &cntNode); 25 26 for (int i = 1; i <= cntNode; i++){ 27 scanf("%d", &val[i]); 28 lnk[i][0] = i - 1; 29 lnk[i][1] = i + 1; 30 } 31 lnk[cntNode][1] = 0; 32 lnk[0][0] = cntNode; 33 lnk[0][1] = 1; 34 35 scanf("%d%d", &Ln, &Rn); 36 L = Ln - 1; 37 R = (Rn + 1) % (cntNode + 1); 38 } 39 40 void moveLeft(char pt){ 41 int tmp; 42 43 assert(pt == 'L' || pt == 'R'); 44 switch(pt){ 45 case 'L':{ 46 assert(L != 0); 47 tmp = L; 48 L = lnk[L][0] == Ln ? lnk[L][1] : lnk[L][0]; 49 Ln = tmp; 50 }break; 51 case 'R':{ 52 assert(Rn != 0); 53 tmp = Rn; 54 Rn = lnk[Rn][0] == R ? lnk[Rn][1] : lnk[Rn][0]; 55 R = tmp; 56 }break; 57 } 58 } 59 60 void moveRight(char pt){ 61 int tmp; 62 63 assert(pt == 'L' || pt == 'R'); 64 switch(pt){ 65 case 'L':{ 66 assert(Ln != 0); 67 tmp = Ln; 68 Ln = lnk[Ln][0] == L ? lnk[Ln][1] : lnk[Ln][0]; 69 L = tmp; 70 }break; 71 case 'R':{ 72 assert(R != 0); 73 tmp = R; 74 R = lnk[R][0] == Rn ? lnk[R][1] : lnk[R][0]; 75 Rn = tmp; 76 }break; 77 } 78 } 79 80 void Ins(char pt, int x){ 81 assert(pt == 'L' || pt == 'R'); 82 switch(pt){ 83 case 'L':{ 84 cntNode++; 85 assert(cntNode < maxn); 86 val[cntNode] = x; 87 if (L == Rn && Ln == R) Rn = cntNode; 88 lnk[cntNode][0] = L; 89 lnk[cntNode][1] = Ln; 90 if (lnk[L][0] == Ln){ 91 lnk[L][0] = cntNode; 92 } 93 else{ 94 lnk[L][1] = cntNode; 95 } 96 if (lnk[Ln][0] == L){ 97 lnk[Ln][0] = cntNode; 98 } 99 else{100 lnk[Ln][1] = cntNode;101 }102 Ln = cntNode;103 }break;104 case 'R':{105 cntNode++;106 assert(cntNode < maxn);107 val[cntNode] = x;108 if (L == Rn && Ln == R) Ln = cntNode;109 lnk[cntNode][0] = R;110 lnk[cntNode][1] = Rn;111 if (lnk[R][0] == Rn){112 lnk[R][0] = cntNode;113 }114 else{115 lnk[R][1] = cntNode;116 }117 if (lnk[Rn][0] == R){118 lnk[Rn][0] = cntNode;119 }120 else{121 lnk[Rn][1] = cntNode;122 }123 Rn = cntNode;124 }break;125 }126 }127 128 void Del(char pt){129 int tmp;130 131 assert(pt == 'L' || pt == 'R');132 switch(pt){133 case 'L':{134 tmp = Ln;135 Ln = lnk[Ln][0] == L ? lnk[Ln][1] : lnk[Ln][0];136 if (lnk[L][0] == tmp){137 lnk[L][0] = Ln;138 }139 else{140 lnk[L][1] = Ln;141 }142 if (lnk[Ln][0] == tmp){143 lnk[Ln][0] = L;144 }145 else{146 lnk[Ln][1] = L;147 }148 }break;149 case 'R':{150 tmp = Rn;151 Rn = lnk[Rn][0] == R ? lnk[Rn][1] : lnk[Rn][0];152 if (lnk[R][0] == tmp){153 lnk[R][0] = Rn;154 }155 else{156 lnk[R][1] = Rn;157 }158 if (lnk[Rn][0] == tmp){159 lnk[Rn][0] = R;160 }161 else{162 lnk[Rn][1] = R;163 }164 165 }break;166 }167 }168 169 void Rev(){170 if (L == Rn && Ln == R) return ;171 172 if (lnk[L][0] == Ln){173 lnk[L][0] = Rn;174 }175 else{176 lnk[L][1] = Rn;177 }178 if (lnk[R][0] == Rn){179 lnk[R][0] = Ln;180 }181 else{182 lnk[R][1] = Ln;183 }184 185 if (lnk[Rn][0] == R){186 lnk[Rn][0] = L;187 }188 else{189 lnk[Rn][1] = L;190 }191 if (lnk[Ln][0] == L){192 lnk[Ln][0] = R;193 }194 else{195 lnk[Ln][1] = R;196 }197 198 swap(Ln, Rn);199 }200 201 void print(){202 int cnt = 0;203 204 L = 0;205 Ln = lnk[0][1];206 printf("%d", val[Ln]);207 moveRight('L');208 while (Ln){209 cnt++;210 assert(cnt < 1e7);211 printf(" %d", val[Ln]);212 moveRight('L');213 }214 puts("");215 }216 217 void deal(){ // follow the commands218 int m, x;219 char buf[3], op[10];220 221 scanf("%d", &m);222 while (m--){223 scanf("%s", op);224 #ifndef ONLINE_JUDGE225 int t1 = L, t2 = Ln;226 printf("L %d R %d\n", Ln, Rn);227 print();228 puts("");229 L = t1;230 Ln = t2;231 #endif232 switch(OP[op]){233 case 1:{234 scanf("%s", buf);235 moveLeft(buf[0]);236 }break;237 case 2:{238 scanf("%s", buf);239 moveRight(buf[0]);240 }241 break;242 case 3:{243 scanf("%s %d", buf, &x);244 Ins(buf[0], x);245 }break;246 case 4:{247 scanf("%s", buf);248 Del(buf[0]);249 }break;250 case 5:{251 Rev();252 }253 break;254 }255 }256 print();257 }258 259 int main(){260 int T;261 262 #ifndef ONLINE_JUDGE263 freopen("in", "r", stdin);264 #endif265 scanf("%d", &T);266 while (T--){267 pre();268 init();269 deal();270 }271 272 return 0;273 }