[数据结构与算法][Acwing] 第 12 场周赛

前言

传送门 :

A.

题意 :
给定一个数组$a[]$,你需要将这个数组去重,使得每个数出现的位置是当前这个数出现的最后一次

思路 :
一开始以为就是简单的判重,结果发现不是,因为还需要考虑顺序

然后想了一会,感觉没有什么微妙的算法

因此只能用 $vector$和$pii$进行操作了,具体操作类似模拟

const int N = 1e3+10;
int  pos[N];
vector<pii> v;



void solve(){
	int n;cin>>n;
	
	memset(pos,0,sizeof pos);
	v.clear();
	
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		pos[x] = i;
	}
	
	for(int i=1;i<=N-1;i++){
		if(pos[i])
		v.pb({pos[i],i});
	}
	
	sort(all(v));
	cout<<v.size()<<endl;
	
	for(auto x : v){
		cout<<x.y<<" ";
	}
	cout<<endl;
	
	
}

B.

题意 :
给定$n,k$,和一个长度$n$的字符串
构造一个长度为$k$的字符串$t$使得$t\in s[a..z]$,并且$t$经可能的小

思路 :
这种题考虑分类讨论,之后使用二分查找$k$

具体操作看代码

void solve(){
    int n,k;cin>>n>>k;
    string s;cin>>s;



    mp.clear();
    vector<int> v;
    string ans="";


    for(auto x : s){
        int temp = x-'a';
        if(mp[temp]) continue;

        mp[temp] = 1;
        v.pb(temp);
    }
    sort(all(v));

    if(k>n){
        cout<<s;
        for(int i=0;i<k-n;i++)cout<<char(v[0]+'a');
        cout<<endl;
        return;
    }
        //小于的情况


    //考虑最后一位 如果不是最大 显然可以加
    if(s[k-1]!=v.back()+'a'){
        ans = s.substr(0,k-1);

        int pos = upper_bound(all(v),s[k-1]-'a') - v.begin();
        ans += v[pos]+'a';
        cout<<ans<<endl;
        return;
    }


    //否则只能在前面一位该
    int i = k-1;
    while(s[i]  == v.back()+'a') i -- ;
    int pos = upper_bound(all(v),s[i]-'a') - v.begin();
    ans = s.substr(0,i);

    ans+= v[pos]+'a';
    for(int j=1;j<=k-i-1;i++) ans+=v[0]+'a';
    cout<<ans<<endl;

}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