洛谷P5884 [IOI2014]game 游戏 题解
题意：
q779 是一个喜欢做游戏的小男生。当有人问问题时，他更喜欢通过玩游戏的方式作答，而不是直接回答。 q779 碰到了他的朋友 cxy ，跟她讲了台湾的航空网。在台湾有 \(n\) 个城市（编号为 \(0,\cdots,n−1\)），其中有些城市之间有航线。每个航线连接两个城市，并且是双向的。
cxy 问 q779 ，是否任意两个城市之间都可以坐飞机互达（直接或间接）， q779 不想直接回答，而是要通过做游戏的方式来告诉她。 cxy 可以问"城市 \(u\) 和 \(v\) 之间有直接航线吗？"， q779 会立刻直接回答该问题。 cxy 会询问每对城市恰好一次，因此总计会有 \(r = \frac{n (n−1)}{2}\) 个问题。如果由前 \(i\)（\(i<r\)）个问题的答案可以推断出整个航空网是否连通，也就是说，是否任意一对城市之间都可以坐飞机互达（直接或间接）， cxy 就获胜。否则意味着她需要知道全部 \(r\) 个回答，此时 q779 获胜。
为了让游戏更好玩，他们俩同意， q779 可以不要管台湾的真实航空网，而是可以随着游戏的进展而编造航空网，也就是根据 cxy 此前的提问来决定此后如何作答。你的任务是，通过决定 q779 如何回答，来帮助他赢得游戏。
输入格式：
- 第 \(1\) 行：一个正整数 \(n\)，代表城市数量。
- 余下 \(r\) 行：每行包含两个整数 \(u\) 和 \(v\)，表示对城市 \(u\) 和 \(v\) 的提问。
输出格式：
- 共 \(r\) 行，对于每次 cxy 的提问，你必须回答在城市 \(v\) 和 \(u\) 之间是否有直接航线。具体而言，返回值 \(1\) 表示有，\(0\) 表示没有。
数据范围：
\(4 \le n \le 1500\)
题目就是说，让你构造一张图
使得它是连通的，但是只能在最后一个询问才能得知它是连通图
属于比较简单的构造题，因为它给的是完全图
所以我们只要把除了最后一条边以外，所有和最后一个点相连的边都砍掉
最后加上最后一条边就好了
时间复杂度 \(O(n^2)\)
代码：
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(2250015))
int n,u[N],v[N];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n; int l=n * (n-1) >> 1;
for(int i=1; i<=l; i++) cin >> u[i] >> v[i];
for(int i=1; i<l; i++)
(u[i] == v[l] || v[i] == v[l]) ? (cout << "0\n") : (cout << "1\n");
cout << "1\n";
return 0;
}
