算法入门经典2 第6章习题 题解

【序】

         这章的课后习题，完成了一共10道，后面真是有些做不动了。之后有空再来补一下剩下的几题，这些题真是写炸了。好多题想法不对，只能看题解慢慢啃了，自己弄懂到去写出来也花了很多时间。就把我完成的题目的解题方法和代码记录一下吧。 这里面6-7， 6-10， 6-13还没有AC，这些题都是比较恶心的模拟，要stl功力很深才可以轻松搞定，我的能力是无法搞定的，加油吧，之后一定要A掉！

【正文】

           题目链接：点击打开链接

【6-1】 判断序列的合法性，栈的典型应用。AC代码：

string line;
stack <char> s;
bool isok(char a, char b){
    if(a == '(' && b == ')') return true;
    else if(a == '[' && b == ']') return true;
    else return false;
}
int main()
{
    int T; scanf("%d%*c", &T);
    while(T--){
        while(!s.empty()) s.pop();
        char ch;
        while((ch = getchar()) != '\n'){
            if(ch == '(' || ch == '['){
                s.push(ch);
            }
            else if(ch == ')' || ch == ']'){
                if(s.empty()) s.push(ch);
                else if(ch == ']'){
                    if(s.top() != '['){

                    }
                    else{
                        s.pop();
                    }
                }
                else if(ch == ')'){
                    if(s.top() != '('){

                    }
                    else{
                        s.pop();
                    }
                }
            }
        }
        if(s.empty()){
            printf("Yes\n");
        }
        else{
            printf("No\n");
        }
    }
    return 0;
}

这个题看着好像挺难的，实际上读懂题意之后就是个水题。

题目的意思是给一棵完全二叉树，从根节点开始，碰到０往左，碰到１往右。

深度不大于8．第一行输入是深度。

除了叶子节点，其他处在每一水平线上的节点值都是一样的，并且用x1 ,x2,x3,x4......等来代替，第二行的输入就给出顺序。。

然后第三行的输入是从根节点到叶子节点的次数。

接下去是每一次x1,x2,x3,x4....的值是多少。（虽然每一层是x1,x2等等中的哪一个不是顺序的，但输入是顺序的，x1,x2,x3，所以要把值对上去。）。。因为每一次这些值不同，所以最终落到的位置也不同，就是要求这么多次，每一次所到的节点组成的串，输出。

所以这个题就是二进制的对应关系了，还有我们输出的时候要保存到一起输出。

int a[200], b[200];
int ans[20000];
char ss[1010];

int main()
{
    int n, q, s, ks = 0;
    while(scanf("%d", &n) && n)
    {
        getchar();
        gets(ss);
        for(int i = 1; i <= (1<<n); i++) scanf("%1d", &a[i]);
        scanf("%d", &q);
        for(int j = 1; j <= q; j++){
            for(int i = 1; i <= n; i++){
                scanf("%1d", &b[i]);
            }
            s = 1;
            for(int i = 1; i <= n; i++){
                if(b[i]){
                    s += (1 <<(n - i));
                }
            }
            ans[j] = a[s];
        }
        printf("S-Tree #%d:\n", ++ks);
        for(int i = 1; i <= q; i++) printf("%d", ans[i]);
        printf("\n\n");
    }
    return 0;
}

const int maxv = 110;
char pre[maxv], in[maxv];
void build(int L1, int R1, int L2, int R2, int rt){
    if(L1 > R1) return;
    for(rt = L2; in[rt] != pre[L1]; rt++);
    build(L1 + 1, L1 + rt - L2, L2, rt - 1, 0);
    build(L1 + 1 + rt - L2, R1, rt + 1, R2, 0);
    cout<<in[rt];
}
int main()
{
    while(cin>>pre>>in){
        int n = strlen(pre) - 1;
        build(0, n, 0, n, 0);
        cout<<endl;
    }
    return 0;
}

char s[20],e[20];
int sx,sy,ex,ey;
int vis[9][9];
int dir[8][2]={{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2}};

struct node{
  int x,y,step;
};

int bfs(int sx,int sy)
{
    node cur,pp;
    int dx,dy;
    queue<node>qq;
    vis[sx][sy]=true;
    cur.x=sx,cur.y=sy,cur.step=0;
    if(cur.x==ex&&cur.y==ey)
        return cur.step;
    qq.push(cur);
    while(!qq.empty())
    {
        cur=qq.front();
        qq.pop();
        if(cur.x==ex&&cur.y==ey)
            return cur.step;
        for(int i=0;i<8;i++)
        {
            dx=cur.x+dir[i][0];
            dy=cur.y+dir[i][1];
            while(dx>=1&&dx<=8&&dy>=1&&dy<=8&&!vis[dx][dy])
            {
                pp.x=dx;
                pp.y=dy;
                pp.step=cur.step+1;
                qq.push(pp);
                vis[dx][dy]=true;
            }
        }
    }
}

