Codeforces Global Round 21 C D E

Codeforces Global Round 21 C D E

C. Fishingprince Plays With Array

• 将A、B数组中是$m$倍数的数全部展开，然后比较A、B数组是否相等。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
//Edit Author: Snow
const int N = 5e4+10;
int a[N];
int b[N];
void cf(){
    
    int n,m;
    cin>>n>>m;
    vector<pair<int,int>>A,B;
    for(int i=1;i<=n;i++){
    
        int x;
        cin>>x;
        int res=1;
        while(x%m==0){
    
            res*=m;
            x/=m;
        }
        if(A.empty()||A.back().first!=x){
    
            A.push_back({
    x,res});
        }
        else{
    
            A.back().second+=res;
        }
    }
    int k;
    cin>>k;
    for(int i=1;i<=k;i++){
    
        int x;
        cin>>x;
        int res=1;
        while(x%m==0){
    
            res*=m;
            x/=m;
        }
        if(B.empty()||B.back().first!=x){
    
            B.push_back({
    x,res});
        }
        else{
    
            B.back().second+=res;
        }
    }
    cout<<((A==B)?"YES":"NO")<<endl;
} 
signed main(){
    
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
    
        cf();
    }
}

D. Permutation Graph

• 分治、递归。 本题采用贪心，如果从点$i$进行跳跃，那么$i$能跳到最远的$j$就是最优策略。例如 3 4 5 可以$3$ ~ $4$ ~ $5$或者$3$直接跳到$5$。那么$3$直接跳$5$是最优策略。那么本题的解决思路就是找到 $1$~$n$ 中最大的数下标$i$然后递归 $1$~$i$ 和 $i$~$n$。区间最大值和最小值可以通过ST或者线段树解决。

代码：ST表

#include<bits/stdc++.h>
using namespace std;
#define int long long
//Edit Author: Snow
const int N = 2.5e5+10;
int a[N],pos[N];
int jump;
int n;
int st[N][20];
int st2[N][20];
void make_st(){
    
    int k=__lg(n);
    for(int i=1;i<=n;i++)st[i][0]=a[i],st2[i][0]=a[i];
    for(int i=1;i<=k;i++){
    
        for(int j=1;j+(1<<i)-1<=n;j++){
    
            st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
            st2[j][i]=min(st2[j][i-1],st2[j+(1<<(i-1))][i-1]);
        }
    }
}
int query_max(int l,int r){
    
    int k=__lg(r-l+1);
    return max(st[l][k],st[r-(1<<k)+1][k]);
}
int query_min(int l,int r){
    
    int k=__lg(r-l+1);
    return min(st2[l][k],st2[r-(1<<k)+1][k]);
}
int dfs(int l,int r){
    
    if(l==r)return 0;
    if(l+1==r)return 1;
    int maxv=query_max(l,r);
    int minv=query_min(l,r);
    int L=pos[maxv];
    int R=pos[minv];
    if(L<R)swap(L,R);
    jump++;
    return dfs(l,L)+1+dfs(R,r);
}
void cf(){
    
    jump=0;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],pos[a[i]]=i;
    //ST
    make_st();
    cout<<dfs(1,n)<<endl;
} 
signed main(){
    
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
    
        cf();
    }
}

代码：线段树

#include<bits/stdc++.h>
using namespace std;
#define int long long
//Edit Author: Snow
const int N = 2.5e5+10;
int n;
int a[N];
int pos[N];
struct Node{
    
    int l,r,minv,maxv;
}tr[N*4];
void pushup(int u){
    
    tr[u].minv=min(tr[u<<1].minv,tr[u<<1|1].minv);
    tr[u].maxv=max(tr[u<<1].maxv,tr[u<<1|1].maxv);
}
void build(int u,int l,int r){
    
    tr[u].l=l,tr[u].r=r;
    if(l==r){
    
        tr[u].minv=tr[u].maxv=a[r];
        return ;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}
int query_max(int u,int l,int r){
    
    if(tr[u].l>=l&&tr[u].r<=r){
    
        return tr[u].maxv;   
    }
    int mid=tr[u].l+tr[u].r>>1;
    int v=0;
    if(l<=mid){
    
        v=query_max(u<<1,l,r);
    }
    if(r>mid){
    
        v=max(v,query_max(u<<1|1,l,r));
    }
    return v;
}
int query_min(int u,int l,int r){
    
    if(tr[u].l>=l&&tr[u].r<=r){
    
        return tr[u].minv;   
    }
    int mid=tr[u].l+tr[u].r>>1;
    int v=2e6;
    if(l<=mid){
    
        v=query_min(u<<1,l,r);
    }
    if(r>mid){
    
        v=min(v,query_min(u<<1|1,l,r));
    }
    return v;
}
int DFS(int l,int r){
    
    if(l+1==r)return 1;
    if(l>=r)return 0;
    int maxv=query_max(1,l,r);
    int minv=query_min(1,l,r);
    int L=pos[maxv];
    int R=pos[minv];
    if(L>R)swap(L,R);
    return DFS(l,L)+1+DFS(R,r);
}
void cf(){
    
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],pos[a[i]]=i;
    if(n==1)cout<<0<<endl;
    else{
    
        build(1,1,n);
        cout<<DFS(1,n)<<endl;
    }
} 
signed main(){
    
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
    
        cf();
    }
}

E. Placing Jinas

• 类杨辉三角的题，将玩具从$(0,0)$开始分裂打表，很容易发现点$(i,j)$是一个$C(i+j,i)$的组合数，容易观察出点$(0,0)$与$(i+j,i)$构成的矩形内所有方案数等于$C(i+1+j+1,i+1)-1$。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
//Edit Author: Snow
const int N = 2e5+10;
int a[N];
const int M = 1e6+10;
int fact[M];
int infact[M];
const int mod=1e9+7;
int qmi(int a,int b,int c){
    
    int res=1;
    while(b){
    
        if(b&1)res=res*a%c;
        a=a*a%c;
        b>>=1;
    }
    return res;
}
int C(int a,int b){
    
    return fact[a]*infact[a-b]%mod*infact[b]%mod;
}
void cf(){
    
    int n;
    cin>>n;
    n++;
    for(int i=1;i<=n;i++)cin>>a[i];
    while(n&&a[n]==0)n--;
    int sum=0;
    for(int i=n;i>=1;i--){
    
        if(i==n){
    
            sum=(sum+C(i+a[i],i)-1)%mod;
        }
        else if(a[i]!=a[i+1]){
    
            sum=(sum+C(i+a[i],i)-C(i+a[i+1],i)+mod)%mod;
        }
    }
    cout<<sum<<endl;
} 
signed main(){
    
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    fact[0]=1;
    infact[0]=1;
    for(int i=1;i<M;i++){
    
        fact[i]=fact[i-1]*i%mod;
        infact[i]=infact[i-1]*qmi(i,mod-2,mod)%mod;//逆元
    }
    // cin>>t;
    while(t--){
    
        cf();
    }
}