夏季学期实训-基础数据结构（栈与队列）-白红宇

夏季学期实训-基础数据结构（栈与队列）

阅读量：5896 次

发布时间：2019-06-19

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

A：HDU 1072 （易）

1 /************************************************** 2  * Author     : xiaohao Z 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/ 4  * Last modified : 2014-07-03 09:37 5  * Filename     : hdu_1072.cpp 6  * Description     :  7  * ************************************************/ 8  9 #include 
      
       10 #include 
       
        11 #include 
        
         12 #include 
         
          13 #include 
          
           14 #include 
           
            15 #include 
            
             16 #include 
             
              17 #include 
              
               18 #include 
               
                19 #include 
                20 #define MP(a, b) make_pair(a, b)21 #define PB(a) push_back(a)22 23 using namespace std;24 typedef long long ll;25 typedef pair
                 
                   pii;26 typedef pair
                  
                    puu;27 typedef pair
                   
                     pid;28 typedef pair
                    
                      pli;29 typedef pair
                     
                       pil;30 31 const int INF = 0x3f3f3f3f;32 const double eps = 1E-6;33 const int LEN = 1001;34 int n;35 char op[LEN];36 queue
                      
                        q;37 stack
                       
                         s;38 39 void solvea(){40 int num;41 scanf("%s", op);42 if(!strcmp(op, "IN")){43 scanf("%d\n", &num);44 q.push(num);45 }else {46 if(q.empty()) puts("None");47 else {48 printf("%d\n", q.front());49 q.pop(); 50 }51 }52 }53 54 void solveb(){55 int num;56 scanf("%s", op);57 if(!strcmp(op, "IN")){58 scanf("%d\n", &num);59 s.push(num);60 }else{61 if(s.empty()){62 puts("None");63 }else {64 printf("%d\n", s.top());65 s.pop(); 66 }67 }68 }69 70 int main()71 {72 // freopen("in.txt", "r", stdin);73 74 int T;75 char con[LEN];76 scanf("%d", &T);77 while(T--){78 while(!s.empty()) s.pop();79 while(!q.empty()) q.pop();80 scanf("%d%s", &n, con);81 for(int i=0; i

代码

B：HDU 1022（易）

1 /************************************************** 2  * Author     : xiaohao Z 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/ 4  * Last modified : 2014-07-03 09:53 5  * Filename     : hdu_1022.cpp 6  * Description     :  7  * ************************************************/ 8 #include 
      
        9 #include 
       
        10 #include 
        
         11 #include 
         
          12 #include 
          
           13 #include 
           
            14 #include 
            
             15 #include 
             
              16 #include 
              
               17 #include 
               
                18 #include 
                19 #define MP(a, b) make_pair(a, b)20 #define PB(a) push_back(a)21 22 using namespace std;23 typedef long long ll;24 typedef pair
                 
                   pii;25 typedef pair
                  
                    puu;26 typedef pair
                   
                     pid;27 typedef pair
                    
                      pli;28 typedef pair
                     
                       pil;29 30 const int INF = 0x3f3f3f3f;31 const double eps = 1E-6;32 const int LEN = 100010;33 34 int I(char c){ return c-'0';}35 36 int main()37 {38 // freopen("in.txt", "r", stdin);39 40 stack
                      
                        s;41 queue
                       
                         q;42 char in[11], out[11];43 int ta, tb, n;44 while(scanf("%d", &n)!=EOF){45 while(!s.empty()) s.pop();46 while(!q.empty()) q.pop();47 scanf("%s%s", &in, &out);48 ta = tb = 0;49 int ans = 1;50 while(1){51 if(s.empty()) {52 s.push(I(in[ta++])); 53 q.push(0);54 }else if(s.top() == I(out[tb])){55 tb ++; s.pop();56 q.push(1);57 if(tb == n) break;58 }else {59 if(ta == n) {60 ans = 0;61 break;62 }else{63 q.push(0);64 s.push(I(in[ta++]));65 }66 }67 }68 if(!ans) puts("No.");69 else{70 puts("Yes.");71 while(!q.empty()){72 if(q.front() == 0) puts("in");73 else puts("out");74 q.pop();75 }76 }77 puts("FINISH");78 }79 return 0;80 }

代码

C: HDU 1387（中等）

1 /************************************************** 2  * Author     : xiaohao Z 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/ 4  * Last modified : 2014-07-03 10:15 5  * Filename     : hdu_1387.cpp 6  * Description     :  7  * ************************************************/ 8  9 #include 
      
       10 #include 
       
        11 #include 
        
         12 #include 
         
          13 #include 
          
           14 #include 
           
            15 #include 
            
             16 #include 
             
              17 #include 
              
               18 #include 
               
                19 #include 
                20 #define MP(a, b) make_pair(a, b)21 #define PB(a) push_back(a)22 23 using namespace std;24 typedef long long ll;25 typedef pair
                 
                   pii;26 typedef pair
                  
                    puu;27 typedef pair
                   
                     pid;28 typedef pair
                    
                      pli;29 typedef pair
                     
                       pil;30 31 const int INF = 0x3f3f3f3f;32 const double eps = 1E-6;33 const int LEN = 1010;34 int n, kase = 1;35 map
                      
                        mp;36 queue
                       
                         qa, q[LEN];37 38 void init(){39 for(int i=0; i

代码

E:HDU 1873（易）

1 /************************************************** 2  * Author     : xiaohao Z 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/ 4  * Last modified : 2014-07-03 12:36 5  * Filename     : hdu_1873.cpp 6  * Description     :  7  * ************************************************/ 8  9 #include 
      
       10 #include 
       
        11 #include 
        
         12 #include 
         
          13 #include 
          
           14 #include 
           
            15 #include 
            
             16 #include 
             
              17 #include 
              
               18 #include 
               
                19 #include 
                20 #define MP(a, b) make_pair(a, b)21 #define PB(a) push_back(a)22 23 using namespace std;24 typedef long long ll;25 typedef pair
                 
                   pii;26 typedef pair
                  
                    puu;27 typedef pair
                   
                     pid;28 typedef pair
                    
                      pli;29 typedef pair
                     
                       pil;30 31 const int INF = 0x3f3f3f3f;32 const double eps = 1E-6;33 const int LEN = 11;34 queue
                      
                        q[LEN][LEN];35 int n;36 37 int main()38 {39 // freopen("in.txt", "r", stdin);40 41 char str[LEN];42 int a, b;43 while(scanf("%d", &n)!=EOF){44 for(int i=0; i
                       
                        0; j--){57 if(q[a][j].empty()) continue;58 ans = 1;59 printf("%d\n", q[a][j].front());60 q[a][j].pop();61 break;62 }63 if(!ans) puts("EMPTY");64 }65 }66 }67 return 0;68 }

