T1 构树
直接 \(O(n^2)\) 暴力枚举连边即可。
code
#include <cstdio>
#include <vector>
#include <set>
#include <utility>
using namespace std;
const int max1 = 1000;
int n, Min[max1 + 5], Max[max1 + 5];
vector <int> part[max1 + 5];
int color[max1 + 5];
set < pair <int, int> > edge;
int main ()
{
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
scanf("%d", &n);
for ( int i = 1; i <= n; i ++ )
scanf("%d%d", &Min[i], &Max[i]);
bool illegal = false;
for ( int i = 1; i <= n; i ++ )
{
int v = Min[i];
if ( i < Min[v] || i > Max[v] )
{ illegal = true; break; }
v = Max[i];
if ( i < Min[v] || i > Max[v] )
{ illegal = true; break; }
}
if ( illegal )
{ printf("-1\n"); return 0; }
for ( int i = 1; i <= n; i ++ )
part[i].push_back(i), color[i] = i;
for ( int i = 1; i <= n; i ++ )
{
int u = i, v = Min[i];
if ( u > v )
swap(u, v);
if ( u == v )
{ illegal = true; break; }
if ( edge.find(make_pair(u, v)) == edge.end() )
{
if ( color[u] == color[v] )
{ illegal = true; break; }
edge.insert(make_pair(u, v));
int id = color[v];
for ( auto p : part[id] )
{
color[p] = color[u];
part[color[u]].push_back(p);
}
part[id].clear();
}
u = i, v = Max[i];
if ( u > v )
swap(u, v);
if ( u == v )
{ illegal = true; break; }
if ( edge.find(make_pair(u, v)) == edge.end() )
{
if ( color[u] == color[v] )
{ illegal = true; break; }
edge.insert(make_pair(u, v));
int id = color[v];
for ( auto p : part[id] )
{
color[p] = color[u];
part[color[u]].push_back(p);
}
part[id].clear();
}
}
if ( illegal )
{ printf("-1\n"); return 0; }
for ( int i = 1; i <= n; i ++ )
{
for ( int j = i + 1; j <= n; j ++ )
{
if ( color[i] == color[j] )
continue;
if ( i >= Min[j] && i <= Max[j] && j >= Min[i] && j <= Max[i] )
{
edge.insert(make_pair(i, j));
int id = color[j];
for ( auto p : part[id] )
{
color[p] = color[i];
part[color[i]].push_back(p);
}
part[id].clear();
}
}
}
if ( (int) edge.size() != n - 1 )
printf("-1\n");
else
for ( auto v : edge )
printf("%d %d\n", v.first, v.second);
return 0;
}
T2 交互
考虑按照中序遍历的顺序求解树的结构，方便起见我们将整棵平衡树定义为 \(0\) 节点的右儿子，记录 \(pre_u\) 表示 \(u\) 节点所在左链的顶部的父亲，按照顺序依次枚举每个节点 \(u\) ，考虑 \(u+1\) 相对于 \(u\) 的位置，如果 \(u+1\) 位于 \(u\) 的子树内，显然 \(u+1\) 为 \(u\) 的右子树内最靠左的点，那么 \(pre_{u+1}=u\) ，继续枚举 \(u\) 求解，如果 \(u+1\) 不在 \(u\) 的子树内，容易发现 \(u\) 和 \(u+1\) 一定存在祖先关系，设 \(p=u\) ，判断 \(u+1\) 是否位于 \(pre_p\) 的子树内，如果位于 \(pre_p\) 的子树内，显然 \(u+1\) 是 \(p\) 的父亲， \(pre_{u+1}=pre_p\) ，否则 \(pre_p\) 是 \(p\) 的父亲，令 \(pre_p\to p\)， 继续判断。
code
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include "interact.h"
using namespace std;
const int max1 = 100;
int lim, pre[max1 + 5], Min[max1 + 5], Max[max1 + 5];
bool Query ( int u, int l, int r )
{
if ( !u )
{
if ( l == 0 && r == lim )
return true;
return false;
}
return query(u, l, r);
}
void Report ( int u, int v )
{
if ( u )
{
report(u, v);
Min[u] = min(Min[u], Min[v]);
Max[u] = max(Max[u], Max[v]);
}
return;
}
void Solve ( int L )
{
if ( !Query(L, Min[L], Max[L]) )
{
pre[L + 1] = L;
Solve(L + 1);
}
else
{
int p = L;
while ( p )
{
if ( !Query(pre[p], Min[pre[p]], Max[p]) )
{
Report(L + 1, p);
pre[L + 1] = pre[p];
Solve(L + 1);
break;
}
else
{
Report(pre[p], p);
p = pre[p];
}
}
}
return;
}
void guess ( int n )
{
lim = n;
Min[0] = 0, Max[0] = n;
for ( int i = 1; i <= n; i ++ )
pre[i] = 0, Min[i] = Max[i] = i;
pre[1] = 0;
Solve(1);
return;
}
T3 构图
容易发现每个点的度数只有 \(k\) 和 \(k+1\) 两种可能，因此枚举度数为 \(k\) 的点的个数，找到边数最小的方案，贪心的连边即可。
code
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int max1 = 1000;
const int inf = 0x3f3f3f3f;
int n, k;
struct Point
{
int x, d;
Point () {}
Point ( int __x, int __d )
{ x = __x, d = __d; }
bool operator < ( const Point &A ) const
{ return d < A.d; }
};
queue <Point> que;
void Solve ( int cnt )
{
for ( int i = cnt + 1; i <= n; i ++ )
que.push(Point(i, k + 1));
for ( int i = 1; i <= cnt; i ++ )
{
for ( int j = 1; j <= k; j ++ )
{
Point now = que.front();
que.pop();
printf("%d %d\n", i, now.x);
--now.d;
que.push(now);
}
}
while ( que.front().d > 0 )
{
Point now = que.front();
que.pop();
while ( now.d > 0 )
{
--now.d;
Point tmp = que.front();
que.pop();
printf("%d %d\n", now.x, tmp.x);
--tmp.d;
que.push(tmp);
}
}
return;
}
int main ()
{
freopen("graph.in", "r", stdin);
freopen("graph.out", "w", stdout);
int Min = inf, cnt = 0;
scanf("%d%d", &n, &k);
for ( int i = 1; i + k <= n; i ++ )
{
int up = i * k + ( max(0, ( n - i ) * ( k + 1 ) - i * k) + 1 >> 1 );
if ( up < Min )
Min = up, cnt = i;
}
printf("%d\n", Min);
Solve(cnt);
return 0;
}