CF2085B Serval and Final MEX

Andy1101 · 2025-03-25 21:33:18 · 题解

题目传送门

思路

本蒟蒻将此题分为 5 种情况。

数组中不包含 0

此时将整个数组合并即可。

if(cnt==0)
{
  cout <<1<<'\n';
  cout <<1<<" "<<n<<'\n';
}

数组中包含 1 个 0

1. 当 0 在下标为 1 的位置上时，此时将前两个数合并，最后将整个数组合并。

   if(a[1]==0)
   {
     cout <<2<<'\n';
     cout <<1<<" "<<2<<'\n';
     cout <<1<<" "<<n-1<<'\n';
   }

2. 当 0 在下标为 n 的位置上时，此时将后两个数合并，最后将整个数组合并。

   else if(a[n]==0)
   {
     cout <<2<<'\n';
     cout <<n-1<<" "<<n<<'\n';
     cout <<1<<" "<<n-1<<'\n';
   }

3. 如果不符合上述条件，那么就先找出 0 的位置（将其设为 p），之后将下标为 1 到 p 的所有数合并，最后将整个数组合并。

   else
   {
     int p;
     for(int i=1;i<=n;i++)
     {
       if(a[i]==0)
       {
         p=i;
         break;
       }
     }
     cout <<2<<'\n';
     cout <<1<<" "<<p<<'\n';
     cout <<1<<" "<<n-p+1<<'\n';
   }

数组中包含 2 个 0

1. 当 0 在前两个位置上，此时将前两个数合并，最后将整个数组合并。

   if(a[1]==0 && a[2]==0)
   {
       cout <<2<<'\n';
       cout <<1<<" "<<2<<'\n';
       cout <<1<<" "<<n-1<<'\n';
   }

2. 当 0 在后两个位置上，此时将后两个数合并，最后将整个数组合并。

   else if(a[n-1]==0 && a[n]==0)
   {
       cout <<2<<'\n';
       cout <<n-1<<" "<<n<<'\n';
       cout <<1<<" "<<n-1<<'\n';
   }

3. 当 0 在下标为 1 和下标为 n 的位置上时，此时先将前两个数合并，再将除了第一个数之外的所有数合并，最后将剩下的两个数合并。

   else if(a[1]==0 && a[n]==0)
   {
       cout <<3<<'\n';
       cout <<1<<" "<<2<<'\n';
       cout <<2<<" "<<n-1<<'\n';
       cout <<1<<" "<<2<<'\n';
   }

4. 当 0 在下标为 1 的位置上并且不在下标为 n 的位置上时，此时先将前两个数合并，再将除了第一个数之外的所有数合并，最后将剩下的两个数合并。（实质上和上一种情况一样）。

5. 当 0 不在下标为 1 的位置上并且在下标为 n 的位置上时，此时先将后两个数合并，再将除了最后一个数之外的所有数合并，最后将剩下的两个数合并。

   else if(a[1]!=0 && a[n]==0)
   {
       cout <<3<<'\n';
       cout <<n-1<<" "<<n<<'\n';
       cout <<1<<" "<<n-2<<'\n';
       cout <<1<<" "<<2<<'\n';
   }

6. 如果不符合上述条件，那么就先找出第一个 0 的位置（将其设为 p），然后先将下标为 1 到 p 的所有数合并，再将除了第一个数之外的所有数合并，最后将剩下的两个数合并。

   else
   {
       int p;
       for(int i=1;i<=n;i++)
       {
           if(a[i]==0)
           {
               p=i;
               break;
           }
       }
       cout <<3<<'\n';
       cout <<1<<" "<<p<<'\n';
       cout <<2<<" "<<n-p+1<<'\n';
       cout <<1<<" "<<2<<'\n';
   }

   数组中包含 n 个 0

   此时先将前两个数合并，再将除了第一个数之外的所有数合并，最后将剩下的两个数合并。

else if(cnt==n)
{
    cout <<3<<"\n";
    cout <<1<<" "<<2<<'\n';
    cout <<2<<" "<<n-1<<'\n';
    cout <<1<<" "<<2<<'\n'; 
}

数组中 0 的数量不符合上述四种情况

1. 当 0 在下标为 1 和下标为 n 的位置上时，此时先将前两个数合并，再将除了第一个数之外的所有数合并，最后将剩下的两个数合并。

   if(a[1]==0 && a[n]==0)
   {
       cout <<3<<'\n';
       cout <<1<<" "<<2<<'\n';
       cout <<2<<" "<<n-1<<'\n';
       cout <<1<<" "<<2<<'\n';
   }

2. 当 0 在下标为 1 的位置上并且不在下标为 n 的位置上时，此时先将前两个数合并，再将除了第一个数之外的所有数合并，最后将剩下的两个数合并。（实质上和上一种情况一样）。

