洛谷 5080 Tweetuzki 爱序列 题解

发表于 | 更新于 | 阅读次数：
本文字数： 754 字 | 阅读时长 ≈ 3 分钟

题意简述

给一个集合$a$，大小为$n$。请你选出若干个数，按某种顺序排好，对于每个数（除了最后一个），它的下一个数要么是他两倍，要么是它$\dfrac{1}{3}$。你最多能从$a$选出多少个数满足这样的条件？

$n<=1e5$，$1<=a_i<=3e18$。

比如${4,8,16,12,24}$，最多就是选出$4$个数，按$12,24,8,16$的顺序排好。容易验证，这样是最长的。

具体思路

我们开一个$map$，记为$pos$。$pos[x]$表示$x$出现的位置。然后$i$向$pos[2\times a[i]]$和$pos[a[i]/3]$连边，如果$pos!=0$。这样我们就建好了一张后继图。图上任意一条路径，就是一个合法的选择方案。（显然）

然后我们讲一下为什么是$DAG$。我们走一条边，要么是乘2，要么是除3，而$2$和$3$是互质的，所以$\dfrac{2^x}{3^y}$不珂能是$1$。也就是说，一个点不会到自己。再换句话，图上没环。

然后就是实现方面的问题了。记得开$longlong$。

精髓总结

关键就是要想到图是个DAG！

代码

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

#include <bits/stdc++.h>using namespace std;
namespace Flandre_Scarlet
{
    #define N 255555
    #define int long long 
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Rd(int cnt,...)
    {
        va_list args;
        va_start(args,cnt);
        F(i,1,cnt) 
        {
            int* x=va_arg(args,int*);R1(*x);
        }
        va_end(args);
    }

    int n,a[N];
    void Input()
    {
        R1(n);F(i,1,n) R1(a[i]);
    }

    map<int,int> pos;
    vector<int> nex[N];
    int ideg[N],odeg[N];
    void Add(int u,int v) {nex[u].p_b(v);++ideg[v],++odeg[u];}
    int dp[N],pre[N]; queue<int> Q;
    void PrintPath(int u)
    {
        if (pre[u]==-1) {printf("%lld",a[u]);return;}
        PrintPath(pre[u]);printf(" %lld",a[u]);
    }
    void Soviet()
    {
        F(i,1,n) pos[a[i]]=i;
        F(i,1,n)
        {
            if (a[i]%3==0 and pos[a[i]/3]!=0) Add(i,pos[a[i]/3]);
            if (pos[a[i]<<1]) Add(i,pos[a[i]<<1]);
        }

        FK(dp);
        F(i,1,n) if (!ideg[i]) Q.push(i),dp[i]=1,pre[i]=-1;
        while(!Q.empty())
        {
            int u=Q.front();Q.pop();
            F(j,0,sz(nex[u])-1)
            {int v=nex[u][j];
                if (dp[u]+1>dp[v])
                {
                    dp[v]=dp[u]+1;pre[v]=u;
                }
                --ideg[v];
                if (ideg[v]==0) Q.push(v);
            }
        }
        int Maxk=max_element(dp+1,dp+n+1)-dp;
        printf("%lld\n",dp[Maxk]);
        PrintPath(Maxk);putchar('\n');
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
    #undef int //long long 
}
int main(){
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w