刘汝佳算法竞赛-入门经典第二部分算法篇第六章 1（Lists）

题目大意：一个人一张张发牌，如果这张牌与这张牌前面的一张或者前面的第三张（后面称之为一位置和三位置）的点数或花式相同，则将这张牌移动到与之对应的位置（优先三位置，也就是说如果一位置与三位置都有以上的性质则移动到三位置之上），移动之后若仍以上的性质，则继续操作，直到已发的所有牌都无法移动之后再继续发牌，（如果一个位置被移空，则删除此位置！）

解题思路：用数组模拟链表，每发一张牌就匹配三位置，如果匹配就移动，否则再看一位置是否满足，如果满足就移动，移动之后，再继续之前的操作，直到所有的都不能移动！如果都不满足，则继续发牌！如此反复直到所有牌都发完！最后只剩下几叠移不动的牌，依次输出每叠的数量。最开始的数是总叠数，如果是1则输出“1 pile remaining: ”其他则输出“6 piles remaining: ”！

解题代码：

  1 //Author:   Freetion
  2 //file:        127 - "Accordian" Patience
  3 
  4 #include <iostream>
  5 #include <math.h>
  6 #include <string.h>
  7 #include <stdio.h>
  8 using namespace std;
  9 
 10 struct node
 11 {
 12     string pile[53];
 13     int num;
 14 }pat[53];
 15 bool noth[53];
 16 
 17 int main()
 18 {
 19     freopen("data.in", "r", stdin);
 20     freopen("data.out", "w", stdout);
 21     string tm;
 22     while (cin >> tm && tm[0] != '#')
 23     {
 24         memset (noth, false, sizeof (noth));
 25         int i = 0;
 26         pat[i].pile[0] = "";
 27         pat[i].pile[0] += tm;
 28         pat[i++].num = 1;
 29         for ( ; i < 52; i ++)
 30         {
 31             pat[i].num = 0;
 32             cin >> pat[i].pile[pat[i].num++]; 
 33         }
 34 /*        for (i = 0; i < 52; i ++)
 35             cout << pat[i].pile[0] << " ";
 36         for (i = 0; i < 52; i ++)
 37             cout << pat[i].num << " ";
 38 */
 39         int total = 52;
 40         for (i = 0; i < 52; i ++)
 41         {
 42             int bf = 0, cm = i - 1;
 43             while (bf < 3 && cm >= 0)
 44             {
 45                 if (noth[cm --])
 46                     continue;
 47                 bf ++;
 48             }
 49             if (bf == 3 && !noth[i])
 50             {
 51                 node& cmp_1 = pat[i];
 52                 node& cmp_2 = pat[cm+1];
 53                 if ( cmp_1.pile[cmp_1.num-1][0] == cmp_2.pile[cmp_2.num-1][0] )
 54                 {
 55                     cmp_2.pile[cmp_2.num] = "";
 56                     cmp_2.pile[cmp_2.num ++] += cmp_1.pile[--cmp_1.num];
 57                     if (cmp_1.num <= 0)
 58                     {
 59                         noth[i] = true;
 60                         total --;
 61                     }
 62                     i = cm;
 63                     continue;
 64                 }
 65                 else if ( cmp_1.pile[cmp_1.num-1][1] == cmp_2.pile[cmp_2.num-1][1] )
 66                 {
 67                     cmp_2.pile[cmp_2.num] = "";
 68                     cmp_2.pile[cmp_2.num ++] += cmp_1.pile[--cmp_1.num];
 69                     if (cmp_1.num <= 0)
 70                     {
 71                         noth[i] = true;
 72                         total --;
 73                     }
 74                     i = cm;
 75                     continue;
 76                 }
 77             }
 78             bf = 0, cm = i - 1;
 79             while (bf < 1 && cm >= 0)
 80             {
 81                 if (noth[cm --])
 82                     continue;
 83                 bf ++;
 84             }
 85             if (bf == 1 && !noth[i])
 86             {
 87                 node& cmp_1 = pat[i];
 88                 node& cmp_2 = pat[cm+1];
 89                 if ( cmp_1.pile[cmp_1.num-1][0] == cmp_2.pile[cmp_2.num-1][0] )
 90                 {
 91                     cmp_2.pile[cmp_2.num] = "";
 92                     cmp_2.pile[cmp_2.num ++] += cmp_1.pile[--cmp_1.num];
 93                     if (cmp_1.num <= 0)
 94                     {
 95                         noth[i] = true;
 96                         total --;
 97                     }
 98                     i = cm;
 99                     continue;
100                 }
101                 else if ( cmp_1.pile[cmp_1.num-1][1] == cmp_2.pile[cmp_2.num-1][1] )
102                 {
103                     cmp_2.pile[cmp_2.num] = "";
104                     cmp_2.pile[cmp_2.num ++] += cmp_1.pile[--cmp_1.num];
105                     if (cmp_1.num <= 0)
106                     {
107                         noth[i] = true;
108                         total --;
109                     }
110                     i = cm;
111                     continue;
112                 }
113             }
114         }
115         if (total > 1)
116             printf ("%d piles remaining:", total);
117         else printf ("%d pile remaining:", total);
118         for (i = 0; i < 52; i ++)
119         {
120             if (!noth[i])
121                 printf (" %d", pat[i].num);
122         }
123         puts("");
124     }
125     return 0;
126 }