3. 当 0 不在下标为 1 的位置上并且在下标为 n 的位置上时，此时先将后两个数合并，再将除了最后一个数之外的所有数合并，最后将剩下的两个数合并。

   else if(a[1]!=0 && a[n]==0)
   {
       cout <<3<<'\n';
       cout <<n-1<<" "<<n<<'\n';
       cout <<1<<" "<<n-2<<'\n';
       cout <<1<<" "<<2<<'\n';
   }

4. 如果不符合上述条件，那么就先找出第一个 0 的位置（将其设为 p），然后先将下标为 1 到 p 的所有数合并，再将除了第一个数之外的所有数合并，最后将剩下的两个数合并。

   else
   {
       int p;
       for(int i=1;i<=n;i++)
       {
           if(a[i]==0)
           {
               p=i;
               break;
           }
       }
       cout <<3<<'\n';
       cout <<1<<" "<<p<<'\n';
       cout <<2<<" "<<n-p+1<<'\n';
       cout <<1<<" "<<2<<'\n';
   }

   AC Code：

#include <bits/stdc++.h>
using namespace std;
const int N=5e3+4;
int a[N];
void solve()
{
    int n;
    cin >>n;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        cin >>a[i];
        if(a[i]==0) cnt++;
    }
    if(cnt==0)
    {
        cout <<1<<'\n';
        cout <<1<<" "<<n<<'\n';
    }
    else if(cnt==1)
    {
        if(a[1]==0)
        {
            cout <<2<<'\n';
            cout <<1<<" "<<2<<'\n';
            cout <<1<<" "<<n-1<<'\n';
        }
        else if(a[n]==0)
        {
            cout <<2<<'\n';
            cout <<n-1<<" "<<n<<'\n';
            cout <<1<<" "<<n-1<<'\n';
        }
        else
        {
            int p;
            for(int i=1;i<=n;i++)
            {
                if(a[i]==0)
                {
                    p=i;
                    break;
                }
            }
            cout <<2<<'\n';
            cout <<1<<" "<<p<<'\n';
            cout <<1<<" "<<n-p+1<<'\n';
        }
    }
    else if(cnt==2)
    {
        if(a[1]==0 && a[2]==0)
        {
            cout <<2<<'\n';
            cout <<1<<" "<<2<<'\n';
            cout <<1<<" "<<n-1<<'\n';
        }
        else if(a[n-1]==0 && a[n]==0)
        {
            cout <<2<<'\n';
            cout <<n-1<<" "<<n<<'\n';
            cout <<1<<" "<<n-1<<'\n';
        }
        else if(a[1]==0 && a[n]==0)
        {
            cout <<3<<'\n';
            cout <<1<<" "<<2<<'\n';
            cout <<2<<" "<<n-1<<'\n';
            cout <<1<<" "<<2<<'\n';
        }
        else if(a[1]==0 && a[n]!=0)
        {
            cout <<3<<'\n';
            cout <<1<<" "<<2<<'\n';
            cout <<2<<" "<<n-1<<'\n';
            cout <<1<<" "<<2<<'\n';
        }
        else if(a[1]!=0 && a[n]==0)
        {
            cout <<3<<'\n';
            cout <<n-1<<" "<<n<<'\n';
            cout <<1<<" "<<n-2<<'\n';
            cout <<1<<" "<<2<<'\n';
        }
        else
        {
            int p;
            for(int i=1;i<=n;i++)
            {
                if(a[i]==0)
                {
                    p=i;
                    break;
                }
            }
            cout <<3<<'\n';
            cout <<1<<" "<<p<<'\n';
            cout <<2<<" "<<n-p+1<<'\n';
            cout <<1<<" "<<2<<'\n';
        }
    }
    else if(cnt==n)
    {
        cout <<3<<"\n";
        cout <<1<<" "<<2<<'\n';
        cout <<2<<" "<<n-1<<'\n';
        cout <<1<<" "<<2<<'\n'; 
    }
    else
    {
        if(a[1]==0 && a[n]==0)
        {
            cout <<3<<'\n';
            cout <<1<<" "<<2<<'\n';
            cout <<2<<" "<<n-1<<'\n';
            cout <<1<<" "<<2<<'\n';
        }
        else if(a[1]==0 && a[n]!=0)
        {
            cout <<3<<'\n';
            cout <<1<<" "<<2<<'\n';
            cout <<2<<" "<<n-1<<'\n';
            cout <<1<<" "<<2<<'\n';
        }
        else if(a[1]!=0 && a[n]==0)
        {
            cout <<3<<'\n';
            cout <<n-1<<" "<<n<<'\n';
            cout <<1<<" "<<n-2<<'\n';
            cout <<1<<" "<<2<<'\n';
        }
        else
        {
            int p;
            for(int i=1;i<=n;i++)
            {
                if(a[i]==0)
                {
                    p=i;
                    break;
                }
            }
            cout <<3<<'\n';
            cout <<1<<" "<<p<<'\n';
            cout <<2<<" "<<n-p+1<<'\n';
            cout <<1<<" "<<2<<'\n';
        }

    }
}
int main()
{
    int t;
    cin >>t;
    while(t--)
    {
        solve();
    }
    return 0;
}