【题解】 —算法竞赛入门经典第二版 【第六章例题】【17/22】

发表于 | 更新于 | 分类于

UVa 210 Concurrency Simulator 【Deque】

题目大意：

本题需要你模拟一些简单程序，每一个程序有以下5种指令：

  • var = val，给变量赋值，简单起见保证变量名为一个字母，变量为所有进程共用，并且初始为0，保证val是不大于100的正整数；
  • print var,输出变量var；
  • lock对所有变量申请独占访问(不影响赋值和打印)
  • unlock解除独占访问
  • end结束程序
    以上指令分别消耗t1,t2,t3,t4,t5的时间,一开始进程按照输入顺序依次插入到等待队列中，每次从等待队列队首选择一个进程执行。每个进程有一个配额(限定时间)Q，当配额用完时,该进程会在执行完当前语句后被立即插入到一个等待队列尾部中。
    但是lock语句和unlock语句会改变进程的执行顺序。当一个程序执行了lock语句,其他进程再执行到lock语句时会被立即插入到一个阻止队列队尾,当程序执行到unlock语句时，阻止队列的队首的第一个进程会被立即插入到等待队列队首。

解题思路：

总体看来需要两个队列分别存取lock的进程和ready(等待)的进程。存取lock进程的队列只需要插入到队尾和从队首取这两种操作即可，普通队列就可完成；存取ready进程的队列除从队首取元素外，既需要插入到队尾又需要插入到队首，故需要双端队列来实现。然后模拟整个过程即可。
具体实现时先把所有操作都存下来，并记录每个起始进程的坐标，然后模拟进程的运行，执行相应语句就行了。

Mycode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <deque>
using namespace std;

bool flag;
char s[1111][11];
int t, n, c[5], q, val[26], ip[1111];
queue<int> B;
deque<int> R;
void run(int idx)
{
    int T = q;
    while(T > 0)
    {
        char *p = s[ip[idx]];
        switch(p[2])
        {
        case '=': //? = ?
            val[p[0] - 'a'] = isdigit(p[5]) ? (p[4] - '0') * 10 + p[5] - '0' : p[4]- '0';
            T -= c[0];
            break;
        case 'i': //print
            printf("%d: %d\n", idx, val[p[6] - 'a']);
            T -= c[1];
            break;
        case 'c': //lock
            if(flag)
            {
                B.push(idx);
                return ;
            }
            flag = true;
            T-= c[2];
            break;
        case 'l': //unlock
            flag = false;
            if(!B.empty())
            {
                int idx2 = B.front();
                B.pop();
                R.push_front(idx2);
            }
            T-= c[3];
            break;
        case 'd':
            return ;
        }
        ip[idx]++;
    }
    R.push_back(idx);
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        flag = false;
        memset(val, 0, sizeof(val));
        scanf("%d%d%d%d%d%d%d",&n,&c[0],&c[1],&c[2],&c[3],&c[4],&q);
        int line = 1;
        for(int i = 1; i <= n; ++i)
        {
            fgets(s[line++], 1111, stdin);
            ip[i] = line - 1;
            while(s[line - 1][2] != 'd')
            {
                fgets(s[line++], 1111, stdin);
            }
            R.push_back(i);
        }
        while(!R.empty())
        {
            int idx1 = R.front();
            R.pop_front();
            run(idx1);
        }
        if(t)   puts("");
    }
    return 0;
}

UVa 514 Rails【stack】

题目大意：

编号为1 ~ n 的n个元素依次入栈，问给出的出栈顺序是否是合法的。

解题思路：

直接模拟比对即可。

Mycode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
using namespace std;

int n, a[1111];
int main()
{
    while(cin >> n && n)
    {
        while(cin >> a[1] && a[1])
        {
            for(int i = 2; i <= n; ++i)
                cin >> a[i];
            int cnt = 1;
            stack<int> s;
            for(int i = 1; i <= n; ++i)
            {
                s.push(i);
                while(!s.empty() && s.top() == a[cnt])
                {
                    s.pop();
                    ++cnt;
                }
            }
            puts(s.empty() ? "Yes" : "No");
        }
        puts("");
    }
    return 0;
}

UVa 442 Matrix Chain Multiplication【stack】

题目大意：

给出$t$个$n \times m$的矩阵，问给出的矩阵乘法表达式是否合法，合法的话进行了多少次普通乘法。

解题思路：

$p \times q$ 的矩阵 只能与$q \times r$的矩阵相乘，此时进行的乘法次数为$p \times q \times r$次，再与其他相乘的时候就是次数之和了。
表达式用栈来模拟就好了。

Mycode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <map>
using namespace std;

char ch;
string op;
int n, a, b;
int main()
{
    while(cin >> n)
    {
        map<char, pair<int, int> > mapa;
        for(int i = 1; i <= n; ++i)
        {
            cin >> ch >> a >> b;
            mapa[ch] =  make_pair(a, b);
        }
        while(cin >> op)
        {
            stack<pair<int, int> > num;
            int res = 0;
            bool flag = true;
            for(int i = 0; i < op.size(); ++i)
            {
                if(op[i] == '(')
                {
                    continue;
                }
                else if(op[i] == ')')
                {
                    pair<int, int> p, q;
                    p = num.top();
                    num.pop();
                    q = num.top();
                    num.pop();
                    if(q.second != p.first)
                    {
                        flag = false;
                        break;
                    }
                    res += q.first * p.second * p.first;
                    num.push(make_pair(q.first, p.second));
                }
                else
                {
                    num.push(mapa[op[i]]);
                }
            }
            if(flag)
                printf("%d\n", res);
            else
                puts("error");
        }
    }
    return 0;
}

