9.26 SMU Autumn 2023 Round 5-526互联

SMU Autumn 2023 Round 5

A - Everyone Loves to Sleep

思路：将小于睡觉时间的闹钟加24：00，找到最小的时间min，答案即为min-睡觉时间

#include<bits/stdc++.h>
using namespace std;
//#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve(){
    PII st;
    int n;cin>>n>>st.first>>st.second;
    vector<PII>ve(n);
    PII ans;
    ans={50,50};

    for(int i=0;i<n;++i){
        cin>>ve[i].first>>ve[i].second;
        if(ve[i]<st){
            ve[i].first+=24;
        }
        ans=min(ans,ve[i]);
    }
    if(ans.second<st.second)ans.second+=60,ans.first--;
    cout<<ans.first-st.first<<' '<<ans.second-st.second<<'\n';

}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

View Code

B - Minimum Varied Number

思路：由于每一位的数不一样，且需要位数尽可能少，那直接从最大的开始取，直到凑够

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve(){
    int n;cin>>n;
    string s;
    for(int i=9;n&&i>=1;--i){
        s.push_back('0'+min(n,i));
        n-=min(n,i);
    }
    std::reverse(s.begin(), s.end());
    cout<<s<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

View Code

C - Color with Occurrences

思路：由于每个串需要是原串的子串，且串的个数最多为10，那么把每个串能够匹配原串的左右边界位置以及该串的编号统计后排序，贪心的覆盖整个串，对于没被覆盖的起点l，找到一个si，使得si.l<=l且si.r最大，统计需要的个数，若最后不能覆盖完，则-1

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e3+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

struct E{
    int l,r,id;
    bool operator<(const E &e)const{
        if(e.l!=l)return l<e.l;
        return r<e.r;
    }
};
void solve(){
    string s;
    int n,len;
    cin>>s>>n;len=s.size();
    s.insert(s.begin(),' ');
    vector<E>f;
    string a;
    auto P=[len,s](int st,string x){
        if(x.size()>len-st+1)return false;
        for(int i=st,j=0;j<x.size();++j,++i){
            if(x[j]!=s[i])return false;
        }
        return true;
    };
    for(int i=1;i<=n;++i){
        cin>>a;
        for(int j=1;j<=len;++j){
            if(P(j,a)){
                f.push_back((E){j,j+(int)a.size()-1,i});
            }
        }
    }
    sort(f.begin(),f.end());
//    cout<<f.size()<<'\n';
//    for(auto v:f)cout<<v.id<<':'<<v.l<<' '<<v.r<<'\n';
    int st=1;
    vector<PII>ans;
    bool ok=false;
    for(int i=0;i<f.size();++i){
        int j=i,p=0,ma=-INF;
        while(j<f.size()&&f[j].l<=st){
            if(f[j].r>ma){
                ma=f[j].r;
                p=j;
            }
            j++;
        }
        if(ma<st)break;
        ans.push_back({f[p].id,f[p].l});
        st=ma+1;
        i=j-1;
        if(st>len){
            ok=true;break;
        }

    }
    if(ok){
        cout<<ans.size()<<'\n';
        for(auto v:ans)cout<<v.first<<' '<<v.second<<'\n';
    }else cout<<"-1\n";
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

View Code

D - Add Modulo 10

思路：多画几个例子可以发现，将数分成了两种，第一种：能整除5的情况，最后一位为5的数都能转化为最后一位为0的数，且之后不会再转化；

第二种：最后一位为：1->2->4->8->6->2->4...，每个循环之间的数刚好差20，那么将数的最后一位转化为同一个数，在判断所有数是不是都相差20

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve(){
    int n;cin>>n;
    bool ok1=true;
    vector<int>f;
    vector<int>ve(n+1);
    for(int i=1;i<=n;++i){
        cin>>ve[i];
        if(ve[i]%5==0&&ve[i]%10!=0)ve[i]+=5;
        if(i>1&&ve[i]!=ve[i-1])ok1=false;
    }
    if(ok1||n==1){
        cout<<"Yes\n";return ;
    }
    for(int i=1;i<=n;++i){
        if(ve[i]%10==0){
            cout<<"No\n";return ;
        }
        int p=ve[i];
        while(p%10!=6){
            p+=p%10;
        }
        f.push_back(p);
    }
    for(int i=1;i<f.size();++i){
        if(abs(f[i]-f[0])%20!=0){
            cout<<"No\n";return ;
        }
    }
    cout<<"Yes\n";
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

View Code

G - Make Them Equal

思路：由于数的范围为1e3，可以先预处理出转化成所有数需要的次数；那么问题就变成01背包问题；可能会t，循环的k可以减少为min（需要的总次数，k）

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e3+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;
vector<int>ve(N+5,INF);
void init(){
    ve[1]=0;
    for(int i=1;i<N;++i){
        for(int j=1;j<=i;++j){
            int x=i/j;
            if(i+x>N)continue;
            ve[i+x]=min(ve[i+x],ve[i]+1);
            if(x==1)break;
        }
    }
}
void solve(){
    int n,k,s=0;cin>>n>>k;
    vector<int>b(n+1),v(n+1),w(n+1);
    for(int i=1;i<=n;++i){
        cin>>b[i];
        v[i]=ve[b[i]];s+=v[i];
    }
    for(int i=1;i<=n;++i)cin>>w[i];
    vector<int>f(min(s,k)+1);
    for(int i=1;i<=n;++i){
        for(int j=min(s,k);j>=v[i];--j)
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    }
    cout<<f[min(s,k)]<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    init();
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

View Code

H - Kill the Monster

思路：k的范围不大，直接暴力枚举k即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e3+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;


void solve(){
    int hc,dc,hm,dm,k,w,a;
    cin>>hc>>dc>>hm>>dm>>k>>w>>a;
    bool ok=false;
    for(int i=0;i<=k;++i){
        int h=hc+i*a,d=dc+(k-i)*w;
        int xc=(hm+d-1)/d,xm=(h+dm-1)/dm;
//        cout<<i<<":"<<h<<' '<<d<<"--"<<xc<<' '<<xm<<'\n';
        if(xc<=xm){
            ok=true;break;
        }
    }
    if(ok)cout<<"YES\n";
    else cout<<"NO\n";
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

View Code

I - Div. 7

思路：暴力枚举与x位数相同的所有数，取最小的替换数

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve(){
    int n;cin>>n;
    if(n%7==0)cout<<n<<'\n';
    else{
        int cnt=4;
        auto P=[](int a,int b){
            int res=0;
            for(int i=0;i<3;++i){
                if(a%10!=b%10)res++;
                a/=10,b/=10;
            }
            return res;
        };
        int ans;
        int p=n,l=0;
        while(p){
            l++;p/=10;
        }
        int st=pow(10,l-1);
        while(st%7)st++;
        for(int i=st;i<pow(10,l);i+=7){
            int c=P(i,n);
            if(c<cnt){
                cnt=c;ans=i;
            }
            if(cnt==1)break;
        }
        cout<<ans<<'\n';
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

View Code

autumn round 2023 smu

autumn round 9.26 2023

contest summer round 2023

9.26

autumn_c

codeforces round 2023 div2