CSU 1807: 最长上升子序列~ 分类讨论

1807: 最长上升子序列~

Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 138 Solved: 17
[Submit][Status][Web Board]

Description

Bobo 在 ICPCCamp 学会了解决最长上升子序列问题后得到了一个长度为 n 的数列 p₁,p₂,…,p_n.

Bobo 想用 1,2,…,n 来替换其中值为 0 的元素，使得 p₁,p₂,…,p_n 互不相同（即 p₁,p₂,…,p_n 是 {1,2,…,n} 的排列）。

现在 Bobo 想知道，替换后最长上升子序列的长度恰好为 (n-1) 数列的数量。

Input

输入包含不超过 300 组数据，其中不超过 20 组的 n 超过 100.

每组数据的第一行包含一个整数 n (1≤n≤10⁵).

第二行包含 n 个整数p₁,p₂,…,p_n (0≤p_i≤n).

保证p₁,p₂,…,p_n中非 0 的元素互不相同。

Output

对于每组数据，输出一个整数表示要求的值。

Sample Input

Sample Output

HINT

Source

湖南省第十二届大学生计算机程序设计竞赛

[Submit][Status][Web Board]

分析：就是大分类讨论，考虑偏移

#include <cstdio>

#include <cstring>

#include <queue>

#include <cmath>

#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5 + ;

const double eps = 1e-;

const double INF = 1e12;

int n,a[N],b[N],m[N];

void solve3(int id){

   memset(b,,sizeof(b));

   b[id] = a[id];int cnt=;

   for(int i=;i<=n;++i){

     if(i==id)continue;

     ++cnt;if(cnt==a[id])++cnt;

     b[i]=cnt;

   }

   for(int i=;i<=n;++i)

    if(a[i]&&a[i]!=b[i]){

        puts("");

        return;

    }

   puts("");

}

void solve1(int id){

  if(a[id+]==id){

     for(int i=;i<=n;++i){

        b[i]=i;

     }

     swap(b[id],b[id+]);

     for(int i=;i<=n;++i){

       if(a[i]&&a[i]!=b[i]){

         puts("");return;

       }

     }

     puts("");

     return;

  }

  int r=id,flag=;

  for(int i=id+;i<=n;++i){

    if(a[i] == )continue;

    if(i!=a[i]){

      if(!flag&&a[i]==i+)r=i;

      else{

          puts("");

          return;

      }

    }

    if(i==a[i])flag=;

  }

  int t1 = ,t2 = ;

  for(int i= id-;i&&a[i]==;--i)++t1;

  for(int i=r+;i<=n&&a[i]==;++i)++t2;

  LL ret = 1ll*(t1+)*t2;

  printf("%lld\n",ret);

}

void solve2(int id){

   if(a[id-]==id){

     for(int i=;i<=n;++i){

        b[i]=i;

     }

     swap(b[id],b[id-]);

     for(int i=;i<=n;++i){

       if(a[i]&&a[i]!=b[i]){

         puts("");return;

       }

     }

     puts("");

     return;

  }

  int r=id,flag=;

  for(int i=id+;i<=n;++i){

    if(a[i]==)continue;

    if(i!=a[i]){

      if(!flag&&a[i]==i-)r=i;

      else{

         puts("");

         return;

      }

    }

    if(i==a[i])flag=;

  }

  int t1 = ,t2 = ;

  for(int i=id-;i&&a[i]==;--i)++t1;

  for(int i=r+;i<=n&&a[i]==;++i)++t2;

  LL ret = 1ll*(t2+)*t1;

  printf("%lld\n",ret);

}

int main(){

  while(~scanf("%d",&n)){

    memset(m,-,sizeof(m));

    for(int i=;i<=n;++i)scanf("%d",&a[i]),m[a[i]]=i;

    bool flag = false;

    for(int i=;i<=n;++i){

      if(a[i]&&(a[i]-i>||i-a[i]>)){

         solve3(i);

         flag = true;

         break;

      }

    }

    if(flag)continue;

    for(int i=;i<=n;++i){

      if(a[i]==||a[i]==i)continue;

      if(a[i]-i==)solve1(i);

      else if(i-a[i]==)solve2(i);

      flag = true;

      break;

    }

    if(flag)continue;

    int cnt=;LL ret=;

    for(int i=;i<=n;++i){

      if(a[i]==)++cnt;

      else if(cnt){

        ret+=1ll*(cnt-)*(cnt-);

        cnt=;

      }

    }

    if(cnt)ret+=1ll*(cnt-)*(cnt-);

    printf("%lld\n",ret);

  }

  return ;

}

巴特西