1894)

A. Simple Design

暴力就行了 1e9跑不满的

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

void solve(){
    int x,k;
    cin>>x>>k;
    for(int i=x;i<=2e9;i++){
        int y=i;
        int sum=0;
        while(y){
            sum+=y%10;
            y/=10;
        }
        if(sum%k==0&&sum>=k){
            cout<<i<<endl;
            return;
        }
    }
}

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

B. Haunted House

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e5 + 10;
int re[N],pr[N];


void solve(){
    int n;
    string s;
    cin>>n>>s;
    reverse(s.begin(),s.end());
    deque<int> idx;
    for(int i=0;i<s.size();i++)
        if(s[i]=='0')idx.push_back(i);
    if(idx.empty()){
        for(int i=0;i<s.size();i++)
            cout<<-1<<" ";
        cout<<endl;
        return;
    }
    int ans=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='0'){
            idx.pop_front();
            cout<<ans<<" ";
        }else{
            if(idx.empty()){
                for(int j=i;j<s.size();j++)
                    cout<<-1<<" ";
                cout<<endl;
                return;
            }else{
                ans += idx[0] - i;
                s[idx[0]] = '1';
                idx.pop_front();
                cout<<ans<<" ";
            }
        }
    }
    cout<<endl;
}

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

C. Medium Design

有个结论: 最小值一定在1处或者在m处。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10;
int n,m;
int pre[N],rev[N];

void solve(){
    vector<int> p;
    cin>>n>>m;
    p.push_back(1);
    p.push_back(m);
    memset(pre,0,sizeof pre);
    memset(rev,0,sizeof rev);
    
    vector<pair<int,int>> x1(n);
    for(auto &[l,r]:x1){
        cin>>l>>r;
        p.push_back(l);
        p.push_back(r);
    }
    sort(p.begin(),p.end());

//    cout<<endl;
//    for(auto u:p) cout<<u<<" ";
//    cout<<endl;

    int idx=lower_bound(p.begin(),p.end(),m)-p.begin()+1;
    for(auto &[l,r]:x1){
        l=lower_bound(p.begin(),p.end(),l)-p.begin()+1;
        r=lower_bound(p.begin(),p.end(),r)-p.begin()+1;
        //cout<<l<<" "<<r<<endl;
    }

    for(auto [l,r]:x1){
        if(l>1){
            pre[l]++;
            pre[r+1]--;
        }
        if(r<idx){
            rev[l]++;
            rev[r+1]--;
        }
    }
    for(int i=1;i<=idx;i++){
        pre[i] += pre[i-1];
        rev[i] += rev[i-1];
    }
    int ans1=*max_element(pre+1,pre+1+idx);
    int ans2=*max_element(rev+1,rev+1+idx);
    cout<< max(ans1,ans2) <<endl;
}

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

D. Counting Rhyme

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int N = 1e6 + 10;
int a[N] , cnt[N];
int f[N]; //fi:gcd恰好为i的对数
bool vis[N];
int n;

void solve(){
    cin>>n;
    for(int i=0;i<=n;i++){
        vis[i]=false;
        f[i]=0;
        cnt[i]=0;
        a[i]=0;
    }
    int cx=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        cnt[a[i]]++;
        cx = max(cx , a[i]);
    }
    for(int i=1;i<=cx;i++)
        for(int j=2*i;j<=cx;j+=i)
            cnt[i] += cnt[j];
    for(int i=cx;i>0;i--){
        f[i] = cnt[i]*(cnt[i]-1)/2;
        for(int j=2*i;j<=cx;j+=i)
            f[i] -= f[j];
    }
    for(int i=1;i<=cx;i++)
        for(int j=a[i];j<=cx;j+=a[i]) vis[j]=true;
    long long ans=0;
    for(int i=1;i<=cx;i++)
        if(!vis[i]) ans+=f[i];
    cout<<ans<<endl;
}

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