社区讨论

想知道怎样找到更优更快的算法

P9345 夕阳西下几时回参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo2l56t8
此快照首次捕获于
2023/10/23 15:37
2 年前
此快照最后确认于
2023/10/23 15:37
2 年前
查看原帖
虽然有点长,但写的很简单,就是不知道这样能优化的更好,十几个点都TLE。
C
#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;
	
}



回复

1 条回复,欢迎继续交流。

正在加载回复...