int main()
{
    while(scanf("%s%s",s,e)!=EOF)
    {
        sx=s[1]-'0';
        sy=s[0]-'a'+1;
        ex=e[1]-'0';
        ey=e[0]-'a'+1;
        memset(vis,false,sizeof(vis));
        printf("To get from %s to %s takes %d knight moves.\n",s,e,bfs(sx,sy));
    }
    return 0;
}

【6-5】基础BFS，在节点中增加一个表示连续穿过障碍的个数，其他和基础BFS相同，求出最短路就可以了，注意必须是连续穿过障碍物个数<=k。

int T, n, m, k, a[25][25], vis[25][25][25];
struct node{int x, y, step, pos;};
int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
int bfs(){
    node now;
    now.x = 1, now.y = 1, now.step = 0, now.pos = 0;
    vis[1][1][0] = 1;
    queue <node> que;
    que.push(now);
    while(!que.empty()){
        now = que.front(); que.pop();
        if(now.x == n && now.y == m) return now.step;
        REP1(i, 0, 4){
            int dx = now.x + dir[i][0], dy = now.y + dir[i][1], pos1 = now.pos;
            if(a[dx][dy] == 1) pos1++;
            else pos1 = 0;
            if(dx >= 1 && dx <= n && dy >= 1 && dy <= m && !vis[dx][dy][pos1] && pos1 <= k){
                que.push(node{dx, dy, now.step + 1, pos1});
                vis[dx][dy][pos1] = 1;
            }
        }
    }
    return -1;
}
int main()
{
    scanf("%d", &T);
    while(T--){
        scanf("%d%d%d",&n,&m,&k);
        REP2(i, 1, n){
            REP2(j, 1, m){
                scanf("%d", &a[i][j]);
            }
        }
        memset(vis, false, sizeof(vis));
        int ans = bfs();
        printf("%d\n", ans);
    }
    return 0;
}

map <LL, int> mp;
char str[1024000];
int cur;
void dfs(int dep){
    if(isdigit(str[cur])){
        LL val = 0;
        while(isdigit(str[cur])){
            val = val * 10 + str[cur++] - '0';
        }
        mp[val<<dep]++;
    }
    else{
        cur++; dfs(dep + 1);
        cur++; dfs(dep + 1);
        cur++;
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%s", str);
        mp.clear();
        cur = 0;
        dfs(0);
        LL sum = 0, maxx = -1;
        for(auto it = mp.begin(); it != mp.end(); it++){
            sum += it->second;
            maxx = max(maxx, 1LL*it->second);
        }
        cout<<sum-maxx<<endl;
    }
    return 0;
}

【6-8】题解参考Blog 点击打开链接

int n;
char g[maxn][maxn];
vector <int> code;
struct node{
    int col, dir;
}Tree[maxn*maxn];

void encode(int r, int c, int w, int dir, int &id){ //起点坐标r, c,宽度 w, 编码后的方向dir, 节点编号
    int ok = 1;
    char ch = g[r][c];
    REP1(i, r, r + w){
        REP1(j, c, c + w){
            if(g[i][j] != ch){
                ok = 0;
                break;
            }
        }
    }
    if(!ok){
        encode(r, c, w / 2, dir * 10 + 1, id);
        encode(r, c + w/ 2, w / 2, dir * 10 + 2, id);
        encode(r + w / 2, c, w / 2, dir * 10 + 3, id);
        encode(r + w / 2, c + w / 2, w / 2, dir * 10 + 4, id);
    }
    else{
        Tree[id].col = (int)(ch - '0');
        int x= dir, k = 1;
        stack <int> s;
        while(x){
            s.push(x % 10);
            x /= 10;
        }
        while(!s.empty()){
            Tree[id].dir += s.top() * k; s.pop();
            k *= 5;
        }
        id++;
    }
}

void draw(int r, int c, int w){ //起点r, c宽度为w画成黑点
    REP1(i, r, r + w){
        REP1(j, c, c + w){
            g[i][j] = '*';
        }
    }
}

