CF1981D D. Turtle and Multiplication 题解

D. Turtle and Multiplication

题目翻译

​ 题目给我们一个数字n，我们需要构造一个长度为n的数组，满足以下条件，数组中的所有元素属于[1, 3e5]，数组中没有两个相邻的元素的乘积相同，数组中不同的数的种类是长度为n下所有合法数组中最小的。输出任意一个符合条件的解。

思路

​ 首先考虑如何在保证没有相邻元素的乘积相同的同时使得数组中不同种类的数的个数最小，我们发现我们选择所有不同的素数来构成数组一定是最优的，因为素数的性质保证了只要相邻两个元素的组成不同乘积就不同，不会出现2 * 6 == 3 * 4这样的情况。x个数组可以组成 （x * (x + 1) ) / 2种不同的组合。我们发现如果从图论的角度抽象这个问题，把不同的两两组合看作两个节点之间的边，那么问题就变成了从这张图中找出一个长度为n的欧拉路，注意到当need（需要的最少素数个数）为奇数时，图一定存在欧拉回路，need为偶数时图中不存在走完所有边的欧拉路，此时我们最少要删除（need - 2）/ 2条边才可以得到一个可以走完所有边的欧拉路，这也就是need个素数时可以产生的最大贡献。

​ 通过素数筛法我们发现3e5范围内的素数是够用的，我们直接全部用素数构造数组即可，找到最小需要的素数数量，然后构建一个这几个素数的完全图，如果need为偶数时3 - 4 ，5 - 6， 7 - 8…这些边去掉，最后就可以保证欧拉路的存在。然后我们找出从1节点开始的欧拉路即可，此时一定可以包含图中所有边，我们输出前n - 1条边组成的节点即可得到长度为n的数组，且一定满足数组的需求定义。

代码

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
std::vector<int> minp, primes;

void sieve(int n) {
    minp.assign(n + 1, 0);
    primes.clear();
    
    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes.push_back(i);
        }
        
        for (auto p : primes) {
            if (i * p > n) {
                break;
            }
            minp[i * p] = p;
            if (p == minp[i]) {
                break;
            }
        }
    }
}

const int N = 2e3;
const int M = 1e7;  //无向边需要开两倍
int cnt = 1;
int head[N];
struct {
    int from;
    int to;
    int nex;
}e[M];
void add(int u, int v){
    cnt++;
    e[cnt].from = u;
    e[cnt].to = v;
    e[cnt].nex = head[u];
    head[u] = cnt;
}

void solve(){
    int n;
    std::cin >> n;
    int need = 1;

    for(int i = 1; i <= 2e3; i++){
        int all = (i * (1 + i)) / 2;
        if(i % 2 == 0)
            all -= (i - 2) / 2;
        if(all + 1 >= n){
            need = i;
            break;
        }
    }

    int all = (need * (1 + need)) / 2;
    if(need % 2 == 0)
        all -= (need - 2) / 2;

    std::vector<std::pair<int, int>> edge(1, {0, 0});

    
    for(int i = 1; i <= need; i++){
        for(int j = i; j <= need; j++){
            if(need % 2 == 0 && i != 1 && i % 2 == 1 && j == i + 1){
                continue;
            }
            edge.push_back({i, j});
            add(i, j);
            add(j, i);
        }
    }

    std::vector<int> ans;
    std::vector<int> use(cnt + 1, false);
    int t = 1;
    std::vector<int> res;

    std::function<void(int)> dfs = [&](int node) -> void{
        for(int now = head[node]; now > 0; now = head[node]){
            
            if(use[now]){
                head[node] = e[now].nex;
                continue;
            }

            use[now] = true;
            if(t == 1)
                use[now ^ 1] = true;
            head[node] = e[now].nex;    //删去遍历过的点
            
            dfs(e[now].to);

            int ind = (t == 1 ? now / 2 : now - 1);

            if(t == 1 && now % 2 == 1){
                ans.push_back(ind);
            }
            else if(t == 1){
                ans.push_back(-ind);
            }
            else
                ans.push_back(ind); //注意对于有向图我们这里实际是找到的逆的路径，所以不用-ind
        }
    };
    dfs(1);

    for(int i = 0; i < ans.size(); i++){
        if(ans[i] > 0){
            if(i == 0)
                res.push_back(edge[ans[i]].ff);
            res.push_back(edge[ans[i]].ss);
        }
        else{
            if(i == 0)
                res.push_back(edge[-ans[i]].ss);
            res.push_back(edge[-ans[i]].ff);
        }
    }

    for(int i = 0; i < n; i++)
        std::cout << primes[res[i]] << sendl[i == n - 1];

    for(int i = 1; i <= need; i++)
        head[i] = 0;
    cnt = 1;
}