A. Stable Arrangement of Rooks
贪心
#include <bits/stdc++.h>
using namespace std;
#define inc(x, l, r) for (int x = l; x <= r; x++)
void solve() {
int n, x;
cin >> n >> x;
if ((n + 1) / 2 < x) {
cout << "-1\n";
} else {
inc(i, 1, n) {
inc(j, 1, n) {
if ((i & 1) && (i + 1) / 2 <= x && i == j)
cout << 'R';
else
cout << '.';
}
cout << '\n';
}
}
}
int main() {
int T;
cin >> T;
while (T--) {
solve();
}
}
分类, 模拟
#include <bits/stdc++.h>
using namespace std;
#define inc(x, l, r) for (int x = l; x <= r; x++)
const int inf = INT_MAX;
void solve() {
int n, l, r, c1, c2;
cin >> n >> l >> r >> c1;
c2 = c1;
int Cost = c1;
cout << Cost << "\n";
inc(i, 2, n) {
int x, y, c;
cin >> x >> y >> c;
int f = 0;
if (x < l) {
c1 = c;
l = x;
f = 1;
} else if (x == l) {
c1 = min(c1, c);
}
if (y > r) {
c2 = c;
r = y;
f = 1;
} else if (y == r) {
c2 = min(c2, c);
}
if (f) {
if (l == x && r == y) {
Cost = c;
} else {
Cost = inf;
}
} else {
if (l == x && r == y) {
Cost = min(Cost, c);
}
}
cout << min(Cost, c1 + c2) << "\n";
}
}
int main() {
int T;
cin >> T;
while (T--) {
solve();
}
}
置换, 环
#include <bits/stdc++.h>
using namespace std;
#define inc(x, l, r) for (int x = l; x <= r; x++)
const int maxn = 1e6 + 5;
int r[maxn];
void solve() {
int n;
cin >> n;
inc(i, 1, n) r[i] = 0;
int x;
inc(i, 1, n) {
if (!r[i]) {
vector<int> v;
while (1) {
cout << "? " << i << "\n";
cout.flush();
cin >> x;
if (x == i)
break;
}
while (1) {
cout << "? " << i << "\n";
cout.flush();
cin >> x;
v.push_back(x);
if (x == i)
break;
}
v.push_back(v[0]);
int p = i;
inc(i, 0, (int)v.size() - 2) {
r[p] = v[i];
p = v[i];
}
}
}
cout << "!";
inc(i, 1, n) cout << " " << r[i];
cout << "\n";
}
int main() {
int T;
cin >> T;
while (T--) {
solve();
}
}
镜像, 思维
#include <bits/stdc++.h>
using namespace std;
#define inc(x, l, r) for (int x = l; x <= r; x++)
#define ll long long
const int maxn = 1e3 + 5;
int a[maxn][maxn];
void solve() {
int n;
cin >> n;
inc(i, 1, 2 * n) inc(j, 1, 2 * n) cin >> a[i][j];
ll res = 0;
inc(i, 1, n) inc(j, 1, n) res += a[i + n][j + n];
cout << res + min({a[n][2 * n], a[n + 1][1], a[n][n + 1], a[n + 1][n],
a[1][2 * n], a[2 * n][1], a[1][n + 1], a[2 * n][n]})
<< "\n";
}
int main() {
int T;
cin >> T;
while (T--) {
solve();
}
}
二分, 前缀和/线段树
#include <bits/stdc++.h>
using namespace std;
#define inc(x, l, r) for (int x = l; x <= r; x++)
#define dec(x, l, r) for (int x = l; x >= r; x--)
#define ll long long
#define pii pair<int, int>
#define fi first
#define se second
const int maxn = 1e6 + 5;
int a[maxn], val[maxn], suf[maxn];
vector<int> b[maxn];
pii st[maxn];
ll pre[maxn], T[maxn];
ll sum(int l, int r) {
if (l > r)
return 0;
return pre[r] - pre[l - 1];
}
void solve() {
int n, m;
cin >> n >> m;
inc(i, 1, n) cin >> a[i];
inc(i, 1, m) {
int k;
cin >> k;
b[i].resize(k);
inc(j, 0, k - 1) cin >> b[i][j];
T[i] = 0;
inc(j, 0, k - 1) T[i] += b[i][j];
val[i] = (T[i] + k - 1) / k;
}
inc(i, 1, m) st[i] = {val[i], 1};
inc(i, 1, n) st[m + i] = {a[i], 2};
sort(st + 1, st + n + m + 1);
suf[n + m + 1] = 0;
int r = 1;
dec(i, n + m, 1) {
if (st[i].se == 2)
suf[i] = suf[i + 1] + 1;
else
suf[i] = suf[i + 1] - 1;
if (suf[i] == -1)
r = min(r, 0);
if (suf[i] < -1)
r = min(r, -1);
}
if (r == -1) {
inc(i, 1, m) for (auto e : b[i]) cout << '0';
cout << "\n";
inc(i, 1, m) b[i].clear();
return;
}
pre[0] = 0;
if (r) {
inc(i, 1, n + m + 1) pre[i] = pre[i - 1] + (int)(suf[i] == 0);
} else {
inc(i, 1, n + m + 1) pre[i] = pre[i - 1] + (int)(suf[i] == -1);
}
inc(i, 1, m) for (auto e : b[i]) {
if (r) {
int rf = (T[i] - e + b[i].size() - 2) / (b[i].size() - 1);
if (rf <= val[i]) {
cout << 1;
continue;
}
int r = lower_bound(st + 1, st + n + m + 1, pii(rf, 0)) - st;
int l = lower_bound(st + 1, st + n + m + 1, pii(val[i], 0)) - st;
if (sum(l + 1, r))
cout << 0;
else
cout << 1;
} else {
int rf = (T[i] - e + b[i].size() - 2) / (b[i].size() - 1);
if (rf >= val[i]) {
cout << 0;
continue;
}
int l = lower_bound(st + 1, st + n + m + 1, pii(rf, 0)) - st;
int r = lower_bound(st + 1, st + n + m + 1, pii(val[i], 0)) - st;
if (sum(l + 1, r) == sum(1, n + m + 1))
cout << 1;
else
cout << 0;
}
}
cout << "\n";
inc(i, 1, m) b[i].clear();
}
int main() {
int T;
cin >> T;
while (T--) {
solve();
}
}