闲话
今天中午放的是 cd 写的 映山红
本来想在博客里开骂的
想了想算了 没啥必要
还是说人和人的品味是互相独立的吧
但是常听隔着年代的歌
这情况大概只能是家长的灌输了吧
我不好评价了
模拟赛
翻了 但是完全没翻！
T1
贪心构造。
我们先把每个点和他对应区间的最小值和最大值连边，过程中并查集维护连通性。然后对每个点扫区间，有能加的边就加上。可以反证法证明正确性？
总时间复杂度 \(O(n^2)\)。
code
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<int, int>; using vi = vector<int>; using vp = vector<pii>;
#define rep(i,s,t) for (register int i = (s), i##END = (t) + 1; i < i##END; ++ i)
#define pre(i,s,t) for (register int i = (s), i##END = (t) - 1; i > i##END; -- i)
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define file(fl) freopen(#fl".in", "r", stdin), freopen(#fl".out", "w", stdout)
#define timer cerr << 1. * clock() / CLOCKS_PER_SEC << '\n'
#define eb emplace_back
const int N = 1e6 + 10;
int n; pii a[N]; vp ans;
int dsu[N];
int find(int u) { return u == dsu[u] ? u : dsu[u] = find(dsu[u]); }
void adde(int u, int v) {
if (find(u) == find(v)) return;
if (u > v) swap(u, v);
ans.eb(u, v); dsu[find(u)] = find(v);
}
pii b[N];
inline bool check() {
rep(i,1,n) b[i].first = 1e9 + 7, b[i].second = -1;
for (auto [u, v] : ans) {
b[u].first = min(b[u].first, v);
b[u].second = max(b[u].second, v);
b[v].first = min(b[v].first, u);
b[v].second = max(b[v].second, u);
}
rep(i,1,n) if (b[i].first != a[i].first or b[i].second != a[i].second) return 0;
iota(dsu, dsu + n + 1, 0);
for (auto [u, v] : ans) {
dsu[find(u)] = find(v);
}
rep(i,1,n) if (find(i) != find(1)) return 0;
return ans.size() == n - 1;
}
signed main() {
cin >> n; iota(dsu, dsu + n + 1, 0);
rep(i,1,n) cin >> a[i].first >> a[i].second;
rep(i,1,n) adde(i, a[i].first), adde(i, a[i].second);
rep(i,1,n) {
if (a[i].first < a[i].second) {
rep(j, a[i].first, a[i].second) {
if (a[j].first <= i and i <= a[j].second)
adde(i, j);
}
}
}
if (!check()) cout << "-1" << '\n';
else for (auto [u, v] : ans) cout << u << ' ' << v << '\n';
}
T2
如果没有 key obs. 的话最多是能拿 92pts 吗？不知道有没有没看出来就切了的人啊！
没观察出来的话可以发现可以先把叶子找出来，并维护目前找到的子树区间以及根，然后直接向两边拓展区间、拼合区间。加一点随机化就可以 \(200\) 次操作过第三个包了。
key obs. 是 \(1\) 号节点肯定没有左儿子，所以从 \(1\) 号节点开始，每次向右拓展一个节点。
如果本节点没有右儿子，则这棵子树的范围和根已经确定了，直接连在 \(i + 1\) 上即可。
反之右子树的左端点确定，递归求解即可。
询问次数是 \(2n\) 的。
code
#include <bits/stdc++.h>
#include "interact.h"
using namespace std;
#define rep(i, s, t) for (register int i = (s), i##END = (t) + 1; i < i##END; ++i)
const int N = 100 + 10;
int lim, pre[N], mnv[N], mxv[N];
bool query_(int u, int l, int r) {
if (!u) {
if (l == 0 and r == lim) return true;
return false;
} return query(u, l, r);
}
void report_(int u, int v) {
if (u) {
report(u, v);
mnv[u] = min(mnv[u], mnv[v]);
mxv[u] = max(mxv[u], mxv[v]);
}
}
void solve(int u) {
if (!query_(u, mnv[u], mxv[u])) {
pre[u + 1] = u;
solve(u + 1);
} else {
int p = u;
while (p) {
if (!query_(pre[p], mnv[pre[p]], mxv[p])) {
report_(u + 1, p);
pre[u + 1] = pre[p];
solve(u + 1);
break;
} else {
report_(pre[p], p);
p = pre[p];
}
}
}
}
void guess(int n) {
lim = n;
mnv[0] = 0, mxv[0] = n;
rep(i,1,n) pre[i] = 0, mnv[i] = mxv[i] = i;
pre[1] = 0;
solve(1);
}
T3
咋搞的都有。场上的思路是按 \(2k + 1\) 分组，每 \(2k + 1\) 个定能组成一个最优子结构，剩下的节点按大小分，看是自成一组还是加入前面的一堆节点。但是好像比较难写。
所以写了个乱搞作法。首先承认这样一个结论：最终的节点度数一定只有 \(k\) 和 \(k + 1\)。这样我们就可以枚举度数为 \(k\) 的节点数量 \(x\)，取 \(x\) 的最大值构造。
构造的话首先将前 \(x\) 个节点和后 \(x + 1\) 个节点分离，前 \(x\) 个节点和后 \(x + 1\) 个节点间需要连 \(kx\) 条边，每次取后 \(x + 1\) 个节点中度数最小的即可。
后 \(x + 1\) 个节点自己再连，拿个 set 维护一下重边即可。
取最小可以用堆，总时间复杂度不会证。
code
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<int, int>; using vi = vector<int>; using vp = vector<pii>;
#define rep(i,s,t) for (register int i = (s), i##END = (t) + 1; i < i##END; ++ i)
#define pre(i,s,t) for (register int i = (s), i##END = (t) - 1; i > i##END; -- i)
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define file(fl) freopen(#fl".in", "r", stdin), freopen(#fl".out", "w", stdout)
#define timer cerr << 1. * clock() / CLOCKS_PER_SEC << '\n'
#define eb emplace_back
const int N = 1e6 + 10;
int n, k, cnt;
struct el {
el(int id = 0, int val = 0, bool ck = 0)
: id(id), val(val), ck(ck) {}
int id, val; bool ck;
bool operator < (const el& b) const {
if (val != b.val) return val > b.val;
if (ck and !b.ck) return false;
return id > b.id;
}
};
priority_queue<el> que;
vector<el> vec;
struct hash_ {
template <typename T>
size_t operator() (T p) const {
if (p.first > p.second) swap(p.first, p.second);
return (size_t) p.first * 13331 + (size_t) p.second;
}
}; unordered_set<pii, hash_> st;
signed main() {
cin >> n >> k;
int x = -1;
rep(i,0,n) if (n - i >= k and (k + 1) * (n - i) >= i * k and !(((k + 1) * (n - i) + i * k) & 1)) x = i;
cout << x << endl;
cout << (x * k + (k + 1) * (n - x)) / 2 << '\n';
rep(i,x+1,n) que.emplace(i, 0, 0);
rep(i,1,x) rep(j,1,k) {
auto tmp = que.top(); que.pop();
cout << i << ' ' << tmp.id << '\n';
que.emplace(tmp.id, tmp.val + 1, 0);
}
while (que.top().val < k + 1) {
el t1 = que.top(), t2; que.pop();
vec.clear();
while (1) {
t2 = que.top(); que.pop();
if (st.count({t1.id, t2.id})) vec.eb(t2);
else { st.insert({t1.id, t2.id}); break; }
}
cout << t1.id << ' ' << t2.id << '\n';
for (auto v : vec) que.emplace(v);
que.emplace(t1.id, t1.val + 1, 1), que.emplace(t2.id, t2.val + 1, 1);
}
}
两道构造一道交互 就是这样的题解