UVa 11988 Broken Keyboard (a.k.a. Beiju Text) 【链表】

题目大意：

Albert的键盘出现了奇妙的故障，所有键都会正常的工作，但是键盘上的Home以及End键有时候会莫名其妙的自己按下。但是盲打很熟练的他一般习惯关闭显示器打字，因为这样很酷。

现在他正在打一段文本，假设你已经知道这段文本以及Home和End键会什么时候出现故障自行按下。请你编写一个程序，求出他最后打出的文本。

解题思路：

  1. 用数组保存这段文本，然后设置一个变量pos保存光标位置，这样输入一个字符相当于在数组中插入一个字符，这时把后面的字符向后移动就可以了。 但是这样会超时。
  2. 采用链表，每输入一个字符就把它存起来，设输入的字符串是s[1~n]，则可以用next[i]表示在当前显示屏中s[i]右边的字符编号(在s中的下标)。 具体做法：用变量记录当前位置和最后一个字母的位置，模拟移动、插入过程。方便起见，开头设置一个虚拟结点。

链表：

用数组模拟链表的方法：一个数组记录原本的值，另一个数组记录该位置的下一个位置的下标。

Mycode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

char s[111111];
int cur, las, nex[111111];
int main()
{
    while(~scanf("%s", s + 1))
    {
        int len = strlen(s + 1);
        cur = las = nex[0] = 0;
        for(int i = 1; i <= len; ++i)
        {
            if(s[i] == '[')
                cur = 0;
            else if(s[i] == ']')
                cur = las;
            else
            {
                nex[i] = nex[cur];
                nex[cur] = i;
                if(cur == las)  las = i;
                cur = i;
            }
        }
        for(int i = nex[0]; i != 0; i = nex[i])
            printf("%c", s[i]);
        puts("");
    }
    return 0;
}

UVa 12657 Boxes in a Line【链表】

题目大意：

现有从左到右编号为1 ~ n的n个盒子摆成一行，分别执行如下4种指令的某些指令，问执行后所有奇数位置的盒子的编号之和。
指令有：

  • 1 x y 将盒子x移动到盒子y的左边 (如果x已经在y的左边，忽略此指令)
  • 2 x y 将盒子x移动到盒子y的右边 (如果x已经在y的右边，忽略此指令)
  • 3 x y 交换盒子x和y的位置
  • 4 反转整条链

解题思路：

采用双向链表模拟整个过程。

解后有感：

小技巧： 对于过程4我们可以不用模拟反转的过程，用个标志进行记录是否进行了反转就可以。如果反转了，那1、2操作将变为相应的2、1操作，3操作无影响，最后结果记录偶数的位置就行。

关于代码：感觉自己写的十分“朴素”，写完后虽然能AC，但日后再看起肯定不好理解，而且调试时也不那么得心应手。看完LRJ大爷的代码，真真感觉到了自己菜爆。

  1. 首先链表的连接操作用一个函数表示，减少代码量的同时增加了美观性，方便调试。
  2. 链表建立时建的循环链表，而且一个循环left和right都构建完了，还是比我的好看多了。
  3. 特判交换位置时的那部分，将两种情况合为一种(其实就是xy的位置不同，完全能想到的)，也就减少了代码量。
  4. 最后的计算只计算正着看的奇数位的和，反转时直接用总和减去此时的值。

日后注意的地方：

  1. 多次用到一种计算时写成函数
  2. 先思考后写代码，逻辑弄清后再写
  3. 能用1行代码写清楚的地方就不用2行。

最后附上我和LRJ大爷的代码 对比感受一下。

Mycode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int n, m;
int op, x, y;
int tem1, tem2;
long long res;
int rig[111111], lef[111111];
void init()
{
    memset(rig, 0, sizeof(rig));
    memset(lef, 0, sizeof(lef));
    for(int i = 0; i <= n; ++i)
        rig[i] = i + 1;
    for(int i = n + 1; i > 0; --i)
        lef[i] = i - 1;
}
void debug()
{
    cout << "\n**************\n";
    for(int i = 0; i <= n+1; ++i)
        cout << rig[i] << " ";
    cout << endl;

    for(int i = 0; i <= n+1; ++i)
        cout << lef[i] << " ";
    cout << endl;

     for(int i = rig[0], j = 1; j <= n; i = rig[i], ++j)
        cout << i << " ";
     cout << endl;
     cout << "**************\n\n";
}
int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    for(int cas = 1; ~scanf("%d%d",&n,&m); ++cas)
    {
        init();

        bool flag = true;
        while(m--)
        {
//            debug();
            scanf("%d",&op);
            if(op == 4)
            {
                flag = !flag;
                continue;
            }
            if(op < 3 && !flag)
                op = 3 - op;
            scanf("%d%d",&x,&y);
            switch(op)
            {
            case 1:
                if(x == lef[y])    break;
                rig[lef[x]] = rig[x];
                lef[rig[x]] = lef[x];
                rig[x] = y;
                lef[x] = lef[y];
                rig[lef[y]] = x;
                lef[y] = x;
                break;
            case 2:
                if(x == rig[y]) break;
                rig[lef[x]] = rig[x];
                lef[rig[x]] = lef[x];
                lef[x] = y;
                rig[x] = rig[y];
                lef[rig[y]] = x;
                rig[y] = x;
                break;
            case 3:
                if(x == lef[y])
                {
                    tem1 = rig[y];
                    tem2 = lef[x];
                    lef[y] = tem2;
                    rig[tem2] = y;
                    rig[x] = tem1;
                    lef[tem1] = x;
                    lef[x] = y;
                    rig[y] = x;
                }
                else if(x == rig[y])
                {
                    tem1 = rig[x];
                    tem2 = lef[y];
                    rig[y] = tem1;
                    lef[tem1] = y;
                    lef[x] = tem2;
                    rig[tem2] = x;
                    lef[y] = x;
                    rig[x] = y;
                }
                else
                {
                    tem1 = lef[y];
                    tem2 = rig[y];
                    lef[y] = lef[x];
                    rig[y] = rig[x];
                    rig[lef[x]] = y;
                    lef[rig[x]] = y;
                    lef[x] = tem1;
                    rig[x] = tem2;
                    rig[tem1] = x;
                    lef[tem2] = x;
                }
                break;
            }
        }

//        debug();

        res = 0;
        if(flag)
        {
//            cout << "orign !\n";
            for(int i = rig[0], j = 1; j <= n; i = rig[i], ++j)
                if(j & 1)   res += i;
        }
        else
        {
//            cout << "reverse !\n";
            for(int i = lef[n + 1], j = 1; j <= n; i = lef[i], ++j)
                if(j & 1)   res += i;
        }
        printf("Case %d: %lld\n", cas, res);
    }
    return 0;
}

