Codeforces Round #271 (Div. 2)

发布时间:2017-5-28 20:47:24 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Codeforces Round #271 (Div. 2)",主要涉及到Codeforces Round #271 (Div. 2)方面的内容,对于Codeforces Round #271 (Div. 2)感兴趣的同学可以参考一下。

Codeforces Round #271 (Div. 2)

A - Keyboard

题意

给你一个字符串,问你这个字符串在键盘的位置往左边挪一位,或者往右边挪一位字符,这个字符串是什么样子

题解

模拟一下就好了

代码

#include<bits/stdc++.h>using namespace std;string s[3];map<char,int>r,c;char ss[2][107];int main(){    s[0]="qwertyuiop";    s[1]="asdfghjkl;";    s[2]="zxcvbnm,./";    for(int i=0;i<3;i++){        for(int j=0;j<s[0].size();j++){            r[s[i][j]]=i;            c[s[i][j]]=j;        }    }    scanf("%s%s",ss[0],ss[1]);    if(ss[0][0]=='R'){        int len = strlen(ss[1]);        for(int i=0;i<len;i++)            printf("%c",s[r[ss[1][i]]][c[ss[1][i]]-1]);    }    else{        int len = strlen(ss[1]);        for(int i=0;i<len;i++)            printf("%c",s[r[ss[1][i]]][c[ss[1][i]]+1]);    }}

B. Worms

题意

给你一个a[i]数组,表示每个区间所能管辖的范围。

第一个区间为[1,a[1]],第二个为[a[1]+1,a[1]+a[2]],然后依次下去……

然后有m个询问,每次给你一个x,问你这个x在哪个区间里面

题解

区间管辖范围呈现单调,所以我们直接二分找到区间就好了嘛

代码

#include<bits/stdc++.h>using namespace std;const int maxn = 1e5+7;int r[maxn],n,m,a[maxn];int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++){        scanf("%d",&a[i]);        r[i]=r[i-1]+a[i];    }    scanf("%d",&m);    for(int i=1;i<=m;i++){        int x;        scanf("%d",&x);        int L=1,R=n,ans=n;        while(L<=R){            int mid=(L+R)/2;            if(r[mid]<x)L=mid+1;            else R=mid-1,ans=mid;        }        cout<<ans<<endl;    }}

C - Captain Marmot

题意

有t次询问,每次询问给你四个点,以及每个点相互对应的旋转中心。

你可以逆时针旋转,你要求使得所有点的旋转次数和最少,然后构成一个正方形,问你旋转次数是多少。

题解

暴力嘛,反正数据范围这么小,判断直角就用dot product就好了嘛

代码

#include<bits/stdc++.h>using namespace std;int x[4],y[4],a[4],b[4];int p[4][4][2];vector<int>X,Y;int dis(int x1,int y1,int x2,int y2){    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);}int dot(int x1,int y1,int x2,int y2,int x3,int y3){    return (x1-x3)*(x2-x3)+(y1-y3)*(y2-y3);}void solve(){    for(int i=0;i<4;i++)        scanf("%d%d%d%d",&x[i],&y[i],&a[i],&b[i]);    for(int i=0;i<4;i++){        p[i][0][0]=x[i];        p[i][0][1]=y[i];        for(int j=1;j<4;j++){            int x=p[i][j-1][0]-a[i];            int y=p[i][j-1][1]-b[i];            p[i][j][0]=-y+a[i];            p[i][j][1]=x+b[i];        }    }    int Ans = 10000;    for(int i=0;i<4;i++){        for(int j=0;j<4;j++){            for(int k=0;k<4;k++){                for(int t=0;t<4;t++){                    X.clear(),Y.clear();                    X.push_back(p[0][i][0]);                    X.push_back(p[1][j][0]);                    X.push_back(p[2][k][0]);                    X.push_back(p[3][t][0]);                    Y.push_back(p[0][i][1]);                    Y.push_back(p[1][j][1]);                    Y.push_back(p[2][k][1]);                    Y.push_back(p[3][t][1]);                    vector<int>tmp;                    for(int ii=0;ii<4;ii++)                        tmp.push_back(ii);                    int flag=0;                    do{                        int dis1 = dis(X[tmp[0]],Y[tmp[0]],X[tmp[1]],Y[tmp[1]]);                        int dis2 = dis(X[tmp[1]],Y[tmp[1]],X[tmp[2]],Y[tmp[2]]);                        int dis3 = dis(X[tmp[2]],Y[tmp[2]],X[tmp[3]],Y[tmp[3]]);                        int dis4 = dis(X[tmp[3]],Y[tmp[3]],X[tmp[0]],Y[tmp[0]]);                        int dot1 = dot(X[tmp[0]],Y[tmp[0]],X[tmp[2]],Y[tmp[2]],X[tmp[1]],Y[tmp[1]]);                        int dot2 = dot(X[tmp[1]],Y[tmp[1]],X[tmp[3]],Y[tmp[3]],X[tmp[2]],Y[tmp[2]]);                        int dot3 = dot(X[tmp[2]],Y[tmp[2]],X[tmp[0]],Y[tmp[0]],X[tmp[3]],Y[tmp[3]]);                        int dot4 = dot(X[tmp[3]],Y[tmp[3]],X[tmp[1]],Y[tmp[1]],X[tmp[0]],Y[tmp[0]]);                        if(dis1>0&&dis1==dis2&&dis2==dis3&&dis3==dis4&&dot1==0&&dot2==0&&dot3==0&&dot4==0)                            flag=1;                    }while(next_permutation(tmp.begin(),tmp.end()));                    if(flag)Ans=min(Ans,i+j+k+t);                }            }        }    }    if(Ans==10000)cout<<"-1"<<endl;    else cout<<Ans<<endl;}int main(){    int t;    scanf("%d",&t);    while(t--)solve();    return 0;}

