Codeforces Round #773 (Div. 2) D

113 阅读 0 评论 75 点赞

我是靠谱客的博主可爱巨人，这篇文章主要介绍Codeforces Round #773 (Div. 2) D，现在分享给大家，希望可以做个参考。

题目大意：

长度为n的序列a，通过输出一定的操作序列使得最终的a可以由重复序列组成，再输出每个重复序列的长度。如果不存在这样的操作序列，则输出-1.
- 重复序列定义：长度为2k的序列，且满足 $x_i=x_{i+k}$
- 操作方式：选择一个位置插入一对相同的数（自定义）
数据范围：

$1 \leq t \leq 30000$

$n \leq 500$

$a_ile1e9$

保证 $n^2 le 250 000$
例子：
$\ 在位置1插入一对3:1,3,3,3,1,2,2,3 \ 在位置5插入一对3:1,3,3,3,1,3,3,2,2,3 \ 在位置5插入一对3:1,3,3,3,1,3,3,3,3,2,2,3 \ 在位置10插入一对3:1,3,3,3,1,3,3,3,3,2,3,3,2,3 \ ([1,3,3,3]+[1,3,3,3])+([3,2,3]+[3,2,3])$

解题思路：

首先每个数都必须出现偶数次才有可能找得到答案

假设x出现了奇数次
- 若插入过程始终没x，则有一个x始终不能匹配
- 若插入过程有x，因为每次插入都是偶数个x，所以仍然会有一个x不能匹配
通过插入的方式可以将某一段变为"倒序"：

例如：
$\ ...,x,y,z,x,x,... \ ...,x,y,z,x,y,y,x,... \ ...,x,y,z,x,y,z,z,y,x,... \ 最终序列变成了：[...]+[(x,y,z)+(x,y,z)])+[z,y,x],... \ 因为[(x,y,z)+(x,y,z)])可以不用理了，所以相当于把[x,y,z]倒序了$
通过以上性质，从头到尾，每次找最近的一对数字的位置 $i$ ， $j$ （ $a_i=a_j$ ），执行以下操作：
$a_i,a_{i+1},...,a_{j-1},a_j \ 翻转一遍为：a_{j-1},...,a_{i+1},a_{i},a_j \ 再翻转一遍：a_j,a_i,a_{i+1},...,a_{j-1}$
每次相当于在一个从头开始的数组操作，所以要记录他们的偏移量

AC代码：

复制代码

#include <bits/stdc++.h>
#define ft first
#define sd second
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define seteps(N) fixed << setprecision(N)
#define endl "n"
const int maxn = 6e5 + 10;
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
const ll mod = 1e9 + 7;
int t, n, a[maxn];
int cntb, b[maxn];
bool vis[maxn];
vector <int> ans;
vector <pii> op;
map <int, int> mp;
int bas;
void init() {
    mp.clear();
    ans.clear();
    op.clear();
    bas = cntb = 0;
    memset(vis, 0, sizeof(bool) * (n + 1));
}
bool pre() { //检测是否合理
    for (int i = 1; i <= n; i++) mp[a[i]]++;
    for (auto np : mp)
        if (np.second & 1)
            return false;
    return true;
}
void cal(int num) {
    int temp = num;
    for (int i = 1; i <= num; i++) {
        op.push_back({bas + temp, b[i]});
        temp++;
    }
    bas += temp; //记录偏移
    ans.push_back(temp); //记录答案
}
void solve() { //以下过程请自行手模一遍
    if (!pre()) {
        puts("-1");
        return;
    }
    for (int i = 1, j, k; i <= n; i++) {
        if (vis[i]) continue;
        for (j = i + 1; j <= n; j++) {
            if (vis[j] || a[i] != a[j]) continue;
            cntb = 0;
            for (k = i; k <= j; k++)
                if (!vis[k])
                    b[++cntb] = a[k];
            break;
        }
        if (j == i + 1) {
            vis[i] = vis[j] = true;
            bas += 2;
            ans.push_back(2);
            continue;
        }
        cal(cntb - 1);
        cntb = 0;
        for (k = j - 1; k >= i + 1; k--) 
            if (!vis[k])
                b[++cntb] = a[k];
        b[++cntb] = a[i]; b[++cntb] = a[i];
        cal(cntb);
        vis[i] = vis[j] = true;
        bas += 2;
        ans.push_back(2);
    }
    cout << op.size() << endl;
    for (auto np : op) cout << np.first << " " << np.second << endl;
    cout << ans.size() << endl;
    for (auto np : ans) cout << np << " ";
    cout << endl;
}
int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        init();
        solve();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
#define ft first
#define sd second
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define seteps(N) fixed << setprecision(N)
#define endl "n"
const int maxn = 6e5 + 10;
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
const ll mod = 1e9 + 7;
int t, n, a[maxn];
int cntb, b[maxn];
bool vis[maxn];
vector <int> ans;
vector <pii> op;
map <int, int> mp;
int bas;
void init() {
    mp.clear();
    ans.clear();
    op.clear();
    bas = cntb = 0;
    memset(vis, 0, sizeof(bool) * (n + 1));
}
bool pre() { //检测是否合理
    for (int i = 1; i <= n; i++) mp[a[i]]++;
    for (auto np : mp)
        if (np.second & 1)
            return false;
    return true;
}
void cal(int num) {
    int temp = num;
    for (int i = 1; i <= num; i++) {
        op.push_back({bas + temp, b[i]});
        temp++;
    }
    bas += temp; //记录偏移
    ans.push_back(temp); //记录答案
}
void solve() { //以下过程请自行手模一遍
    if (!pre()) {
        puts("-1");
        return;
    }
    for (int i = 1, j, k; i <= n; i++) {
        if (vis[i]) continue;
        for (j = i + 1; j <= n; j++) {
            if (vis[j] || a[i] != a[j]) continue;
            cntb = 0;
            for (k = i; k <= j; k++)
                if (!vis[k])
                    b[++cntb] = a[k];
            break;
        }
        if (j == i + 1) {
            vis[i] = vis[j] = true;
            bas += 2;
            ans.push_back(2);
            continue;
        }
        cal(cntb - 1);
        cntb = 0;
        for (k = j - 1; k >= i + 1; k--) 
            if (!vis[k])
                b[++cntb] = a[k];
        b[++cntb] = a[i]; b[++cntb] = a[i];
        cal(cntb);
        vis[i] = vis[j] = true;
        bas += 2;
        ans.push_back(2);
    }
    cout << op.size() << endl;
    for (auto np : op) cout << np.first << " " << np.second << endl;
    cout << ans.size() << endl;
    for (auto np : ans) cout << np << " ";
    cout << endl;
}
int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        init();
        solve();
    }
}