当前位置: 首页 > news >正文

#162 (Div. 2)

A.

B.

C.

D. Good Sequences 

题意:从一个递增数字序列中找出一串最长的序列满足任意相邻的数字不互质。

分析:

The main idea is DP. Let's define dp[x] as the maximal value of the length of the good sequence whose last element is x, and define d[i] as the (maximal value of dp[x] where x is divisible by i).

You should calculate dp[x] in the increasing order of x. The value of dp[x] is (maximal value of d[i] where i is a divisor of x) + 1. After you calculate dp[x], for each divisor i of x, you should update d[i] too.

This algorithm works in O(nlogn) because the sum of the number of the divisor from 1 to n is O(nlogn).

Note that there is a corner case. When the set is {1}, you should output 1.

不打质数表
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define clr(x) memset(x,0,sizeof(x))
const int maxn = 100005;

int dp[maxn];
int pr[maxn];

int main()
{
    int i, j, k, tp;
    int n, p, res,r,tmp;
    while (scanf("%d",&n)!=EOF)
    {
        clr(dp);
        for (i=0; i<n; i++)
        {
            scanf("%d",&p);
            if (i==n-1)
                r = p;
            tmp = 0;
            tp = 0;
            for (j=2; j*j<=p; j++)
            {
                if (p%j==0)
                {
                    pr[tp++] = j;
                    tmp = tmp>dp[j]?tmp:dp[j];
                    while (p%j==0)
                        p /= j;
                }
            }
            if (p!=1)
            {
                pr[tp++] = p;
                tmp = tmp>dp[p]?tmp:dp[p];
            }
            tmp++;
            while (tp--)
                dp[pr[tp]] = tmp;

        }
        res = 0;
        for (i=0; i<=r; i++)
            if (dp[i]>res)
                res = dp[i];
        if (res == 0)
            res++;
        printf("%d\n",res);
    }
    return 0;
}

 

打质数表
#include <cstdio>
#include <cstring>
#include <cmath>
#define clr(x) memset(x,0,sizeof(x))
const int maxn = 100005;
int dp[maxn];
int p[maxn];
int main()
{
    int i, j, k;
    clr(p);
    for (i=2; i<100001; i++){
        if (p[i]==0){
            for (j=i; j<100001; j+=i)
                p[j] = i;
        }
    }
    int res,n, t, x, tmp;
    while (scanf("%d",&n)!=EOF)
    {
        clr(dp);
        for (i=0; i<n; i++)
        {
            scanf("%d",&t);
            x = t;
            tmp = 0;
            while (x>1){
                tmp = dp[p[x]]>tmp?dp[p[x]]:tmp;
                x /= p[x];
            }
            x = t;
            tmp++;
            while (x>1){
                dp[p[x]] = tmp;
                x /= p[x];
            }
        }
        res = 1;
        for (i=2; i<=100000; ++i)
            if (dp[i]>res)
                res = dp[i];
        printf("%d\n",res);
    }
    return 0;
}

 

转载于:https://www.cnblogs.com/dream-wind/archive/2013/02/11/2910030.html

相关文章:

  • oracle开启归档模式
  • 本报记者 何泉峰 摄
  • Centos6安装桌面小记
  • 黑马程序员--小结asp.net中get、post用法区别
  • 什么时候单点集也可以是开集?
  • PL/SQL编程(四)
  • Controller的激活与URL路由
  • 关于网站二级联动菜单前台不能正常显示的问题
  • composer 安装 ubuntu 12.04
  • 在Struts2的Action中取得请求参数值的几种方法 .
  • mysqlreport指南
  • telerik的RadAutoCompleteBox控件学习二
  • (一) storm的集群安装与配置
  • (转载)利用webkit抓取动态网页和链接
  • Silverlight数据绑定引擎
  • IE9 : DOM Exception: INVALID_CHARACTER_ERR (5)
  • [ 一起学React系列 -- 8 ] React中的文件上传
  • 《用数据讲故事》作者Cole N. Knaflic:消除一切无效的图表
  • Debian下无root权限使用Python访问Oracle
  • JS+CSS实现数字滚动
  • Linux Process Manage
  • niucms就是以城市为分割单位,在上面 小区/乡村/同城论坛+58+团购
  • node-glob通配符
  • 服务器之间,相同帐号,实现免密钥登录
  • 关于Java中分层中遇到的一些问题
  • 汉诺塔算法
  • 前端相关框架总和
  • 区块链共识机制优缺点对比都是什么
  • 使用 5W1H 写出高可读的 Git Commit Message
  • 腾讯视频格式如何转换成mp4 将下载的qlv文件转换成mp4的方法
  • 想使用 MongoDB ,你应该了解这8个方面!
  • 带你开发类似Pokemon Go的AR游戏
  • 摩拜创始人胡玮炜也彻底离开了,共享单车行业还有未来吗? ...
  • ​​​​​​​Installing ROS on the Raspberry Pi
  • ​你们这样子,耽误我的工作进度怎么办?
  • (11)MSP430F5529 定时器B
  • (31)对象的克隆
  • (delphi11最新学习资料) Object Pascal 学习笔记---第8章第2节(共同的基类)
  • (ibm)Java 语言的 XPath API
  • (动手学习深度学习)第13章 计算机视觉---微调
  • (二)Eureka服务搭建,服务注册,服务发现
  • (二)WCF的Binding模型
  • (二)基于wpr_simulation 的Ros机器人运动控制,gazebo仿真
  • (附源码)spring boot车辆管理系统 毕业设计 031034
  • (教学思路 C#之类三)方法参数类型(ref、out、parmas)
  • (六)Hibernate的二级缓存
  • (切换多语言)vantUI+vue-i18n进行国际化配置及新增没有的语言包
  • (转)shell中括号的特殊用法 linux if多条件判断
  • .desktop 桌面快捷_Linux桌面环境那么多,这几款优秀的任你选
  • .Net 垃圾回收机制原理(二)
  • .net 托管代码与非托管代码
  • .NET上SQLite的连接
  • .Net下使用 Geb.Video.FFMPEG 操作视频文件
  • @Async注解的坑,小心
  • [ 隧道技术 ] cpolar 工具详解之将内网端口映射到公网