LRJ’s code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// UVa12657 Boxes in a Line
// Rujia Liu
#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn = 100000 + 5;
int n, left[maxn], right[maxn];

inline void link(int L, int R) {
  right[L] = R; left[R] = L;
}

int main() {
  int m, kase = 0;
  while(scanf("%d%d", &n, &m) == 2) {
    for(int i = 1; i <= n; i++) {
      left[i] = i-1;
      right[i] = (i+1) % (n+1);
    }
    right[0] = 1; left[0] = n;
    int op, X, Y, inv = 0;

    while(m--) {
      scanf("%d", &op);
      if(op == 4) inv = !inv;
      else {
        scanf("%d%d", &X, &Y);
        if(op == 3 && right[Y] == X) swap(X, Y);
        if(op != 3 && inv) op = 3 - op;
        if(op == 1 && X == left[Y]) continue;
        if(op == 2 && X == right[Y]) continue;

        int LX = left[X], RX = right[X], LY = left[Y], RY = right[Y];
        if(op == 1) {
          link(LX, RX); link(LY, X); link(X, Y);
        }
        else if(op == 2) {
          link(LX, RX); link(Y, X); link(X, RY);
        }
        else if(op == 3) {
          if(right[X] == Y) { link(LX, Y); link(Y, X); link(X, RY); }
          else { link(LX, Y); link(Y, RX); link(LY, X); link(X, RY); }
        }
      }
    }

    int b = 0;
    long long ans = 0;
    for(int i = 1; i <= n; i++) {
      b = right[b];
      if(i % 2 == 1) ans += b;
    }
    if(inv && n % 2 == 0) ans = (long long)n*(n+1)/2 - ans;
    printf("Case %d: %lld\n", ++kase, ans);
  }
  return 0;
}

UVa 679 Dropping Balls 【二叉树编号】

题目大意：

一棵二叉树最大深度为D，所有叶子的深度都相同，所有结点从上到下从左到右编号为1，2，3，……，$2^D - 1$。在结点1处放个小球，它会往下落。每个结点处都有一个开关，初始时全部关闭，当有小球落到一个开关时其状态就会改变。当小球到达结点时若此开关开着则往左走，否则往右走，直到走到叶子结点。
一些球从1处依次往下落，问第i个会落在哪。

解题思路：

很明显对于一个结点k而言，其左子结点为$2 \times k$，右子结点为$2 \times k + 1$。因为每个球最终都会落在叶子结点上，所以前两个一定是第一个落在左子树上，第二个落在右子树上。推广到一般来看，只需知道小球是第几个落在根的子树里的就能知道它下一步是往左还是往右了。
具体的，拿第一步为例，如果一开始i & 1，那它就往左，此时位置变为1 << 1，在新的“根结点”处它就成了第i + 1 << 1个来到此结点的小球了；同理，如果一开始!(i & 1)，那它就往右，位置变为1 << 1 | 1，新的“根结点”处变成第i << 1个到此位置的小球。然后我们就可以反复执行此过程直到小球落到叶子结点了。

Mycode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int t, n, d;
int main()
{
    while(cin >> t && t != -1)
    {
        while(t--)
        {
            cin >> d >> n;
            int k = 1;
            for(int i = 1; i < d; ++i)
            {
                if(n & 1)
                {
                    k = k << 1;
                    n = n + 1 >> 1;
                }
                else
                {
                    k = k << 1 | 1;
                    n = n >> 1;
                }
            }
            cout << k << endl;
        }
    }
    return 0;
}

UVa 122 Trees on the level 【二叉树的层次遍历】

题目大意：

输入一颗二叉树，请你从上到下、从左到右的顺序输出各个结点的值。输入的格式详情参照题目说明。

解题思路：

  1. 我们可以将树上结点编号，然后把二叉树存到数组里。结点最多256个，如果他们形成一条链的话，最后一个结点的编号高达$2^{256} - 1​$，数组根本开不下。
  2. 采用动态结构，将需要的建立新的结点，然后将其组织成一棵树。