void decode(vector <int> s){
    int len = s.size();
    REP1(i, 0, len){
        int x = s[i], k = 1;
        Tree[i].col = 1;
        while(x > 0){ //解码路径，低位对应低层
            Tree[i].dir += (x % 5) * k;
            x /= 5, k *= 10;
        }
    }
    REP1(i, 0, len){
        int dir = Tree[i].dir;
        int r = 0, c = 0, w = n;
        while(dir > 0){
            int x = dir % 10;
            if(x == 1) w /= 2;
            if(x == 2) {c += w / 2; w /= 2;}
            if(x == 3) {r += w / 2; w /= 2;}
            if(x == 4) {r += w / 2; c += w / 2; w /= 2;}
            dir /= 10;
        }
        draw(r, c, w);
    }
    REP1(i, 0, n){
        REP1(j, 0, n){
            if(g[i][j] != '*') g[i][j] = '.';
        }
    }
    REP1(i, 0, n){
        puts(g[i]);
    }
}

int main()
{
    int ks = 0;
    while(scanf("%d", &n) != EOF)
    {
        if(n == 0) break;
        CLR(g, '\0');
        code.clear();
        CLR(Tree, 0);
        if(ks) puts("");
        printf("Image %d\n", ++ks);
        if(n > 0){
            REP1(i, 0, n) scanf("%s", g[i]);
            int id = 1;
            encode(0, 0, n, 0, id);
            vector <int> ans;
            REP1(i, 1, id){
                if(Tree[i].col == 1){
                    ans.push_back(Tree[i].dir);
                }
            }
            sort(ans.begin(), ans.end());
            REP1(i, 0, (int)ans.size()){
                printf("%d", ans[i]);
                if((i + 1) % 12 == 0 || i == (int)ans.size() - 1) printf("\n");
                else printf(" ");
            }
            printf("Total number of black nodes = %d\n", (int)ans.size());
        }
        else{
            n = -n;
            int x;
            while(scanf("%d", &x) && x != -1) code.push_back(x);
            decode(code);
        }
    }
    return 0;
}

char card[54][54][2];
int top[54], sum; //sum记录合并的堆数
int match(char *a, char *b){
    if(a[0] == b[0] || a[1] == b[1]) return 1;
    else return 0;
}
int shift(int now, int s){
    int cnt  = 0, tmp = now;
    while(tmp >= 0 && cnt < s){
        if(top[--tmp] >= 0) cnt++;
    }
    if(tmp >= 0 && match(card[now][top[now]], card[tmp][top[tmp]])){
        top[tmp]++;
        card[tmp][top[tmp]][0] = card[now][top[now]][0];
        card[tmp][top[tmp]][1] = card[now][top[now]][1];
        if(--top[now] < 0) sum++;
        return tmp;
    }
    else{
        return -1;
    }
}
int main()
{
    while(scanf("%s", card[0][0]) && card[0][0][0] != '#'){
        REP1(i, 1, 52) scanf("%s", card[i][0]);
        CLR(top, 0);
        sum = 0;
        for(int now = 1; now < 52;){
            while(top[now] < 0) now++;
            int dis = shift(now, 3);
            if(dis != -1){
                now = dis;
            }
            else{
                dis = shift(now, 1);
                if(dis != -1){
                    now = dis;
                }
                else{
                    now++;
                }
            }
        }
        printf("%d pile", 52 - sum);
        if(51 > sum) printf("s");
        printf(" remaining:");
        REP1(i, 0, 52){
            if(top[i] >= 0){
                printf(" %d", top[i] + 1);
            }
        }
        printf("\n");
    }
    return 0;
}

用栈维护即可。对应BFS序列映射出了每个节点和根节点的距离，遍历dfs序列，对当前节点和栈顶节点比较，如果该节点距离根节点更远，则说明该节点为栈顶节点的孩子节点，则记录后将节点放入栈中。否则弹掉栈顶元素继续比较。需要注意一点，即当元素与栈顶元素的距离值大1的时候要视为相等,因为它们属于兄弟节点。

int d[maxn], n;
vector <int> g[maxn];

int main()
{
    while(scanf("%d", &n) != EOF)
    {
        REP2(i, 1, n){
            int x;
            scanf("%d", &x);
            d[x] = i;
        }
        REP1(i, 0, maxn) g[i].clear();
        stack <int> s;
        int root;
        scanf("%d", &root);
        s.push(root);
        REP1(i, 1, n){
            int x;
            scanf("%d", &x);
            while(1){
                int u = s.top();
                if(u == root || d[u] + 1 < d[x]){
                    g[u].push_back(x);
                    s.push(x);
                    break;
                }
                else{
                    s.pop();
                }
            }
        }
        REP2(i, 1, n){
            printf("%d:", i);
            for(int j = 0; j < g[i].size(); j++){
                printf(" %d", g[i][j]);
            }
            printf("\n");
        }
    }
    return 0;
}

