【MX-X5-T4】「GFOI Round 1」epitaxy
题目描述
给你两个正整数 \(n, m\)。
定义一个 \(1 \sim n\) 的排列 \(p\) 的价值为所有的 \(n - m + 1\) 个长度为 \(m\) 的连续子串内最大值的最大公因数。（规定单个数的最大公因数为其自身。）
请你求出一个在所有 \(1 \sim n\) 的排列中价值最大的排列，如果有多个，求出任意一个均可。
Solution
观察样例，有一发现：
最大值的最大公因数（最大值的公因数以下成为“答案”）一定是 \(n\) 的因数。
证明：
不论怎么排列，\(n\) 一定会出现在那 \(n-m+1\) 个子串中，所以最大的答案一定是 \(n\) 的因数。
那么，能不能确定答案的值呢？
由于要使答案最大，所以我们考虑对于一个 \(n\) 的因数，判断能否构造出排列，设一个排列的答案为 \(k\)，发现对于一个答案 \(k\)，在排列中对 \(k\) 产生贡献数字越少越好，所以产生贡献的数的下标一定是 \(m\) 的正整数倍，最少需要 \(n/m\) 个数去产生贡献。
对 \(k\) 产生贡献的值一定是 \(k\) 的正整数倍，且因为答案是最大值的公因数，所以放在相应位置的数的值依次为 \(n\)，\(n-k\)，\(n-2 \times k\)，以此类推，能给出最多 \(n/k\) 个数去产生贡献。
下面一行代表下标，上面一行代表值。
发现判断能否构造出答案 \(k\)，当且仅当 \(\frac{n}{k} \ge \frac{n}{m}\) 即 \(m \ge k\) 时。
所以最大的答案显然为：
- 小于等于 \(m\) 且为 \(n\) 的因数的最大正整数。
那么我们可以用 \(O(m)\) 的复杂度找到 \(k\)，怎么构造呢？
其实非常简单，在锚定那 \(\frac{n}{m}\) 个数之后把剩下的 \(n-\frac{n}{m}\) 个数从大到小依次排列下去即可。
为什么呢？
设我们构造到了第 \(i\) 个锚定数和第 \(i+1\) 个锚定数之间，则两数值分别为 \(n-(i-1) \times k\) 和 \(n-i \times k\)，构造的数值域为 $\left [ n-(i+1) \times m, n-i \times m\right ] $。
因为 \(m \ge k\)，
所以 \(-i \times k \ge -i \times m\)，
所以 \(n-(i-1) \times k > n-i \times k \ge n-i \times m > n-(i+1) \times m\)。
所以构造的数永远小于锚定的数，区间最大值依旧是锚定值，答案不变。
那么代码便呼之欲出了。
代码
// written by Naught
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define Maxn 1000005
#define fo(i, l, r) for (int i = l; i <= r; ++i)
#define fr(i, r, l) for (int i = l; i >= r; --i)
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21], *p1 = buf, *p2 = buf;
inline int read(int x=0, bool f=0, char c=getchar()) {for(;!isdigit(c);c=getchar()) f^=!(c^45);for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);return f?-x:x;}
int n, m, ans[Maxn];
bool t[Maxn];
int main()
{
int _ = read();
while (_--)
{
n = read(), m = read();
fo(i, 1, n) ans[i] = 0, t[i] = true;
int k = 1, num = n/m, tmp = 0;
// 找 k
fr(i, 1, m) if(n % i == 0) {k = i; break;}
// 构造序列
fo(i, 1, num) ans[i*m] = n-tmp*k, t[n-tmp*k] = false, ++tmp;
int i = 1, j = n;
while(i <= n)
{
if(ans[i]) {++i; continue;}
if(!t[j]) {--j; continue;}
ans[i] = j, t[j] = false;
}
fo(i, 1, n) printf("%d%c", ans[i], " \n"[i==n]);
}
return 0;
}