PS：下面的代码是参照LRJ大爷给出的代码写的，随着学习的深入越加觉得LRJ大爷真是tql！

Mycode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
const int MAX = 1111;

bool flag;
char s[MAX];
struct node
{
    int val;
    bool have_val;
    node *left, *right;
    node() : have_val(false), left(NULL), right(NULL) {}
} *root;

void addnode(int val, char* s)
{
    node* u = root;
    for(int i = 0; s[i]; ++i)
    {
        if(s[i] == 'L')
        {
            if(u -> left == NULL)
                u -> left = new node();
            u = u -> left;
        }
        else if(s[i] == 'R')
        {
            if(u -> right == NULL)
                u -> right = new node();
            u = u -> right;
        }
    }
    if(u -> have_val)   flag = false;
    u -> val = val;
    u -> have_val = true;
}

void delete_tree(node* u)
{
    if(u == NULL)   return ;
    delete_tree(u -> left);
    delete_tree(u -> right);
    delete u;
}

bool read()
{
    flag = true;
    delete_tree(root);
    root = new node();
    for(;;)
    {
        if(scanf("%s", s) != 1) return false;
        if(strcmp(s, "()") == 0)    break;
        int v;
        sscanf(&s[1], "%d", &v);
        addnode(v, strchr(s, ',')+1);
    }
    return true;
}

bool bfs(vector<int>& res)
{
    res.clear();
    queue<node*> Q;
    Q.push(root);
    while(!Q.empty())
    {
        node* u = Q.front();
        Q.pop();
        if(!u -> have_val)  return false;
        res.push_back(u -> val);
        if(u -> left != NULL)   Q.push(u -> left);
        if(u -> right != NULL)  Q.push(u -> right);
    }
    return true;
}

int main()
{
    vector<int> res;
    while(read())
    {
        if(!bfs(res))   flag = false;
        if(flag)
        {
            for(int i = 0; i < res.size(); ++i)
            {
                printf("%d%c", res[i], i == res.size() - 1 ? '\n' : ' ');
            }
        }
        else
            puts("not complete");
    }
    return 0;
}

UVa 548 Tree 【二叉树的递归遍历】

题目大意：

给出一颗点带权的二叉树的中序和后序遍历，找一个叶子使得它到根的路径上的权和最小。如果有多解，该叶子本身权应尽量小。

解题思路：

后序遍历的最后一个字符是根，我们在中序遍历中找到它，然后就可以找到左右子树的中序和后序遍历了。根据这个把树通过递归构建出来，然后再执行一次递归遍历来找最优解就OK了。

Mycode：(参考紫书)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
using namespace std;
const int MAX = 10010;

int n, in_order[MAX], post_order[MAX], lch[MAX], rch[MAX];

bool read_list(int* a)
{
    string line;
    if(!getline(cin, line)) return false;
    stringstream ss(line);
    n = 0;
    int x;
    while(ss >> x)  a[n++] = x;
    return n > 0;
}

int build(int L1, int R1, int L2, int R2)
{
    if(L1 > R1) return 0;
    int root = post_order[R2];
    int p = L1;
    while(in_order[p] != root)  ++p;
    int cnt = p - L1;
    lch[root] = build(L1, p-1, L2, L2+cnt-1);
    rch[root] = build(p+1, R1, L2+cnt, R2-1);
    return root;
}

int best, bestsum;

void dfs(int u, int sum)
{
    sum += u;
    if(!lch[u] && !rch[u])
    {
        if(sum < bestsum || (sum == bestsum && u < best))
        {
            best = u;
            bestsum = sum;
        }
    }
    if(lch[u])  dfs(lch[u], sum);
    if(rch[u])  dfs(rch[u], sum);
}

int main()
{
    while(read_list(in_order))
    {
        read_list(post_order);
        build(0, n-1, 0, n-1);
        bestsum = 1111111111;
        dfs(post_order[n-1], 0);
        printf("%d\n", best);
    }
    return 0;
}

UVa 839 Not so Mobile【二叉树的递归遍历】

题目大意：

输入一个树状天平，根据力矩相等原则判断是否平衡。采用递归方式输入，0表示中间结点。

解题思路：

其实可以直接做，就是看怎么写写的既简洁又高效，直接保留书上给的代码了，就不献丑了。。

LRJ’s code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 算法：在“建树”时直接读入并判断，并且无须把树保存下来
#include<iostream>
using namespace std;

// 输入一个子天平，返回子天平是否平衡，参数W修改为子天平的总重量
bool solve(int& W)
{
    int W1, D1, W2, D2;
    bool b1 = true, b2 = true;
    cin >> W1 >> D1 >> W2 >> D2;
    if(!W1)
        b1 = solve(W1);
    if(!W2)
        b2 = solve(W2);
    W = W1 + W2;
    return b1 && b2 && (W1 * D1 == W2 * D2);
}

int main()
{
    int T, W;
    cin >> T;
    while(T--)
    {
        if(solve(W))
            cout << "YES\n";
        else
            cout << "NO\n";
        if(T)
            cout << "\n";
    }
    return 0;
}

UVa 699 The Falling Leaves【二叉树的递归遍历】

题目大意：

给一颗二叉树，每个节点都有一个水平位置，左子结点在它左边一个单位，右子结点在它右边一个单位。按照先序遍历的方式输入，请你从左到右输出每个水平位置的所有结点的权值之和。