View Code

开始时我用得字符数组，而不是字符串，但是用字符数组时，运行到此条语句时cmp_2.pile[cmp_2.num ++] 当cmp_2.num == 50时，自加就变成了25529。直到现在也没弄明白为什么！如果哪位大神路过此地又恰巧知道其中原理时请告知！谢谢。。。

101 - The Blocks Problem

题目大意：提供一个大牛的博客http://www.cnblogs.com/devymex/archive/2010/08/04/1792128.html

解题思路：模拟操作就是了！

解题代码：

  1 //Author    :Freetion
  2 //file        :101 - The Blocks Problem
  3 
  4 #include <stdio.h>
  5 #include <string.h>
  6 
  7 struct node
  8 {
  9     int top;
 10     int up[30];
 11 }pos[30];
 12 
 13 int main()
 14 {
 15 //    freopen("data.in", "r", stdin);
 16 //    freopen("data.out", "w", stdout);
 17     int n;
 18     char in[2][6];
 19     int p1, on1, p2, on2, ope;
 20     int num1, num2;
 21     while (scanf ("%d", &n) == 1)
 22     {
 23         for (int i = 0; i < n; i ++)
 24         {
 25             pos[i].top = 0;
 26             pos[i].up[pos[i].top ++] = i;
 27         }
 28         while (scanf("%s", in[0]) == 1)
 29         {
 30             if (in[0][0] == 'q')
 31                 break;
 32             scanf ("%d %s %d", &num1, in[1], &num2);
 33             p1 = p2 = -1;
 34             for (int i = 0; i < n; i ++)
 35             {
 36                 for (int j = 0; j < pos[i].top; j ++)
 37                 {
 38                     if (num1 == pos[i].up[j])
 39                         p1 = i, on1 = j;
 40                     if (num2 == pos[i].up[j])
 41                         p2 = i, on2 = j;
 42                     if (p1 != -1 && p2 != -1)
 43                         break;
 44                 }
 45                 if (p1 != -1 && p2 != -1)
 46                         break;
 47             }
 48             if (p1 == p2)
 49                 continue;
 50             if (in[0][0] == 'm')
 51                 ope = 1;
 52             else ope = 3;
 53             if (in[1][1] == 'v')
 54                 ope ++;
 55             if (ope == 1)
 56             {
 57                 for (int i = on1+1; i < pos[p1].top; i ++)
 58                 {
 59                     node& A = pos[pos[p1].up[i]];
 60                     A.up[A.top ++] = pos[p1].up[i];
 61                 }
 62                 pos[p1].top = on1+1;
 63                 for (int i = on2+1; i < pos[p2].top; i ++)
 64                 {
 65                     node& A = pos[pos[p2].up[i]];
 66                     A.up[A.top ++] = pos[p2].up[i];
 67                 }
 68                 pos[p2].top = on2 +1;
 69                     pos[p2].up[pos[p2].top ++] = pos[p1].up[--pos[p1].top];
 70             }
 71             else if (ope == 2)
 72             {
 73                 for (int i = on1+1; i < pos[p1].top; i ++)
 74                 {
 75                     node& A = pos[pos[p1].up[i]];
 76                     A.up[A.top ++] = pos[p1].up[i];
 77                 }
 78                 pos[p1].top = on1+1;
 79                     pos[p2].up[pos[p2].top ++] = pos[p1].up[--pos[p1].top];
 80             }
 81             else if (ope == 3)
 82             {
 83                 for (int i = on2+1; i < pos[p2].top; i ++)
 84                 {
 85                     node& A = pos[pos[p2].up[i]];
 86                     A.up[A.top ++] = pos[p2].up[i];
 87                 }
 88                 pos[p2].top = on2 +1;
 89                 for (int i = on1; i < pos[p1].top; i ++)
 90                 {
 91                     pos[p2].up[pos[p2].top ++] = pos[p1].up[i];
 92                 }
 93                 pos[p1].top = on1;
 94             }
 95             else if (ope == 4)
 96             {
 97                 for (int i = on1; i < pos[p1].top; i ++)
 98                 {
 99                     pos[p2].up[pos[p2].top ++] = pos[p1].up[i];
100                 }
101                 pos[p1].top = on1;
102             }
103         }
104         for (int i = 0; i < n; i ++)
105         {
106             printf ("%d:", i);
107             for (int j = 0; j < pos[i].top; j ++)
108                 printf (" %d", pos[i].up[j]);
109             printf ("
");
110         }
111     }
112     return 0;
113 }

View Code

133 - The Dole Queue

题目大意：给你一个n个数组成的环，再给出一个顺时钟数的数k，一个逆时钟数的数m。要你从开始的位置同时朝顺时钟和逆时钟两个方向数，将顺时钟数到的第k个数和逆时钟数到的第m个数同时从环中剔除，然后继续数直到环上没有数了。如果数到的是同一个数，则只剔除这一个数。

解题思路：直接操作，水题！ps：样例中三角型代表的是空格。

解题代码：

 1 //Author    :Freetion
 2 //file        :133 - The Dole Queue
 3 
 4 #include <stdio.h>
 5 #include <string.h>
 6 using namespace std;
 7 int pp[30];
 8 int k, m;
 9 bool jug[30];
10 
11 int main()
12 {
13 //    freopen("data.in", "r", stdin);
14 //    freopen("data.out", "w", stdout);
15     int k, m, n;
16     while (~scanf ("%d%d%d", &n, &k, &m) && (k+m+n))
17     {
18         memset(jug, true, sizeof (jug));
19         int shu = 1;
20         int ni = n;
21         int total = n;
22         int num;
23         while (total)
24         {
25             num = 0;
26             while (num < k)
27             {
28                 if (shu > n)
29                     shu -= n;
30                 if (jug[shu++])
31                     num ++;
32             }
33             shu --;
34             num = 0;
35             while (num < m)
36             {
37                 if (ni <= 0)
38                     ni += n;
39                 if (jug[ni --])
40                     num ++;
41             }
42             ni ++;
43             if (ni == shu)
44             {
45                 printf ("%3d", ni);
46                 jug[ni] = false;
47                 total --;
48             }
49             else
50             {
51                 printf ("%3d%3d", shu, ni);
52                 jug[ni] = jug[shu] = false;
53                 total -= 2;
54             }
55             if (total)
56                 printf (",");
57         }
58         printf ("
");
59     }
60 }

View Code

10152 - ShellSort

题目大意：给出一堆龟壳，我们要将它们按照另一种顺序排好，而每次操作都只能移动一个龟壳，并且只能将其放在这一堆的最上面。问使用最少的移动次数时依次移动龟壳的顺序。

解题思路：

解题代码：

 1 //Author    :Freetion
 2 //file        :10152 - ShellSort
 3 
 4 #include <iostream>
 5 #include <stdio.h>
 6 #include <string>
 7 #include <map>
 8 using namespace std;
 9 
10 const int max_n = 202;
11 
12 string str1[max_n], str2[max_n];
13 
14 int main()
15 {
16 //    freopen("data.in", "r", stdin);
17 //    freopen("data.out", "w", stdout);
18     int n, T;
19     scanf ("%d", &T);
20     while (T --)
21     {
22         scanf ("%d", &n);
23         getchar();
24         for (int i = n-1; i >= 0; i --)
25         {
26             getline(cin, str1[i]);
27         }
28         for (int i = n-1; i >= 0; i --)
29         {
30             getline(cin, str2[i]);
31         }
32         int j = 0;
33         for (int i = 0; i < n; i ++)
34         {
35             if (str1[i] == str2[j])
36                 j ++;
37         }
38         for (; j < n; j ++)
39             cout << str2[j] << endl;
40         printf ("
");
41     }
42     return 0;
43 }

View Code

673 - Parentheses Balance

解题思路：将左括号入栈，如果碰上右括号则看是否与前一个左括号匹配，如果匹配则左括号匹配出栈，直到最后看栈是否空，空则Yes，否则No。

解题代码：

 1 //Author    :Freetion
 2 //file        :uva-673 Parentheses Balance
 3 
 4 #include <stdio.h>
 5 #include <stack>
 6 #include <string>
 7 #include <iostream>
 8 using namespace std;
 9 string str;
10 char mat(const char s)
11 {
12     if (s == ']')
13         return '[';
14     if (s == ')')
15         return '(';
16     return 0;
17 }
18 
19 bool jug()
20 {
21     stack <char> st;
22     st.push('0');
23     int len = str.size();
24     for (int i = 0; i < len; i ++)
25     {
26         if (st.top() != mat(str[i]))
27             st.push(str[i]);
28         else st.pop();
29     }
30     return st.size() == 1;
31 }
32 
33 int main()
34 {
35     int n;
36     scanf ("%d", &n);
37     getchar();
38     while (n --)
39     {
40         getline(cin, str);
41         if (str.size() == 0 || jug())
42             printf ("Yes
");
43         else printf ("No
");
44     }
45     return 0;
46 }

View Code

442 - Matrix Chain Multiplication

题目意思是让我们求矩阵相乘的总次数，另外括号是里面限定了只有两个矩阵！

解题思路：可以利用上题括号匹配，将先算的矩阵找出来，然后判断是否可以相乘，可以则计算次数，不可以则退出循环。

解题代码：

 1 //Author    :Freetion
 2 //file        :442 - Matrix Chain Multiplication
 3 
 4 #include <stdio.h>
 5 #include <string.h>
 6 #include <stack>
 7 #include <iostream>
 8 using namespace std;
 9 
10 struct node
11 {    
12     int x, y;
13 }Matrix[30];
14 
15 int main ()
16 {
17 //    freopen("data.in", "r", stdin);
18 //    freopen("data.out", "w", stdout);
19     int n;
20     char s[2];
21     char mul[1000];
22     while (~scanf ("%d", &n))
23     {
24         for (int i = 0; i < n; i ++)
25         {
26             scanf ("%s", s);
27             scanf ("%d%d", &Matrix[s[0]-'A'].x, &Matrix[s[0]-'A'].y);
28         }
29         while (~scanf ("%s", mul))
30         {
31             int len = strlen(mul);
32             node temp[30];
33             int top = 0;
34             int ans = 0;
35             bool falg = 1;
36             for (int i = 0; i < len; i ++)
37             {
38                 if (mul[i] >= 'A' && mul[i] <= 'Z')
39                     temp[top ++] = Matrix[mul[i]- 'A'];
40                 else if (mul[i] == ')' && top > 1)
41                 {
42                     if (temp[top-2].y != temp[top-1].x)
43                     {    falg = 0;    break;    }
44                     ans += temp[top-2].y * temp[top-2].x * temp[top-1].y;
45                     temp[top-2].y = temp[top-1].y;
46                     top --;
47                 }
48             }
49             if (falg)
50                 printf ("%d
", ans);
51             else
52                 printf  ("error
");
53         }
54     }
55 }

View Code

11111 - Generalized Matrioshkas

此题与673相似，只是将左括号换成了负数，右括号换成了与之互为相反数的正数。当然依旧需要左右括号匹配，与此同时，这一级数的括号所用的数字，要比下一级括号所用的数字之和要大！

解题代码：

 1 //Author    :Freetion
 2 //file        :11111 - Generalized Matrioshkas
 3 
 4 #include <stdio.h>
 5 #include <string>
 6 #include <sstream>
 7 #include <iostream>
 8 #include <stack>
 9 using namespace std;
10 
11 struct node
12 {
13     node(const int &a, const int &b):cap(a), left(b) {}
14     int cap, left;
15 };
16 
17 int main ()
18 {
19     freopen ("data.in", "r", stdin);
20     freopen ("data.out", "w", stdout);
21     string line;
22     while (getline(cin, line))
23     {
24         stack <node> ope;
25         istringstream ss(line);
26         int t;
27         bool judge = false;
28         while (ss >> t)
29         {
30             if (t < 0)
31             {    
32                 if(ope.empty())
33                     ope.push(node(-t, -t));
34                 else
35                 {
36                     ope.top().left += t;
37                     if (ope.top().left <= 0)
38                     {    judge = 1;    break;    }
39                     else
40                         ope.push(node(-t, -t));
41                 }
42             }
43             else
44             {
45                 if (ope.empty() || ope.top().cap != t)
46                 {    judge = 1;    break;    }    
47                 else
48                     ope.pop();
49             }
50         }
51         if (judge || !ope.empty())
52             printf (":-( Try again.
");
53         else printf (":-) Matrioshka!
");
54     }
55     return 0;
56 }

View Code

11234 - Expressions

这题我也是百度思路的，所以直接贴代码：

 1 //Author    :Freetion
 2 //file        :11234 - Expressions
 3 //´ËÊÇºÃÌâ£¡ 
 4 
 5 #include <stdio.h>
 6 #include <string>
 7 #include <stack>
 8 #include <queue>
 9 #include <iostream>
10 using namespace std;
11 
12 struct node
13 {
14     char ope;
15     node *left;
16     node *right;
17     node (char s, node *l, node *r)
18     {
19         ope = s;
20         left = l;
21         right = r;
22     }
23     node (char s)
24     {
25         ope = s;
26         left = NULL;
27         right = NULL;
28     }
29 };
30 
31 int main()
32 {
33     string str;
34     int T;
35     scanf ("%d", &T);
36     getchar();
37     while (T--)
38     {
39         stack <node *> ans;
40         cin >> str;
41         int len = str.length();
42         for (int i = 0; i < len; i ++)
43         {
44             if (islower(str[i]))
45             {
46                 node *new_node = new node(str[i]);
47                 ans.push(new_node);
48             }
49             else
50             {
51                 node *a = ans.top();
52                 ans.pop();
53                 node *b = ans.top();
54                 ans.pop();
55                 node *new_node = new node(str[i], b, a);
56                 ans.push(new_node);
57             }
58         }
59         node *root = ans.top();
60         ans.pop();
61         queue <node *> p;
62         p.push(root);
63         while (!p.empty())
64         {
65             node *q = p.front();
66             p.pop();
67             if (q -> left != NULL)
68                 p.push(q -> left);
69             if (q -> right != NULL)
70                 p.push(q -> right);
71             ans.push(q);
72         }
73         while (!ans.empty())
74         {
75             printf ("%c", ans.top()->ope);
76             ans.pop();
77         }
78         cout << endl;
79     }
80     return 0;
81 }

View Code

540 - Team Queue

题目大意：这题不难但是题意好难搞清楚（当然这是对我来说），看看能否说的清楚：给你一个初始队列，这个队列不同于一般的队列，它由多个队列组成一个大队列，然后依次输入操作，ENQUEUE n，代表将数n加入队列，如果在哪个队列里有与n相等的元素则加入该队列之后，如果没有则加入到最后那个队列之后，也就是输入的第一个队列。DEQUEUE 代表删除操作，删除操作是这样的，是按照队列来进行操作的，按队列先进先出的规则，也就是说哪个队列先加入元素，则先输出哪个队列里的元素。输出元素的规则就是先进先出，哪个元素先加入这个队列，则先输出哪个元素，直到把加入该队列的元素都输出之后，再输出次优先的队列中的元素。每次只删除一个元素！（应该差不多了）

解题思路：运用队列来做！

解题代码：

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string>
 4 #include <queue>
 5 #include <map>
 6 using namespace std;
 7 
 8 int main()
 9 {
10     int n, k, T = 1;
11     while (~scanf ("%d", &n), n)
12     {
13         map <int, int> num;
14         queue <int> que[1004];
15         queue <int> que_num;
16         printf ("Scenario #%d
", T++);
17         for (int i = 0; i < n; i ++)
18         {
19             scanf ("%d", &k);
20             for (int j =  0; j < k; j ++)
21             {
22                 int x;
23                 scanf ("%d", &x);
24                 num[x] = i;
25             }
26         }
27         string str;
28         while (cin >> str && str[0] != 'S')
29         {
30             if (str[0] == 'E')
31             {
32                 int x;
33                 scanf ("%d", &x);
34             //    cout << num[x] << endl;
35                 if (que[num[x]].empty())
36                     que_num.push(num[x]);
37                 que[num[x]].push(x);
38             //    cout << que_num.size() << endl;
39             }
40             else
41             {
42                 int t = que_num.front();
43                 printf ("%d
", que[t].front());
44                 que[t].pop();
45                 if (que[t].empty())
46                     que_num.pop();
47             }
48         }
49         printf ("
");
50     }
51 }

View Code

10050 - Hartals

水题一道

解题代码：

 1 //Author    :Freetion
 2 //file        :10050 - Hartals
 3 
 4 #include <stdio.h>
 5 #include <iostream>
 6 #include <string.h>
 7 using namespace std;
 8 const int max_n = 3660;
 9 bool ba[max_n];
10 
11 int main()
12 {
13     int T;
14     int n, p;
15     scanf ("%d", &T);
16     while (T--)
17     {
18         scanf ("%d%d", &n, &p);
19         memset(ba, false, sizeof (ba));
20         for (int i = 0; i < p; i ++)
21         {
22             int h;
23             scanf ("%d", &h);
24             for (int j = h; j <= n; j += h)
25             {
26                 int wek = (j+6)%7;
27                 if (wek != 5 && wek != 6)
28                     ba[j] = true;
29             }
30         }
31         int ans = 0;
32         for (int i = 0; i <= n; i ++)
33             if (ba[i])
34                 ans ++;
35         printf ("%d
", ans);
36     }
37     return 0;
38 }

View Code

刘汝佳 算法竞赛-入门经典 第二部分 算法篇 第六章 1（Lists）

11111 - Generalized Matrioshkas

刘汝佳算法竞赛-入门经典第二部分算法篇第六章 1（Lists）