CF967

A

题意

给你一个循环的数列，你可以进行以下操作，选择相邻两个中的一个删除，求最少操作次数，使得数列中的所有元素相等。

方法

直接求最大的个数相等的数目maxn，输出n-maxn即可。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
    int n;  cin>>n;
    std::vector<int> a(n,0);
    map<int,int> mp;
    for(auto &t: a)
    {
        cin>>t;
        mp[t]++;
    }
    int maxn=0;
    for(auto [x,y]: mp)
    {
        maxn=max(maxn,y);
    }
    cout<<n-maxn<<"\n";
}
int main()
{
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}

B

题意

看题目吧。

方法

构造。直接按照交错构造即可。

偶数的全排列无法构造。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
    int n;  cin>>n;
    if(n%2==0)    cout<<-1<<"\n";
    else
    {
        for(int i=n;i>0;i-=2)   cout<<i<<" ";
        for(int i=2;i<n;i+=2)   cout<<i<<" \n";
        cout<<"\n";
    }
}
int main()
{
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}

D

题意

给你一个数列，你需要选出其中的一个子序列（不能有重复元素），要求你需要找到最小的全排列。

方法

不难发现：我们可以只需要让奇数位大，偶数位小即可。

这里可以先找每一个数字出现的最晚位置，存入 一个vector中，后面再贪心地不断往前进行添加，然后再删去即可。

这里可以用双指针进行维护一个区间[l,r]，维护的想法可以参考一下Z函数的实现。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
    int n;  cin>>n;
    std::vector<int> a(n,0);
    for(int i=0;i<n;i++)    cin>>a[i];
    std::vector<int> book(n+1,-1);
    std::vector<pair<int,int>> b;
    for(int i=n-1;i>=0;i--)
    {
        if(book[a[i]]==-1)
        {
            b.push_back({i,a[i]});
            book[a[i]]=i;
        }
    }
    sort(b.begin(),b.end());

    book.assign(n+1,0);			//book是用来记录是否出现的
    std::map<int, int> map;		//map是用来记录出现次数的
    int ptr1=0,ptr2=0,cur=0;
    std::vector<int> ans;
    while(ptr2<b.size())
    {
        auto [id,val]=b[ptr2];
        for(cur;cur<=id;cur++)
        {
            if(book[a[cur]]==0)
            {
                map[a[cur]]++;
            }
        }
        if(book[val])
        {
            ptr2++;
            continue;
        }
        while(book[val]==0)
        {
            int tmp=0;
            if(ans.size()%2==0)
            {
                tmp=map.rbegin()->first;
            }
            else
            {
                tmp=map.begin()->first;
            }
            book[tmp]=1;
            ans.push_back(tmp);
            map.erase(tmp);

            for(ptr1;a[ptr1]!=tmp;ptr1++)
            {
                if(map.count(a[ptr1]))
                {
                    map[a[ptr1]]--;
                    if(map[a[ptr1]]==0) map.erase(a[ptr1]);
                }
            }
        }
        ptr2++;
    }
    cout<<ans.size()<<"\n";
    for(int i=0;i<ans.size();i++)
    {
        cout<<ans[i]<<" \n"[i==ans.size()-1];
    }
}
int main()
{
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}