UOJ26 【IOI2014】Game 题解

题目链接：UOJ26 【IOI2014】Game

题意：

健佳是一个喜欢做游戏的小男生。当有人问问题时，他更喜欢通过玩游戏的方式作答，而不是直接回答。健佳碰到了他的朋友梅玉，跟她讲了台湾的航空网。在台湾有 $n$ 个城市（编号为 $0,\ldots,n-1)$ ，其中有些城市之间有航线。每个航线连接两个城市，并且是双向的。

梅玉问健佳，是否任意两个城市之间都可以坐飞机互达（直接或间接），健佳不想直接回答，而是要通过做游戏的方式来告诉她。梅玉可以问”城市 $u$ 和 $v$ 之间有直接航线吗? “，健佳会立刻直接回答该问题。梅玉会询问每对城市恰好一次，因此总计会有 $r=n(n-1) / 2$ 个问题。如果由前 $i(i<r)$ 个问题的答案可以推断出整个航空网是否连通，也就是说，是否任意一对城市之间都可以坐飞机互达（直接或间接），梅玉就获胜。否则意味着她需要知道全部 $r$ 个回答，此时健佳获胜。

为了让游戏更好玩，他们俩同意，健佳可以不要管台湾的真实航空网，而是可以随着游戏的进展而编造航空网，也就是根据梅玉此前的提问来决定此后如何作答。你的任务是，通过决定健佳如何回答，来帮助他赢得游戏。

任务：

请写出一个可以帮助健佳获胜的程序。注意，无论是梅玉还是健佳，都不知道对方的策略。梅玉可以以任意的顺序来询问城市对，而健佳必须在不清楚后面提问的前提下立刻给出回答。你需要实现下面的两个函数：

• initialize(n) —— 我们会先调用你的 initialize 函数。参数 $n$ 是城市数目，满足 $4 \leq n \leq 1500$ 。
• hasEdge(u, v) —— 接着我们会调用 hasEdge 函数$r = n(n - 1)/2$ 次。这些调用代表了梅玉的提问，顺序与她提问的次序相同。你必须回答在城市 $v$ 和 $u$ 之间是否有直接航线。具体而言，返回值 $1$ 表示有，$0$ 表示没有。

这道题好像还蛮简单的，而且还是构造题

什么样的图才会问到最后一次呢？显然是树。

对于点 $n$ 的询问，共有 $n-1$ 个，那么我们在前 $n-2$ 次均回答 $\mathrm{False}$ ，然后在第 $n-1$ 次回答 $\mathrm{True}$ 。

时间复杂度 $\mathcal{O}(1)$ （单次询问）

代码：

#include "game.h"
#include <bits/stdc++.h>

#define N ((int)(1605))

int deg[N];
void initialize(int n) {}
int hasEdge(int u, int v)
{
	if(u > v) std::swap(u, v);
	return ++deg[v] == v;
}

---

参考文献：

[1] https://yhx-12243.github.io/OI-transit/records/uoj26.html