Codeforces Round #271 (Div. 2)

A. Keyboard

题意：一个人打字，可能会左偏一位，可能会右偏一位，给出一串字符，求它本来的串

和紫书的破损的键盘一样

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include <cmath>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 char s[]="qwertyuiopasdfghjkl;zxcvbnm,./";

 char a[],t[];

 int main()

 {

     char ch;

     int i,j,len;

     a['L']=;

     a['R']=-;

     cin>>ch;

     cin>>t;

     len=strlen(t);

     for(i=;i<len;i++){

         for(j=;j<;j++){

             if(t[i]==s[j]){

                 t[i]=s[j+a[ch]];

                 break;

             }

         }

     }

     cout<<t<<"\n";

 return ;

 }

B. Worms

题意：给出n,a[1],a[2],a[3]---a[n],第一堆的编号为1到a[i],第二堆的编号为a[1]+1到a[1]+1+a[2],再给出m个数，询问它们分别在哪一堆

把每一堆的起始和结束储存在b[]数组中，再用lower_bound查找

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include <cmath>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 int a[],b[];

 int main()

 {

     int n,m,i,j,x,tmp;

     scanf("%d",&n);

     for(i=;i<=n;i++) scanf("%d",&a[i]);

     b[]=;

     b[]=b[]+a[]-;

     for(i=;i<=n;i++){

         b[*i-]=b[*i-]+;

         b[*i]=b[*i-]+a[i]-;

     }

     scanf("%d",&m);

     while(m--){

         scanf("%d",&x);

         tmp=lower_bound(b+,b++*n,x)-b;

         printf("%d\n",(tmp+)/);

     }

   return ;

 }

后来搜CD的题解时，发现有这样做的，将每一个属于哪一堆储存在数组中感觉有点类似哈希= =

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include <cmath>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 int vis[];

 int main()

 {

     int n,m,i,j,a,s=;

     scanf("%d",&n);

     for(i=;i<=n;i++){

         scanf("%d",&a);

         for(j=;j<a;j++){

             s++;

             vis[s]=i;

         }

     }

     scanf("%d",&m);

     while(m--){

         scanf("%d",&a);

         printf("%d\n",vis[a]);

     }

     return ;

 }

C. Captain Marmot

题意：给出n个兵团，每个兵团里面有四个点，给出这四个点的起始坐标，旋转中心坐标，问这四个点至少经过多少次旋转能够得到一个正方形

因为一个点只有4种情况，不旋转，旋转90，旋转180，旋转270，

用p[i][j]表示：i表示点的状态，j表示的是这是第几个点。

再4*4*4*4枚举，枚举的时候枚举正方形的边长是否相等，还有对角线长度平方是否为边长平方的2倍

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include <cmath>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 LL d[];

 struct node{

     int x,y;

 } p[][],center[];

 LL dis(node a,node b){

     return(LL)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);

 }

 void check(){

     int ans=;

     for(int i=;i<;i++)

     {

         for(int j=;j<;j++)

         {

             for(int k=;k<;k++)

             {

                 for(int l=;l<;l++)

                 {

                     d[]=dis(p[i][],p[j][]);

                     d[]=dis(p[j][],p[k][]);

                     d[]=dis(p[k][],p[l][]);

                     d[]=dis(p[l][],p[i][]);//正方形的4条直角边

                     d[]=dis(p[i][],p[k][]);// 正方形的对角线

                     d[]=dis(p[j][],p[l][]);

                     sort(d,d+);

                     if(d[]==)

                         continue;

                     else

                         if(d[]==d[]&&d[]==d[]&&d[]==d[]&&d[]*==d[]&&d[]==d[])//判断边长和对角线

                     {

                         ans=min(ans,i+j+k+l);

                     }

                 }

             }

         }

     }

     if(ans!=) printf("%d\n",ans);

     else printf("-1\n");

 }

 int main()

 {

     int n,j;

     scanf("%d",&n);

     while(n--){

         for(int i=;i<;i++)

         {

             cin>>p[][i].x>>p[][i].y;

             cin>>center[i].x>>center[i].y;

             int xx=p[][i].x-center[i].x;

             int yy=p[][i].y-center[i].y;

             p[][i].x=center[i].x-yy;//分别计算出一个点旋转所能够得到的四种状态

             p[][i].y=center[i].y+xx;

             p[][i].x=center[i].x-xx;

             p[][i].y=center[i].y-yy;

             p[][i].x=center[i].x+yy;

             p[][i].y=center[i].y-xx;

         }

         check();

     }

 return ;

 }

D. Flowers

题意：给出吃白花必须是k的整数倍，给出吃花朵数的区间 a,b,问满足这样条件的方案数共有多少

dp[i]表示吃到第i朵花的方案数

dp[i]=dp[i-1]+dp[i-k];

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include <cmath>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 int mod=1e9+;

 int dp[];

 int main()

 {

     int i,j,t,k,a,b;

     scanf("%d %d",&t,&k);

     dp[]=;

     for(i=;i<=;i++){

         dp[i]=dp[i-];

         if(i>=k) dp[i]=(dp[i]+dp[i-k])%mod;

     }

     for(i=;i<=;i++){

         dp[i]=(dp[i]+dp[i-])%mod;//再求出前缀和

     }

     while(t--){

         scanf("%d %d",&a,&b);

     printf("%d\n",((dp[b]-dp[a-])%mod+mod)%mod);//注意这儿要在括号里面加个mod再mod一次，因为这个挂在了第三个

     }

     return ;

 }

巴特西

Codeforces Round #271 (Div. 2)

最新文章

热门文章