西南科技大学第18届校赛D题（大三学长身败名裂qaq）

数学分析是一窍不通，个人感觉这次校赛好难啊qaq

• 前言
• • 感觉这次运气真不好一来就两道题（C，D）不会做，D题看了大概有两个多小时,主要前几天在acwing上做了和其差不多的题
• 一、最开始错误的思路
• • • acwing 上的第4367题学到了一个可以在O(n)时间复杂度解决类似于最长公共子序列的问题，但校赛的题加上了限制，也就是要求的是可以限制一个点不能移动，有就是求出的公共子序列必须含有那个限制的点，到这里我就懵逼了，试着改了下那个O(n)的算法但发现它只能求最长公共子序列。
    • 于是我用算法基础课学过的求最长公共前缀的板子去做，不过他的空间复杂度很高也寄了(大概是N^2 左右 本题也就是10^10)
  • acwing4367题
• 二、真正解题思路
• • • 1.由于限制了有些元素不可被选取，那么答案就是排列长度去掉排列的包含那个不可取元素 的最长公共子序列长度。 我们需要先求出A 数组上元素在B数组上的位置，可以通过先求出1-n在B中元素的位置a1[i]，再通过a1[a[i]]求出A数组元素在B数组的位置保存为a[]，这时候求数列A,B 的最长公共子序列问题其实就是求数列 a的最长上升子序列问题。最后求出1-n元素在a[]上的位置保存为b[]，及a数组保存的是A数组元素在B数组的位置，b数组保存的是1-n元素在a数组上的位置。b数组的作用把查询的1-n元素转换为a数组上对应元素的位置，详细作用后面会讲解。
    • 2.根据发布的题解思路一个动态规划+二分的解法
    • 求解最长上升子序列长度，就可以求解本题。
    • 我们创建一个长度为n 的数组 l和一个R数组 。
    • 我们先从左往右遍历数列 l求解该遍历顺序下的最长上升子序列长度，但是在算法步骤的2.2之前要统计arr数列当中有多少元素小于当前遍历到a[i]的元素 ，并把这个统计结果存入数组l[i]当中。然后从右往左遍历数列a[i] ，求解该遍历顺序下的最长下降子序列长度，同样地，在步骤2.2之前，统计有多少元素大于当前的遍历的 ，将结果存入 R[i]当中。这样两遍处理完所需要的数据之后，在数列的某个元素 被固定选取的情况下，数列 的最长上升子序列长度就是 l[i]+R[i]+1。
    • 最后输出结果就是n-l[i]-R[i]-1
    • (注意) 这里我们可以通过二分查找来查找2.3那个在升序中大于target值的第一个元素和降序中小于target的的一个元素。我们可以用自带的库中自带upper_bound函数来解决升序二分查找的问题，及返回它的大于等于目标值的元素的位置 lower_bound(array.begin(),array.end(),a[i])-array.begin();
    • 三个参数 数组开始的地址，结束的地址，目标值
    • 由于最后返回的是一个地址，我们可以通过减去首地址得到它的位置
    • 关于降序中的二分查找这里参考的是acwing闫总二分查找的板子
    • 3.通过的到数组l和 R 及各个位置元素对应的他们之前最长升序子序列长度和各个位置元素对应他们之后最长降序子序列长度他们加起来就再加上他本身1就是包含他们的最长子序列的长度。及 包含i 的最长子序列长度为l[i]+R[i]+1。
    • 4.我们通过查询访问1-n中的访问元素，将他们通过a1数组转换到B数组中的位置再通过b数组转换到我们研究的求最长子序列数组a数组的位置上，及通过 a1[m] 转换到B数组上 在通过b[a1[m]]转换到a数组对应元素的位置。及通过这两次操作可以快速地的到访问元素m在a数组上的位置。
    • 5.通过的到在a数组上的位置我们可以通过 l[b[a1[m]]]+R[b[a[m]]]+1求出a数组包含元素m的最长子序列长度。最后(n-l[b[m]]-R[b[m]]-1)的到最后的结果
• 详细代码如下
• • 2.ac结果
• 总结
• • • 下次参加比赛再也不敢托大了，这些超出自己能力范围外的题还是要懂得取舍，做了两个多小时人都麻了,后面都想退赛了qaq。

---

前言 感觉这次运气真不好一来就两道题（C，D）不会做，D题看了大概有两个多小时,主要前几天在acwing上做了和其差不多的题 一、最开始错误的思路 acwing 上的第4367题学到了一个可以在O(n)时间复杂度解决类似于最长公共子序列的问题，但校赛的题加上了限制，也就是要求的是可以限制一个点不能移动，有就是求出的公共子序列必须含有那个限制的点，到这里我就懵逼了，试着改了下那个O(n)的算法但发现它只能求最长公共子序列。 于是我用算法基础课学过的求最长公共前缀的板子去做，不过他的空间复杂度很高也寄了(大概是N^2 左右 本题也就是10^10) acwing4367题

acwing第4367题的题目链接
acwing第4367题的代码

acwing上最长公共前缀的板子

