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

题意：。