「ALFR Round 3」B Swap & Delete

· · 题解

有人看到这道题可能直接就懵逼了，但是说句实话，如果你看懂了样例你就会发现，这题它纯纯一个分类讨论啊！！！

根据样例，我们可以发现，一旦 a_i 与 a_1 或者 a_n 相等，这组数据就只要两个操作：

  1. 如果 a_n\ne a_i，那就交换 a_n 和 a_i，否则交换 a_1 和 a_i。

  2. 直接给整个序列删掉！（因为上一步已经使得 a_1=a_n 了）

但是，先别急着打！看数据：

数据范围

子任务 分值 限制
1 10 n\le 3
2 20 n\le 10
3 20 a_i\le 2
4 10 保证所有 a_i 相等
5 40 -

对于 100\% 的数据，1\le T \le 5，1\le n\le 10^5，0\le a_i\le 10^9。

子任务 4，保证所有 a_i 都相等？！

于是，我们可以轻松地得到另一个东西：如果 a_1 本来就等于 a_n，你就可以直接给整个序列删掉！

那为什么不能先判样例的情况再判上面那种情况呢？

先给大家造一组有毒的数据：

1 2 1 2 1

如果你要是先判样例的情况的话。。。你懂的hhh，虽然我没试探过这道题目的数据强度，但是你自己去可以试试。

然后我们还可以把上面那组数据爆改一下：

3 2 1 2 4

于是，我们得到下面的结论：

如果 a_i=a_j，我们就可以发现，我们需要 3 次操作就可以把整个序列删掉，be like：

第一步：2 3 1 2 4
第二步：2 3 1 4 2
第三步：（只有空气了，因为序列被删光了（））

但是，但是，这样了还没结束！

因为，如果这 n 个数字互不相等，怎么弄？

呃，可想而知，我们要。。。一个一个删。。。于是，这种情况就要 n 次操作了。

综上，所有情况都被推导出来了。

然后就是，上代码！！！

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
const int A=1000000005;
int n,a[N];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        if(a[1]==a[n])
        {
            cout<<1<<endl;//先判有没有 a[1]==a[n] 这种情况，避免发生类似 1 2 1 2 1 的数据把你卡了。
        }
        else
        {
            bool flag=1;
            for(int i=2;i<n;i++)
            {
                if(a[i]==a[1]||a[i]==a[n])
                {
                    cout<<2<<endl;
                    flag=0;
                    break;
                }
            }//判样例的情况。
            if(flag)
            {
                bool flag2=1;
                for(int i=2;i<n;i++)
                {
                    for(int j=i+1;j<n;j++)
                    {
                        if(a[i]==a[j])
                        {
                            cout<<3<<endl;
                            flag2=0;
                            break;
                        }
                    }
                }//再判上面的第三种情况。
                if(flag2)
                {
                    cout<<n<<endl;
                }//如果都不满足，那就是剩下的那种情况，输出 n 就完了！
            }
        }
    }
    return 0;//完结撒花~~~
}