Codeforces ラウンド #271 (ディビジョン 2) ソリューション Report_html/css_WEB-ITnose

質問アドレス: http://codeforces.com/contest/474

質問 A: キーボード

水の模擬質問。

コードは次のとおりです:

#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;}

質問B: ワーム

水の質問。 。

コードは次のとおりです:

#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;}

質問C: キャプテン・マーモット

合計 4*4*4*4 の状況を暴力的に列挙し、それぞれの場合で正方形であるかどうかを判断します。実はずっと長方形だと思ってました。 。

判定方法：4つの辺と2つの対角線をそれぞれ計算します。次に、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 __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;}

質問 D: 花

DP、まだ水の質問です。 。次のように考えることができます:

n 番目の状況は 2 つだけあり、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 __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;}

でできることは限られています。 。悲しい。 。