Codeforces Round #514 (Div. 2) C. Sequence Transformation(递归)

C. Sequence Transformation

题目链接：https://codeforces.com/contest/1059/problem/C

题意：

现在有1~n共n个数，然后执行下面操作：

1.求出余下数的gcd，然后将gcd加入答案队列；

2.从中任意删除一个数，如果余下数的个数大于0，回到步骤1。

问答案队列字典序最大是什么。

题解：

这明明是递归在做极其方便，我偏偏用for循环来搞，加各种判断...

首先对于1,2,3...n来说，我们每次删去一个数时，肯定首先删去的是奇数嘛，奇数有(n+1)/2个，也就是前(n+1)/2都为1。

现在考虑如果不选奇数位置，答案有没有可能更优。更优的话考虑我们留下3,6,9....这样的（之前相当于我们留下2,4,6...这样的），即3的倍数。

前n个有n/3个3的倍数，有n/2个2的倍数，容易验证当n>3时，2的倍数的个数是大于3的倍数的个数的。同理，可以验证留下4,5的倍数...

会发现，当n>3时，2的倍数的个数是最多的，也就是我们删去的数个数是最少的，要求字典序最大，我们就留2的倍数就行了。对于n<=3，答案显而易见。

之后的式子就是2,4,.....2*k，全为2的倍数，这个时候提取2出来，就变为2*(1+2+...+k)，又回到刚才那个问题了。所以直接递归求解就是了。

代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;

vector <int> ans;

void solve(int x,int y){

    if(x==){

        ans.push_back(y);return ;

    }

    if(x==){

        ans.push_back(y);ans.push_back(*y);return ;

    }

    if(x==){

        ans.push_back(y);ans.push_back(y);ans.push_back(*y);return ;

    }

    int tmp=x;

    for(int i=;i<=x;i+=) ans.push_back(y),tmp--;

    solve(tmp,*y);

}

int main(){

    cin>>n;

    solve(n,);

    for(auto v:ans) cout<< v<<" ";

    return ;

}

巴特西

Codeforces Round #514 (Div. 2) C. Sequence Transformation(递归)

最新文章

热门文章