解题思路：

按照递归建树的思想，输入的同时直接进行记录，真正的树不必记录下来。

Mycode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX = 222;

int sum[MAX];

void build(int pos)
{
    int v;
    scanf("%d", &v);
    if(v == -1) return ;

    sum[pos] += v;
    build(pos - 1);
    build(pos + 1);
}

bool init()
{
    int v;
    scanf("%d", &v);
    if(v == -1) return false;
    memset(sum, 0, sizeof(sum));

    int pos = MAX >> 1;
    sum[pos] = v;
    build(pos - 1);
    build(pos + 1);
    return true;
}

int main()
{
    for(int cas = 1; init(); ++cas)
    {
        printf("Case %d:\n", cas);
        int p = 0;
        while(sum[p] == 0)  ++p;
        printf("%d", sum[p++]);
        while(sum[p] != 0)  printf(" %d", sum[p++]);
        puts("\n");
    }
    return 0;
}

UVa 297 Quadtrees【四叉树】

题目大意：

给两棵四分树的先序遍历，求二者合并之后（黑色部分合并）黑色像素的个数。p表示中间结点，f表示黑色(full)，e表示白色(empty)。

解题思路：

根据前面二叉树递归建树的思想建四叉树，然后统计就可以了。

然后，这个题有毒吧？我写的为啥过不了啊？？uDebug上的数据AC的代码过不了，我的能过，这都什么啊，找了一上午的问题，愣是没找出来。难受啊。把输入的字符串定义为全局变量直接访问而非通过参数传递访问就AC了。
UPD：经过一下午的对比，发现因为我字符数组定义的位置不同，返回的结果不一样？定义在最上面AC，中间RE，最下面WA，真是神了。。

Mycode(Wrong Answer)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX = 1024 + 10;

//char s[MAX] 放这里 AC
int n, res, pos;
//char s[MAX] 放这里 RE
bool vis[35][35];
char s[MAX];   //放这里 WA
void solve(char* s, int x, int y, int w)
{
    char op = s[pos++];
    if(op == 'p')
    {
        solve(s, x,         y + w / 2, w / 2);
        solve(s, x,         y,         w / 2);
        solve(s, x + w / 2, y,         w / 2);
        solve(s, x + w / 2, y + w / 2, w / 2);
    }
    else if(op == 'f')
    {
        for(int i = x; i < x + w; ++i)
        {
            for(int j = y; j < y + w; ++j)
            {
                if(vis[i][j] == false)
                {
                    vis[i][j] = true;
                    ++res;
                }
            }
        }
    }
}

int main()
{
    scanf("%d",&n);
    while(n--)
    {
        res = 0;
        memset(vis, false, sizeof(vis));

        for(int i = 0; i < 2; ++i)
        {
            pos = 0;
            scanf("%s", s);
            solve(s, 0, 0, 32);
        }

        printf("There are %d black pixels.\n", res);
    }
    return 0;
}

Mycode(Accepted):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX = 1024 + 10;

char s[MAX];
int n, res, pos;
bool vis[35][35];
void solve(int x, int y, int w)
{
    char op = s[pos++];
    if(op == 'p')
    {
        solve(x,         y + w / 2, w / 2);
        solve(x,         y,         w / 2);
        solve(x + w / 2, y,         w / 2);
        solve(x + w / 2, y + w / 2, w / 2);
    }
    else if(op == 'f')
    {
        for(int i = x; i < x + w; ++i)
        {
            for(int j = y; j < y + w; ++j)
            {
                if(vis[i][j] == false)
                {
                    vis[i][j] = true;
                    ++res;
                }
            }
        }
    }
}

int main()
{
    scanf("%d",&n);
    while(n--)
    {
        res = 0;
        memset(vis, false, sizeof(vis));

        for(int i = 0; i < 2; ++i)
        {
            pos = 0;
            scanf("%s", s);
            solve(0, 0, 32);
        }

        printf("There are %d black pixels.\n", res);
    }
    return 0;
}

LRJ’s code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// UVa297 Quadtrees
// Rujia Liu
// 题意：给两棵四分树的先序遍历，求二者合并之后（黑色部分合并）黑色像素的个数。p表示中间结点，f表示黑色（full），e表示白色（empty）
// 算法：先建树，然后统计
#include<cstdio>
#include<cstring>

const int len = 32;
const int maxn = 1024 + 10;
char s[maxn];
int buf[len][len], cnt;

// 把字符串s[p..]导出到以(r,c)为左上角，边长为w的缓冲区中
// 2 1
// 3 4
void draw(const char* s, int& p, int r, int c, int w) {
  char ch = s[p++];
  if(ch == 'p') {
    draw(s, p, r,     c+w/2, w/2); // 1
    draw(s, p, r,     c    , w/2); // 2
    draw(s, p, r+w/2, c    , w/2); // 3
    draw(s, p, r+w/2, c+w/2, w/2); // 4
  } else if(ch == 'f') { // 画黑像素（白像素不画）
    for(int i = r; i < r+w; i++)
      for(int j = c; j < c+w; j++)
       if(buf[i][j] == 0) { buf[i][j] = 1; cnt++; }
  }
}

int main() {
  int T;
  scanf("%d", &T);
  while(T--) {
    memset(buf, 0, sizeof(buf));
    cnt = 0;
    for(int i = 0; i < 2; i++) {
      scanf("%s", s);
      int p = 0;
      draw(s, p, 0, 0, len);
    }
    printf("There are %d black pixels.\n", cnt);
  }
  return 0;
}

