Fundamental Datastructure

11988 - Broken Keyboard (a.k.a. Beiju Text)

可以用deque来模拟。

#include <iostream>
#include <string>
#include <string.h>
#include <stdio.h>
#include <queue>
using namespace std;

const int MAX = 100005;

char ch[MAX];

int main() {
    while (scanf("%s", ch) != EOF) {
        deque<string> Q;
        string buffer = "";
        int toward = 1;
        int n = strlen(ch);
        
        for (int i = 0; i < n; i++) {
            if (ch[i] == '[') {
                if (toward > 0)  Q.push_back(buffer);
                else  Q.push_front(buffer);
                toward = -1;
                buffer = "";
            } else if (ch[i] == ']') {
                if (toward > 0)  Q.push_back(buffer);
                else  Q.push_front(buffer);
                toward = 1;
                buffer = "";
            } else {
                buffer += ch[i];
            }
        }

        if (toward > 0)  Q.push_back(buffer);
        else  Q.push_front(buffer);

        for (int i = 0; i < Q.size(); i++) {
            printf("%s", Q[i].c_str());
        }
        printf("
");
    }
}

10410 - Tree Reconstruction

一点点解析。

#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 1005;

int n, bfs[MAXN], dfs[MAXN];
int idx[MAXN], root[MAXN];

int main() {
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; i++)  scanf("%d", &bfs[i]);
        for (int i = 0; i < n; i++)  scanf("%d", &dfs[i]);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (bfs[i] == dfs[j]) {
                    idx[i] = j;
                    break;
                }
            }
        }      
        int p = 1;
        for (int i = 0; i < n; i++) {
            root[i] = bfs[0];
        }
        vector<vector<int> > tree(n + 1);
        while (p < n) {
            vector<int> sons;
            sons.push_back(p);
            int max_idx = idx[p];
            int i;
            for (i = p + 1; i < n; i++) {
                if (root[idx[i]] != root[idx[p]] || idx[i] < max_idx) {
                    break;
                }
                max_idx = idx[i];
                sons.push_back(i);
            }
            tree[root[idx[p]]] = sons;
            p = i;
            for (i = sons.size() - 1; i >= 0; i--) {
                int j = idx[sons[i]];
                int r = root[j];
                while (j < n && root[j] == r) {
                    root[j++] = bfs[sons[i]];
                }
            }
        }
        for (int j = 1; j <= n; j++) {
            printf("%d:", j);
            for (int k = 0; k < tree[j].size(); k++) {
                printf(" %d", bfs[tree[j][k]]);
            }
            printf("
");
        }
    }
}

10895 - Matrix Transpose

行列互换后排序。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct Data {
    int r, c, v;
    bool operator < (const Data& d) const {
        if (r != d.r) {
            return r < d.r;
        } else {
            return c < d.c;
        }
    }
};

int main() {
    int m, n;
    while (scanf("%d%d", &m, &n) != EOF) {
        vector<Data> datas;
        for (int i = 1; i <= m; i++) {
            int r;
            scanf("%d", &r);
            for (int j = 0; j < r; j++) {
                Data d;
                scanf("%d", &d.r);
                d.c = i;
                datas.push_back(d);
            }
            for (int j = 0; j < r; j++) {
                scanf("%d", &datas[datas.size() - r + j].v);
            }
        }
        sort(datas.begin(), datas.end());
        int mm = 1, i = 0;
        printf("%d %d
", n, m);
        while (mm <= n) {
            vector<Data> row;
            while (i < datas.size() && datas[i].r == mm) {
                row.push_back(datas[i]);
                i++;
            }
            mm++;
            printf("%d", (int)row.size());
            for (int j = 0; j < row.size(); j++) {
                printf(" %d", row[j].c);
            }
            printf("
");
            for (int j = 0; j < row.size(); j++) {
                if (j)  printf(" ");
                printf("%d", row[j].v);
            }
            printf("
");
        }
    }
}