CF679div.2
A Finding Sasuke
题意：给出长度为 \(n\) 的序列 \(a_i(i=1,2,\cdots,n,0<|a_i|\le100)\)，求 \(b_i(i=1,2,\cdots,n,0<|b_i|\le100)\) 使得 \(\sum_{i=1}^na_ib_i=0\)。
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;#define debug(x) cout << #x << " is " << x << endl#define inc(i, a, b) for (int i = a; i <= b; i)typedef long long ll;const int INF = 0x3f3f3f3f, N = 105;int t, n;int a[N];int main() {scanf("%d", &t);while (t--) {scanf("%d", &n);for (int i = 1; i <= n; i) scanf("%d", &a[i]);for (int i = 1; i <= n; i = 2) printf("%d %d ", -a[i 1], a[i]);puts("");} return 0;}B A New Technique
题意：给出 \(n\times m\) 的矩阵以及 \(n\) 行打乱的结果和 \(m\) 列打乱的结果，输出原矩阵。
根据 m 列的结果存储每个数的行号，通过 n 行的结果找出原矩阵输出。
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;#define debug(x) cout << #x << " is " << x << endl#define inc(i, a, b) for (int i = a; i <= b; i)typedef long long ll;const int INF = 0x3f3f3f3f, N = 505;int t, n, m;int a[N][N], top[N*N], ans[N][N];int main() {scanf("%d", &t);while (t--) {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i) {for (int j = 1; j <= m; j) {scanf("%d", &a[i][j]);}}int x;for (int i = 1; i <= m; i) {for (int j = 1; j <= n; j) {scanf("%d", &x);top[x] = j;}}for (int i = 1; i <= n; i) {for (int j = 1; j <= m; j) {ans[top[a[i][j]]][j] = a[i][j];}}for (int i = 1; i <= n; i) {for (int j = 1; j <= m; j) {printf("%d ", ans[i][j]);}puts("");}} return 0;}C Perform Easily
题意：给出 \(a_1,a_2,\cdots,a_6(1\le a_i\le10^9)\) 和长度为 n 的序列 \(b_1,b_2,\cdots,b_n(1\le b_i\le10^9)\) 且有 \(b_i>a_j\ \forall1\le i\le n\ 1\le j\le6\)，存在区间 \([min,max]\)，对任意 \(b_i\) 存在 \(j\in[1,6],\ k\in[min,max]\) 使得 \(b_i=a_j k\)，求 \(\min(max-min)\)。
找出所有 \(b_i-a_j(val)\) 并存储对应 \(i(id)\)，对所有值根据 \(val\) 排序，只需求包含 \(n\) 种 \(id\) 的最小区间长度，对于每个 \(l\)，求出满足条件的最小 r，用双指针即可求出最小区间长度。
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;#define debug(x) cout << #x << " is " << x << endl#define inc(i, a, b) for (int i = a; i <= b; i)typedef long long ll;const ll INF = 0x3f3f3f3f;const int N = 1e5 5;struct node {ll val, id;bool operator < (const node &b) const {return val < b.val;}node (int val = 0, int id = 0) : val(val), id(id) {}}c[6*N];ll n, tot, cnt, ans = INF;ll a[10], b[N], vis[6*N];int main() {for (int i = 1; i <= 6; i) {scanf("%lld", &a[i]);}scanf("%lld", &n);for (int i = 1; i <= n; i) {scanf("%lld", &b[i]);for (int j = 1; j <= 6; j) c[ tot] = node(b[i] - a[j], i);}sort(c 1, c tot 1);int r = 1;for (int i = 1; i <= tot; i) {while (r < tot && cnt < n) {vis[c[r].id] ;if (vis[c[r].id] == 1) cnt ;r ;}if (cnt == n) ans = min(ans, c[r-1].val - c[i].val);vis[c[i].id]--;if (!vis[c[i].id]) cnt--;}printf("%lld\n", ans); return 0;}D Shurikens
题意：卖 \(n(1\le n\le10^5)\) 价格为 \(1,2,\cdots,n\) 的东西，顾客每次买价格最低的物品，\(2n\) 个事件： 放上物品，- x 价格为 x 的物品被买走，求满足要求的物品序列，没有输出 NO。
\(a_i\) 表示第 i 次买走的物品，\(id[i]\) 表示价格为 i 的物品的序号，\(ed[i]\)表示序号为 i 的物品前有多少空位，从小到大遍历价格，尽量放在可放的最后一个位置，并查集维护。
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;#define debug(x) cout << #x << " is " << x << endl#define inc(i, a, b) for (int i = a; i <= b; i)typedef long long ll;const int INF = 0x3f3f3f3f, N = 1e5 5;int n, cnt, tot;char op[3];int a[N], ans[N], id[N], ed[N];int f[N], g[N];int ff(int x) { return x == f[x] ? x : f[x] = ff(f[x]); }int fg(int x) { return x == g[x] ? x : g[x] = fg(g[x]); }int main() {scanf("%d", &n);for (int i = 1; i <= 2 * n; i) {scanf("%s", op);if (op[0] == ' ') cnt;else if (op[0] == '-') {scanf("%d", &a[ tot]);id[a[tot]] = tot;ed[tot] = cnt;if (tot > cnt) { puts("NO"); exit(0); }}}for (int i = 1; i <= n; i) {f[i] = g[i] = i;}for (int i = 1; i <= n; i) {int x = id[i];int y = ff(ed[x]), z = fg(x - 1);if (y <= ed[z]) { puts("NO"); exit(0); }ans[y] = i;f[y] = y - 1; g[x] = x - 1;}puts("YES");for (int i = 1; i <= n; i) printf("%d ", ans[i]);puts(""); return 0;}E Solo mid Oracle
题意：。