A - AUS

statements

#include <bits/stdc++.h>
#define int long long
using namespace std;
int f[30];
int find(int x){
    if(f[x]!=x) f[x]=find(f[x]);
    return f[x];
}
void merge(int x,int y){
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy) f[fx]=fy;
}
void solve(){
    string s1,s2,s3;
    cin>>s1>>s2>>s3;
    int len1=s1.length();
    int len2=s2.length();
    int len3=s3.length();
    if(len1==len2&&len2==len3){
        for(int i=1;i<=26;i++) f[i]=i;
        for(int i=0;i<len1;i++)
            merge(s1[i]-'a'+1,s2[i]-'a'+1);
        bool flag=0;
        for(int i=0;i<len1;i++){
            int fx=find(s1[i]-'a'+1);
            int fy=find(s3[i]-'a'+1);
            if(fx!=fy) flag=1;
        }
        if(flag) cout<<"YES\n";
        else cout<<"NO\n";
    }
    else{
        if(len1==len2) cout<<"YES\n";
        else cout<<"NO\n";
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}

K - Kind of Bingo

statements

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int val[N];
int cnt[N];
int n,m,k;
bool check(int limit){
    int now=0;
    for(int i=1;i<=limit;i++){
        int b=(val[i]-1)/m+1;
        cnt[b]++;
        now=max(now,cnt[b]);
    }
    for(int i=1;i<=limit;i++){
        int b=(val[i]-1)/m+1;
        cnt[b]--;
    }
    return m-now<=k;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m>>k;
        for(int i=1;i<=n*m;i++) cin>>val[i];
        int l=m,r=n*m;
        int ans;
        while(l<=r){
            int mid=(l+r)>>1;
            if(check(mid)) ans=mid,r=mid-1;
            else l=mid+1; 
        }
        cout<<ans<<'\n';
    }
    return 0;
}

Elevator II

statements

#include <iostream>
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct e{
    int l,r;
    int id;
};
bool cmpl(e a,e b){
    if(a.l==b.l) return a.r>b.r;
    else return a.l<b.l;
}
bool cmpr(e a,e b){
    if(a.r==b.r) return a.l<b.l;
    else return a.r>b.r;
}
void solve(){
    int n,f,ans=0;
    cin>>n>>f;
    vector<e>a(n+1);
    vector<bool>vis(n+1,false);
    for(int i=1;i<=n;i++){
        cin>>a[i].l>>a[i].r;
        a[i].id=i;
        ans+=a[i].r-a[i].l;
    }
    vector<int>re;
    sort(a.begin()+1,a.end(),cmpl);
    for(int i=1;i<=n;i++){
        if(a[i].r>=f){
            if(a[i].l<=f){
                f=a[i].r;
            }
            else {
                ans+=a[i].l-f;
                f=a[i].r;
            }
            re.push_back(a[i].id);
            vis[a[i].id]=true;
        }
    }
    cout<<ans<<"\n";
    for(int i=0;i<re.size();i++){
        cout<<re[i]<<" ";
    }
    sort(a.begin()+1,a.end(),cmpr);
    for(int i=1;i<=n;i++){
        if(vis[a[i].id]==false){
            cout<<a[i].id<<" ";
        }
    }
    cout<<"\n";
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

M - Make It Divisible

statements

solutions

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+10;
int a[N];
int n;
int arr[N];
int ls[N],rs[N];
int stk[N];
void build(){
   int top = 0;
   for (int i = 1; i <= n; i++) {
       int pos = top;
       while (pos > 0 && arr[stk[pos]] > arr[i]) {
           pos--;
       }
       if (pos > 0) {
           rs[stk[pos]] = i;
       }
       if (pos < top) {
           ls[i] = stk[pos + 1];
       }
       stk[++pos] = i;
       top = pos;
   }
}
bool dfs(int x) {
    if (x == 0) return true;
    // 左子树存在则左值必须被当前节点整除
    if (ls[x] && (arr[ls[x]] % arr[x] != 0)) return false;
    if (rs[x] && (arr[rs[x]] % arr[x] != 0)) return false;
    return dfs(ls[x]) && dfs(rs[x]);
}
bool check(int x){
    for(int i=1;i<=n;i++){
        arr[i]=a[i]+x;
        ls[i]=rs[i]=0;
    }
    build();
    return dfs(stk[1]); 
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int k;
        cin>>n>>k;
        for(int i=1;i<=n;i++) cin>>a[i];
        int g=0;
        for(int i=1;i<n;i++)
            g=__gcd(g,abs(a[i+1]-a[i]));
        if(g==0){
            cout<<k<<' '<<k*(k+1)/2<<'\n';
            continue ;
        }
        vector<int> factors;
        for(int i=1;i<=g/i;i++){
            if(g%i==0){
                factors.push_back(i);
                if(g/i!=i) factors.push_back(g/i);
            }
        }
        int ans1=0,ans2=0;
        int mn=*min_element(a+1,a+n+1);
        for(int d:factors){
            int x=d-mn;
            if(x<1||x>k) continue;
            if(check(x)) ans1++,ans2+=x;
        }
        cout<<ans1<<' '<<ans2<<'\n';
    }
    return 0;
}