题解

思路

考虑直接构造。

解题方法

容易发现 $n$ 一定是某一段的最大值，故答案一定是 $n$ 的因数。

如果 $2m>n$，则构造 $\dfrac{n+1}{2}$ 位置是 $n$，其他位置乱填，此时任意一个区间必然包含 $n$，答案为 $n$

其余情况至少有两个最大值不同的段，考虑现在 $x$ 的倍数只有 $\dfrac{n}{x}$ 个，其中 $x$ 是答案。

若 $x>m$，则必有一段长为 $m$ 的段没有 $x$ 的倍数，故 $x\leq m$。

所以猜想此时答案是 $m$ 以下最大的 $n$ 的因数。

考虑构造：$x,1,...,x-1,2x,x+1,...,2x-1,3x,...$

然后就做完了。

复杂度

时间复杂度: $O(Tn)$

空间复杂度: $O(1)$

Code

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T;cin>>T;
	while(T--){
		int n,m;cin>>n>>m;
		if(m*2>n){
			int cnt=0;
			for(int i=1;i<=n;++i)if(i==(n+1)/2)cout<<n<<" ";else cout<<(++cnt)<<" ";
			cout<<'\n';
			continue;
		}
		int T=1;
		for(int i=m;i>=1;--i)if(n%i==0){T=i;break;}
		int cnt=0;
		for(int i=1;i<=n/T;++i){
			cout<<T*i<<" ";++cnt;
			for(int j=1;j<T&&cnt<n;++j)cout<<(i-1)*T+j<<" ",++cnt;
		}
		cout<<'\n';
	}
	return 0;
}

思路

貌似跟官方题解不一样？

我们考虑最优情况下，对答案造成贡献的数会被我们放在什么位置。

发现下标为 $m$ 的倍数能够“控制”的数是最多的，所以我们考虑将数填入下标为 $m$ 的倍数的地方。

接下来我们来考虑答案。不难发现 $n$ 一定是对答案有贡献的；其次 $n$ 最多只能完全“控制” $m-1$ 个数。

这就意味着我们可以枚举 $[n-m,n)$ 中的每一个值，将其作为可能的第二小的有贡献的数，计算其与 $n$ 的 $\gcd$ 取 $\max$ 即可。

然后对于剩余的没有填的空位，降序将剩余的数填入即可。

Code

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define sc second
#define pii pair<int,int>
#define pb push_back
#define umap unordered_map
#define mset multiset
#define pq priority_queue
#define ull unsigned long long
#define i128 __int128
const int maxn=1e6+10;
int n,m,a[maxn],vis[maxn];
void solve(){
    cin>>n>>m;
    int maxx=0,maxi=0;
    for(int i=1;i<=m;i++) if(maxx<__gcd(n,n-i)) maxi=n-i,maxx=__gcd(n,i);
    int num=n;
    for(int i=m;i<=n;i+=m) a[i]=num,vis[num]=1,num-=maxx;
    vector<int> vec;
    for(int i=n;i;i--) if(!vis[i]) vec.pb(i);
    int z=0;
    for(int i=1;i<=n;i++) if(!a[i]) a[i]=vec[z++];
    for(int i=1;i<=n;i++) cout<<a[i]<<" ",a[i]=vis[i]=0;
    cout<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--) solve();
    return 0;
}

P11132 【MX-X5-T4】「GFOI Round 1」epitaxy

基于次大值的构造。

考虑到如果最大值和次大值都出现那么结果一定为 $1$。而如果次大值在序列中出现 $2m-1$ 次，则一定会与最大值一起出现，这是不好的。

因此，我们构造把次大值放在序列开头，之后最大值必须要放在前 $m$ 个位置。这中间有 $m-2$ 个空位，我们填上 $n-2\sim n-m-1$，剩下的位置需要填入一个 $1\sim n-m$ 的排列，这是一个完全相同的子问题。

如果我们不把空位填上 $n-2\sim n-m-1$，就是希望能更改答案序列中的值。而这种更改上述构造方式也能做到，所以直接这样构造是没有问题的。另外，也可以把次大值放在序列结尾，但是只是改变一个方向，本质相同。如果不把次大值贴紧开头，与这个构造也是等价的，但变得不好处理。

我们发现答案序列中的数构成等差序列且公差为 $n$ 的约数时才能更新答案，所以我们枚举公差，按照上述方式构造即可。

注意有可能 $m$ 过大，最小值不能出现 $2m-1$ 次，这个时候把最大值放中间就好了。我因为这个边界条件卡了一整场，警示后人。

#include <bits/stdc++.h>
using namespace std;
long long t,n,m,ans=0;
int main()
{
	scanf("%lld",&t);
	while(t--)
	   {
	   	scanf("%lld%lld",&n,&m);
	   	if(m>n/2)
	   	   {
	   	   	for(int i=1;i<=n/2;i++)printf("%lld ",1ll*i);
	   	   	printf("%lld ",n);
	   	   	for(int i=n/2+2;i<=n;i++)printf("%lld ",i-1ll);
		   }
	   	else
		   	{
		   	bool flag=1;
			for(int i=m;i>=2;i--)
			   	if(n%i==0)
			   	    {
			   	    long long now=n;
			   	    flag=0;
				   	while(now>0)
				   	    {
				   	    printf("%lld ",now-1);
				   	    for(int j=1;j<=i-2;j++)printf("%lld ",now-1-j);
				   	    printf("%lld ",now);
				   	    now-=i;
						}
					break;
					}
			if(flag)for(int i=1;i<=n;i++)printf("%lld ",i);
		    }
		printf("\n");
	   }
	return 0;
}