「Luogu P5080 Tweetuzki 爱序列」
2024-09-04 20:54:27
题目大意
给出一些数,需要求出 \(\frac{a_{i+1}}{3}=a_i\) 或 \(a_{i+1}=2 \times a_i\) 时最长的序列 \(a\).
分析
可以发现符合条件的序列 \(a\) 中不会出现重复的数字,而且对于一个数它的下一个位置最多只有两种情况,于是问题就变成了无环有向图最长链,这样就可以想到记忆化搜索,\(f_i\) 表示 \(i\) 为起点时的最长链长度,为了记录下路径,所以还需要用一个 \(nxt_i\) 表示 \(i\) 的下一个位置时什么,最后直接输出就好了.
代码
#include<bits/stdc++.h>
#define REP(i,first,last) for(int i=first;i<=last;++i)
#define DOW(i,first,last) for(int i=first;i>=last;--i)
using namespace std;
const int MAXN=1e6+7;
int N;
struct Edge//链式前向星
{
int to,next;
}edge[MAXN*2];
int edge_head[MAXN];
int edge_cnt=0;
#define TO_POINT(now) for(int edge_i=edge_head[now];edge_i;edge_i=edge[edge_i].next)
#define TO edge[edge_i].to
void AddEdge(int f,int t)
{
edge[++edge_cnt].to=t;
edge[edge_cnt].next=edge_head[f];
edge_head[f]=edge_cnt;
}
bool visit[MAXN];
long long arr[MAXN];//原数组
long long a[MAXN];//去重以后的数组
int f[MAXN];//记录每个位置的最长链长度
int Find(long long num)//二分查找是否存在这个数
{
int left=1,right=N,middle;
while(left<=right)
{
middle=(left+right)>>1;
if(a[middle]>=num)
{
right=middle-1;
if(a[middle]==num)
{
return middle;
}
}
else
{
left=middle+1;
}
}
return 0;
}
int nxt[MAXN];//记录下一个位置
void DFS(int now)//DFS
{
if(f[now])//如果搜索过就不需要搜索了
{
return;
}
f[now]=1;//开始的长度为1
TO_POINT(now)
{
DFS(TO);
if(f[TO]+1>f[now])//找到在自己连出的边中的最长链长度
{
f[now]=f[TO]+1;
nxt[now]=TO;//记录下一个位置
}
}
}
int main()
{
scanf("%d",&N);
REP(i,1,N)
{
scanf("%lld",&arr[i]);
}
sort(arr+1,arr+1+N);
arr[0]=arr[1]-1;
int cnt=0;
REP(i,1,N)//去重
{
if(arr[i]!=arr[i-1])
{
a[++cnt]=arr[i];
}
}
N=cnt;
int l;
REP(i,1,N)//对于每一个点连边
{
if(a[i]%3==0)//需要判断整除
{
l=Find(a[i]/3);
if(l)
{
AddEdge(i,l);
}
}
l=Find(a[i]*2);
if(l)
{
AddEdge(i,l);
}
}
int answer=0,st;
REP(i,1,N)//如果没有访问过就DFS这个位置
{
if(!f[i])
{
DFS(i);
}
if(f[i]>answer)//记录下最长链的开头
{
answer=f[i];
st=i;
}
}
printf("%d\n",answer);//输出答案
int now=st;
while(now)
{
printf("%lld ",a[now]);
now=nxt[now];
}
return 0;
}
最新文章
- Linux文件计数
- C#在excel中添加超链接
- 基于.NET的Excel开发：单元格区域的操作（读取、赋值、边框和格式）
- js中“==”与"==="的区别
- vbox导入虚拟电脑网卡MAC问题
- c++ 走向高级之日积月累
- dede如何按自己写的ID进行排序
- Javascript与Ajax
- TD(TestDirector 8.0)在win7 ie8下无法用的解决方案：
- CSS层
- Android实现获取应用程序相关信息列表的方法
- Selenium2+python自动化28-table定位
- java内存模型7-处理器内存模型
- 到底什么样的企业才适合实施SAP系统？
- hover与click样式冲突
- sonarqube6.7部署文档
- Docker（二）搭建和使用Docker
- 在myeclipse中使用./和../遇到的问题
- PHP运算符优先级
- 【函数】SAS宏的特殊字符引用【转载】