UVa 572 Oil Deposits 【DFS】

题目大意：

求给定的图中有多少个@的连通块，每个@与它周围相邻的八个小块是联通的。

解题思路：

DFS入门题。
可以用vis标记访问过的内容，也可以直接将访问过的改为无关的符号(用过一次不再用时可以这样做)。

Mycode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
const int MAX = 105;

int dir[][2] = {0,1,1,0,0,-1,-1,0,1,1,-1,-1,1,-1,-1,1};
int n, m, res;
char mapa[MAX][MAX];
void DFS(int x, int y)
{
    int xx, yy;
    for(int i = 0; i < 8; ++i)
    {
        xx = x + dir[i][0];
        yy = y + dir[i][1];
        if(xx < 1 || yy < 1 || xx > n || yy > m)
            continue;
        if(mapa[xx][yy] == '*')
            continue;
        mapa[xx][yy] = '*';
        DFS(xx, yy);
    }
}
int main()
{
    while(cin >> n >> m && (n || m))
    {
        res = 0;
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                cin >> mapa[i][j];

        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                if(mapa[i][j] == '@')
                    DFS(i, j), ++res;

        cout << res << endl;
    }
    return 0;
}

UVa 1103 Ancient Messages 【DFS】

题目大意：

编程识别6种古代象形文字，每组数据包含一个H行W列的字符矩阵，每个字符矩阵为4个相邻像素点的十六进制(eg: $10011100$ 对应字符就是$9C$)。转化为2进制后，1代表黑点，0代表白点。
输入满足：
1.不会出现上述6种符号外的其他符号。
2.输入至少包含一个符号，且每个黑像素都属于一个符号。
3.图像中的每个黑色像素都是有效象形文字的一部分。
4.象形文字不接触也不包含。
5.如果两个黑像素有公共顶点那么他们一定有公共边。
6.所有符号形状和给出的图形拓扑等价(可以随意拉伸但不能拉断)。

解题思路：

1.16进制转换为2进制，建图。
2.观察发现每个图都有一个与其他图像完全不同的特征——洞的个数，可以把此作为为突破点。
3.第一遍把所有象形文字“抠”出来，具体操作是将所有为0的部分标记一下。
4.第二遍开始给每个象形文字的洞标号。具体操作是找没被标记的部分开始DFS，将第i个图的洞全部标记为i号。
5.第三遍数洞的个数。因为上一步已经将第i号的洞标记为了i，这时就遍历整个图看有几个连通块编号为i即可。
(自己的代码不够精简，很明显的DFS0和DFS1是可以合并的，加个if判断就好了)
【小技巧】因为步骤一中第一个非象形文字的洞的0不好确定，所以我们建图时可以从(1,1)开始存储给出的图，这样(0,0)必定是非象形文字的洞的0了。

Mycode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <bits/stdc++.h>
using namespace std;
const int MAX = 205;

string res;
int vis[MAX][MAX];
int mapa[MAX][MAX];
map<char, string> q;
int h, w, cas, tot, t;
string ans = "WAKJSD";
int dir[][2] = {0,1,1,0,-1,0,0,-1};
void debug()
{
    for(int i = 0; i <= h + 1; ++i)
    {
        for(int j = 0; j <= w * 4 + 1; ++j)
        {
            cout << mapa[i][j];
        }
        cout << endl;
    }
}
void debug2()
{
    for(int i = 0; i <= h + 1; ++i)
    {
        for(int j = 0; j <= w * 4 + 1; ++j)
        {
            cout << vis[i][j];
        }
        cout << endl;
    }
}
void initq()
{
    q['0'] = "0000"; q['1'] = "0001"; q['2'] = "0010"; q['3'] = "0011";
    q['4'] = "0100"; q['5'] = "0101"; q['6'] = "0110"; q['7'] = "0111";
    q['8'] = "1000"; q['9'] = "1001"; q['a'] = "1010"; q['b'] = "1011";
    q['c'] = "1100"; q['d'] = "1101"; q['e'] = "1110"; q['f'] = "1111";
}
void init()
{
    tot = 1;
    res = "";
    memset(vis, 0, sizeof(vis));
    memset(mapa, 0, sizeof(mapa));
}
void Readmap()
{
    char tem;
    string t;
    int tot = 0;
    for(int i = 0; i < h * w; ++i)
    {
        cin >> tem;
        t = q[tem];
        for(int j = 0; j < 4; ++j)
        {
            mapa[tot / (w * 4) + 1][tot % (w * 4) + 1] = t[j] - '0';
            ++tot;
        }
    }
}
void DFS0(int x, int y, int now)
{
    int xx, yy;
    for(int i = 0; i < 4; ++i)
    {
        xx = x + dir[i][0];
        yy = y + dir[i][1];
        if(xx < 0 || yy < 0 || xx > h + 1 || yy > w * 4 + 1)
            continue;
        if(vis[xx][yy])
            continue;
        if(mapa[xx][yy])
            continue;
        vis[xx][yy] = now;
        DFS0(xx, yy, now);
    }
}
void DFS1(int x, int y, int now)
{
    int xx, yy;
    for(int i = 0; i < 4; ++i)
    {
        xx = x + dir[i][0];
        yy = y + dir[i][1];
        if(xx < 1 || yy < 1 || xx > h || yy > w * 4)
            continue;
        if(vis[xx][yy])
            continue;
        if(mapa[xx][yy] == 0)
            vis[xx][yy] = now;
        else
            vis[xx][yy] = 1;
        DFS1(xx, yy, now);
    }
}
void DFS2(int x, int y, int k)
{
    int xx, yy;
    for(int i = 0; i < 4; ++i)
    {
        xx = x + dir[i][0];
        yy = y + dir[i][1];
        if(xx < 1 || yy < 1 || xx > h || yy > w * 4)
            continue;
        if(vis[xx][yy] != k)
            continue;
        vis[xx][yy] = 1;
        DFS2(xx, yy, k);
    }
}
void solve()
{
    DFS0(0, 0, tot);
    //debug2();
    //---above---
    for(int i = 1; i <= h; ++i)
        for(int j = 1; j <= w * 4; ++j)
            if(mapa[i][j] && vis[i][j] == 0)
                DFS1(i, j, ++tot);
    //debug2();
    for(int k = 2; k <= tot; ++k)
    {
        t = 0;
        for(int i = 1; i <= h; ++i)
            for(int j = 1; j <= w * 4; ++j)
                if(vis[i][j] == k)
                {
                    DFS2(i, j, k);
                    ++t;
                }
        //cout << "t = " << t << endl;
        //debug2();
        res += ans[t];
    }
    sort(res.begin(), res.end());
}
int main()
{
    initq();
    while(cin >> h >> w && (h || w))
    {
        init();
        Readmap();
        //debug();
        solve();
        cout << "Case " << ++cas << ": " << res << endl;
    }
    return 0;
}

