SMU Spring 2023 Trial Contest Round 10

SMU Spring 2023 Trial Contest Round 10

 A - Remove Duplicates

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=2e2+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-6;
typedef long long ll;

int n,a[55],b[1005];
vector<int>ans;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=0;i<n;++i)cin>>a[i];
    for(int i=n-1;i>=0;--i){
        if(b[a[i]]==0)ans.push_back(a[i]);
        b[a[i]]++;
    }
    cout<<ans.size()<<'\n';
    for(int i=ans.size()-1;i>=0;--i)cout<<ans[i]<<' ';
    return 0;
}

B - File Name

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=2e2+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-6;
typedef long long ll;

int n,ans;
string s;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    cin>>s;
    int a=0;
    for(int i=0;i<n;++i){
        if(s[i]=='x'){
            a++;
        }
        else{
            if(a>=3){
                ans+=(a-2);
            }
            a=0;
        }
    }
    if(a>=3)ans+=(a-2);
    cout<<ans;
    return 0;
}

 C - Letters

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-6;
typedef long long ll;

ll n,m,a[N];
vector<ll>ve;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;++i){
        cin>>a[i];
        if(i)a[i]+=a[i-1];
    }
    ll x;
    //for(int i=0;i<n;++i)cout<<a[i]<<' ';cout<<'\n';
    for(int i=0;i<m;++i){
        cin>>x;
        int p= lower_bound(a,a+n,x)-a;
        p--;
        if(p>=0){
            x-=a[p];
        }
        cout<<p+2<<' '<<x<<'\n';
    }
    return 0;
}

D - Almost Arithmetic Progression

思路：维护成等差数列，确定a1和d后即可确定等差数列，根据a1和a2确立等差数列的情况有9种，遍历每一种求最小值，若每种都不成立则无

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-6;
typedef long long ll;

ll n,a[N],b[3]={-1,0,1},ans=-1;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    if(n<=2)cout<<0;
    else{
        ll res;
        for(int i=0;i<3;++i){
            for(int j=0;j<3;++j){
                res=0;
                ll aa=a[1]+b[i],bb=a[2]+b[j];
                ll d=bb-aa,a1=aa;
                res+=abs(b[i])+abs(b[j]);
                bool ok=true;
                for(int k=3;k<=n;++k){
                    ll x=a1+(k-1)*d;
                    ll dd=abs(a[k]-x);
                    if(dd>1){
                        ok=false;
                        break;
                    }
                    res+=dd;
                }
                if(ok&&(res<ans||ans==-1))ans=res;
            }
        }
        cout<<ans;
    }

    return 0;
}

E - Bus Video System

思路：x0表示最初人数，由x和y的关系可以得出x0的取值范围为-Si<=x0<=w-Si，Si表示前i个数前缀和，且x0的取值范围为0~w，

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=1e3+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-6;
typedef long long ll;

ll n,w,a[N];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>w;
    ll ma,x,s=0,mi;
    for(int i=0;i<n;++i){
        cin>>x;
        s+=x;
        if(i==0)ma=w-s,mi=-s;
        else{
            ma=min(w-s,ma),mi=max(-s,mi);
        }
    }
    if(ma>=mi&&ma>=0&&mi<=w){
        if(mi<0)mi=0;
        if(ma>w)ma=w;
        cout<<ma-mi+1;
    }
    else cout<<0;
    return 0;
}

F - Mentors

思路：存编号和能力，按能力升序排，存下每个编号的徒弟数，对矛盾的处理：能力大的一方徒弟数减一

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-6;
typedef long long ll;

int n,k,a[N],b[N];
struct E{
    int id,s;
    bool operator<(const E&e)const {
        if(s==e.s)return id<e.id;
        return s<e.s;
    }
}g[N];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=0;i<n;++i){
        cin>>a[i];
        g[i].id=i,g[i].s=a[i];
    }
    sort(g,g+n);
    for(int i=0;i<n;++i){
        int t=i;
        while(g[i].s==g[i+1].s&&i+1<n){
            b[g[i].id]=t;
            ++i;
        }
        b[g[i].id]=t;
    }
    for(int i=0,x,y;i<k;++i){
        cin>>x>>y;
        if(a[x-1]>a[y-1]){
            b[x-1]--;
        }
        else if(a[x-1]<a[y-1]){
            b[y-1]--;
        }
    }
    for(int i=0;i<n;++i)cout<<b[i]<<' ';
    return 0;
}

G - Petya's Exams

思路：对考试时间排序，每次测试从发布时间开始遍历，找到 准备的时长 天，并且这些天没有其他任务，若找不全则-1

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=2e2+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-6;
typedef long long ll;

int n,m,ans[N];
struct E{
    int l,r,c,id;
}g[N];
bool cmp(E a,E b){
    return a.r<b.r;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        cin>>g[i].l>>g[i].r>>g[i].c;
        g[i].id=i;
        ans[g[i].r]=m+1;
    }
    sort(g+1,g+m+1,cmp);
    for(int i=1;i<=m;++i){
        int cnt=0;
        for(int j=g[i].l;j<=g[i].r;++j){
            if(!ans[j]){
                ans[j]=g[i].id;
                cnt++;
            }
            if(cnt==g[i].c)break;
        }
        if(cnt!=g[i].c){
            cout<<-1;
            return 0;
        }
    }
    for(int i=1;i<=n;++i)cout<<ans[i]<<' ';
    return 0;
}