题解：CF1981D Turtle and Multiplication

elswzl · 2025-06-26 14:52:55 · 题解

思路

首先对于所有 a_i，让它们都设为质数，那么最开始的条件就有其充要条件：

不存在无序对 (x,y)，使得有两个 i 同时满足 (a_i,a_{i+1}) = (x,y)。

也就是我们可以给任意两个数字连一条无向边，然后构造的序列就是其中的一个不含重边的路径。

显然，当 n 为奇数，则原图为欧拉图。

当 n 为偶数，只需要删除 \frac{n}{2}-1 条边就能使原图变为欧拉图。

那么，跑一个找欧拉路径的代码即可。但是其实这个新图点数非常少，直接搜索也能过，虽然不会证。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=3e3+5;
int m,n;
bool v[M][M];
int st[N],cnt;
bool dfs(int x){
    st[++cnt]=x;
    if(cnt>=m)return 1;
    for(int y=1;y<=n;y++){
        if(!v[x][y]){
            v[x][y]=1;v[y][x]=1;
            if(dfs(y))return 1;
            v[x][y]=0;v[y][x]=0;
        }
    }
    cnt--;
    return 0;
}
void work(){
    cnt=0;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)v[i][j]=0;
    if(!(n&1))for(int i=4;i<=n;i+=2){v[i][i-1]=v[i-1][i]=1;}
    return dfs(1),void();
}
bool isp[N];
int pri[N],top;
signed main(){
    for(int i=2;i<=1e6;i++){
        if(isp[i])continue;
        pri[++top]=i;
        for(int j=i;j<=1e6;j+=i)isp[j]=1;
    }
    int T;cin>>T;
    while(T--){
        cin>>m;
        for(n=1;n<=m*2;){
            if(n&1)if(n*(n+1)/2+1>=m)break;
            if(!(n&1))if(n*n/2+2>=m)break;
            n++;
        }
        work();
        for(int i=1;i<=m;i++)cout<<pri[st[i]]<<" ";cout<<"\n";
    }
    return 0;
}
/*
n(n+1)/2+1>=m odd
or
n^2/2+2 even
*/