二、真正解题思路 1.由于限制了有些元素不可被选取，那么答案就是排列长度去掉排列的包含那个不可取元素 的最长公共子序列长度。 我们需要先求出A 数组上元素在B数组上的位置，可以通过先求出1-n在B中元素的位置a1[i]，再通过a1[a[i]]求出A数组元素在B数组的位置保存为a[]，这时候求数列A,B 的最长公共子序列问题其实就是求数列 a的最长上升子序列问题。最后求出1-n元素在a[]上的位置保存为b[]，及a数组保存的是A数组元素在B数组的位置，b数组保存的是1-n元素在a数组上的位置。b数组的作用把查询的1-n元素转换为a数组上对应元素的位置，详细作用后面会讲解。 2.根据发布的题解思路一个动态规划+二分的解法

求解最长上升子序列长度，就可以求解本题。 我们创建一个长度为n 的数组 l和一个R数组 。 我们先从左往右遍历数列 l求解该遍历顺序下的最长上升子序列长度，但是在算法步骤的2.2之前要统计arr数列当中有多少元素小于当前遍历到a[i]的元素 ，并把这个统计结果存入数组l[i]当中。然后从右往左遍历数列a[i] ，求解该遍历顺序下的最长下降子序列长度，同样地，在步骤2.2之前，统计有多少元素大于当前的遍历的 ，将结果存入 R[i]当中。这样两遍处理完所需要的数据之后，在数列的某个元素 被固定选取的情况下，数列 的最长上升子序列长度就是 l[i]+R[i]+1。 最后输出结果就是n-l[i]-R[i]-1 (注意) 这里我们可以通过二分查找来查找2.3那个在升序中大于target值的第一个元素和降序中小于target的的一个元素。我们可以用自带的库中自带upper_bound函数来解决升序二分查找的问题，及返回它的大于等于目标值的元素的位置 lower_bound(array.begin(),array.end(),a[i])-array.begin(); 三个参数 数组开始的地址，结束的地址，目标值 由于最后返回的是一个地址，我们可以通过减去首地址得到它的位置 关于降序中的二分查找这里参考的是acwing闫总二分查找的板子

acwing 二分查找板子

3.通过的到数组l和 R 及各个位置元素对应的他们之前最长升序子序列长度和各个位置元素对应他们之后最长降序子序列长度他们加起来就再加上他本身1就是包含他们的最长子序列的长度。及 包含i 的最长子序列长度为l[i]+R[i]+1。 4.我们通过查询访问1-n中的访问元素，将他们通过a1数组转换到B数组中的位置再通过b数组转换到我们研究的求最长子序列数组a数组的位置上，及通过 a1[m] 转换到B数组上 在通过b[a1[m]]转换到a数组对应元素的位置。及通过这两次操作可以快速地的到访问元素m在a数组上的位置。 5.通过的到在a数组上的位置我们可以通过 l[b[a1[m]]]+R[b[a[m]]]+1求出a数组包含元素m的最长子序列长度。最后(n-l[b[m]]-R[b[m]]-1)的到最后的结果 详细代码如下

#include 
#include 
#include
using namespace std;
int n;
int a[100003], b[120003];
int a1[100003];
int b1[100003];
int R[100003];
int l[100003];
//升序，比所有元素小，放到最外侧  
//就替换到数列中大于他的第一个元素 
vector array;
void solve(int x)
{
    array.clear();
    for(int i=1;i<=x;i++){
        if(array.empty()){
            array.push_back(a[i]);
        }
        else if(array[array.size()-1]::iterator  upper;
            upper=lower_bound(array.begin(),array.end(),a[i]);
            int j=upper-array.begin(); 
            l[i]=j; 
            array[j]=a[i];
        }
    }
}
//降序，比所有元素小，放到最外侧
//就替换到数列中小于他的第一个元素  
void solved(int x)
{
    array.clear();
    array.push_back(a[x]);
    for(int i=n;i>=1;i--){
        if(a[i]>1;
                if(a[i]>=array[mid])r=mid;
                else l=mid+1;
            }
            array[r]=a[i];
            R[i]=r;
        }
     
    }
 
}
int main()
{
    scanf("%d", &n);
    for(int i=1;i<=n;i++){
        scanf("%d", &a[i]);
    }
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d", &x);
        a1[x]=i;//元素i在B中出现的位置 
    }
    for(int i=1;i<=n;i++){
          
        a[i]=a1[a[i]];//a中第i个元素在数列B的位置 
        b[a[i]]=i;//元素i在a中出现的位置 
    }   
solve(n);
solved(n);
int k;
cin>>k;
for(int i=0;i>m;
    m=a1[m];
    // 获取m元素在B中的位置 
    // b[m] 获取元素B在b[i]中的位置
    cout<<(n-l[b[m]]-R[b[m]]-1)< 
2.ac结果 
 
 
总结 
下次参加比赛再也不敢托大了，这些超出自己能力范围外的题还是要懂得取舍，做了两个多小时人都麻了,后面都想退赛了qaq。