UVa 816 Abbott’s Revenge 【BFS】

题目大意：

在一个最多包含9 * 9个交叉点的迷宫中，输入起点、离开起点时的朝向和终点，求一条最短路(多解时输出任意一条)。

解题思路：

这个相对于一般的最短路问题而言多了方向，因此无法用最短路的算法求解，这时考虑到使用BFS来解决。
对于路径的打印，可以采用递归的方式打印。如果最短路很长的话递归可能会引起栈的溢出，此时改用循环，用vector记录路径。
PS：一开始接触这个题目时毫无头绪，也是参照了书上的内容一点一点扣了很久才弄明白的。

Mycode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;

//确定好方向后确定走的路线
const int MAX = 11;
const char* dirs = "NESW";
const char* turns = "FLR";
const int dr[] = {-1,0,1,0};
const int dc[] = {0,1,0,-1};

int dis[MAX][MAX][4];               //此位置到起点的距离
bool iscon[MAX][MAX][4][3];         //是否能到达
int r0, c0, r1, c1, r2, c2, dir;
struct node
{
    int r, c, dir;
    node(int r = 0, int c = 0, int dir = 0) : r(r), c(c), dir(dir) {}
}p[MAX][MAX][4];                    //父结点

int dir_id(char c)
{
    return strchr(dirs, c) - dirs;
}

int turn_id(int c)
{
    return strchr(turns, c) - turns;
}

bool read()
{
    char s[99];
    scanf("%s", s);
    if(strcmp(s, "END") == 0)
        return false;
    printf("%s\n", s);
    scanf("%d%d%s%d%d",&r0,&c0,s,&r2,&c2);

    dir = dir_id(s[0]);
    r1 = r0 + dr[dir];
    c1 = c0 + dc[dir];

    memset(iscon, false, sizeof(iscon));
    int r, c;
    while(scanf("%d",&r) && r)
    {
        scanf("%d", &c);
        while(scanf("%s", s) && s[0] != '*')
        {
            for(int i = 1; s[i]; ++i)
                iscon[r][c][dir_id(s[0])][turn_id(s[i])] = true;
        }
    }
    return true;
}

void print_ans(node u)
{
    vector<node> G;
    while(true)
    {
        G.push_back(u);
        if(dis[u.r][u.c][u.dir] == 0)   break;
        u = p[u.r][u.c][u.dir];
    }
    G.push_back(node(r0, c0, dir));

    int cnt = 0;
    for(int i = G.size() - 1; i >= 0; --i)
    {
        if(cnt % 10 == 0)   printf(" ");
        printf(" (%d,%d)",G[i].r,G[i].c);
        if(++cnt % 10 == 0) puts("");
    }
    if(cnt % 10)    puts("");
}

node walk(const node& u, int turn)
{
    int dir = u.dir;
    if(turn == 1)   dir = (dir + 3) % 4;
    if(turn == 2)   dir = (dir + 1) % 4;
    return node(u.r + dr[dir], u.c + dc[dir], dir);
}

bool islegal(int r, int c)
{
    return r >= 1 && c >= 1 && r <= 9 && c <= 9;
}

void solve()
{
    queue<node> Q;
    memset(dis, -1, sizeof(dis));
    dis[r1][c1][dir] = 0;
    node u(r1, c1, dir);
    Q.push(u);
    while(!Q.empty())
    {
        node u = Q.front();
        Q.pop();
        if(u.r == r2 && u.c == c2)
        {
            print_ans(u);
            return ;
        }
        //模拟从此位置出发往三个方向走(FLR)
        for(int i = 0; i < 3; ++i)
        {
            node v = walk(u, i);
            if(iscon[u.r][u.c][u.dir][i] && islegal(v.r, v.c) && dis[v.r][v.c][v.dir] < 0)
            {
                dis[v.r][v.c][v.dir] = dis[u.r][u.c][u.dir] + 1;
                p[v.r][v.c][v.dir] = u;
                Q.push(v);
            }
        }
    }
    puts("  No Solution Possible");
}

