(B. Repetitions Decoding)[https://codeforces.com/problemset/problem/1641/B]

tag:

  • cf2000
  • 构造模拟

题意：

给定序列，通过添加一堆两个相同的相邻数字构造相同子串，求构造过程

题解：

简单来说，这题其实就是找到一个简单的规律去消去相同的数字

我们不妨先把相同的最近两个数字先消去，要想消去这两个数字，就要在其中添加一系列数字

例如：1 2 3 1 2 3

我们要想消去1，那么可以这样构造 1 2 3 1 (2 ( 3 3 ) 2 ) 2 3

此时剩余 3 2 2 3

尽管肉眼检查发现已经可以了，但是我们依然也可以直接按照刚才的操作如法炮制

3 2 3 (2 2) 2

此时剩下的就是2 2 ，构造结束。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 100005;



void mai() {
	int n;
	vector<int>rp;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int tmp = 0;
		cin >> tmp;
		rp.push_back(tmp);
	}
	int vis[3000] = {};
	int len = 0;
	vector<int>ve;
	vector<pair<int, int> >op;
	for (int i = 0; i < rp.size(); ) {
		int tmp = 0;
		for (int j = i + 1; j <rp.size(); j++) {
			if (rp[i] == rp[j]) {
				tmp = j;
			}
		}
		if (tmp == 0) {
			cout << "-1" << "\n";
			return;
		}
		else {
			len += (tmp - i + 1);
			int cnt = 0;
			vector<int>kk;
			ve.push_back((tmp - i) * 2);
			for (int j = i + 1; j < tmp; j++) {

				op.push_back({ len + cnt,rp[j] });
				cnt++;
			}
			len += cnt;
			for (int j = tmp - 1; j >= i + 1; j--) {
				kk.push_back(rp[j]);
				//op.push_back({len+cnt,rp[j]}});
			}
			for (int j = tmp + 1; j < rp.size(); j++)kk.push_back(rp[j]);
			rp = kk;
			//for (auto k : rp)cout << k << " ";
			//cout << rp.size() << "))))))))\n";
		}
	}
	cout << op.size() << "\n";
	for (auto k : op) {
		cout << k.first << " " << k.second << "\n";
	}
	cout << ve.size() << "\n";
	for (auto k : ve) {
		cout << k << " ";
	}
	cout << "\n";

}
int main() {
	int t;
	cin >> t;
	while (t--)mai();
}