编写题解 1835: 蓝桥杯2016年第七届真题-碱基

解题思路:

注意事项:

参考代码:

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <cmath>

#include <cstring>

#include <stack>

#include <queue>

#include <set>

#include <map>

#include <vector>

#include <sstream>

#include <string.h>

using namespace std;

typedef long long ll;

const int inf=0x3f3f3f3f;

const ll mod=1000000007;

const ll N=25;

const double pai=3.14159265358979;

const int maxn2=1e9;

#define mem(a,b) memset(a,b,sizeof(a))

priority_queue<int,vector<int>,greater<int> >pq;

map<string,vector<int> >mp;

vector<int>v,ve;

map<string,vector<int> >::iterator it1;

int n,m,k,x;

string s,s1;

map<string,int>vis;

map<string,int>::iterator it;

ll ans,dp[105][105];

void solve()

{

   mem(dp,0);

   x=v.size();

   dp[0][0]=1;

   for(int i=1;i<=x;++i)

   {

       dp[i][0]=1;

       for(int j=1;j<=i;++j)

       {

           dp[i][j]=dp[i-1][j-1]*v[i-1]+dp[i-1][j];//状态转移方程

           dp[i][j]%=mod;

       }

   }

   ans+=dp[x][m];

   ans%=mod;

}

int main()

{

   scanf("%d %d %d",&n,&m,&k);

   for(int i=1;i<=n;++i)

   {

       cin >> s;

       vis.clear();//初始时默认为false

       for(int j=0;j+k<=s.size();++j)//以后再遇到截取字符串固定长度时，记得j+k<=s.size()

       {

           s1=s.substr(j,k);

           vis[s1]++;//先收集所有长度为k的子串，记录每个子串出现次数

       }

       for(it=vis.begin();it!=vis.end();++it)

           //first为键，second为值，map是红黑树结构，会自动对键的字典序排序

       {

           s=it->first;

           ve=mp[s];//取原来记录下的vector数组

           ve.push_back(it->second);//将新的出现次数插入数组尾部

           mp[s]=ve;

       }

   }

   for(it1=mp.begin();it1!=mp.end();++it1)

   {

       v=it1->second;

       if(v.size()<m)continue;//明显不满足条件，提前剪枝

       solve();

   }

   printf("%lld\n",ans);

   return 0;

}