想知道怎样找到更优更快的算法
查看原帖
想知道怎样找到更优更快的算法
848091
zhuimeng1233楼主2023/5/15 23:19

虽然有点长,但写的很简单,就是不知道这样能优化的更好,十几个点都TLE。

#include <iostream>
#include <string>
#include <bits/stdc++.h>
using namespace std;

int b[300001];
bool cs[3000001];
//int xl[300000];
inline void bxl(const int n,const int k)
{
	int qw=0;
	int xl[n+1];
	
	for(int i=0;i<=n+1;++i)
	 xl[i]=i;
	xl[n+1]=xl[1];
	
 while(true)  {
	for(int i=1;i<n;++i)
	{
		b[i]=__gcd(xl[i],xl[i+1]);
		 cs[b[i]]=true;
		 
	}
	for (int i=1;i<=n;++i)
	{
		if(cs[i])
		 {
		 cs[i]=false;
		 ++qw;
		 }
		 
	}
	
	
	if (qw==k)
	 {
	 	cout<<"yes"<<endl;
	 	 for (int i=1;i<=n;++i)
	 	  cout<<xl[i]<<' ';
	 	 cout<<endl;
	 	 return;
	 }
	else
	{
		qw=0;
	   if(!next_permutation(xl+1,xl+n+1)||!next_permutation(xl+1,xl+n+1)||!next_permutation(xl+1,xl+n+1)||!next_permutation(xl+1,xl+n+1)||!next_permutation(xl+1,xl+n+1))
		{
			
		cout<<"no"<<endl;
		
		return;
		
		}
		//next_permutation(xl+1,xl+n+1);
		
	}
}

}

int main (){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t;
	cin>>t;
	
	for (int n,k,i=1;i<=t;i++)
	{
		cin>>n>>k;
		
		if(k*2>n)
		{
			cout<<"no"<<endl;
			
			continue;
			
		}
		
		bxl(n,k);
		
	}
	
	
	return 0;
	
}



2023/5/15 23:19
加载中...