CF512E-Fox-And-Ploygon

本来以为是一道奇怪的dp题，，，然而发现它不是求最小值，而是求具体方案。。。

有一种思路是这样的：

将这个被分成许多三角形的多边形映射成一个有根树，其中每个三角形是一个非根、非叶子节点，每条对角线是一条边，根节点和叶子节点都在多边形外。通过旋转该树直到旋转成了目标状态。目标状态可为任何一种构型的树。实际上是先构造出初始状态下的数，然后以同样的根构造出目标状态下的树，然后旋转、计数。请允许我用官方题解中的图。

#include <bits/stdc++.h>
using namespace std;

int n;
vector <int> e[1001];
bool have[1001];

struct node {
	int leftMark, rightMark;
	node* sonLeft, *sonRight;
	void updateMark() {
		leftMark = sonLeft->leftMark;
		rightMark = sonRight->rightMark;
	}
}*start, *want;

struct step {
	int fromA, fromB;
	int toA, toB;
};

node* addNode(int L, int R, int from) {
	node *t = new node();
	t->leftMark = L;
	t->rightMark = R;
	if(L == R+1)
		return t;
	for(int i = 0; i < e[L].size(); i++)
		if(e[L][i] != from)
			have[e[L][i]] = true;
	int M = -1;
	for(int j = 0; j < e[R].size(); j++)
		if(e[R][j] != from)
			if(have[e[R][j]])
				M = e[R][j];
	for(int i = 0; i < e[L].size(); i++)
		have[e[L][i]] = false;
	t->sonLeft = addNode(L, M, R);
	t->sonRight = addNode(M, R, L);
	return t;
}

node* input() {
	for(int i = 1; i <= n; i++)
		e[i].clear();
	for(int i = 1; i <= n-3; i++) {
		int a, b;
		cin >> a >> b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	for(int i = 1; i <= n; i++) {
		int j = i+1;
		if(i == n) j = 1;
		e[i].push_back(j);
		e[j].push_back(i);
	}
	return addNode(n, 1, -1);
}

void print(node *p, string append) {
	cout << append << p->leftMark << " " << p->rightMark << endl;
	if(p->sonLeft != NULL)
		print(p->sonLeft, append + "\t");
	if(p->sonRight != NULL)
		print(p->sonRight, append + "\t");
}

vector <step> record;

void rotateR(node *r) {
	step t;
	node *s = r->sonLeft;
	node *a = s->sonLeft;
	node *b = s->sonRight;
	node *c = r->sonRight;
	t.fromA = s->leftMark;
	t.fromB = s->rightMark;
	r->sonLeft = a;
	r->sonRight = s;
	s->sonLeft = b;
	s->sonRight = c;
	s->updateMark();
	r->updateMark();
	t.toA = s->leftMark;
	t.toB = s->rightMark;
	record.push_back(t);
}

void rotateL(node *r) {
	step t;
	node *s = r->sonRight;
	node *a = r->sonLeft;
	node *b = s->sonLeft;
	node *c = s->sonRight;
	t.fromA = s->leftMark;
	t.fromB = s->rightMark;
	r->sonLeft = s;
	r->sonRight = c;
	s->sonLeft = a;
	s->sonRight = b;
	s->updateMark();
	r->updateMark();
	t.toA = s->leftMark;
	t.toB = s->rightMark;
	record.push_back(t);
}

void rotateRT(node *p, int middle) {
	int myMiddle = p->sonLeft->rightMark;
	if(myMiddle == middle)
		return;
	if(myMiddle < middle) {
		rotateRT(p->sonLeft, middle);
		rotateR(p);
	} else if(myMiddle > middle) {
		rotateRT(p->sonRight, middle);
		rotateL(p);
	}
}

void norm(node *p) {
	if(p->leftMark - p->rightMark <= 2) return;
	int middle = (p->leftMark + p->rightMark) / 2;
	rotateRT(p, middle);
	norm(p->sonLeft);
	norm(p->sonRight);
}

int main() {
	ios :: sync_with_stdio(false);
	memset(have, 0, sizeof(have));
	cin >> n;
	start = input();
	norm(start);
	vector <step> record1 = record;
	record.clear();
	want = input();
	norm(want);
	cout << record.size() + record1.size() << endl;
	for(int i = 0; i < record1.size(); i++)
		cout << record1[i].fromA << " " << record1[i].fromB << endl;
	for(int i = record.size()-1; i >= 0; i--)
		cout << record[i].toA << " " << record[i].toB << endl;
	return 0;
}

好烦啊QAQ

然而还有一种简单而暴力的思路：

我们只需要进行一系列的变换使初始状态中所有的对角线变成以1号节点为端点的对角线并正序存储变换的步骤，然后在进行一系列变换使目标状态中所有的对角线也变成以1号节点为端点的对角线并倒序存储变换的步骤（毕竟这实际上是倒推），记一下总数并输出步骤即可

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef vector<pii> vii;

constexpr int maxn = 1010;

int n;
bool e[maxn][maxn];

pii flip(int a, int b, bool inv) {
  int x = -1, y;
  for (int i = 0; i < n; i++)
    if (e[a][i] && e[b][i])
      if (x == -1)
        x = i;
      else {
        y = i;
        break;
      }
  e[a][b] = e[b][a] = false;
  e[x][y] = e[y][x] = true;
  return inv ? make_pair(x, y) : make_pair(a, b);
}

vii solve(bool inv) {
  memset(e, 0, sizeof(e));
  for (int i = 0; i < n; i++)
    e[i][(i + 1) % n] = e[(i + 1) % n][i] = true;
  for (int i = 0, a, b; i < n - 3; i++) {
    cin >> a >> b;
    a--;
    b--;
    e[a][b] = e[b][a] = true;
  }
  vii res;
  for (int i = 1; i < n;) {
    if (e[0][i]) {
      i++;
      continue;
    }
    int j;
    for (j = i + 1; e[0][j] == 0; j++)
      ;
    res.push_back(flip(i - 1, j, inv));
  }
  return res;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin >> n;
  vii a = solve(false), b = solve(true);
  cout << a.size() + b.size() << endl;
  for (int i = 0; i < (int)a.size(); i++)
    cout << a[i].first + 1 << " " << a[i].second + 1 << endl;
  for (int i = b.size() - 1; i >= 0; i--)
    cout << b[i].first + 1 << " " << b[i].second + 1 << endl;
  return 0;
}

明显简单了许多