Dashboard – Codeforces Global Round 13 – Codeforces()

Dashboard – Codeforces Global Round 13 – Codeforces

1.Problem – B – Codeforces

题意:存在n行1e6+2列,然后会有n个障碍物。可以将障碍物水平移动,和垂直移动。都有对应的消费。你需要从起点(1,1)到终点(n,1e6+2).问最少消费多少。

思路:只要存在两个点之间的y距离是大于1的那这条路肯定是通的。那最小值就是0。如果全在一列上,那就是有一个点需要移动两次,那就比较u+v和2*v的最小值。如果是有点错位我只要把他横移或者竖移一下就可以了。那就只要比较u,v最小值就可以了。

#include<bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);#define fel(i,x,y) for(int i=x;i<=y;i++)#define fhl(i,x,y) for(int i=x;i>=y;i--)#define inf 0x3fffffff#define ll long long#define pb push_back#define endl "\n"#define int long longconst int N=200;int n,u,v;int a[N];void slove(){    cin>>n>>u>>v;    fel(i,1,n){        cin>>a[i];    }    int cnt=0;    for(int i=2;i<=n;i++){        if(a[i]==a[i-1])cnt++;        else if(abs(a[i]-a[i-1])>1){            cout<<0<<endl;            return;        }    }    if(cnt==n-1){        cout<<min(u+v,v*2)<<endl;    }    else cout<<min(u,v)<<endl;}signed main(){    IOS    int t;    cin>>t;    while(t--){        slove();    }    return 0;}

2.Problem – C – Codeforces

题意:任意选择一个点,下一次跳到s[i]+i,,直到最后跳到n点以外。同时s[i]–;问最少需要选择多少次可以使得所有点都变成1.

思路:考虑用1个b数组来记录1—i-1踩到i点的次数,如果b[i]<a[i]-1,那就还需要选择a[i]作为起点。如果b[i]>a[i]-1那多余的跳到的次数会转移个a[i+1] (因为多余的次数跳到这个点上时此点是1).

#include<bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);#define fel(i,x,y) for(int i=x;i<=y;i++)#define fhl(i,x,y) for(int i=x;i>=y;i--)#define inf 0x3fffffff#define ll long long#define pb push_back#define endl "\n"#define int long longconst int N=5e3+100;int a[N],b[N],n;void slove(){    cin>>n;    fel(i,1,n){        cin>>a[i];        b[i]=0;    }    int ans=0;    for(int i=1;i<=n;i++){        int t=b[i];        if(b[i]<a[i]-1){            ans+=a[i]-1-b[i];            t+=a[i]-1-b[i];        }        b[i+1]+=t-a[i]+1;        if(i+2<=n)            for(int j=i+2;j<=min(n,a[i]+i);j++){                b[j]++;            }    }    cout<<ans<<endl;}signed main(){    IOS    int t;    cin>>t;    while(t--){        slove();    }    return 0;}

3.Problem – D – Codeforces

题意:q此询问,输入x,y。如果x可以到y就输出yes。u和u+v之间有边当且仅当u&v=v。

思路:举个列子比如说0111肯定是可以到1000,0111&0001=0001,0111+0001=1000,所以发现u&v==v的同时u+v,这就会导致u的低位一会向高位合并或者移动。所以就考虑只要u的后缀1的个数是小于u+v的就不可能了。

#include<bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);#define fel(i,x,y) for(int i=x;i<=y;i++)#define fhl(i,x,y) for(int i=x;i>=y;i--)#define inf 0x3fffffff#define ll long long#define pb push_back#define endl "\n"#define int long long//发先每一个数如果加上一个数那我的一只能向更高位进,所以后缀1的个数x肯定是大于y的,//定义f[i,x]是x最1-i位1的个数,想要是x可以变成y,显先必须的满足f[i,x]>=f[i,y];int x,y;int sumx[50],sumy[50];void slove(){    memset(sumx,0,sizeof(sumx));    memset(sumy,0,sizeof(sumy));    cin>>x>>y;    if(x>y){        cout<<"NO"<<endl;        return;    }    for(int i=1;i<=30;i++){        sumx[i]=sumx[i-1];        sumy[i]=sumy[i-1];        if(x&1)sumx[i]++;        if(y&1)sumy[i]++;        x/=2,y/=2;    }    for(int i=1;i<=30;i++){        if(sumx[i]<sumy[i]){            cout<<"NO"<<endl;            return;        }    }    cout<<"YES"<<endl;}signed main(){    IOS    int t;    cin>>t;    while(t--){        slove();    }    return 0;}
————————

