9/15越努力越幸运-思维赛(2)-蒲公英云

9/15越努力越幸运-思维赛(2)

F.CodeForces - 999C

题意：给一个字符串，k次操作，每次操作删除最左边字典序最小的字母；

解：统计所有字母的个数，从’a’到’z’，用k-每个字母的个数，找到不能删除的那个字母，或者不能完全删除的那个字母；

遍历字母串，不删的直接输出，删的continue；特别处理一下不能完全删除的部分，用cnt来记录不能完全删除那个字母的个数；

用vis来标记那个位置；然后输出即可（可能表述不对，看代码咯~）

#include <bits/stdc++.h>
using namespace std;
const int MAXN=4e5+10;
const int INF=0x3f3f3f3f;
typedef long long ll;
bool vis[MAXN];
int num[30];
int main(){
    ios::sync_with_stdio(false);
    int n,k;
    string s;
    cin>>n>>k>>s;
    for(int i=0;i<n;i++){
        num[s[i]-'a']++;
    }
    if(k>=n)cout<<endl;
    else {
        int sum=0,cnt=0;
        int flag=0;
        for(int i=0;i<26;i++){
            sum+=num[i];
            if(sum>=k){
                flag=i;break;
            }
        }
        if(sum==k){
            for(int i=0;i<n;i++)
                if((s[i]-'a')>flag)
                cout<<s[i];
            cout<<endl;
        }
        else {
            cnt=sum-k;
            for(int i=n-1;i>=0;i--){
                if((s[i]-'a')==flag){
                    vis[i]=true;
                    cnt--;
                }
                if(cnt==0)break;
            }
            for(int i=0;i<n;i++){
                if((s[i]-'a')>flag||vis[i])cout<<s[i];
            }
            cout<<endl;
        }
    }
    return 0;
}

E.CodeForces - 1005B

题意：给两个字符串：s和t；每次只能删除字符串最左边的一个字符，求最少删掉多少个能让两个字符串相等（两个字符串都能删）

解：求最少能删掉的个数==所有个数-最终两个字符串相等个数*2

所以只要求最终两个字符串相等的长度，又因为每次只能删掉最左边的一个，所有从后往前遍历，s[i]==t[j]，对答案的贡献+2；不相等直接退出；

#include <bits/stdc++.h>
using namespace std;
const int MAXN=2e5+10;
const int INF=0x3f3f3f3f;
typedef long long ll;
int main(){
    ios::sync_with_stdio(false);
    string s,t;
    cin>>s>>t;
    int len1=s.size();
    int len2=t.size();
    int l=len1-1,r=len2-1;
    //cout<<l<<' '<<r<<endl;
    int ans=0;
    while(l>=0&&r>=0&&s[l]==t[r]){
        ans++;
        l--,r--;
    }
    //cout<<ans<<endl;
    cout<<len1+len2-ans*2<<endl;
    return 0;
}

D.CodeForces - 999B

题意：给一个长度为n字符串，让你解密；
加密规则：设d为n的因子，每次反转字符串[1-d]；因子从n开始一直到1
解：解密—也是反转字符串，因子从1开始一直到n；
用了vector的翻转；

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
typedef long long ll;
int tot;
int divx[MAXN];
void get_div(int n){
    for(int i=2;i<=n;i++){
        if(n%i==0){
            divx[tot++]=i;
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    int n;
    string s;
    cin>>n>>s;
    get_div(n);
    //for(int i=0;i<tot;i++)cout<<divx[i]<<' ';cout<<endl;
    vector<char>vec;
    for(int i=0;i<tot;i++){
        for(int j=0;j<divx[i];j++){
            vec.push_back(s[j]);
        }
        reverse(vec.begin(),vec.end());
        for(int j=0;j<divx[i];j++){
            s[j]=vec[j];
        }
        vec.clear();
    }
    cout<<s<<endl;
    return 0;
}