专栏文章

题解：CF1981D Turtle and Multiplication

eelswzl
CF1981D题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip1ay5b
此快照首次捕获于
2025/12/03 04:32
3 个月前
此快照最后确认于
2025/12/03 04:32
3 个月前
查看原文

思路

首先对于所有 aia_i，让它们都设为质数，那么最开始的条件就有其充要条件：
不存在无序对 (x,y)(x,y)，使得有两个 ii 同时满足 (ai,ai+1)=(x,y)(a_i,a_{i+1}) = (x,y)。
也就是我们可以给任意两个数字连一条无向边，然后构造的序列就是其中的一个不含重边的路径。
显然，当 nn 为奇数，则原图为欧拉图。
当 nn 为偶数，只需要删除 n2−1\frac{n}{2}-1 条边就能使原图变为欧拉图。
那么，跑一个找欧拉路径的代码即可。但是其实这个新图点数非常少，直接搜索也能过，虽然不会证。

代码

CPP
#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
*/

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...