質問アドレス: 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;}水の質問。 。
コードは次のとおりです:
#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;}合計 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;}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;}
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
