A. Keyboard
题意：一个人打字，可能会左偏一位，可能会右偏一位，给出一串字符，求它本来的串
和紫书的破损的键盘一样
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cmath>
#include<algorithm>
using namespace std; typedef long long LL;
char s[]="qwertyuiopasdfghjkl;zxcvbnm,./";
char a[],t[]; int main()
{
char ch;
int i,j,len;
a['L']=;
a['R']=-;
cin>>ch;
cin>>t;
len=strlen(t);
for(i=;i<len;i++){
for(j=;j<;j++){
if(t[i]==s[j]){
t[i]=s[j+a[ch]];
break;
}
}
}
cout<<t<<"\n";
return ;
}
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查找
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cmath>
#include<algorithm>
using namespace std; typedef long long LL;
int a[],b[]; int main()
{
int n,m,i,j,x,tmp;
scanf("%d",&n);
for(i=;i<=n;i++) scanf("%d",&a[i]);
b[]=;
b[]=b[]+a[]-; for(i=;i<=n;i++){
b[*i-]=b[*i-]+;
b[*i]=b[*i-]+a[i]-;
} scanf("%d",&m);
while(m--){
scanf("%d",&x);
tmp=lower_bound(b+,b++*n,x)-b;
printf("%d\n",(tmp+)/);
}
return ;
}
后来搜CD的题解时，发现有这样做的，将每一个属于哪一堆储存在数组中 感觉有点类似哈希= =
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cmath>
#include<algorithm>
using namespace std; typedef long long LL;
int vis[]; int main()
{
int n,m,i,j,a,s=;
scanf("%d",&n);
for(i=;i<=n;i++){
scanf("%d",&a);
for(j=;j<a;j++){
s++;
vis[s]=i;
}
} scanf("%d",&m);
while(m--){
scanf("%d",&a); printf("%d\n",vis[a]);
}
return ;
}
C. Captain Marmot
题意：给出n个兵团，每个兵团里面有四个点，给出这四个点的起始坐标，旋转中心坐标，问这四个点至少经过多少次旋转能够得到一个正方形
因为一个点只有4种情况，不旋转，旋转90，旋转180，旋转270，
用p[i][j]表示：i表示点的状态，j表示的是这是第几个点。
再4*4*4*4枚举，枚举的时候枚举正方形的边长是否相等，还有对角线长度平方是否为边长平方的2倍
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cmath>
#include<algorithm>
using namespace std; typedef long long LL;
LL d[]; struct node{
int x,y;
} p[][],center[]; LL dis(node a,node b){
return(LL)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
} void check(){
int ans=;
for(int i=;i<;i++)
{
for(int j=;j<;j++)
{
for(int k=;k<;k++)
{
for(int l=;l<;l++)
{
d[]=dis(p[i][],p[j][]);
d[]=dis(p[j][],p[k][]);
d[]=dis(p[k][],p[l][]);
d[]=dis(p[l][],p[i][]);//正方形的4条直角边
d[]=dis(p[i][],p[k][]);// 正方形的对角线
d[]=dis(p[j][],p[l][]);
sort(d,d+);
if(d[]==)
continue;
else
if(d[]==d[]&&d[]==d[]&&d[]==d[]&&d[]*==d[]&&d[]==d[])//判断边长和对角线
{
ans=min(ans,i+j+k+l); }
} }
}
} if(ans!=) printf("%d\n",ans);
else printf("-1\n");
} int main()
{
int n,j;
scanf("%d",&n);
while(n--){
for(int i=;i<;i++)
{
cin>>p[][i].x>>p[][i].y;
cin>>center[i].x>>center[i].y;
int xx=p[][i].x-center[i].x;
int yy=p[][i].y-center[i].y;
p[][i].x=center[i].x-yy;//分别计算出一个点旋转所能够得到的四种状态
p[][i].y=center[i].y+xx;
p[][i].x=center[i].x-xx;
p[][i].y=center[i].y-yy;
p[][i].x=center[i].x+yy;
p[][i].y=center[i].y-xx;
}
check();
}
return ;
}
D. Flowers
题意：给出吃白花必须是k的整数倍，给出吃花朵数的区间 a,b,问满足这样条件的方案数共有多少
dp[i]表示吃到第i朵花的方案数
dp[i]=dp[i-1]+dp[i-k];
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cmath>
#include<algorithm>
using namespace std; typedef long long LL;
int mod=1e9+;
int dp[]; int main()
{
int i,j,t,k,a,b;
scanf("%d %d",&t,&k);
dp[]=;
for(i=;i<=;i++){
dp[i]=dp[i-];
if(i>=k) dp[i]=(dp[i]+dp[i-k])%mod;
} for(i=;i<=;i++){
dp[i]=(dp[i]+dp[i-])%mod;//再求出前缀和
} while(t--){
scanf("%d %d",&a,&b);
printf("%d\n",((dp[b]-dp[a-])%mod+mod)%mod);//注意这儿要在括号里面加个mod再mod一次，因为这个挂在了第三个
}
return ;
}