链接：超越姐爱字符串 来源：牛客网

题目描述

超越学姐非常喜欢自己的名字，以至于英文字母她只喜欢“c”和“y”。因此超越学姐喜欢只含有“c”和“y”的字符串，且字符串中不能出现两个连续的“c”。请你求出有多少种长度为n的字符串是超越学姐喜欢的字符串。答案对1e9+7取模。

输入描述:

输入一个整数n。

1<=n<=100000

输出描述:

输出一个整数表示答案。

示例1 输入

3

输出

5

说明

cyy,cyc,yyy,yyc,ycy

动态规划： 第i位可能有两种情况，c或者y，i位的c只能由i-1位的y转化而来。i位的y却可以由i-1位的c或y转换而来,最后一位的c加上y的数量即为整个可能的组合，过程中不断对数组取余防止溢出，公式 > (a + b) % c = （a % c + b % c) % c 代码：

#include<iostream>
#define max 100007
#define N 1000000007
using namespace std;
int main(){
	long long dp[max][2] = {0};
	int n;
	dp[1][0] = 1;   //初始为c为y都可以
	dp[1][1] = 1;
	cin>>n;
	for(long long k=2;k<=n;k++){
		dp[k][0] += dp[k-1][0];
		dp[k][0] += dp[k-1][1];
		dp[k][0] = dp[k][0] % N;
		dp[k][1] += dp[k-1][0];
		dp[k][1] = dp[k][1] % N;		
	}
	cout<<(dp[n][0] + dp[n][1]) % N<<endl;
    return 0;
}

题目描述

 有n个长度为m的文本串，每个串只含有’0’和’1’。接下来有Q次询问，每次给出一个长度为m的字符串，且只含有’0’,‘1’和’_‘。如10_1_1。下划线可以匹配’0’或’1’。即10_1_1可以匹配101111,101101,100111,100101四种串。每次询问求出n个文本串中有多少个可以与当前询问的串匹配。

输入描述:

第一行输入n,m

接下来n行，每行输入一个长度为m的01串表示一个文本串。

第n+2行输入Q

接下来Q行，每行输入一个长度为m的字符串(只包含’0’,‘1’,’_‘)。

1<=n,m<=1000,1<=Q<=3000。

输出描述:

对于每次询问，输出n个文本串中有多少个与当前询问的串匹配。

示例1

输入

5 6

101101

011011

100110

111000

101111

2

1011_1

11

输出

2

3

说明

第一次询问：有101101，101111与1011_1匹配

第二次询问：有101101, 100110, 101111与11匹配

分析:

只有0和1的串，判断是否相等可以想到位运算 & 且

0 & 1 = 0，

0 & 0 = 0，

1 & 0 = 0，

1 & 1 = 1，

用数组超时才知道有一个叫做bitset的东西

可以发现只要是0参与的位运算结果都为0，两个1参与的位运算结果才为1，题意中_参与的匹配都为相等，因此可以将_看做0，关键是添加一个位运算结果数组q，与要询问的数组b共同决定给定的数组a，而位运算的结果都为0因此q对应位置为0，

询问的数组为1要想匹配1则q数组应该存1，

而询问的数组为0，先转化为1，再和0进行匹配，结果为0，q数组放置的值就为0，直接采用为运算即可

#include<iostream>
#include<string>
#include<bitset>
using namespace std;

int main(){	
    int n,m;
	int temp;
    char data;
    string data1;
    int t;
    int j=0;
    int count;
	cin>>n>>m;
	string b;
	bitset<1002> p,q,list[n];  //p存放处理过的b，q存放第三者结果
    temp = n;
    while(temp--){
		cin>>data1;
		for(int k=0;k<m;k++){
			list[j][k] = data1[k]-'0';  /*转化为数字*/
	}
	j++;
	}
	cin>>t;
	while(t--){
	count = 0;
	cin>>b;
	for(int k=0;k<m;k++){
		if(b[k]=='_')
			p[k] = q[k] = 0;
		else{
			p[k]=1;
			q[k]= b[k]=='1'? 1:0;
		}
	}
	
	for(int k=0;k<n;k++){
		if((p & list[k] )== q)
			count++;
	}
	cout<<count<<endl;
}
	return 0;
}