D. Flowers

题意

现在给你一堆花,有红花和白花,只有连续的k朵白花放在一起,才会觉得好看。

现在给你t个询问,问你摆放长度为l到r的好看的摆放方法种类有多少种

题解

预处理dp之后,利用前缀和进行O(1)回答就好了

我一开始写的dp是,dp[i][0]表示长度为i,结尾是红花的方案数,dp[i][1]表示结尾为白花的方案数,dp方程写完的时候,才发现这俩转移方程一样的……

代码

#include<bits/stdc++.h>using namespace std;const int maxn = 1e5+7;const long long mod = 1e9+7;int t,k,l,r;long long dp[maxn][2];int main(){    scanf("%d%d",&t,&k);    dp[0][0]=1;    for(int i=1;i<=100000;i++){        dp[i][0]=(dp[i-1][0]+dp[i-1][1])%mod;        if(i>=k)dp[i][1]=(dp[i-k][0]+dp[i-k][1])%mod;    }    dp[0][0]=0;    for(int i=1;i<=100000;i++)        (dp[i][0]+=dp[i-1][0])%=mod,        (dp[i][1]+=dp[i-1][1])%=mod;    for(int i=1;i<=t;i++){        int l,r;        scanf("%d%d",&l,&r);        printf("%lld\n",((dp[r][0]+dp[r][1]-dp[l-1][1]-dp[l-1][0])%mod+mod)%mod);    }}

E - Pillars

题意

让你找到最长的子序列,满足abs(h[i]-h[i-1])>=d

题解

显然就和最长上升子序列一个道理,把绝对值拆开之后,用一个线段树去维护就好了

注意要离散化

代码

