Codeforces Round #514 (Div. 2) C. Sequence Transformation-白红宇

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

阅读量：5797 次

发布时间：2019-06-18

本文共 1614 字，大约阅读时间需要 5 分钟。

题目大意：给你一个n

从1，2，3......n这个序列中

依次进行以下操作：1 、求所有数的最大公因数，放入a序列里面

　　　　　　　　　2 、任意删去一个元素

　　　　　　　　　一直到序列为空

根据删除元素的不同，导致序列a的字典序可能不同

输出字典序最大的a序列

看到这题，首先我想到gcd的两个特性，首先gcd(a1,a2,a3,a4.....an) <= min(a1,a2,a3,a4...an);

其次任意两个相邻的数 gcd等于1 gcd（4，5） == 1

回过头看序列 1 ，2 ， 3 ， 4 ，5 ，6 ，7 ，8

先举例8个数首先，你这个开头的1不删除，你的gcd永远不可能超过1，所以我的第一个删除的原属就是这个1

其次，相邻两个数gcd等于1，为了让gcd尽早的大于1，那么对于3，5，7，我们都应该删除（这时候不能删除2，4，6，8，原因你可以自己思考）

那么就删除3，5，7这3个元素

序列中生下了2，4，6，8这4个元素

这时gcd == 2，那么你这个2不删的话，你的gcd永远不可能大于2，所以这个2，是要首先删除的，

剩下4，6，8这三个元素，类比上面的删除中间元素，删除6

剩下两个元素4，8 ，当序列中只剩下两个元素的时候，先输出两个数gcd，然后输出最大的数即可

总结一下就是：删除1，3，5，7。。。。。

　　　　　　　删除2，6，10 ，14 。。。。。

　　　　　　　删除4 ，12，20，28 .。。。。

当然上面讨论的都是偶数的情况，奇数的情况是否使用呢？

交给判题姬判断吧

其实奇数的情况和偶数的情况是一样的，无非就是1，2，3，4，5

删除1，剩下2，3，4，5

那么删2，4还是删3，5

推了几个例子发现删3，5比较好

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               using namespace std;#define ll long long#define se second#define fi first#define oo 0x3fffffffint arr[1000005];vector
               
                 q;set
                
                  s;int gcd(int a,int b){ return b == 0? a:gcd(b,a%b);}int main(){ int n; scanf("%d",&n); for(int i = 1; i <= n; ++i) { arr[i] = i; s.insert(i); } if(n == 1) { printf("1\n"); return 0; } //if(n%2 == 0) //{ int cnt = n; int ans = 1; while(s.size() != 2) { for(int i = ans; i <= n && s.size() != 2; i+=ans*2) { //cout << i << endl; printf("%d ",ans); s.erase(i); } ans *= 2; } set
                 
                  ::iterator it; it = s.begin(); //it ++; cout << gcd(*it,*(it++)) << " " ; cout << *it << endl; //} return 0;}