闲话:做这场的 B 用时跟 C 差不多
不会直接构造,因此这是一个无脑做法。
考虑对于 \(\forall x \in [1, n], y \in [1, m], (x + 3y, 3x + y)\) 看成一个点,那么选择的 \((x, y)\) 要满足,不存在一行或一列有超过 \(1\) 个点。
这启发我们对于合法的点 \((a, b)\),行和列连边,即 \(a \to b\),那么就是要构造出这个二分图的一个最大匹配。
考察合法的连边,\(a, b\) 应满足什么条件。不难推出:
- \(8 \mid (3a - b)\);
- \(\max(3a - 8m, \frac{a + 8}{3}) \le b \le \min(3a - 8, \frac{8n + a}{3})\)。
所以如果知道了 \(a\),那么 \(a\) 连出去的 \(b\) 模 \(8\) 都相等,并且在所有模 \(8\) 与它相等的数中是一段区间。
因为 \(a\) 有 \(O(n + m)\) 个,所以直接枚举 \(a\),贪心取出最小的满足要求的 \(b\),即可构造。实现时可以开 \(8\) 个 set
。
时间复杂度 \(O((n + m) \log (n + m))\)。
code
// Problem: C - One Three Nine
// Contest: AtCoder - AtCoder Regular Contest 139
// URL: https://atcoder.jp/contests/arc139/tasks/arc139_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 1000100;
ll n, m;
set<ll> S[8];
void solve() {
scanf("%lld%lld", &n, &m);
for (ll y = 4; y <= n * 3 + m; ++y) {
S[y % 8].insert(y);
}
for (int i = 0; i < 8; ++i) {
S[i].insert(-1e9);
S[i].insert(1e9);
}
vector<pii> vc;
for (ll a = 4; a <= n + m * 3; ++a) {
ll l = max(3 * a - m * 8, (a + 10) / 3), r = min(3 * a - 8, (8 * n + a) / 3);
if (l > r) {
continue;
}
ll b = *S[3 * a % 8].lower_bound(l);
if (b > r) {
continue;
}
// printf("%lld %lld\n", a, b);
ll x = (3 * b - a) / 8, y = (3 * a - b) / 8;
vc.pb(x, y);
S[3 * a % 8].erase(b);
}
printf("%d\n", (int)vc.size());
for (pii p : vc) {
printf("%lld %lld\n", p.fst, p.scd);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- AtCoder Regular Contest Three Nineatcoder regular contest three atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest degree atcoder regular contest 167 atcoder regular contest sliding atcoder regular contest 164 atcoder regular contest builder disconnected atcoder regular contest