Codeforces Round #271 (Div. 2) Solution Report_html/css_WEB-ITnose

Question address: http://codeforces.com/contest/474

Question A: Keyboard

Simulating water question.

The code is as follows:

#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;#define LL __int64char s[]={"qwertyuiopasdfghjkl;zxcvbnm,./"};int main(){    int i, x, j, len;    char c, s1[200];    scanf("%c",&c);    if(c=='L')        x=1;    else        x=-1;        scanf("%s",s1);    len=strlen(s1);    for(i=0;i<len;i++)    {        for(j=0;;j++)        {            if(s[j]==s1[i])            {                printf("%c", s[j+x]);                break;            }        }    }    return 0;}

Question B: Worms

Water question. .

The code is as follows:

#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;#define LL __int64int dp[1100000];int main(){    int n, m, i, j, sum=0, x;    scanf("%d",&n);    for(i=0;i<n;i++)    {        scanf("%d",&x);        for(j=sum;j<sum+x;j++)        {            dp[j]=i;        }        sum+=x;    }    scanf("%d",&m);    while(m--)    {        scanf("%d",&x);        printf("%d\n",dp[x-1]+1);    }    return 0;}

Question C: Captain Marmot

Violent enumeration, a total of 4*4*4*4 In each case, determine whether it is a square. I actually always thought it was a rectangle. .

Judgment method: Calculate the four sides and two diagonals respectively. Then sort, the 4 small ones must be sides, and the 2 big ones are diagonals, and then determine whether the sides are equal, whether the diagonals are all equal, and whether the diagonal is sqrt(2) times the side (the best here Use the square to determine whether it is 2 times). Then just find the output with the fewest moves.

The code is as follows:

#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;#define LL __int64const int mod=1e9+7;struct node{    LL x, y;}t1[5], t2[5], fei[5];node solve(node x, node y, int z){    node t;    t=x;    int i;    for(i=0;i<z;i++)    {        x.x=y.y-t.y+y.x;        x.y=t.x-y.x+y.y;        t=x;    }    return t;}LL dist(node a, node b){    LL x=a.x-b.x;    LL y=a.y-b.y;    return x*x+y*y;}bool judge(){    int i, j;    LL d[6];    d[0]=dist(fei[0],fei[1]);    d[1]=dist(fei[1],fei[2]);    d[2]=dist(fei[2],fei[3]);    d[3]=dist(fei[3],fei[0]);    d[4]=dist(fei[0],fei[2]);    d[5]=dist(fei[1],fei[3]);    sort(d,d+6);    if(d[0]==0) return 0;    if(d[0]==d[1]&&d[1]==d[2]&&d[2]==d[3]&&d[4]==2*d[0]&&d[4]==d[5])        return 1;    return 0;}int main(){    int t, i, j, k, h, min1;    scanf("%d",&t);    while(t--)    {        min1=20;        for(i=0;i<4;i++)        {            scanf("%I64d%I64d%I64d%I64d",&t1[i].x,&t1[i].y,&t2[i].x,&t2[i].y);        }        for(i=0;i<4;i++)        {            fei[0]=solve(t1[0],t2[0],i);            for(j=0;j<4;j++)            {                fei[1]=solve(t1[1],t2[1],j);                for(k=0;k<4;k++)                {                    fei[2]=solve(t1[2],t2[2],k);                    for(h=0;h<4;h++)                    {                        fei[3]=solve(t1[3],t2[3],h);                        if(judge())                            {                                min1=min(min1,i+j+k+h);                            }                    }                }            }        }        if(min1==20) puts("-1");        else            printf("%d\n",min1);    }    return 0;}

Question D: Flowers

DP, again a water question. . You can think of it this way:

There are only two situations for the nth one. If the nth one is R, then the number of situations is dp[n-1]. If the nth one is W, since W can only be k consecutive times, so the n-k 1st to nth ones must all be W, then the number of situations at this time is dp[n-k]. So the state transition equation is:

dp[n]=dp[n-1] dp[n-k].

Then use an array to save the prefix sum.

The code is as follows:

#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;#define LL __int64const int mod=1e9+7;LL dp[110000], sum[110000];int main(){    int i, j, n, k, a, b;    LL x=0;    sum[0]=0;    dp[0]=0;    scanf("%d%d",&n,&k);    for(i=1;i<=k-1;i++)        dp[i]=1;    dp[k]=2;    for(i=k+1;i<=100000;i++)    {        dp[i]=dp[i-k]+dp[i-1];        dp[i]%=mod;    }    for(i=1;i<=100000;i++)    {        sum[i]=(sum[i-1]+dp[i])%mod;    }    while(n--)    {        scanf("%d%d",&a,&b);        printf("%I64d\n",(sum[b]+mod-sum[a-1])%mod);    }    return 0;}

There is only so much you can do. . sad. .