代码

F:HDU1509（中等）

1 /************************************************** 2  * Author     : xiaohao Z 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/ 4  * Last modified : 2014-07-03 17:46 5  * Filename     : hdu_1059.cpp 6  * Description     :  7  * ************************************************/ 8  9 #include 
      
       10 #include 
       
        11 #include 
        
         12 #include 
         
          13 #include 
          
           14 #include 
           
            15 #include 
            
             16 #include 
             
              17 #include 
              
               18 #include 
               
                19 #include 
                20 #define MP(a, b) make_pair(a, b)21 #define PB(a) push_back(a)22 23 using namespace std;24 typedef long long ll;25 typedef pair
                 
                   pii;26 typedef pair
                  
                    puu;27 typedef pair
                   
                     pid;28 typedef pair
                    
                      pli;29 typedef pair
                     
                       pil;30 31 const int INF = 0x3f3f3f3f;32 const double eps = 1E-6;33 const int LEN = 1010;34 35 struct Mes{36 char s[51];37 int m, p, tag;38 };39 40 struct cmp{41 bool operator() (Mes a, Mes b){42 if(a.p == b.p) return a.tag > b.tag;43 else return a.p > b.p;44 }45 };46 47 int main()48 {49 // freopen("in.txt", "r", stdin);50 51 priority_queue
                      
                       , cmp> q;52 char str[LEN];53 int top = 1;54 while(!q.empty()) q.pop();55 while(scanf("%s", str)!=EOF){56 if(!strcmp(str, "PUT")){57 Mes tp;58 scanf("%s%d%d", tp.s, &tp.m, &tp.p);59 tp.tag = top++;60 q.push(tp);61 }else{62 if(q.empty()) puts("EMPTY QUEUE!");63 else {64 printf("%s %d\n", q.top().s, q.top().m);65 q.pop();66 }67 }68 }69 return 0;70 }

代码

G:HDU 1870（易）

