H. Another Goose Goose Duck Problem

The duck has a killing skill which its cool down can be arbitrary chosen between [l,r], and he meets a goose every b seconds, how much time can the duck kill exactly k geese?

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int l,r,b,k;
    cin>>l>>r>>b>>k;
    cout<<(l+b-1)/b*k*b<<'\n';
    return 0;
}

K. Maximum GCD

You have an array ai. You can do any number of the following operation
on the array: Choose an element ai and a positive integer x, change ai into
(ai mod x). 0 cannot appear in the array after any operation. Maximize
the GCD of the array after the operations

能变为之间任意一个数。

solutions

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int a[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    vector<int> factors;
    int mn=*min_element(a+1,a+n+1);
    for(int i=1;i<=mn/i;i++){
        if(mn%i==0){
            factors.push_back(i);
            if(mn/i!=i) factors.push_back(mn/i);
        }
    }
    sort(factors.begin(),factors.end(),greater<int>());
    int ans=(mn-1)/2;
    auto check=[&](int m){
        for(int i=1;i<=n;i++){
            if(!(m<=(a[i]-1)/2||a[i]%m==0)) return 0;
        }
        return 1;
    };
    for(auto factor:factors){
        if(factor<ans) break;
        if(check(factor)) ans=factor; 
    }
    cout<<ans<<'\n';
    return 0;
}

A - TreeScript

Given a tree of size n, you need to create nodes such that just before you create i, the pi must be still in a register, find the minimum number of registers needed.

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int to[N<<1],ne[N<<1],h[N],idx=0;
void add(int a,int b){
    to[++idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
}
int dp[N];
void dfs(int u){
    int mx=0,smx=0;
    for(int i=h[u];~i;i=ne[i]){
        int v=to[i];
        dfs(v);
        if(dp[v]>=mx) smx=mx,mx=dp[v];
        else if(dp[v]>smx) smx=dp[v];
    }
    // cout<<mx<<' '<<smx<<'\n';
    dp[u]=max(mx,smx+1);
    // cout<<dp[u]<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) h[i]=-1,dp[i]=0;
        for(int i=1;i<=n;i++){
            int fa;
            cin>>fa;
            if(fa) add(fa,i);
        }
        dfs(1);
        cout<<dp[1]<<'\n';
    }
    return 0;
}

L. Delete Permutation

Given a permutation a, answer whether you can turn it into another
sequence q by performing the following operations: Choose an interval of
length li and delete the maximum element

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,m,k;
struct BIT{
    int tr[N];
    int lowbit(int x){return x&(-x);}
    void add(int x,int val){
        for(int i=x;i<=n;i+=lowbit(i))
            tr[i]+=val;
    }
    int query(int x){
        int res=0;
        for(int i=x;i>=1;i-=lowbit(i))
            res+=tr[i];
        return res;
    }
    void clear(){
        for(int i=1;i<=n;i++) tr[i]=0;
    }
}bit;
int a[N],b[N],pos[N],vis[N];//vis[i]为1表示需要保留
void solve(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pos[a[i]]=i;
        vis[i]=0;
    }
    for(int i=1;i<=m;i++){
        cin>>b[i];
        vis[b[i]]=1;
    }
    multiset<int> stlen;
    for(int i=1;i<=k;i++){
        int len;
        cin>>len;
        stlen.insert(len);
    }
    //判断b是否是a的子序列
    int j=1;
    for(int i=1;i<=n&&j<=m;++i) {
        if (a[i]==b[j]) ++j;
    }
    if(j<=m){cout<<"NO\n"; return; }
    set<int> stbig;
    bit.clear();
    for(int i=1;i<=n;i++) bit.add(i,1);
    stbig.insert(0);
    stbig.insert(n+1);
    for(int i=n;i>=1;i--){
        if(vis[i]){
            stbig.insert(pos[i]);
            continue ;
        }
        set<int>::iterator it=stbig.lower_bound(pos[i]);
        int l=*(prev(it)),r=*it;
        int len=bit.query(r-1)-bit.query(l);
        multiset<int>::iterator it2=stlen.upper_bound(len);
        bit.add(pos[i],-1);
        if(it2==stlen.begin()){
            cout<<"NO\n";
            return ;
        }
        else stlen.erase(prev(it2));
    }
    cout<<"YES\n";
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}

E. Goose, Goose, DUCK?