#include<bits/stdc++.h>using namespace std;const int maxn = 1e6+7;typedef int SgTreeDataType;struct treenode{  int L , R  ;  SgTreeDataType sum , lazy;  void updata(SgTreeDataType v)  {      sum = v;      lazy = v;  }};treenode tree[maxn*4];inline void push_down(int o){    SgTreeDataType lazyval = tree[o].lazy;    if(lazyval==0)return;    tree[2*o].updata(lazyval) ; tree[2*o+1].updata(lazyval);    tree[o].lazy = 0;}inline void push_up(int o){    tree[o].sum = max(tree[2*o].sum , tree[2*o+1].sum);}inline void build_tree(int L , int R , int o){    tree[o].L = L , tree[o].R = R,tree[o].sum = tree[o].lazy = 0;    if (R > L)    {        int mid = (L+R) >> 1;        build_tree(L,mid,o*2);        build_tree(mid+1,R,o*2+1);    }}inline void updata(int QL,int QR,SgTreeDataType v,int o){    int L = tree[o].L , R = tree[o].R;    if (QL <= L && R <= QR) tree[o].updata(v);    else    {        push_down(o);        int mid = (L+R)>>1;        if (QL <= mid) updata(QL,QR,v,o*2);        if (QR >  mid) updata(QL,QR,v,o*2+1);        push_up(o);    }}inline SgTreeDataType query(int QL,int QR,int o){    int L = tree[o].L , R = tree[o].R;    if (QL <= L && R <= QR) return tree[o].sum;    else    {        push_down(o);        int mid = (L+R)>>1;        SgTreeDataType res = 0;        if (QL <= mid) res=max(res,query(QL,QR,2*o));        if (QR > mid) res=max(res,query(QL,QR,2*o+1));        push_up(o);        return res;    }}int n,dp[maxn];long long h[maxn],d;vector<long long>V;map<long long,int>H;int main(){    scanf("%d%lld",&n,&d);    for(int i=1;i<=n;i++)    {        scanf("%lld",&h[i]);        V.push_back(h[i]);        V.push_back(h[i]-d);        V.push_back(h[i]+d);    }    sort(V.begin(),V.end());    V.erase(unique(V.begin(),V.end()),V.end());    for(int i=0;i<V.size();i++)        H[V[i]]=i+1;    build_tree(1,V.size()+5,1);    int Ans=0,Ans2=0;    for(int i=1;i<=n;i++){        dp[i]=max(query(1,H[h[i]-d],1),query(H[h[i]+d],V.size()+5,1))+1;        if(dp[i]>Ans){            Ans=dp[i];            Ans2=i;        }        updata(H[h[i]],H[h[i]],dp[i],1);    }    cout<<Ans<<endl;    vector<int>tmp;    tmp.push_back(Ans2);    for(int i=Ans2;i;i--){        if(dp[i]==Ans-1&&abs(h[i]-h[Ans2])>=d){            Ans2=i;            Ans--;            tmp.push_back(Ans2);        }    }    reverse(tmp.begin(),tmp.end());    for(int i=0;i<tmp.size();i++)        cout<<tmp[i]<<" ";    cout<<endl;}

F - Ant colony

题意

查询区间gcd是多少,且查询区间有多少个数等于这个gcd

题解

线段树去维护区间gcd是什么,然后用二分去找到区间有多少个这个数

代码

#include<bits/stdc++.h>using namespace std;const int maxn = 1e6+7;typedef int SgTreeDataType;struct treenode{  int L , R  ;  SgTreeDataType sum , lazy;  void updata(SgTreeDataType v)  {      sum = v;      lazy = v;  }};int gcd(int a,int b){    if(b==0)return a;    return gcd(b,a%b);}treenode tree[maxn*4];inline void push_down(int o){}inline void push_up(int o){    tree[o].sum = gcd(tree[o<<1].sum,tree[o<<1|1].sum);}inline void build_tree(int L , int R , int o){    tree[o].L = L , tree[o].R = R,tree[o].sum = tree[o].lazy = 0;    if (R > L)    {        int mid = (L+R) >> 1;        build_tree(L,mid,o*2);        build_tree(mid+1,R,o*2+1);    }}inline void updata(int QL,int QR,SgTreeDataType v,int o){    int L = tree[o].L , R = tree[o].R;    if (QL <= L && R <= QR) tree[o].updata(v);    else    {        push_down(o);        int mid = (L+R)>>1;        if (QL <= mid) updata(QL,QR,v,o*2);        if (QR >  mid) updata(QL,QR,v,o*2+1);        push_up(o);    }}inline SgTreeDataType query(int QL,int QR,int o){    int L = tree[o].L , R = tree[o].R;    if (QL <= L && R <= QR) return tree[o].sum;    else    {        push_down(o);        int mid = (L+R)>>1;        SgTreeDataType res = 0;        if (QL <= mid) res=gcd(res,query(QL,QR,2*o));        if (QR > mid) res=gcd(res,query(QL,QR,2*o+1));        push_up(o);        return res;    }}int n,m,a[maxn];pair<int,int>p[maxn];int main(){    scanf("%d",&n);    build_tree(1,n,1);    for(int i=1;i<=n;i++)    {        scanf("%d",&a[i]);        updata(i,i,a[i],1);        p[i].first=a[i];        p[i].second=i;    }    scanf("%d",&m);    sort(p+1,p+1+n);    for(int i=1;i<=m;i++){        int l,r;        scanf("%d%d",&l,&r);        int pp=query(l,r,1);        int L=lower_bound(p+1,p+1+n,make_pair(pp,l))-(p+1);        int R=lower_bound(p+1,p+1+n,make_pair(pp,r+1))-(p+1);        printf("%d\n",(r-l+1)-(R-L));    }

上一篇:事件
下一篇:Mac系统终端命令行不执行命令 总出现command not found解决方法

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。