5.线性表操作（list)
题目描述
线性表最基本、最简单、也是最常用的一种数据结构。一个线性表是n个具有相同特性的数据元素的有限序列。用list容器存储m个线性表（m<10)，并实现线性表的以下操作。
insert i loc e：在第i个表的第loc位置插入元素e。表位置从1开始，有效插入位置1 ~ 表长+1。
delete i loc : 删除第i表的第loc个元素。
merge i j：使用sort方法对第i，j个表升序排序，再使用merge方法将第j个表合并到第i个表。
unique i : 对第i个表降序排序，使用unique方法删除重复元素。
display i: 输出第i个表元素个数及各元素。
所有操作的表序号i，j输入均合法。位置lco, 元素e均为整数，注意判断插入和删除的位置loc。
输入
第一行：表个数m(>0)
第二行到第m+1行，每行一个表的数据，格式为：数据个数n, 后跟n个整数。
第m+2行：操作次数t，后跟t行，每行一个操作，见题目描述。
输出
对t个操作，分别输出一行，输出操作后的表。具体输出格式见样例。
样例输入
3
10 43 54 23 12 76 -4 53 50 34 10
3 3 243 12
6 3 12 32 42 53 50
7
insert 1 1 15
delete 2 3
merge 2 3
unique 2
display 3
delete 1 1
insert 1 12 200
样例输出
11 15 43 54 23 12 76 -4 53 50 34 10
2 3 243
8 3 3 12 32 42 50 53 243
7 243 53 50 42 32 12 3
0
10 43 54 23 12 76 -4 53 50 34 10
10 43 54 23 12 76 -4 53 50 34 10
题解
#include<bits/stdc++.h> using namespace std; int main() { int n, m, num; cin >> m; list<list<int> > l(m); for (auto &i : l) { cin >> n; for (int j = 0; j < n; j++) { cin >> num; i.push_back(num); } } int q; cin >> q; for (int i = 0; i < q; i++) { string op; int pos1, pos2, num; cin >> op >> pos1; pos1--; if (op == "insert") { cin >> pos2 >> num; pos2--; auto i = l.begin(); advance(i, pos1); if (0 <= pos2 && pos2 <= i->size()) { auto j = i->begin(); advance(j, pos2); i->insert(j, num); } } if (op == "delete") { cin >> pos2; pos2--; auto i = l.begin(); advance(i, pos1); if (0 <= pos2 && pos2 < i->size()) { auto j = i->begin(); advance(j, pos2); i->erase(j); } } if (op == "merge") { cin >> pos2; pos2--; auto i = l.begin(), j = l.begin(); advance(i, pos1); advance(j, pos2); i->sort(); j->sort(); i->merge(*j); } if (op == "unique") { auto i = l.begin(); advance(i, pos1); i->sort(greater<int>()); i->unique(); } auto I = l.begin(); advance(I, pos1); cout << I->size(); for (auto j = I->begin(); j != I->end(); j++) cout << " " << *j; cout << endl; } }
6.多项式运算（list)
题目描述
一元多项式按照升幂表示为：
Pn(x) = p0+ p1x + p2x2+ … +pnxn。(n>=0)
用list容器存储一元多项式的系数和指数。输入两个一元多项式，求多项式加、减、乘。
输入
测试次数
每组测试数据两行：
第一行，第一个多项式：项数n 系数1 指数1 系数2 指数2 … 系数n 指数n(按升幂给出）
第二行，第二个多项式：项数n 系数1 指数1 系数2 指数2 …系数n 指数n(按升幂给出）
假设系数为整型。
输出
每组测试数据输出三行，分别是两个多项式的加、减、乘。具体输出格式见样例（即通常多项式表示，注意1，-1的情况。）
样例输入
2
3 -9 0 4 1 -3 5
1 -7 0
2 1 0 -1 3
3 1 0 1 1 -1 2
样例输出
-16+4x-3x^5
-2+4x-3x^5
63-28x+21x^5
2+x-x^2-x^3
-x+x^2-x^3
1+x-x^2-x^3-x^4+x^5
题解
#include<bits/stdc++.h> #define P pair<int,int> #define scd second #define fst first using namespace std; vector<int> add, mul, sub; P nowop; void Add(P cur) { add[cur.scd] += cur.fst; } void Sub_1(P cur) { sub[cur.scd] += cur.fst; } void Sub_2(P cur) { sub[cur.scd] -= cur.fst; } void Mul(P cur) { P nowans; nowans.scd = cur.scd + nowop.scd; nowans.fst = cur.fst * nowop.fst; mul[nowans.scd] += nowans.fst; } int main() { int t, n1, n2; cin >> t; while (t--) { int value, index, n3; cin >> n1; n3 = max(n1, n2); list<P > l1, l2; add.clear(); mul.clear(); sub.clear(); for (int i = 0; i < 100; i++) { add.push_back(0); sub.push_back(0); mul.push_back(0); } for (int i = 0; i < n1; i++) { cin >> value >> index; l1.push_back(P(value, index)); } cin >> n2; for (int i = 0; i < n2; i++) { cin >> value >> index; l2.push_back(P(value, index)); } for_each(l1.begin(), l1.end(), Add); for_each(l2.begin(), l2.end(), Add); for_each(l1.begin(), l1.end(), Sub_1); for_each(l2.begin(), l2.end(), Sub_2); for (auto i = l1.begin(); i != l1.end(); i++) { nowop = *i; for_each(l2.begin(), l2.end(), Mul); } ///print ans// int flag = 0; for (int i = 0; i < add.size(); i++) { if (add[i] == 0) continue; if (add[i] != 0 && i == 0) { cout << add[0]; flag = 1; continue; } if (add[i] == -1) cout << "-"; else if (add[i] > 1) { if (flag) cout << "+"; cout << add[i]; } else if (add[i] == 1) { if (flag) cout << "+"; } else if (add[i] != 1) cout << add[i]; if (i >= 1)cout << "x"; if (i > 1) cout << "^" << i; flag = 1; } if (flag == 0) cout << 0; cout << endl; flag = 0; for (int i = 0; i < sub.size(); i++) { if (sub[i] == 0) continue; if (sub[i] != 0 && i == 0) { cout << sub[0]; flag = 1; continue; } if (sub[i] == -1) cout << "-"; else if (sub[i] > 1) { if (flag) cout << "+"; cout << sub[i]; } else if (sub[i] == 1) { if (flag) cout << "+"; } else if (sub[i] != 1) cout << sub[i]; if (i >= 1)cout << "x"; if (i > 1) cout << "^" << i; flag = 1; } if (flag == 0) cout << 0; cout << endl; flag = 0; for (int i = 0; i < mul.size(); i++) { if (mul[i] == 0) continue; if (mul[i] != 0 && i == 0) { cout << mul[0]; flag = 1; continue; } if (mul[i] == -1) cout << "-"; else if (mul[i] > 1) { if (flag) cout << "+"; cout << mul[i]; } else if (mul[i] == 1) { if (flag) cout << "+"; } else if (mul[i] != 1) cout << mul[i]; if (i >= 1)cout << "x"; if (i > 1) cout << "^" << i; flag = 1; } if (flag == 0) cout << 0; cout << endl; } }
7.约瑟夫环(list)
题目描述
N个人围成一个圆圈，每个人都有唯一的一个编号，编号从1到N，从编号为1的人开始报数，依次报到K，报数为K的人出列，他的下一个又从1开始报数，直到所有的人都出列，求这个出列的序列。
（必须用list）
输入
测试次数t
每次输入n和k
输出
出队序列
样例输入
2
5 3
10 4
样例输出
3 1 5 2 4
4 8 2 7 3 10 9 1 6 5
题解
#include<bits/stdc++.h> #define P pair<int,int> using namespace std; int main() { int t, n, k; cin >> t; while (t--) { cin >> n >> k; list<int> table; vector<int> ans; for (int i = 1; i <= n; i++) { table.push_back(i); } auto I = table.begin(); while (table.size()) { for (int i = 0; i < k - 1; i++) { I++; if (I == table.end()) I++; } auto died = I; I++; if (I == table.end()) I++; ans.push_back(*died); table.erase(died); } for (int i = 0; i < ans.size(); i++) { cout << ans[i] << " \n"[i == ans.size() - 1]; } } }
