题意： #

定义如下序列的变换（由一个已知序列生成另一个序列）：

如果序列是空的则停止，否则在新序列的最后加上当前序列所有元素的 gcd，然后从原序列中移除一个元素。重复上述操作直到停止，问能得到的最大字典序的序列。

题很简单，相信聪明的你一定能做出来。

思路 #

很显然，前面几个数必然是 1，所以要想让字典序尽量大就得尽快出现别的数，要想让一个数出现就得删掉全部不是它倍数的数，那么最快能出现的数就是 2 了，只要把所有奇数删掉就行了。然后就剩下了一堆偶数，是不是看起来似曾相识？没错他又变成了刚才的问题只不过所有数都乘了 2（禁止套娃）。那啥时候停呢？当 n 小于 3 的时候，因为此时无法用刚才的规律。

是不是很有意思呢？其实递归的题都挺有意思的。

代码 #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i <= int(r); ++i)
#define ford(i, n) for (int i = int(n)-1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define endl '\n'
#define _ <<' '<<
#define de(x) cout<<#x<<" = "<<(x)<<endl
#define de2(x,y) cout<<#x<<" = "<<(x) _ #y<<" = "<<y<<endl;
 
using namespace std;
 
const int INF = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int, int> pii;
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
 
void solve(int x,int mul){
    if(x==1) cout<<mul<<' ';
    else if(x==2) cout<<mul<<' '<<2*mul<<' ';
    else if(x==3) cout<<mul<<' '<<mul<<' '<<3*mul<<' ';
    else{
        for(int i=1;i<=x;i+=2) cout<<mul<<' ';
        solve(x/2,mul*2);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    solve(n,1);
    return 0;
}

Codeforces 1059C - Sequence Transformation 题解

题意： #

思路 #

代码 #