const int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
const int N = 15;
char str[25];
int n, m, sx, sy, u, f, to[7][7], g[15][15];
int vis[15][15][7][7];
vector <pair <int, int> > ans ;

void init(){
    to[1][2] = 4, to[1][3] = 2, to[1][4] = 5, to[1][5] = 3;
    to[2][1] = 3; to[2][3] = 6; to[2][4] = 1; to[2][6] = 4;
    to[3][1] = 5; to[3][2] = 1; to[3][5] = 6; to[3][6] = 2;
    to[4][1] = 2; to[4][2] = 6; to[4][5] = 1; to[4][6] = 5;
    to[5][1] = 4; to[5][3] = 1; to[5][4] = 6; to[5][6] = 3;
    to[6][2] = 3; to[6][3] = 5; to[6][4] = 2; to[6][5] = 4;
}

struct State{
    int x, y, u, f, pre;
    State(){}
    State(int x, int y, int u, int f, int pre) : x(x), y(y), u(u), f(f), pre(pre) {}
}que[10005];

void tra(int &vu, int &vf, int d){
    if(d == 0){
        int tmp = vf; vf = 7 - vu; vu = tmp;
    }
    if(d == 1){
        int tmp = vu; vu = 7 - vf; vf = tmp;
    }
    if(d == 2) vu = 7 - to[vu][vf];
    if(d == 3) vu = to[vu][vf];
}

void print(int u){
    if(u == -1) return ;
    print(que[u].pre);
    ans.push_back(MP(que[u].x, que[u].y));
}

void bfs(){
    ans.clear();
    CLR(vis, false);
    int head = 0, tail = 0;
    que[tail++] = State(sx, sy, u, f, -1);
    vis[sx][sy][u][f] = 1;
    while(head != tail){
        State u = que[head++];
        REP1(i, 0, 4){
            int dx = u.x + dir[i][0];
            int dy = u.y + dir[i][1];
            if(dx <= 0 || dx > n || dy <= 0 || dy > m) continue;
            if(g[dx][dy] != -1 && u.u != g[dx][dy]) continue;
            if(dx == sx && dy == sy){
                print(head - 1);
                ans.push_back(MP(sx, sy));
                int sz = ans.size();
                REP1(i, 0, sz){
                    if(i % 9 == 0) printf("\n  ");
                    printf("(%d,%d)%c", ans[i].first, ans[i].second, i == sz - 1 ? '\n' : ',');
                }
                return ;
            }
            State v = u;
            v.x = dx;
            v.y = dy;
            tra(v.u, v.f, i);
            if(vis[v.x][v.y][v.u][v.f]) continue;
            vis[v.x][v.y][v.u][v.f] = 1;
            v.pre = head - 1;
            que[tail++] = v;
        }
    }
    printf("\n  No Solution Possible\n");
}

int main()
{
    init();
    while(scanf("%s", str) != EOF){
        if(strcmp(str, "END") == 0) break;
        printf("%s", str);
        scanf("%d%d%d%d%d%d", &n, &m, &sx, &sy, &u, &f);
        REP2(i, 1, n){
            REP2(j, 1, m){
                scanf("%d", &g[i][j]);
            }
        }
        bfs();
    }
    return 0;
}

struct edge{
    int v, next;
    edge(){}
    edge(int v, int next) : v(v), next(next) {}
}E[200000];
int p[maxn], T, cnt, du[maxn];
bool vis[maxn];
void init(){
    T = 0;
    memset(p, -1, sizeof(p));
    memset(vis, false, sizeof(vis));
    memset(du, 0, sizeof(du));
}
void ins(int u, int v){
    E[T] = edge(v, p[u]);
    p[u] = T++;
}
void add(int u, int v){
    ins(u, v);
    ins(v, u);
}
void dfs(int u){
    vis[u] = 1;
    if(du[u] % 2 == 1) cnt++;
    for(int i = p[u]; ~i; i = E[i].next){
        int v = E[i].v;
        if(vis[v]) continue;
        dfs(v);
    }
}
int main()
{
    int v, e, t, ks = 0;
    while(scanf("%d%d%d", &v, &e, &t) != EOF)
    {
        if(v == 0) break;
        init();
        REP1(i, 0, e){
            int x, y;
            scanf("%d%d", &x, &y);
            add(x, y);
            add(y, x);
            du[x]++; du[y]++;
        }
        int ans = 0;
        REP2(i, 1, v){
            if(!vis[i] && p[i] != -1){
                cnt = 0;
                dfs(i);
                ans += max(cnt, 2);
            }
        }
        printf("Case %d: %d\n", ++ks, t * (max(ans / 2 - 1, 0) + e));
    }
    return 0;
}