4th

· · 题解

简化题意

Mirko 和 Slavko 轮流拿走一个长度为 n 的字符串内的字母放入自己的字符串中。Mirko 先手，但每次只取字符串最右侧的字母；Slavko 后手，可以随意取剩余的字母。

当字符串中的字母被取完后，若 Slavko 的字符串的字典序小于 Mirko 的字符串，则输出 DA 和 Slavko 的字符串；否则，则输出 NE 和 Slavko 的字符串。

思路分析

Mirko 拿字母的方式固定，可以放在一边，Slavko 可以随意取为被拿走的字母，要使 Slavko 的字符串字典序小，考虑贪心，每次取走取剩余的最小字母；当最小字母有多个时，取最右侧的，以保证 Mirko 取走的字母较大。

每次 Slavko 取字母时都要取最小的，考虑到 n\leqslant2\times10^5，每次遍历整个字符串绝对会超时，又因为字符串中只含小写字母，我们可以考虑用 vector 存储每个字母出现的位置，遍历时从字母 a 开始遍历，寻找未被取走的最靠右的字母即可。

如果还是会超时怎么办？我们可以考虑加一个小小的剪枝，在遍历后将已遍历过的部分删去。

本题中最难的部分解决了，其它部分代码注释有详解，就不再赘述了。

思路呈现

代码呈现

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<queue>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<bitset>
#include<cctype>
#include<cstdlib>
#include<functional>
#include<istream>
#include<sstream>
#define int long long 
using namespace std;
const int N=300000,M=30,inf=0x3f3f3f3f3f3f3f,mod=10007;
bool vis[N];//记录字母是否被拿走 
vector<int>a[M];//记录每个字母出现的位置 
signed main()
{
    memset(vis,0,sizeof(vis));//初始都没有被拿走 
    int n;
    bool book;
    string s,mir,sla;
    scanf("%lld",&n);
    cin>>s;
    for(int i=0;i<n;i++)//记录每个字母出现的位置
        a[s[i]-'a'].push_back(i);
    while(mir.size()+sla.size()<s.size())
    {
        while(vis[n-1]==true)//如果已被拿走，向前扫 
            n--;
        mir+=s[n-1];//Mirko先手，拿走最右侧字母
        vis[n-1]=true;//标记已拿
        book=false;//辅助变量 
        for(int i=0;i<26;i++)//寻找剩下的最小的且最靠右的字母
        {
            if(!a[i].empty())
                for(int j=a[i].size()-1;j>=0;j--)//倒着遍历，先考虑拿最右侧的（贪心）
                    if(vis[a[i][j]]==false)//还没有拿走的最小的最靠右的字母 
                    {
                        sla+='a'+i;//Slavko后手，拿走剩下的最小的且最靠右的字母
                        vis[a[i][j]]=true;//标记已拿
                        a[i].erase(a[i].begin()+j);//因为已经拿走的是该字母中位置最靠右的，所以删去它及其后面的 
                        book=true;
                        break;
                    } 
            if(book==true)
                break; 
        }
    }
    if(mir<=sla)//直接比较两字符串大小，即比较字符串字典序 
        printf("NE\n");
    else
        printf("DA\n");
    cout<<sla;
    return 0;
}