Output Specification:
For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.
Sample Input:
00100 8 3 71120 7 88666 00000 4 99999 00100 1 12309 68237 6 71120 33218 3 00000 99999 5 68237 88666 8 -1 12309 2 33218
Sample Output:
71120 7 88666 88666 8 00000 00000 4 99999 99999 5 68237 68237 6 00100 00100 1 12309 12309 2 33218 33218 3 -1
坑
1.要输出5位数，不足补0，所以要用printf("%05d")。-1不能补0，需要特判。
2.块长度为1时，需要特判。
思路
代码
#include<iostream> #include<vector> #include<map> using namespace std; const int N = 100005; struct Node { int v, ne; }; Node node[N]; map<int, Node> st; int main() { int first, n, k; cin >> first >> n >> k; for (int i = 0; i < n; i++) { int add, data, next; cin >> add >> data >> next; st[add] = { data,next }; } vector<int> blockhead; vector<int> blocktail; int cnt = 1; int curp = first; int curtail = first; if (k == 1) { blockhead.push_back(curp); blocktail.push_back(curtail); curtail = st[curp].ne; for (int _ = 1; _ < n; _++) { curp = st[curp].ne; blockhead.push_back(curp); blocktail.push_back(curtail); curtail = st[curp].ne; } } else { for (int _ = 0; _ < n; _++) { curp = st[curp].ne; // cout << curp << endl; cnt++; if (st[curp].ne == -1) { blockhead.push_back(curp); blocktail.push_back(curtail); break; } else if (cnt == k) { cnt = 0; blockhead.push_back(curp); blocktail.push_back(curtail); curtail = st[curp].ne; } } } first = blocktail[blocktail.size() - 1]; for (int i = blockhead.size() - 1; i >= 1; i--) st[blockhead[i]].ne = blocktail[i - 1]; st[blockhead[0]].ne = -1; curp = first; while (st[curp].ne != -1) { printf("%05d %d %05d\n", curp, st[curp].v, st[curp].ne); curp = st[curp].ne; } printf("%05d %d -1", curp, st[curp].v); return 0; }
1166 Summit
A summit (峰会) is a meeting of heads of state or government. Arranging the rest areas for the summit is not a simple job. The ideal arrangement of one area is to invite those heads so that everyone is a direct friend of everyone.
Now given a set of tentative arrangements, your job is to tell the organizers whether or not each area is all set.
Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers N ( ≤ 200 ) N (≤ 200)N(≤200), the number of heads in the summit, and M MM, the number of friendship relations. Then M MM lines follow, each gives a pair of indices of the heads who are friends to each other. The heads are indexed from 1 11 to N NN.
Then there is another positive integer K ( ≤ 100 ) K (≤ 100)K(≤100), and K KK lines of tentative arrangement of rest areas follow, each first gives a positive number L ( ≤ N ) L (≤ N)L(≤N), then followed by a sequence of L distinct indices of the heads. All the numbers in a line are separated by a space.
Output Specification:
For each of the K KK areas, print in a line your advice in the following format:
if in this area everyone is a direct friend of everyone, and no friend is missing (that is, no one else is a direct friend of everyone in this area), print Area X is OK…
if in this area everyone is a direct friend of everyone, yet there are some other heads who may also be invited without breaking the ideal arrangement, print Area X may invite more people, such as H. where H is the smallest index of the head who may be invited.
if in this area the arrangement is not an ideal one, then print Area X needs help. so the host can provide some special service to help the heads get to know each other.
Here X XX is the index of an area, starting from 1 11 to K KK.
Sample Input:
8 10 5 6 7 8 6 4 3 6 4 5 2 3 8 2 2 7 5 3 3 4 6 4 5 4 3 6 3 2 8 7 2 2 3 1 1 2 4 6 3 3 2 1
Sample Output:
Area 1 is OK. Area 2 is OK. Area 3 is OK. Area 4 is OK. Area 5 may invite more people, such as 3. Area 6 needs help.
坑
似乎没有
#include<iostream> #include<vector> #include<set> using namespace std; vector<int> g[205]; int n, m, k; bool check(int i, int j) { for (auto node : g[i]) { if (node == j) return true; } return false; } int main() { cin >> n >> m; while (m--) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } cin >> k; for (int areanum = 1; areanum <= k;areanum++) { int l; vector<int> table; set<int> st; cin >> l; for (int i = 0; i < l;i++) { int t; cin >> t; table.push_back(t); st.insert(t); } bool help = false; for (int i = 0; i < l; i++) { for (int j = i + 1; j < l; j++) if (check(table[i], table[j]) == false) { help = true; break; } if (help) break; } if (help == true) printf("Area %d needs help.\n", areanum); else { bool inviteflag = false; for (int i = 1; i <= n; i++) { bool invite = true; if (st.count(i) == 0) { for (auto node : table) if (check(node, i) == false) { invite = false; break; } if (invite == true) { inviteflag = true; printf("Area %d may invite more people, such as %d.\n", areanum, i); break; } } } if (!inviteflag) printf("Area %d is OK.\n", areanum); } } return 0; }
1167 Cartesian Tree
A Cartesian tree is a binary tree constructed from a sequence of distinct numbers. The tree is heap-ordered, and an inorder traversal returns the original sequence. For example, given the sequence { 8 , 15 , 3 , 4 , 1 , 5 , 12 , 10 , 18 , 6 } \{ 8, 15, 3, 4, 1, 5, 12, 10, 18, 6 \}{8,15,3,4,1,5,12,10,18,6}, the min-heap Cartesian tree is shown by the figure.
Your job is to output the level-order traversal sequence of the min-heap Cartesian tree.
Input Specification:
Each input file contains one test case. Each case starts from giving a positive integer N ( ≤ 30 ) N (≤30)N(≤30), and then N NN distinct numbers in the next line, separated by a space. All the numbers are in the range of int.
Output Specification:
For each test case, print in a line the level-order traversal sequence of the min-heap Cartesian tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the beginning or the end of the line.
Sample Input:
10
8 15 3 4 1 5 12 10 18 6
Sample Output:
1 3 5 8 4 6 15 10 12 18
坑
没有
思路
静态二叉树
代码
#include<iostream> #include<vector> #include<queue> using namespace std; typedef pair<int, int> PII;//值，数组位置 struct Node { PII val; int l, r; }; int idx = 1; Node node[35]; int a[35]; int n; priority_queue<PII, vector<PII>, greater<PII>> pq; void insert(PII piip,int i) { if (piip.second < node[i].val.second) { if (node[i].l == 0) { node[++idx] = { piip,0,0 }; node[i].l = idx; return; } else { insert(piip, node[i].l); return; } } else { if (node[i].r == 0) { node[++idx] = { piip,0,0 }; node[i].r = idx; return; } else { insert(piip, node[i].r); return; } } } void bfs() { queue<int> q; q.push(1); vector<int> buffer; while (!q.empty()) { int p = q.front(); q.pop(); buffer.push_back(node[p].val.first); if (node[p].l) q.push(node[p].l); if (node[p].r) q.push(node[p].r); } for (int i = 0; i < buffer.size() - 1; i++) cout << buffer[i] << " "; cout << buffer[buffer.size() - 1]; } int main() { cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n; i++) pq.push({ a[i],i }); PII r = pq.top(); pq.pop(); node[1].val = r; while (!pq.empty()) { PII piip = pq.top(); pq.pop(); insert(piip,1); } bfs(); }
