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

题意:。

来源:https://www.icode9.com/content-4-748101.html

(0)

相关推荐