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 = ; char ch[MAX]; int main() {
while (scanf("%s", ch) != EOF) {
deque<string> Q;
string buffer = "";
int toward = ;
int n = strlen(ch); for (int i = ; i < n; i++) {
if (ch[i] == '[') {
if (toward > ) Q.push_back(buffer);
else Q.push_front(buffer);
toward = -;
buffer = "";
} else if (ch[i] == ']') {
if (toward > ) Q.push_back(buffer);
else Q.push_front(buffer);
toward = ;
buffer = "";
} else {
buffer += ch[i];
}
} if (toward > ) Q.push_back(buffer);
else Q.push_front(buffer); for (int i = ; i < Q.size(); i++) {
printf("%s", Q[i].c_str());
}
printf("\n");
}
}

10410 - Tree Reconstruction

一点点解析。

#include <cstdio>
#include <vector>
using namespace std; const int MAXN = ; int n, bfs[MAXN], dfs[MAXN];
int idx[MAXN], root[MAXN]; int main() {
while (scanf("%d", &n) != EOF) {
for (int i = ; i < n; i++) scanf("%d", &bfs[i]);
for (int i = ; i < n; i++) scanf("%d", &dfs[i]);
for (int i = ; i < n; i++) {
for (int j = ; j < n; j++) {
if (bfs[i] == dfs[j]) {
idx[i] = j;
break;
}
}
}
int p = ;
for (int i = ; i < n; i++) {
root[i] = bfs[];
}
vector<vector<int> > tree(n + );
while (p < n) {
vector<int> sons;
sons.push_back(p);
int max_idx = idx[p];
int i;
for (i = p + ; 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() - ; i >= ; i--) {
int j = idx[sons[i]];
int r = root[j];
while (j < n && root[j] == r) {
root[j++] = bfs[sons[i]];
}
}
}
for (int j = ; j <= n; j++) {
printf("%d:", j);
for (int k = ; k < tree[j].size(); k++) {
printf(" %d", bfs[tree[j][k]]);
}
printf("\n");
}
}
}

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 = ; i <= m; i++) {
int r;
scanf("%d", &r);
for (int j = ; j < r; j++) {
Data d;
scanf("%d", &d.r);
d.c = i;
datas.push_back(d);
}
for (int j = ; j < r; j++) {
scanf("%d", &datas[datas.size() - r + j].v);
}
}
sort(datas.begin(), datas.end());
int mm = , i = ;
printf("%d %d\n", 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 = ; j < row.size(); j++) {
printf(" %d", row[j].c);
}
printf("\n");
for (int j = ; j < row.size(); j++) {
if (j) printf(" ");
printf("%d", row[j].v);
}
printf("\n");
}
}
}
上一篇:JS数组的基本用法


下一篇:javascript 面向对象技术