CodeforcesRound#271(Div.2)解题报告_html/css_WEB-ITnose

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 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;}<="" script=""></len;i++)></set></map></queue></ctype.h></math.h></stdlib.h></cstring></string></cstdio></iostream>

水题。。

代码如下：

#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include 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--)="" printf("%d\n",dp[x-1]+1);="" return="" 0;}<="" script=""></n;i++)></set></map></queue></ctype.h></math.h></stdlib.h></cstring></string></cstdio></iostream>

暴力枚举，共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 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;" y="a.y-b.y;" x*x+y*y;}bool="" judge(){="" int="" i,="" j;="" 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)" 0;="" 1;="" 0;}int="" main(){="" t,="" 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);="" 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())="" if(min1="=20)" puts("-1");="" else="" printf("%d\n",min1);="" 0;}<="" script=""></z;i++)></set></map></queue></ctype.h></math.h></stdlib.h></cstring></string></cstdio></iostream>

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 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;}</set></map></queue></ctype.h></math.h></stdlib.h></cstring></string></cstdio></iostream>