2017计蒜之道 预赛 第一场
A
16种情况手动暴力即可
#include <bits/stdc++.h>
#define nmax 7
using namespace std;
int mp[nmax][nmax];
int n,m;
int cnt = 0;
void ge()
{
cnt++;
}
void check()
{
if(mp[0][0] == 1 && mp[0][3] == 1 && mp[0][6] == 1){
//printf("1
");
ge();
}
if(mp[0][0] == 1 && mp[3][0] == 1 && mp[6][0] == 1){
//printf("2
");
ge();
}
if(mp[0][6] == 1 && mp[3][6] == 1 && mp[6][6] == 1){
//printf("3
");
ge();
}
if(mp[6][0] == 1 && mp[6][3] == 1 && mp[6][6] == 1){
//printf("4
");
ge();
}
if(mp[1][1] == 1 && mp[1][3] == 1 && mp[1][5] == 1){
//printf("5
");
ge();
}
if(mp[1][1] == 1 && mp[3][1] == 1 && mp[5][1] == 1){
//printf("6
");
ge();
}
if(mp[5][1] == 1 && mp[5][3] == 1 && mp[5][5] == 1){
//printf("7
");
ge();
}
if(mp[1][5] == 1 && mp[3][5] == 1 && mp[5][5] == 1){
//printf("8
");
ge();
}
if(mp[2][2] == 1 && mp[2][3] == 1 && mp[2][4] == 1){
//printf("9
");
ge();
}
if(mp[4][2] == 1 && mp[4][3] == 1 && mp[4][4] == 1){
//printf("10
");
ge();
}
if(mp[2][2] == 1 && mp[3][2] == 1 && mp[4][2] == 1){
//printf("11
");
ge();
}
if(mp[2][4] == 1 && mp[3][4] == 1 && mp[4][4] == 1){
//printf("12
");
ge();
}
if(mp[0][3] == 1 && mp[1][3] == 1 && mp[2][3] == 1){
//printf("13
");
ge();
}
if(mp[4][3] == 1 && mp[5][3] == 1 && mp[6][3] == 1){
//printf("14
");
ge();
}
if(mp[3][4] == 1 && mp[3][5] == 1 && mp[3][6] == 1){
//printf("15
");
ge();
}
if(mp[3][2] == 1 && mp[3][1] == 1 && mp[3][0] == 1){
//printf("16
");
ge();
}
}
void out()
{
for(int i = 0; i<7;++i){
for(int j = 0; j<7;++j){
printf(" %d ",mp[i][j]);
}
printf("
");
}
}
int main()
{
while(scanf("%d %d",&n,&m) != EOF){
int x,y;
cnt = 0;
memset(mp,0,sizeof(mp));
for(int i = 0; i<n; ++i){
scanf("%d %d",&x,&y);
mp[x+3][y+3] = 1;
}
for(int i = 0; i<m;++i){
scanf("%d %d",&x,&y);
mp[x+3][y+3] = 2;
}
//out();
check();
printf("%d
",cnt);
}
return 0;
}
B
按题意生成主串,然后裸的KMP,算出子串个数即可。
#include <bits/stdc++.h>
#define nmax 1000000+5
using namespace std;
int w[nmax];
char str[nmax];
char buf[nmax];
int Next[nmax];
int n,a,b,l,r,ans;
void getstr(int pos)
{
if(w[pos]>=l && w[pos] <=r){
if(w[pos] & 1) str[pos] = 'T';
else str[pos] = 'A';
}else{
if(w[pos] & 1) str[pos] = 'C';
else str[pos] = 'G';
}
}
void make()
{
for(int i = 0; i<n;++i){
if(!i) w[i] = b;
else{
w[i] = (w[i-1] + a) % n;
}
getstr(i);
}
str[n] = ' ';
}
void MakeNext(int M){
int i=0,j=-1;
Next[i] = -1;
while(i<M){
if(j==-1||buf[i]==buf[j])Next[++i] = ++j;
else j = Next[j];
}
}
int KMP(int pos,int N,int M){
int i = pos, j = 0,ans = 0;
while(i<N){
if(str[i]==buf[j]||j==-1)i++,j++;
else j = Next[j];
if(j==M){
ans++;
j = Next[j-1];
i--;
}
}
return ans;
}
int main()
{
while(scanf("%d %d %d %d %d",&n,&a,&b,&l,&r) != EOF){
ans = 0;
make();
scanf("%s",buf);
MakeNext(strlen(buf));
int ans = KMP(0,n,strlen(buf));
printf("%d
",ans);
}
return 0;
}
C
想复杂了,打表发现循环可以分为三段,第一段GCGC……,第二段ATAT……第三段GCGC……。
然后分类讨论,可以成功匹配的t串,只有3种情况。
第一种:全为GC串,可以在第一段和第三段根据长度求出。
第二种:全为AT串,可以在第二段根据长度求出。
第三种:前为GC串后为AT串或者前为AT串后为GC串,只有1种可以匹配的情况。
D
目前还没看,感觉an互质上要做文章。