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

博主链接

题目链接

题意：

给你一个n，一共有数1~n，每次取出他们的GCD放入数组中，并随便删除一个数，最后要求数组的字典序最大。

题解：

先删除奇数，在删2^…次方的倍数（<mark>需要注意：比如删2的倍数时，不能删4的倍数，8的倍数…</mark>）并用变量记录倒数第二轮删的最大数（比如n=6,倒数第二轮也就是第一轮，删了2的倍数也就是删掉了2,6，这个时候用变量记录下6，倒数第一轮则删了4的倍数，删掉了4 ）,然后再比较下倒数第二轮删的最大数和倒数第一轮删的最大数那个大。(特判一下3)

代码: (可能有点乱，勿介)

#include<stdio.h>
#include<bits/stdc++.h>
#define met(a) memset(a,0,sizeof(a))
#define fup(i,a,n,b) for(int i=a;i<n;i+=b)
#define fow(j,a,n,b) for(int j=a;j>0;j-=b)
#define ll long long int
const ll LINF=0x3f3f3f3f3f3f3f;
#define MOD(x) (x)%mod
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
int a[maxn];
int b[maxn];
int main(int argc, char *argv[]){
	int n,cnt=1,ans=2;
	scanf("%d", &n);
	int num = n;
	if (n == 3) {
		printf("1 1 3\n");
		return 0;
	}
	for (int i = 1; i<=n; i += 2)a[cnt++] = 1,num--;
	int mm = 0,nn=0;
	while (num) {
		int i;
		for (i = ans; i <= n; i += ans) if (i % (ans * 2) != 0) { a[cnt++] = ans, num--; nn = i; }
		if(num)mm = nn;
		ans *= 2;
	}
	if (n % (ans / 2) == 0)a[cnt - 1] = n;
	else if(mm!=0&&mm>a[cnt-1])a[cnt-1] = mm;
	for (int i = 1; i <= n; i++) { 
		if(i==1)
		printf("%d", a[i]); 
		else printf(" %d", a[i]);
	}

	puts("");
	return 0;
}