题目地址：http://codeforces.com/contest/474

A题：Keyboard

模拟水题。

代码例如以下：

#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 __int64

char 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;

}

B题：Worms

水题。。

代码例如以下：

#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 __int64

int 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;

}

C题：Captain Marmot

暴力枚举，共4*4*4*4种情况。对每一种情况分别推断是否是正方形。

我竟然一直都以为是矩形。。

推断方法：将4条边与两条对角线分别计算出来。然后排序，4个小的肯定是边，2个大的是对角线，然后推断边是否都相等，对角线是否都相等，对角线是否是边的sqrt(2)倍（这里最好是用平方来推断是否是2倍）。然后找出移动次数最少的输出就可以。

代码例如以下：

#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 __int64

const 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;

}

D题：Flowers

DP。还是水题。。能够这样考虑：

第n个仅仅有两种情况。若第n个是R。那么情况数为dp[n-1]种。若第n个是W，因为W仅仅能连续k个，所以说，第n-k+1至第n个必须都是W，那么此时情况数为dp[n-k]种。

所以状态转移方程为：

dp[n]=dp[n-1]+dp[n-k]。

然后用一个数组保存前缀和就可以。

代码例如以下：

#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 __int64

const 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;

}

自己能做出来的仅仅有这么些。。

sad。

。