Dashboard – Codeforces Global Round 13 – Codeforces

1.Problem – B – Codeforces

题意:存在n行1e6+2列,然后会有n个障碍物。可以将障碍物水平移动,和垂直移动。都有对应的消费。你需要从起点(1,1)到终点(n,1e6+2).问最少消费多少。

思路:只要存在两个点之间的y距离是大于1的那这条路肯定是通的。那最小值就是0。如果全在一列上,那就是有一个点需要移动两次,那就比较u+v和2*v的最小值。如果是有点错位我只要把他横移或者竖移一下就可以了。那就只要比较u,v最小值就可以了。

#include<bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);#define fel(i,x,y) for(int i=x;i<=y;i++)#define fhl(i,x,y) for(int i=x;i>=y;i--)#define inf 0x3fffffff#define ll long long#define pb push_back#define endl "\n"#define int long longconst int N=200;int n,u,v;int a[N];void slove(){    cin>>n>>u>>v;    fel(i,1,n){        cin>>a[i];    }    int cnt=0;    for(int i=2;i<=n;i++){        if(a[i]==a[i-1])cnt++;        else if(abs(a[i]-a[i-1])>1){            cout<<0<<endl;            return;        }    }    if(cnt==n-1){        cout<<min(u+v,v*2)<<endl;    }    else cout<<min(u,v)<<endl;}signed main(){    IOS    int t;    cin>>t;    while(t--){        slove();    }    return 0;}

2.Problem – C – Codeforces

题意:任意选择一个点,下一次跳到s[i]+i,,直到最后跳到n点以外。同时s[i]–;问最少需要选择多少次可以使得所有点都变成1.

思路:考虑用1个b数组来记录1—i-1踩到i点的次数,如果b[i]<a[i]-1,那就还需要选择a[i]作为起点。如果b[i]>a[i]-1那多余的跳到的次数会转移个a[i+1] (因为多余的次数跳到这个点上时此点是1).

#include<bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);#define fel(i,x,y) for(int i=x;i<=y;i++)#define fhl(i,x,y) for(int i=x;i>=y;i--)#define inf 0x3fffffff#define ll long long#define pb push_back#define endl "\n"#define int long longconst int N=5e3+100;int a[N],b[N],n;void slove(){    cin>>n;    fel(i,1,n){        cin>>a[i];        b[i]=0;    }    int ans=0;    for(int i=1;i<=n;i++){        int t=b[i];        if(b[i]<a[i]-1){            ans+=a[i]-1-b[i];            t+=a[i]-1-b[i];        }        b[i+1]+=t-a[i]+1;        if(i+2<=n)            for(int j=i+2;j<=min(n,a[i]+i);j++){                b[j]++;            }    }    cout<<ans<<endl;}signed main(){    IOS    int t;    cin>>t;    while(t--){        slove();    }    return 0;}

3.Problem – D – Codeforces

题意:q此询问,输入x,y。如果x可以到y就输出yes。u和u+v之间有边当且仅当u&v=v。

思路:举个列子比如说0111肯定是可以到1000,0111&0001=0001,0111+0001=1000,所以发现u&v==v的同时u+v,这就会导致u的低位一会向高位合并或者移动。所以就考虑只要u的后缀1的个数是小于u+v的就不可能了。

#include<bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);#define fel(i,x,y) for(int i=x;i<=y;i++)#define fhl(i,x,y) for(int i=x;i>=y;i--)#define inf 0x3fffffff#define ll long long#define pb push_back#define endl "\n"#define int long long//发先每一个数如果加上一个数那我的一只能向更高位进,所以后缀1的个数x肯定是大于y的,//定义f[i,x]是x最1-i位1的个数,想要是x可以变成y,显先必须的满足f[i,x]>=f[i,y];int x,y;int sumx[50],sumy[50];void slove(){    memset(sumx,0,sizeof(sumx));    memset(sumy,0,sizeof(sumy));    cin>>x>>y;    if(x>y){        cout<<"NO"<<endl;        return;    }    for(int i=1;i<=30;i++){        sumx[i]=sumx[i-1];        sumy[i]=sumy[i-1];        if(x&1)sumx[i]++;        if(y&1)sumy[i]++;        x/=2,y/=2;    }    for(int i=1;i<=30;i++){        if(sumx[i]<sumy[i]){            cout<<"NO"<<endl;            return;        }    }    cout<<"YES"<<endl;}signed main(){    IOS    int t;    cin>>t;    while(t--){        slove();    }    return 0;}