Input
3 -1 4 -1output
-2 -7 -4题目大意： 给定出n个数，让你计算(x-a1)(x-a2)(x-a3)……(x-an)展开为多项式后，x^i前的系数(i = 0, 1, ……，n-1)。
思路：由于n <= 10， 可以采用DFS或者状态压缩，这里我用的是状态压缩。
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int>v(n); for (int i = 0; i < n; i++) { cin >> v[i]; v[i] = -v[i]; } int ans[15]; for (int i = 1; i <= n; i++) ans[i] = 0; for (int i = 1; i < (1 << n); i++) { int cnt = 0; int now = 1; for (int k = 0; (1 << k) <= i; k++) { if (i & (1 << k)) { cnt++; now = now * v[k]; } } ans[cnt] += now; } cout << ans[1]; for (int i = 2; i <= n; i++) { printf(" %d", ans[i]); } }Input
4 4 6 0 9 -1 11 10 -25 11 -10 9 2 41 17 12 30output
MinD(11, 11, 12) = 2题目大意： 给出三组数， 要求从分别从三组数中各取一个元素a, b, c，使得|a-b| + |a - c| + |c - b|最小，如果不唯一，则取a，b，c最大；
思路：题目中每个数组的大小为10^4， 如果暴力去写，O(n ^3)的复杂度肯定超时。 优化方法： |a - b| + |a - c| + |c - b|的值，是等于三数中最大的那个减去最小的那个的差乘以2。 如下图， 我们可以知道， |a - b| + |a - c| + |c - b|的值就是b到a的距离，加上b到c的距离再乘以2。故我们可以选一个数组， 枚举其中的元素作为中间值b，再去另外两个数组中寻找合适的小于等于b且最接近b的a，大于等于b且最接近b的c，即为答案。寻找a,c的过程可以使用二分查找，故先对三个数组进行排序，复杂度O(K * nlog n)， K为常数。 PS：一开始没仔细看输出条件，导致后面改的时候变得很繁琐，还加了很多没有用的代码，懒得再改了。
#include <bits/stdc++.h> using namespace std; int find(vector<int>c, int k) { int ans = -1e9; int l = 0, r = c.size() - 1; while (l <= r) { int mid = (l + r) / 2; if (c[mid] > k) r = mid - 1; else if (c[mid] <= k) { if (k - c[mid] < k - ans) ans = c[mid]; l = mid + 1; } } return ans; } // 二分找接近k，小于等于k的值，没找到返回-1e9； int find_(vector<int>c, int k) { int ans = -1e9; int l = 0, r = c.size() - 1; while (l <= r) { int mid = (l + r) / 2; if (c[mid] >= k) { if (c[mid] - k < abs(k - ans)) { ans = c[mid]; } r = mid - 1; } else if (c[mid] < k) { l = mid + 1; } } return ans; } // 二分找最接近k，大于等于k的值，没找到返回-1e9 bool jud = false; vector<int>cmp(vector<int>& x, vector<int>& y) { if (x.size() != 4) return y; if (y.size() != 4) return x; if (x[3] < y[3]) return x; if (y[3] < x[3]) return y; if (x[0] > y[0]) return x; if (y[0] > x[0]) return y; if (x[1] > y[1]) return x; return y; } vector<int> solution(vector<int>a, vector<int>b, vector<int>c) { int mi = 1e9; vector<int>ans; for (int i = a.size() - 1; i >= 0; i--) { int now = a[i]; int x = find(b, a[i]); int y = find_(c, a[i]); if (x != -1e9 && y != -1e9) { now = 2 * (y - x); if (now < mi || (now == mi && a[i] + x + y > ans[0] + ans[1] + ans[2])) { jud = 1; mi = now; ans = { a[i], x, y, mi}; } } x = find(c, a[i]); y = find_(b, a[i]); if (x != -1e9 && y != -1e9) { now = 2 * (y - x); if (now < mi ||(now == mi && a[i] + x + y > ans[0] + ans[1] + ans[2])) { mi = now; jud = 1; ans = { a[i], y, x, mi }; } } } return ans; } int main() { int a, b, c; cin >> a >> b >> c; vector<int>aa(a), bb(b), cc(c); for (int i = 0; i < a; i++) cin >> aa[i]; for (int j = 0; j < b; j++) cin >> bb[j]; for (int i = 0; i < c; i++) cin >> cc[i]; sort(aa.begin(), aa.end()); sort(bb.begin(), bb.end()); sort(cc.begin(), cc.end()); vector<int>x = solution(aa, bb, cc); vector<int>y = solution(bb, aa, cc); if (jud) { swap(y[0], y[1]); } vector<int>ans = cmp(x, y); jud = 0; vector<int>z = solution(cc, bb, aa); if (jud) { swap(z[0], z[2]); } ans = cmp(ans, z); printf("MinD(%d, %d, %d) = %d",ans[0], ans[1], ans[2], ans[3]); }Input
11 7456 3 7457 7458 7459 157 6666 3 5551 5552 7777 100 1234 3 5678 9012 0002 80 8888 0 340 2468 3 0001 0004 2222 110 7777 1 6666 57 3721 1 2333 30 9012 3 1236 1235 1234 10 1235 2 5678 9012 50 2222 4 1236 2468 6661 6662 16 2333 4 3721 6661 6662 6663 44output
4 8888 1 340 0001 15 340 5551 4 157 7456 4 157题目大意： 略
思路：并查集+map+结构体排序
#include <bits/stdc++.h> using namespace std; map<int, int>root; map<int, int>grade; int ff(int x) { if (root.find(x) == root.end()) { root[x] = x; return x; } while (x != root[x]) x = root[x]; return x; } struct Node { int id,cnt, val; }; bool cmp(Node a, Node b) { if (a.val != b.val) return a.val > b.val; if (a.cnt != b.cnt) return a.cnt < b.cnt; return a.id < b.id; } int main() { int n; cin >> n; while (n--) { int a, k, g; cin >> a >> k; int c_a = a; a = ff(a); while (k--) { int t; cin >> t; t = ff(t);a = ff(a); if (a < t) root[t] = a; else root[a] = t; } cin >> g; grade[c_a] = g; } map<int, pair<int, int>>vv; for (auto it : root) { int tt = it.first; int g = 0; if (grade.find(tt) != grade.end()) g = grade[tt]; tt = ff(tt); if (vv.find(tt) == vv.end()) vv[tt].first = 0, vv[tt].second = 0; vv[tt].first++; vv[tt].second += g; } vector<Node>ans; for (auto it : vv) { ans.push_back({ ff(it.first), it.second.first, it.second.second }); } cout << ans.size() << endl; sort(ans.begin(), ans.end(), cmp); for (int i = 0; i < ans.size(); i++) { printf("d %d %d\n", ans[i].id, ans[i].cnt, ans[i].val); } }Input
4 30 12 20 15 10 9 6 8 7output
8 2题目大意： 给出n种商品的价格，n种优惠券以及你所有的钱D。每种优惠券对同一种商品只能用一次，且每次购买一个商品，只能用一张优惠券（不能同时使用多张）。求最多可以买多少个商品（每种商品可以重复购买），同时，剩下的最多的钱是多少。
思路 :对于每种商品，购买他的最低价格序列是确定的，即它的价格减去从高到低排列的代金券的价格。故可以维护一个大小为N的优先队列，代表每种商品的购买最低价格是多少。
先对商品和代金券分别排序（代金券从大到小排序），然后构造优先队列，队列的每个元素由三部分组成，分别如下。队列的优先级由第二部分的值即最低花费价格来确定。
这个商品的价格购买这个商品最低花费的价格用到第几张代金券假设第 i 个商品价格为ai，第 j 张代金券价值为bj。
初始时队列中的每个元素为（ai， ai - b0，0)
维护过程：当我们所剩余的价格大于等于0的时候，拿出队列顶部的元素假设为（ai，ai - bj，j），这是我们当前花费最少的钱能购买到的商品，如果剩余的钱不能购买，直接跳出循环，否则的话弹出顶部元素，更新剩余的钱，计数器cnt++，同时将（ai， ai - b(j + 1)，j+1)加入队列中。
细节
因为不能购买原价商品，即每次买商品必须使用代金券，所以当 j + 1 == n的时候代表代金券已经用完了就不需要再在加入队列了，优先队列默认大根堆，所以改用bj - ai复杂度分析：因为题干保证了商品价格一定是大于代金券的值的，所以每次我们剩余的钱最少会减少1，堆的维护为log(n)，故时间复杂度最坏情况下为O(D log n)，D为我们初始所拥有的钱，最大为10^6，应该不会超时。
#include <bits/stdc++.h> using namespace std; int a[100005], b[100005]; int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (int i = 0; i < n; i++) scanf("%d", &b[i]); sort(a, a + n); sort(b, b + n, greater<int>()); priority_queue < pair<int, pair<int, int>>>q; for (int i = 0; i < n; i++) { q.push(make_pair(b[0] - a[i], make_pair(a[i], 0))); // 优先队列默认大根堆， 所以采用b[0] - a[i]; } int cnt = 0; while (m >= 0 && !q.empty()) { int aa = q.top().second.first, bb = q.top().second.second + 1; int cc = q.top().first; q.pop(); if (m + cc >= 0) { m += cc; cnt++; } else break; if (bb == n) continue; else q.push(make_pair(b[bb] - aa, make_pair(aa, bb))); } printf("%d %d", cnt, m); }最后总结： 好好学英语！
