题解：P9928 [NFLSPC #6] 来点不那么魔怔的题面

cjh666_ · 2024-05-04 11:32:40 · 题解

题意一下

• 在长度为 n 的数组 q 中找到一个恰好有 k 个数的序号与自身大小相同（例如下标为 j 若合法，则 q_{j} 为此集合第 j 小的。简单点来说，要达成这个条件，我们就要在 q 提取一个单调递增的序列，（因为单调递增，所以每个数下标越小，则值越小）。

思路一下

• 一个上升序列，判断序列长度，是从前一个不大于此点的点的长度转移过来的，第一个想到什么？没错，DP。先规定状态，这个简单：dp[i] 为在 q 中序号为 i 的点为最高点，向前的最长序列长度。那状态转移方程呢？dp[i] \gets \max (dp[j])+1 (j<i，q[j]<q[i]) 在向前的比自己小的点中找到一个最大的长度在加上自己的一个长度。边界，很幸运，这题没有什么特殊边界，直接初始为 1 就好。

  注意

• 题目不是输出整个序列，而是有 k 个合法点的序列，因为我们这个方法的特殊，每个点都是合法的，有解则输出 k 个。

  DP代码如下

#include<bits/stdc++.h>
using namespace std;
int a[100005],dp[100005],b[100005];
int main(){
    int n,k,ans=-1;
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        dp[i]=1;//边界
        for(int j=1;j<i;j++)
            if(a[j]<a[i])dp[i]=max(dp[i],dp[j]+1);
        ans=max(dp[i],ans); 
        if(ans==k)break;    
    }
    if(ans<k){
        cout<<-1<<endl;
        return 0;
    }
    else cout<<k<<endl;
    int siz=0;
    for(int i=n;i>=1;i--){
        if(dp[i]==ans){
            b[++siz]=i;
            ans--;
        }
    }
    for(int i=k;i>=1;i--){
        cout<<b[i]<<' ';
    }
}

分析一下

• 这份代码的时间复杂度为 n_{}^{2}，空间复杂度为 n，但数据范围不如人意，n = 1 \times 10_{}^{5}，n_{}^{2} 不能接受。这里本蒟蒻没有想到什么优化方法，所以走了另一条路（手动捂脸）。代码这个东西，你想到的方法都要试一下，平时没事多写几种方法，没 AC 也没事。

AC 思路

• 首先我们维护一个数组，让这个数组单调递增，怎么加入新节点呢？我们用二分，找到一个大小大于的最小新节点的节点，把它更新掉，然后我们记录这个新节点的前一个点，这里有人就不理解了，为什么可以更新，更新了新节点的上一个位置的不就有可能会乱了吗？
• 这就是这个代码的核心了，我们从小到大向上枚举的，所以我们对于每个节点都会单独记录他前面的一个最大值，而对于更新的新值，不会影响前面的点，同时也不会影响序列的长度。
• 那序列怎么变长呢？我们开始的时候，将 r \gets siz +1 如果新节点的大小是最大的，那么就会使 siz 增加，使序列增长。没理解的同学也没关系，代码奉上，同学们可以在边看代码边理解。
• 这种方法的时间复杂度是 n log(n)，空间复杂度是 n，可以通过本题。

  AC 代码

  #include<bits/stdc++.h>
  using namespace std;
  int n,k,siz=0;
  int a[100005],b[100005],q[100005];
  void dfs(int x,int num){//x为点的下标，num为已经拿了的点数
  if(num>k)return ;
  dfs(q[x],num+1);//递归前一个点，点数加1。
  cout<<x<<' ';//先递归再输出，是小的序号在前。
  }
  int main(){
  cin>>n>>k;
  for(int i=1;i<=n;i++)cin>>a[i];
  for(int i=1;i<=n;i++){
      int l=0,r=siz+1;
      while(l+1<r){
          int mid=r+l>>1;
          if(a[i]>=a[b[mid]])l=mid;
          else r=mid;
      }       //二分
      b[r]=i;//注意这里不是记录a的值，而是记录下标，方便后面取出。
      q[b[r]]=b[r-1];//记录这个点的前一个点第一个在它前面，且比它小的点。
      if(r==siz+1)siz++;
  }
  if(siz<k){
      cout<<-1<<endl;
      return 0;
  }
  else cout<<k<<endl;
  dfs(b[siz],1);//从最大的往下找。
  }

结语

• 这道题做完了（舒坦），如果有同学这种单调序列的题的话可以去做一下 P1020 导弹拦截，跟这道题目有相似之处。
• 不太会写题解，有问题的地方欢迎指出