int main()
{
    while(read())
        solve();
    return 0;
}

UVa 10305 Ordering Tasks 【拓扑排序】

题目大意：

给出n个任务和m个限制条件，要求任务i必须在任务j之前完成。请给出一个合适的任务完成顺序。

解题思路：

拓扑排序裸题。

Mycode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int MAX = 105;

int n, m;
int in[MAX];
bool vis[MAX];
vector<int> res;
vector<int> G[MAX];
int main()
{
    while(scanf("%d%d",&n,&m) && (n + m))
    {
        for(int i = 0; i <= n; ++i) G[i].clear();
        memset(in, 0, sizeof(in));
        memset(vis, false, sizeof(vis));
        for(int i = 0; i < m; ++i)
        {
            int u, v;
            scanf("%d%d",&u,&v);
            in[v]++;
            G[u].push_back(v);
        }
        bool flag = true;
        res.clear();
        while(flag)
        {
            flag = false;
            for(int i = 1; i <= n; ++i)
            {
                if(vis[i])  continue;
                if(in[i] == 0)
                {
                    res.push_back(i);
                    vis[i] = true;
                    flag = true;
                    for(int j = 0; j < G[i].size(); ++j)
                        in[G[i][j]]--;
                }
            }
            if(!flag)   break;
        }
        if(res.size() != n)
            puts("Impossible");
        else
            for(int i = 0; i < res.size(); ++i)
                printf("%d%c", res[i], i == res.size() - 1 ? '\n' : ' ');
    }
    return 0;
}

UVa 10129 Play on Words 【欧拉回路】【并查集】

题目大意：

给出n个单词，能否可以把他们排成一列，使得每个单词的第一个字母和上一个单词的最后一个字母相同。

解题思路：

将字母看做结点，单词看成有向边，那么当且仅当图中有欧拉回路的时候问题有解。
有向图存在欧拉回路的条件有两个：1. 底图(即忽略方向后得到的无向图)联通 2.度数满足欧拉道路的条件。
这里判断条件1时用的并查集，判断条件二时直接记录的度数。

欧拉回路

  • 无向图中从一个结点出发走出一条道路，每条边恰好经过一次，这样的道路称为欧拉道路。
  • 度：无向图里，度为一个顶点关联边的个数。
  • 如果一个无向图是联通的，且最多有两个度数为奇数的点，那么一定存在欧拉道路。如果有两个奇点，则必须从一个奇点出发到另一个奇点终止，其余情况，则可以从任意点出发，最终一定会回到该点(称为欧拉回路)。

–> 类推出有向图：

  • 最多只能有两个点的入度不等于出度，而且必须是其中一个点的出度恰好比入度大1(起点)，另一个的入度比出度大1(终点)。
  • 前提条件：忽略方向后，图是联通的。

Mycode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

char s[1111];
bool vis[256];
int t, n, tot, f[256], deg[256];

int Find(int x)
{
    return f[x] == x ? x : f[x] = Find(f[x]);
}

void init()
{
    for(int i = 'a'; i <= 'z'; ++i)
        f[i] = i;
    memset(vis, 0, sizeof(vis));
    memset(deg, 0, sizeof(deg));
}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        init();
        tot = 26;
        scanf("%d",&n);
        for(int i = 0; i < n; ++i)
        {
            scanf("%s", s);
            char x = s[0];
            char y = s[strlen(s) - 1];
            ++deg[x], --deg[y];
            vis[x] = vis[y] = true;
            int t1 = Find(x), t2 = Find(y);
            if(t1 != t2)
            {
                f[t2] = t1;
                --tot;
            }
        }
        vector<int> d;
        for(int i = 'a'; i <= 'z'; ++i)
        {
            if(vis[i] == false) --tot;
            else if(deg[i]) d.push_back(deg[i]);
        }

        bool ok = ((tot == 1) && (d.empty() || (d.size() == 2 && d[0] + d[1] == 0 && abs(d[0]) == 1)));
        puts(ok ? "Ordering is possible." : "The door cannot be opened.");
    }
    return 0;
}

UVa 10562 Undraw the Trees 【树的结构】

题目大意：

给出一个多叉树，将其转化为括号表示法。

解题思路：

直接在二维字符数组中递归，无需建树。

MyCode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 222;

int t, n;
char buf[N][N];

void DFS(int r, int c)
{
    printf("%c(", buf[r][c]);
    if(r + 1 < n && buf[r + 1][c] == '|')
    {
        int i = c;
        while(i - 1 >= 0 && buf[r + 2][i - 1] == '-')   --i;
        while(buf[r + 2][i] == '-' && buf[r + 3][i] != '\0')
        {
            if(!isspace(buf[r + 3][i]))
                DFS(r + 3, i);
            ++i;
        }
    }
    printf(")");
}

void solve()
{
    n = 0;
    while(1)
    {
        fgets(buf[n], N, stdin);
        if(buf[n][0] == '#')
            break;
        else
            ++n;
    }
    printf("(");
    if(n)
    {
        int len = strlen(buf[0]);
        for(int i = 0; i < len; ++i)
            if(buf[0][i] != ' ')
            {
                DFS(0, i);
                break;
            }
    }
    puts(")");
}

int main()
{
    scanf("%d", &t);
    getchar();
    while(t--)  solve();
    return 0;
}
Donate comment here
0%