CF968

A

题意

给你一个字符串，你可以将其分为任意多段，需要保证任意一段\((i,j)\)，都有\(i_{th}\)段的首字母小于\(j_{th}\)段的尾字母，判断能否执行。

方法

直接分成两段即可。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
    int n;  cin>>n;
    string s;   cin>>s;
    if(s[0]!=s[n-1])    cout<<"YEs\n";
    else    cout<<"NO\n";
}    
int main()
{
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}

B

题意

存在一个数列，Alice和Bob轮流进行操作，Alice可以选择\((a_i,a_{i+1})\)，然后选择将\(a_i\)变为两者中比较大的，\(a_{i+1}\)删去。Bob也可以进行操作，进行类似的操作（这里是取较小的）。Alice的目的是\(a_1\)尽可能大，Bob相反，求最后的结果。

方法

不难想到：Alice每次取最小的删去，Bob取最大的删去，这样轮流操作，可以得到最后的答案就是中位数。（先排序）

代码

#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];
    }
    sort(a.begin(),a.end(),greater<int>());
    cout<<a[(n+1)/2-1]<<"\n";
}    
int main()
{
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}

C

题意

给你一个字符串，要求你进行重排，使得”好对“最多，（好对：快乐对或者是一个子段首尾相同）。

快乐对：一个子段内部存在两个相邻的字符\(a_k,a_{k+1}\)，(\(a_k,a_{k+1}\)不同)使得\(a_k\)不等于子段首字母，或者\(a_{k+1}\)不等于子段尾字母不同时成立。

方法

可以想到：最短的快乐对就是两个字符，并且互不相同。这样就可以尽可能的多。另外不难发现：好对的数目是确定的（即两个字符相同）。如果两个字符相邻，那么快乐对的数目也会减少。所以我们可以这样进行构造：

循环出现，出现次数多的尽可能先出现，知道全部消失为止。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
    int n;  cin>>n;
    string s;   cin>>s;
    std::map<int,int> map;
    for (int i = 0; i < n; ++i)
    {
        map[s[i]-'a']++;
    }
    std::vector<pair<int,int>> v;
    for(int i=0;i<26;i++)
    {
        if(map[i]!=0)
        {
            v.push_back({map[i],i});
        }
    }
    sort(v.begin(),v.end(),greater<pair<int,int>>());
    while(1)
    {
        bool ok=false;
        for(auto &[x,y]: v)
        {
            if(x!=0)
            {
                ok=true;
                cout<<char(y+'a');
                x--;
            }
        }
        //全部为空，直接结束
        if(ok==false)
        {
            break;
        }
    }
    cout<<"\n";
}    
int main()
{
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}