A - Minimum Spanning Trees
咕
B - Line Graphs
咕
C - Valentine's Day
咕
D - Play Games with Rounddog
咕
E - Welcome Party
先将所有同学按照 x 升序排序,枚举 x_i 为当前选唱歌的同学的 x 的最大值,则同学 i+1\dots n 必须选脱口秀,此外前 i-1 个同学可以任意选择。设 y_{\max}=\max_{k=i+1}^n y_i,若 y_{\max}\ge x_i,则前 i-1 个同学都选唱歌一定最优;若 y_{\max}\lt x_i,则在 y_1\dots y_{i-1} 中找分别大于等于和小于 x_i 且最接近 x_i 的两个值 \mathrm{mx},\mathrm{mn},答案即为 |\max(y_{\max},\mathrm{mx})-x_i| 和 |\max(y_{\max},\mathrm{mn})-x_i| 中的最小值。枚举时用set维护,总复杂度 O(n\log n)。
F - Dense Subgraph
咕
G - Closest Pair of Segments
咕
H - Coins
咕
I - Block Breaker
签到题,简单模拟即可。
J - Domino Covering
咕
K - Make Rounddog Happy
咕
Code
A - Minimum Spanning Trees
B - Line Graphs
C - Valentine's Day
D - Play Games with Rounddog
E - Welcome Party
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <set>
#define MAX_N 100005
#define INF 0x3f3f3f3f3f3f3f3fLL
#define fi first
#define se second
#define pii pair<int, int>
#define int long long
using namespace std;
int T, n;
pii p[MAX_N];
int getl(multiset<int> &st, int x) {
if (!st.size()) {
return -1;
}
auto it = st.upper_bound(x);
if (it == st.begin()) {
return -1;
}
return *(--it);
}
int getr(multiset<int> &st, int x) {
if (!st.size()) {
return -1;
}
auto it = st.lower_bound(x);
if (it == st.end()) {
return -1;
}
return *it;
}
signed main() {
scanf("%lld", &T);
while (T--) {
scanf("%lld", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld%lld", &p[i].fi, &p[i].se);
}
sort(p + 1, p + 1 + n);
multiset<int> st1, st2;
for (int i = 1; i <= n; i++) {
st2.insert(p[i].se);
}
int ans = INF;
for (int i = 1; i <= n; i++) {
st2.erase(st2.find(p[i].se));
int mx = -INF;
if (st2.size()) {
mx = *(--st2.end());
}
ans = min(ans, abs(mx - p[i].fi));
if (mx < p[i].fi) {
int l = getl(st1, p[i].fi);
int r = getr(st1, p[i].fi);
if (l != -1) {
ans = min(ans, abs(max(mx, l) - p[i].fi));
}
if (r != -1) {
ans = min(ans, abs(max(mx, r) - p[i].fi));
}
}
st1.insert(p[i].se);
}
printf("%lld\n", ans);
}
}
F - Dense Subgraph
G - Closest Pair of Segments
H - Coins
I - Block Breaker
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 2005
using namespace std;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
int T, n, m, q, ans;
bool vis[MAX_N][MAX_N];
bool ok(int x, int y) {
return 1 <= x && x <= n && 1 <= y && y <= m;
}
bool uns(int x, int y) {
return (vis[x - 1][y] || vis[x + 1][y]) && (vis[x][y - 1] || vis[x][y + 1]);
}
void dfs(int x, int y) {
ans++, vis[x][y] = true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (!vis[nx][ny] && ok(nx, ny) && uns(nx, ny)) {
dfs(nx, ny);
}
}
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d%d", &n, &m, &q);
for (int i = 0; i <= n + 1; i++) {
for (int j = 0; j <= m + 1; j++) {
vis[i][j] = false;
}
}
int x, y;
while (q--) {
scanf("%d%d", &x, &y);
ans = 0;
if (!vis[x][y]) {
ans++, vis[x][y] = true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (!vis[nx][ny] && ok(nx, ny) && uns(nx, ny)) {
dfs(nx, ny);
}
}
}
printf("%d\n", ans);
}
}
}
J - Domino Covering
K - Make Rounddog Happy