http://codeforces.com/contest/1419/problem/D2

D2. Sage’s Birthday (hard version)

 

题意：给定一个数列，重新排列，要使得满足 a[i]<a[i−1]&&a[i]<a[i+1]a[i]<a[i-1]\&\& a[i]<a[i+1] 的数（首尾必不满足）最多。

从小到大排序，前一半数插到后一半数里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(x) cout<<#x<<":\t"<<x<<endl;
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
int n;
int a[N], b[N];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	sort(a + 1, a + n + 1);
	int p = 1, q = n / 2 + 1;
	for (int i = 1; i <= n; i++) {
		if (i & 1)b[i] = a[q++];
		else b[i] = a[p++];
	}
	int ans = 0;
	for (int i = 2; i < n; i++)if (b[i] < b[i - 1] && b[i] < b[i + 1])ans++;
	printf("%d\n", ans);
	for (int i = 1; i <= n; i++)printf("%d%c", b[i], " \n"[i == n]);
	return 0;
}

 

E. Decryption

 

题意：给定 n，把 n 的所有大于 1 的因数排成一个圆，如果相邻的两个数互质，则在它们中间插入它们的LCM，要最小化插入次数，求排列。

dfs

atcoder做过类似的一道题。把所有因子排列成圆，使得相邻因子不互质。

本题类似，只要 n 不是两个不同质数的乘积，则必然可以使得插入次数为 0.

设 n 的各个质因子的幂次为 c[i]={2,2,2}c[i]=\{2,2,2\}，则枚举方式为 [0,0,0],[0,0,1],[0,0,2],[0,1,2],[0,1,1],[0,1,0],[0,2,0],[0,2,1],[0,2,2],[1,2,0],[1,2,1]⋯[0,0,0],[0,0,1],[0,0,2],[0,1,2],[0,1,1],[0,1,0],[0,2,0],[0,2,1],[0,2,2],[1,2,0],[1,2,1]\cdots.

当 c[i−1]c[i-1] 为奇数，则递减枚举 c[i]c[i]，否则递增枚举。

这样可以不需要将 nn 插入圆即可满足相邻不互质，但是不能保证首尾不互质，所以把 n 插入首尾之间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e6+10;
const int INF=0x3f3f3f3f;
const ll inf=0x3f3f3f3f3f3f3f3f;
const ll mod=998244353;
#define ull unsigned ll
#define debug(x) cout<<#x<<":\t"<<x<<endl;
int T;
ll n;
int m;
ll pr[100],p[100][100];
int c[100],tmp[100],tot; ll ans[N];
void dfs(int dep){
    if(dep>m){
        ll x=1;
        //for(int i=1;i<=m;i++)printf("%d%c",tmp[i]," \n"[i==m]);
        for(int i=1;i<=m;i++)x*=p[i][tmp[i]];
        if(x!=1&&x!=n)ans[++tot]=x;
        return;
    }
    if(tmp[dep-1]%2==0){
        for(tmp[dep]=0;tmp[dep]<=c[dep];tmp[dep]++){
            dfs(dep+1);
        }
    }
    else{
        for(tmp[dep]=c[dep];tmp[dep]>=0;tmp[dep]--){
            dfs(dep+1);
        }
    }
}
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    return b==0?a:gcd(b,a%b);
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%lld",&n);
        m=0;
        ll tn=n;
        for(ll i=2;i*i<=tn;i++){
            if(tn%i)continue;
            pr[++m]=i;
            c[m]=tmp[m]=0;
            while(tn%i==0){
                c[m]++;
                tn/=i;
            }
        }
        if(tn!=1){
            pr[++m]=tn;
            c[m]=1;
            tmp[m]=0;
        }
        //debug(m)
        for(int i=1;i<=m;i++){
            p[i][0]=1;
            for(int j=1;j<=100;j++)p[i][j]=p[i][j-1]*pr[i];
        }
        tot=0;
        dfs(1);
        ans[++tot]=n;
        for(int i=1;i<=tot;i++)printf("%lld%c",ans[i]," \n"[i==tot]);
        if(m==2&&c[1]==c[2]&&c[1]==1)puts("1");
        else puts("0");
    }
    return 0;
}