CF512E Fox And Polygon 题解

题意：

狐狸 Ciel 设计了一种叫“多边形”的智力游戏！它是通过把一个 $n$ 边形分成三角形来进行的。

目标是通过一些复杂的规则把一种分法转换成另一种分法。

$n$ 边形的一种“分法”是 $n - 3$ 条不相交的对角线构成的集合。

每一步可以选择一条对角线（但不能是 $n$ 边形的边）然后翻转这条对角线。

对于一条对角线 $AB$ ，假设它的两边分别是 $\triangle ABC$ 和 $\triangle ABD$ 。

“翻转”对角线 $AB$ ，就是删除对角线 $AB$ ，并添加对角线 $CD$ 。

Ciel 证明了对于任何一个起点和终点都有合法的翻转方式

她想让你对于任何一个 $n \le 1000$ 的局面，在 $20000$ 次操作内完成。

输入格式

第一行是一个整数 $n$，表示多边形的边数。

接下来 $n - 3$ 行，每一行有两个正整数 $A_i$ 和 $B_i$ ，表示开始有对角线 $A_iB_i$ 被连接。

接下来 $n - 3$ 行，每一行两个正整数 $C_i$ 和 $D_i$ ，表示目标中对角线 $C_iD_i$ 被连接

输入保证合法。

输出格式

首先输出一个整数 $k$ ，表示需要 $k$ 次翻转。

接下来 $k$ 行，每一行两个整数 $A_i$ 和 $B_i$ ，表示第 $i$ 次翻转对角线 $A_iB_i$ ，顺序任意。

如果有多种操作方法，只需输出其中一种。

虽说给的是个多边形，但是好像大部分都是在考图论。

由于题目没有要求给出最少的移动方式，所以我们尝试搞一个中继状态。

这样只需要算出起始状态到中继状态、终止状态到中继状态的方案，把后者翻转后合并即可。

显然要取最简单的中继状态，即所有的对角线都连向同一个点（不妨认为是 $1$ ）。

那么怎么将任意状态变成这个状态呢？

注意到我们每次有意义的翻转操作都会选择由节点 $1,a,x,b$ 组成的四边形

并且这个四边形中 $(a,b)$ 是唯一存在的对角线，然后翻转对角线 $(a,b)$ ，得到 $(1,x)$ 。

最简单的思路是去寻找这样的 $(a,b)$ ，复杂度是 $\mathcal{O}(n^2)$ 的，虽然可以通过本题，但是~~不够优雅~~。

不妨称与 $1$ 直接相连的点为关键点，这里相连可以通过多边形的边。

考虑以所有初始的关键点为起点 dfs 这张图，目标是把每个点都变成关键点。

每次我们枚举当前点 $u$ 的出边 $(u,v)$ ，注意这里 $u,v$ 如果已经访问过了就返回，

若 $v$ 是关键点，直接 dfs 即可。（刚才假定了 $v$ 没访问过）
若 $v$ 不是关键点，则一定存在至少一条 $u$ 的出边 $(u,b_i)$ 使得 $u,v,b_i$ 构成三角形

注意到 $b_i$ 中一定有一个是关键点，记它为 $b_k$ ，并记和 $v$ 相连的那个为 $b_1$ 。

显然 $1,u,b_{k-1},b_k$ 构成一组 $1,a,x,b$ 型的四边形。

而当我们翻转它以后，$b_{k-1}$ 成为了关键点，于是 $1,u,b_{k-1},b_{k-2}$ 会成为下一个这样的四边形。

以此类推，这样子一路翻下来，最后到 $1,u,b_1,b_2$ 时翻转一下，就把所有的 $b_i$ 都搞成关键点了。

例如下图的情况，$u=5,\,v=4,\,b_1=3,\,b_k=b_2=2$ 。（这里等于 $5$ 即对应图上的 $v_5$ ）

由于 $b_k$ 是关键点且与任意的 $b_i$ 连通，且 $b_{k-1}$ 没转好以前 $b_{k-2}$ 之类的都动不了

所以我们可以仅仅将 $b_i$ 标记为 $u$ 就返回，等再次遍历到它的时候，直接翻转 $(u,b_i)$ 。

这样时间复杂度就是 $\mathcal{O}(n)$ 的，并且操作数显然小于 $2n$ 。

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e5 + 15))
#define pb push_back
#define Fi first
#define Se second

vector<int> vec[N];
vector<pii> ans1, ans2;
int n, flag = 1, vip[N], vis[N];
void dfs(int u)
{
    vis[u] = -1;
    for(auto v : vec[u]) if(~vis[v])
    {
        if(vis[v])
        {
            if(!vip[v]) { 
                flag ? ans1.pb({u, vis[v]}) : ans2.pb({1, v});
            } dfs(v);
        }else vis[v] = u;
    }
}
void solve()
{
    rep(i, 1, n) { vec[i].clear(), vis[i] = vip[i] = 0; }
    vis[1] = -1; vip[1] = 1;
    rep(i, 1, n) { vec[i].pb(i % n + 1), vec[i % n + 1].pb(i); }
    rep(i, 1, n - 3)
    {
        static int x, y; cin >> x >> y;
        vec[x].pb(y); vec[y].pb(x); if(x == 1 || y == 1) vip[x + y - 1] = true;
    }
    for(auto v : vec[1]) dfs(v);
}
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; solve(); flag = 0; solve();
    cout << ans1.size() + ans2.size() << '\n';
    rep(i, 0, ans1.size() - 1) cout << ans1[i].Fi << ' ' << ans1[i].Se << '\n';
    Rep(i, ans2.size() - 1, 0) cout << ans2[i].Fi << ' ' << ans2[i].Se << '\n';
    return 0;
}