首页 > 代码库 > 2017 计蒜之道 初赛 第一场 A、B题
2017 计蒜之道 初赛 第一场 A、B题
A题 阿里的新游戏
题目概述：
阿里九游开放平台近日上架了一款新的益智类游戏——成三棋。成三棋是我国非常古老的一个双人棋类游戏，其棋盘如下图所示：
成三棋的棋盘上有很多条线段，只能在线段交叉点上放入棋子。我们可以用坐标系来描述棋盘：
如果一条线段上的三个交叉点都被同一玩家的棋子占据的话，则称这条线段被该玩家 成三。现在，小红和小明两人在游戏平台上下棋，其中小红的棋子是黑色的。请你帮小红计算他成三的线段数。
样例对应的棋盘如下：
输入格式
输入第一行两个整数 n,m(3 \le n, m \le 9)n,m(3≤n,m≤9)，nn表示小红的棋子数，mm 表示小明的棋子数。
接下来 nn 行输入小红的棋子坐标。
接下来 mm 行输入小明的棋子坐标。
输入保证坐标合法，并且棋子之间不重合。
输出格式
输出小红成三的线段数。
样例输入
6 3 -1 0 -2 0 -3 0 -1 -1 -1 1 1 0 0 2 0 3 2 2
样例输出
2
水题，粗暴的做使用16个if就可以AC，我是用了4个数组,px,nx,py,ny(p代表正，n代表负)，看棋子落在了哪一个维度，因为不会有重复的，所以当某一个数组的某一个值等于3，即为成三（虽然我很想吐槽小明去干嘛了）
#include <stdio.h> int py[4],px[4],nx[4],ny[4]; int main(){ int n,m; int x,y; scanf("%d %d",&n,&m); for(int i=0;i<n;i++){ scanf("%d %d",&x,&y); if(x>0){ px[x]++; } if(x<0){ nx[-x]++; } if(y>0){ py[y]++; } if(y<0){ ny[-y]++; } if(x==0&&y>0){ py[0]++; } if(x==0&&y<0){ ny[0]++; } if(y==0&&x>0){ px[0]++; } if(y==0&&x<0){ nx[0]++; } } for(int i=0;i<m;i++){ scanf("%d %d",&x,&y); } int res=0; for(int i=0;i<=3;i++){ if(nx[i]==3){ res++; } if(px[i]==3){ res++; } if(ny[i]==3){ res++; } if(py[i]==3){ res++; } } printf("%d\n",res); return 0; }
B题 阿里天池的新任务（简单）
阿里“天池”竞赛平台近日推出了一个新的挑战任务：对于给定的一串 DNA 碱基序列 tt，判断它在另一个根据规则生成的 DNA 碱基序列 ss中出现了多少次。
输入格式
数据第一行为 55 个整数，分别代表 n , a , b , L , Rn,a,b,L,R。第二行为一个仅包含A、T、G、C的一个序列 tt。
数据保证 0 < a < n,0<a<n, 0 \le b < n,0≤b<n, 0 \le L \le R < n,0≤L≤R<n, |t| \le 10^{6}∣t∣≤10?6??，a,na,n 互质。
对于简单版本，1 \leq n \leq 10^{6}1≤n≤10?6??；
对于中等版本，1 \leq n \leq 10^{9}, a = 11≤n≤10?9??,a=1；
对于困难版本，1 \leq n \leq 10^{9}1≤n≤10?9??。
输出格式
输出一个整数，为 tt 在 ss 中出现的次数。
样例说明
对于第一组样例，生成的 ss 为TTTCGGAAAGGCC。
样例输入1
13 2 5 4 9 AGG
样例输出1
1
样例输入2
103 51 0 40 60 ACTG
样例输出2
5
这个题因为数据规模较小可以生成t,所以可以直接使用KMP算法出结果。
#include <stdio.h>
#include <string.h>
char s[1000005];
char t[1000005];
int nexts[1000005];
int lens,lent;
void getnexts() {
nexts[0]=-1;
int k=-1,j=0;
while(j<lent) {
if(k==-1||t[k]==t[j]) {
++j,++k;
nexts[j]=k;
} else k=nexts[k];
}
}
void KMP() {
int i=0,j=0,ans=0,pos=0,f=1;
while(i<lens) {
if(s[i]==t[j]) {
++i,++j;
if(j==lent) {
++ans;
}
} else if(nexts[j]==-1) {
++i;
} else j=nexts[j];
}
printf("%d\n",ans);
}
int main(){
int n,a,b,l,r;
scanf("%d %d %d %d %d",&n,&a,&b,&l,&r);
int w=b-a;
scanf("%s",t);
for(int i=0;i<n;i++){
w=(w+a)%n;
if(l<=w&&w<=r&&w%2==0){
s[i]=‘A‘;
}
else if(l<=w&&w<=r&&w%2==1){
s[i]=‘T‘;
}
else if((w<l||r<w)&&w%2==0){
s[i]=‘G‘;
}
else if((w<l||r<w)&&w%2==1){
s[i]=‘C‘;
}
else{
}
}
lens=strlen(s),lent=strlen(t);
getnexts();
KMP();
return 0;
}
2017 计蒜之道 初赛 第一场 A、B题