A. Keyboard
题意：一个人打字，可能会左偏一位，可能会右偏一位，给出一串字符，求它本来的串
和紫书的破损的键盘一样
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<algorithm> 6 using namespace std; 7 8 typedef long long LL; 9 char s[100]="qwertyuiopasdfghjkl;zxcvbnm,./"; 10 char a[1005],t[1005]; 11 12 int main() 13 { 14 char ch; 15 int i,j,len; 16 a['L']=1; 17 a['R']=-1; 18 cin>>ch; 19 cin>>t; 20 len=strlen(t); 21 for(i=0;i<len;i++){ 22 for(j=0;j<30;j++){ 23 if(t[i]==s[j]){ 24 t[i]=s[j+a[ch]]; 25 break; 26 } 27 } 28 } 29 cout<<t<<" "; 30 return 0; 31 }
B. Worms
题意：给出n,a[1],a[2],a[3]---a[n],第一堆的编号为1到a[i],第二堆的编号为a[1]+1到a[1]+1+a[2],再给出m个数，询问它们分别在哪一堆
把每一堆的起始和结束储存在b[]数组中，再用lower_bound查找
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<algorithm> 6 using namespace std; 7 8 typedef long long LL; 9 int a[100005],b[200005]; 10 11 int main() 12 { 13 int n,m,i,j,x,tmp; 14 scanf("%d",&n); 15 for(i=1;i<=n;i++) scanf("%d",&a[i]); 16 b[1]=1; 17 b[2]=b[1]+a[1]-1; 18 19 for(i=2;i<=n;i++){ 20 b[2*i-1]=b[2*i-2]+1; 21 b[2*i]=b[2*i-1]+a[i]-1; 22 } 23 24 25 scanf("%d",&m); 26 while(m--){ 27 scanf("%d",&x); 28 tmp=lower_bound(b+1,b+1+2*n,x)-b; 29 printf("%d ",(tmp+1)/2); 30 } 31 return 0; 32 }
后来搜CD的题解时，发现有这样做的，将每一个属于哪一堆储存在数组中 感觉有点类似哈希= =
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<algorithm> 6 using namespace std; 7 8 typedef long long LL; 9 int vis[1000005]; 10 11 int main() 12 { 13 int n,m,i,j,a,s=0; 14 scanf("%d",&n); 15 for(i=1;i<=n;i++){ 16 scanf("%d",&a); 17 for(j=0;j<a;j++){ 18 s++; 19 vis[s]=i; 20 } 21 } 22 23 scanf("%d",&m); 24 while(m--){ 25 scanf("%d",&a); 26 printf("%d ",vis[a]); 27 } 28 return 0; 29 }
C. Captain Marmot
题意：给出n个兵团，每个兵团里面有四个点，给出这四个点的起始坐标，旋转中心坐标，问这四个点至少经过多少次旋转能够得到一个正方形
因为一个点只有4种情况，不旋转，旋转90，旋转180，旋转270，
用p[i][j]表示：i表示点的状态，j表示的是这是第几个点。
再4*4*4*4枚举，枚举的时候枚举正方形的边长是否相等，还有对角线长度平方是否为边长平方的2倍
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<algorithm> 6 using namespace std; 7 8 typedef long long LL; 9 LL d[10]; 10 11 struct node{ 12 int x,y; 13 } p[10][10],center[10]; 14 15 LL dis(node a,node b){ 16 return(LL)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); 17 } 18 19 void check(){ 20 int ans=10005; 21 for(int i=0;i<4;i++) 22 { 23 for(int j=0;j<4;j++) 24 { 25 for(int k=0;k<4;k++) 26 { 27 for(int l=0;l<4;l++) 28 { 29 d[0]=dis(p[i][0],p[j][1]); 30 d[1]=dis(p[j][1],p[k][2]); 31 d[2]=dis(p[k][2],p[l][3]); 32 d[3]=dis(p[l][3],p[i][0]);//正方形的4条直角边 33 d[4]=dis(p[i][0],p[k][2]);// 正方形的对角线 34 d[5]=dis(p[j][1],p[l][3]); 35 sort(d,d+6); 36 if(d[0]==0) 37 continue; 38 else 39 if(d[0]==d[1]&&d[1]==d[2]&&d[2]==d[3]&&d[0]*2==d[4]&&d[4]==d[5])//判断边长和对角线 40 { 41 ans=min(ans,i+j+k+l); 42 43 } 44 } 45 46 } 47 } 48 } 49 50 if(ans!=10005) printf("%d ",ans); 51 else printf("-1 "); 52 } 53 54 int main() 55 { 56 int n,j; 57 scanf("%d",&n); 58 while(n--){ 59 for(int i=0;i<4;i++) 60 { 61 cin>>p[0][i].x>>p[0][i].y; 62 cin>>center[i].x>>center[i].y; 63 int xx=p[0][i].x-center[i].x; 64 int yy=p[0][i].y-center[i].y; 65 p[1][i].x=center[i].x-yy;//分别计算出一个点旋转所能够得到的四种状态 66 p[1][i].y=center[i].y+xx; 67 p[2][i].x=center[i].x-xx; 68 p[2][i].y=center[i].y-yy; 69 p[3][i].x=center[i].x+yy; 70 p[3][i].y=center[i].y-xx; 71 } 72 check(); 73 } 74 return 0; 75 }
D. Flowers
题意：给出吃白花必须是k的整数倍，给出吃花朵数的区间 a,b,问满足这样条件的方案数共有多少
dp[i]表示吃到第i朵花的方案数
dp[i]=dp[i-1]+dp[i-k];
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<algorithm> 6 using namespace std; 7 8 typedef long long LL; 9 int mod=1e9+7; 10 int dp[100005]; 11 12 int main() 13 { 14 int i,j,t,k,a,b; 15 scanf("%d %d",&t,&k); 16 dp[0]=1; 17 for(i=1;i<=100005;i++){ 18 dp[i]=dp[i-1]; 19 if(i>=k) dp[i]=(dp[i]+dp[i-k])%mod; 20 } 21 22 for(i=1;i<=100005;i++){ 23 dp[i]=(dp[i]+dp[i-1])%mod;//再求出前缀和 24 } 25 26 while(t--){ 27 scanf("%d %d",&a,&b); 28 printf("%d ",((dp[b]-dp[a-1])%mod+mod)%mod);//注意这儿要在括号里面加个mod再mod一次，因为这个挂在了第三个 29 } 30 return 0; 31 }