[TJOI2013]最长上升子序列 [SCOI2009]游戏

简介: [TJOI2013]最长上升子序列 [SCOI2009]游戏

[TJOI2013]最长上升子序列

题目描述

运行代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n;
int f[N], tr[N];
vector<int> v; 
void add(int x, int k)
{
    for ( ; x <= n; x += x & -x) 
        tr[x] = max(tr[x], k);
} 
int query(int x)
{
    int r = 0;
    for ( ; x; x -= x & -x)
        r = max(r, tr[x]);
    return r;
}
int main()
{
    cin>>n; 
    for (int i = 1; i <= n; i ++ )
    {
        int x;
        cin>>x;
        v.insert(v.begin() + x, i);
    }
    for (auto x : v) {
        f[x] = query(x - 1) + 1;
        add(x, f[x]);
    }
    for (int i = 1; i <= n; i ++ )
    {
        f[i] = max(f[i], f[i - 1]);
        cout<<f[i]<<endl;
    } 
    return 0;
}

代码思路

  • int f[N], tr[N]; 分别存储原序列每个位置的最长上升子序列长度和树状数组。vector<int> v; 用于存储离散化后的序列位置。
  • 函数 add(x, k): 更新树状数组 tr[],使得位置 x 对应的值变为 max(tr[x], k)。这是通过位运算快速定位并更新相关位置实现的。
  • 函数 query(x): 查询位置 x 之前(包括 x)的最大值。这是树状数组查询操作的基本应用。
  • 主函数 main():
  • 输入序列长度 n
  • 遍历输入每个元素的位置 x,并在向量 v 的对应位置插入当前的序号 i,实现离散化。
  • 遍历离散化后的序列 v,对每个位置 x
  • 计算其最长上升子序列长度 f[x] 为当前位置左边最大长度加上 1。
  • 更新树状数组 tr[]
  • 最后再次遍历 f[],利用前一个位置的最长上升子序列长度更新当前的 f[i],保证连续性,并输出最终的最长上升子序列长度序列。

[SCOI2009]游戏

题目描述

运行代码

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=1e4;
int p[N],v[N],dp[N];
signed main()
{
    int n;
    cin>>n;
    for(int i=2;i<=n;i++)  
    {
        if(!v[i]) 
         p[++p[0]]=i;
        for(int j=1;j<=p[0] && i*p[j]<=n;j++)
        {
            v[i*p[j]]=1;
            if(!(i%p[j])) break;
        }
    }
    for(int i=dp[0]=1;i<=p[0];i++) 
        for(int j=n;j>=p[i];j--)
            for(int k=p[i];k<=j;k*=p[i])
                dp[j]+=dp[j-k];
    dp[0]=0;
    for(int i=1;i<=n;i++)
        dp[0]+=dp[i];
    cout<<dp[0]+1<<endl;
    return 0;
}

代码思路

素数筛

  • 使用埃拉托斯特尼筛法生成素数:初始化数组v[N]标记每个数是否为合数,数组p[N]存储素数。
  • 当遍历到数i时,如果v[i]为0,说明i是素数,将其存入素数数组p中。
  • 针对当前素数i,将所有i的倍数标记为合数(v[i*p[j]]=1),当遇到i的平方时跳出内层循环,减少重复计算。

计算欧拉函数之和

  • 初始化动态规划数组dp[N],其中dp[i]表示小于等于i的数中,欧拉函数值的和。
  • 外层循环遍历素数数组p。内层循环倒序遍历从n到每个素数的倍数(步进为当前素数)。内内层循环计算当前素数的幂次方(不超过当前数j),累加到dp数组中,实际上是在计算形如φ(j-k)的和,其中k是当前素数的幂次方序列,这样做可以高效地累加每个数的欧拉函数值。
  • 最后,dp[0]=0用于初始化累加和的起始值。
  • 遍历dp数组,累加所有dp[i]的值,得到小于等于n的所有欧拉函数值之和。
  • 输出结果加1(因为题目要求包括n自身),cout<<dp[0]+1<<endl;
目录
相关文章
|
7月前
|
算法 前端开发
不可能得到的最短骰子序列
不可能得到的最短骰子序列
50 0
【Leetcode -575.分糖果 -594.最长和谐子序列】
【Leetcode -575.分糖果 -594.最长和谐子序列】
56 0
【动态规划刷题 15】最长定差子序列&& 最长的斐波那契子序列的长度
【动态规划刷题 15】最长定差子序列&& 最长的斐波那契子序列的长度
|
2月前
合唱队行 (最长上升子序列)
合唱队行 (最长上升子序列)
25 0
|
6月前
|
人工智能 BI
【动态规划】最长非降子序列 01背包 插入加号
1. 计算给定整数序列的最长非升子序列。 2. 解决 0-1 背包问题,找出使总价值最大的物品组合。 3. 找出在整数中插入加号的方法,使得加号后的整数和最小。
35 0
|
7月前
代码随想录 Day44 动规12 LeetCode T300 最长递增子序列 T674 最长连续递增序列 T718 最长重复子数组
代码随想录 Day44 动规12 LeetCode T300 最长递增子序列 T674 最长连续递增序列 T718 最长重复子数组
66 0
|
7月前
|
人工智能 算法 Java
最长连续不重复子序列(蓝桥杯每日一题)
最长连续不重复子序列(蓝桥杯每日一题)
42 0
|
7月前
leetcode-6131:不可能得到的最短骰子序列
leetcode-6131:不可能得到的最短骰子序列
51 0
|
算法
代码随想录算法训练营第五十二天 | LeetCode 300. 最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组
代码随想录算法训练营第五十二天 | LeetCode 300. 最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组
51 1
|
7月前
|
算法 程序员 索引
【算法训练-动态规划 三】【双序列DP问题】最长重复子数组、最长公共子串、最长公共子序列、编辑距离
【算法训练-动态规划 三】【双序列DP问题】最长重复子数组、最长公共子串、最长公共子序列、编辑距离
113 0