1 /************************************************** 2  * Author     : xiaohao Z 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/ 4  * Last modified : 2014-07-03 18:34 5  * Filename     : hdu_1870.cpp 6  * Description     :  7  * ************************************************/ 8  9 #include 
      
       10 #include 
       
        11 #include 
        
         12 #include 
         
          13 #include 
          
           14 #include 
           
            15 #include 
            
             16 #include 
             
              17 #include 
              
               18 #include 
               
                19 #include 
                20 #define MP(a, b) make_pair(a, b)21 #define PB(a) push_back(a)22 23 using namespace std;24 typedef long long ll;25 typedef pair
                 
                   pii;26 typedef pair
                  
                    puu;27 typedef pair
                   
                     pid;28 typedef pair
                    
                      pli;29 typedef pair
                     
                       pil;30 31 const int INF = 0x3f3f3f3f;32 const double eps = 1E-6;33 const int LEN = 100010;34 char str[LEN];35 36 int main()37 {38 // freopen("in.txt", "r", stdin);39 40 while(scanf("%s", &str)!=EOF){41 int len = strlen(str);42 int ans = 0;43 for(int i=0; i

代码

I:POJ 3253 （中等）

1 /************************************************** 2  * Author     : xiaohao Z 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/ 4  * Last modified : 2014-07-13 11:43 5  * Filename     : poj_3253.cpp 6  * Description     :  7  * ************************************************/ 8  9 #include 
      
       10 #include 
       
        11 #include 
        
         12 #include 
         
          13 #include 
          
           14 #include 
           
            15 #include 
            
             16 #include 
             
              17 #include 
              
               18 #include 
               
                19 #include 
                20 #define MP(a, b) make_pair(a, b)21 #define PB(a) push_back(a)22 23 using namespace std;24 typedef long long ll;25 typedef pair
                 
                   pii;26 typedef pair
                  
                    puu;27 typedef pair
                   
                     pid;28 typedef pair
                    
                      pli;29 typedef pair
                     
                       pil;30 31 const int INF = 0x3f3f3f3f;32 const double eps = 1E-6;33 priority_queue

, greater

> q;34 int n;35 36 int main()37 {38 // freopen("in.txt", "r", stdin);39 40 while(cin >> n){41 while(!q.empty()) q.pop();42 for(int i=0; i

> num;45 q.push(num);46 }47 ll ans = 0;48 while(q.size() > 1){49 int a = q.top(); q.pop();50 int b = q.top(); q.pop();51 ans += (a + b);52 q.push(a + b);53 }54 cout << ans << endl;55 }56 return 0;57 }

View Code

J:POJ 2312 （较难）

1 /************************************************** 2  * Author     : xiaohao Z 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/ 4  * Last modified : 2014-07-13 10:22 5  * Filename     : poj_2312.cpp 6  * Description     :  7  * ************************************************/ 8  9 #include 
      
       10 #include 
       
        11 #include 
        
         12 #include 
         
          13 #include 
          
           14 #include 
           
            15 #include 
            
             16 #include 
             
              17 #include 
              
               18 #include 
               
                19 #include 
                20 #define MP(a, b) make_pair(a, b)21 #define PB(a) push_back(a)22 23 using namespace std;24 typedef long long ll;25 typedef pair
                 
                   pii;26 typedef pair
                  
                    puu;27 typedef pair
                   
                     pid;28 typedef pair
                    
                      pli;29 typedef pair
                     
                       pil;30 31 const int INF = 0x3f3f3f3f;32 const double eps = 1E-6;33 const int LEN = 310;34 char Map[LEN][LEN];35 int m, n, vis[LEN][LEN], sx, sy;36 int xx[] = { 0, 0, 1,-1};37 int yy[] = { 1,-1, 0, 0};38 struct P{39 int x, y, st;40 };41 42 struct cmp{43 bool operator() (P a, P b){44 return a.st > b.st;45 }46 };47 48 P mpp(int _x, int _y, int _st){49 P ret;50 ret.x = _x;ret.y = _y;ret.st = _st;51 return ret;52 }53 54 bool J(int x, int y){55 return x >= 0 && x < n && y >= 0 && y < m && Map[x][y] != 'S' && Map[x][y] != 'R';56 }57 58 int bfs(){59 priority_queue
                      
                       , cmp> q;60 memset(vis, 0, sizeof vis);61 vis[sx][sy] = 1;62 q.push(mpp(sx, sy, 0));63 while(!q.empty()){64 P nvex = q.top(); q.pop();65 int x = nvex.x, y = nvex.y, st = nvex.st;66 if(Map[x][y] == 'T') return st;67 for(int i=0; i<4; i++){68 int tx = x + xx[i];69 int ty = y + yy[i];70 int nst = st + 1;71 if(J(tx, ty) && !vis[tx][ty]){72 if(Map[tx][ty] == 'B') nst ++;73 vis[tx][ty] = 1;74 q.push(mpp(tx, ty, nst));75 }76 }77 }78 return -1;79 }80 81 int main()82 {83 // freopen("in.txt", "r", stdin);84 85 while(cin >> n >> m){86 if(!n && !m) break;87 for(int i=0; i
                       
                        > Map[i][j];90 if(Map[i][j] == 'Y'){91 sx = i; sy = j;92 }93 }94 }95 int ans = bfs();96 cout << ans << endl;97 }98 return 0;99 }