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;
}