[COCI2010-2011#2] IGRA 题解

wzb13958817049 · 2023-11-12 08:40:43 · 题解

思路

贪心，因为 Mirko 每次只会拿最后一个单词，所以 Slavko 要想赢就要拿剩下单词中字典序最小的且排在越后面越好。这样我们可以很好的想到暴力，去拿 O(n) 的时间复杂度去跑一遍剩余序列找最小且最后的字母。但是只有 40 分，因此就可以想到把所有字母的位置保存在数组中，从而去寻找最小且最后的字母。

#include<bits/stdc++.h>
using namespace std;
long long n,j;
string a,ans1,ans2;//ans1表示Slavko拿到的最美丽单词
//ans2表示Mirko拿到的单词
vector<long long> mp[27];
bool vis[200005];//该位置是否被访问过
int main(){
    cin>>n>>a;
    for(int i=0;i<a.size();i++) mp[a[i]-'a'+1].push_back(i);//把字母保存到vector中
    j=n-1;//最后一个字母的下标
    while(ans1.size()+ans2.size()<a.size()){
        while(vis[j]==1 && j!=0) j--;//Mirko先手
        ans2+=a[j];vis[j]=1;//记录下标为j的字母已经被拿走
        bool falg=0;
        for(int i=1;i<=26;i++){//从小到大遍历，找到第一个有的字母(最小)
            for(int k=mp[i].size()-1;k>=0;k--){//从后往前遍历因为越后面越好
                if(vis[mp[i][k]]==0){//如果没被拿走
                    ans1+='a'+i-1;
                    vis[mp[i][k]]=1;//标记
                    mp[i].erase(mp[i].begin()+k);//删除
                    falg=1;
                    break;
                }
            }
            if(falg==1) break;
        }   
    }
    if(ans1<ans2) cout<<"DA";
    else cout<<"NE";
    cout<<"\n"<<ans1;//输出答案
    return 0;   
}

但是因为代码太朴素，还是会 T，那怎么办呢？剪枝，记录上一次拿的字母，下次从上一个字母开始访问，可以大大的省时间。

ACcode

#include<bits/stdc++.h>
using namespace std;
long long n,j,kkk;
string a,ans1,ans2;
vector<long long> mp[27];
bool vis[200005];
int main(){
    cin>>n>>a;
    for(int i=0;i<a.size();i++) mp[a[i]-'a'+1].push_back(i);
    j=n-1;
    while(ans1.size()+ans2.size()<a.size()){
        while(vis[j]==1 && j!=0) j--;
        ans2+=a[j];vis[j]=1;
        bool falg=0;
        for(int i=kkk;i<=26;i++){
            for(int k=mp[i].size()-1;k>=0;k--){
                if(vis[mp[i][k]]==0){
                    ans1+='a'+i-1;
                    vis[mp[i][k]]=1;
                    mp[i].erase(mp[i].begin()+k);
                    kkk=i;
                    falg=1;
                    break;
                }
            }
            if(falg==1) break;
        }   
    }
    if(ans1<ans2) cout<<"DA";
    else cout<<"NE";
    cout<<"\n"<<ans1;
    return 0;   
}