Codeforces Global Round 21(A-E)

Catalog

A. NIT orz

B. NIT Destroys the Universe

C. Fishingprince Plays With Array

D. Permutation Graph

E. Placing Jinas

---

A. NIT orz

Problem - A - CodeforcesCodeforces. Programming competitions and contests, programming communityhttps://codeforces.com/contest/1696/problem/A

Sign in

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
void solve()
{ 
    int n,z,ans=0,x;
    cin>>n>>z;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        if((x|z)>=ans)
            ans=x|z;
    }
    cout<<ans<<"\n";
    return ;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

B. NIT Destroys the Universe

Problem - B - CodeforcesCodeforces. Programming competitions and contests, programming communityhttps://codeforces.com/contest/1696/problem/B

The question : Give you an array , We can operate : Select an interval , Let all the numbers in this interval become the smallest non negative numbers that have never appeared in this interval (mex). How many steps can I take to set this array all to 0.

Ideas : It takes only two steps at most to set all to 0, We started by choosing the entire array to become theirs mex, At this time, all the numbers will become a non 0 Number of numbers ( If not 0 Just one step , Directly all become 0). The second step is to select the whole array again , This is the time 0 There must be no , So it becomes 0.

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
int arr[100005];
void solve()
{
    int n,cnt=0;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>arr[i];
    if(arr[1]!=0)
        cnt++;
    for(int i=2;i<=n;i++)
        if(arr[i]>0&&arr[i-1]==0)
            cnt++; 
    if(cnt==0)
        cout<<"0";
    else if(cnt==1)
        cout<<"1";
    else
        cout<<"2";
    cout<<"\n";
    return ;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

C. Fishingprince Plays With Array

Problem - C - Codeforceshttps://codeforces.com/contest/1696/problem/C

The question : Give you two lengths and two arrays , There is also a limited length k, When an element in the array is k A multiple of the , You can divide it into k Divide this element by k The average of . Empathy , Yes k Connected by the same number of hours , Can be combined into one number , by k Multiply by the same number . Ask whether there is the first array to get the second array .

Ideas : Split the two arrays according to the first rule , See whether the two arrays after all splitting are the same , Pay attention to the data range , I use the structure to record the value and continuous number of numbers .

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#define int long long
using namespace std;
int a[50004],b[50004];
struct node
{
    int num,sum;
}anum[50004],bnum[50004];
void solve()
{

    int n,m,k,x,cnt;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        anum[i]={-1,0};
    }
    scanf("%lld",&k);
    for(int i=1;i<=k;i++)
    {
        scanf("%lld",&b[i]);
        bnum[i]={-1,0};
    }
    int tot1=1;
    for(int i=1;i<=n;i++)
    {
        x=a[i];
        cnt=1;
        while(x%m==0)
        {
            x/=m;
            cnt*=m;
        }
        if(x==anum[tot1].num)
            anum[tot1].sum+=cnt;
        else
        {
            if(anum[tot1].num!=-1)
                tot1++;
            anum[tot1].num=x;
            anum[tot1].sum=cnt;
        }
    }
    int tot2=1; 
    for(int i=1;i<=k;i++)
    {
        x=b[i];
        cnt=1;
        while(x%m==0)
        {
            x/=m;
            cnt*=m;
        }
        if(x==bnum[tot2].num)
            bnum[tot2].sum+=cnt;
        else
        {
            if(bnum[tot2].num!=-1)
                tot2++;
            bnum[tot2].num=x;
            bnum[tot2].sum=cnt;
        }
    }
    if(tot1!=tot2)
    {
        printf("NO\n");
        return ;
    }
    for(int i=1;i<=tot1;i++)
    {
        if(anum[i].num!=bnum[i].num||anum[i].sum!=bnum[i].sum)
        {
            printf("NO\n");
            return ;
        }
    }
    printf("YES\n");
    return ;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

D. Permutation Graph

Problem - D - Codeforceshttps://codeforces.com/contest/1696/problem/D

The question : Give an array , If meet i and j They are in the interval [a[i] a[i+1] ......a[j] ] The minimum and maximum of , Then there is an edge , Ask from 1 Go to No n At least how many steps are needed at the No .

Ideas : When you see the maximum and minimum of the interval, you must go directly st Table or segment tree . We first query the maximum and minimum values of the entire interval . If you find out , It means that the two points can be connected , After these two points are connected , The interval they surround does not need to be connected , Because the shortest path of this section has been found , Namely 1, Then perform the above operations recursively for the interval where the shortest path is not found .( Because the above operation requires us to know the position of the maximum and minimum value , So I have to open one pos Array record location )

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
using namespace std;
struct node
{
    int l,r,mx,mn;
}tr[4*250004];
int a[250004],pos[250004];
void build(int node,int l,int r)
{
    tr[node].l=l,tr[node].r=r;
    if(l==r)
    {
        tr[node].mx=a[l];
        tr[node].mn=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(node*2,l,mid);
    build(node*2+1,mid+1,r);
    tr[node].mx=max(tr[node*2].mx,tr[node*2+1].mx);
    tr[node].mn=min(tr[node*2].mn,tr[node*2+1].mn);
    return;
}
int querymx(int node,int l,int r)
{
    if(l<=tr[node].l&&tr[node].r<=r)
        return tr[node].mx;
    int mid=(tr[node].l+tr[node].r)>>1;
    int ans=-1e9;
    if(l<=mid)
        ans=max(ans,querymx(node*2,l,r));
    if(r>mid)
        ans=max(ans,querymx(node*2+1,l,r));
    return ans;
}
int querymn(int node,int l,int r)
{
    if(l<=tr[node].l&&tr[node].r<=r)
        return tr[node].mn;
    int mid=(tr[node].l+tr[node].r)>>1;
    int ans=1e9;
    if(l<=mid)
        ans=min(ans,querymn(node*2,l,r));
    if(r>mid)
        ans=min(ans,querymn(node*2+1,l,r));
    return ans;
}   
bool check(int l,int r)
{
    if(a[l]==querymn(1,l,r)&&a[r]==querymx(1,l,r))
        return true;
    else
        return false;
}
int dfs(int l,int r)
{
    if(l+1==r) return 1;
    if(l>=r) return 0;
    int L=pos[querymn(1,l,r)];
    int R=pos[querymx(1,l,r)];
    if(L>R)
    {
        int t=L;
        L=R;
        R=t;
    }
    return 1+dfs(l,L)+dfs(R,r);
}
void solve()
{
    int n; 
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),pos[a[i]]=i;
    if(n==1)
    {
        printf("0\n");
        return ;    
    }
    build(1,1,n);
    printf("%d\n",dfs(1,n));
    return ;   
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

E. Placing Jinas

Problem - E - Codeforceshttps://codeforces.com/contest/1696/problem/E

A wonderful Combinatorial Mathematics .

The question : Give an array that will not grow a, The first i Listed in <a[i] The grid of the row is white . There is a doll from (0,0) set out , It can also go down and right every time Two places at once . Every time I split up , You will take the doll in the lattice before your separation . Ask to finish the doll in the white lattice , How many dolls did you take .

Ideas : This , The number of dolls in each grid is equivalent to the number of paths to the current point , It is a classic combinatorial number model , For each point (x,y), The number of dolls you can get is Then the number of doll grids that can be taken on the white grid of each column is Then sum each column , The following is the detailed derivation process :

 

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#define int long long
const int mod=1e9+7;
using namespace std;
int fact[400005];
int infact[400005];
int a[400005];
int ksm(int x,int y)
{
    int res=1;
    while(y)
    {
        if(y&1)
            res=res*x%mod;
        y>>=1;
        x=x*x%mod;
    }
    return res;
}
void init()
{
    fact[0]=1;
    infact[0]=1;
    for(int i=1;i<=4e5+2;i++)
    {
        fact[i]=fact[i-1]*i%mod;
        infact[i]=infact[i-1]*ksm(i,mod-2)%mod;
    }
}
int c(int a,int b)
{
    if(a<b)
        return 0;
    return fact[a]*infact[b]%mod*infact[a-b]%mod;
}
void solve()
{ 
    int n;
    cin>>n;
    int ans=0;
    for(int i=0;i<=n;i++)
    {
        cin>>a[i];
        ans=(ans+c(a[i]+i,i+1))%mod;
    }
    cout<<ans<<"\n";
    return ;
}
signed main()
{
    init();
    solve();
    return 0;
}

Fight hard