bstringk.cpp

离散01串问题 &laquo 问题描述： (n,k)01 串定义为：长度为n 的01 串

#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

int n,k,m;//m=n/k;根据条件，子串的长度只能从1～(n/k)。

__int64 reduct,*snum;//reduct记录被减枝的串的个数，snum[i]记录第n-i层下有几个串
short *v, *count;//串长为1时，v[t]记录t层的值；count记录到t层，所积累的连续相同子串数。
int **dcount, **value;//value[i][t]中i表示当前子串长度,t代表当前深度；value[i][t]用来记录值，方便后面比较。
                      //dcount[i][t]中i表示当前子串长度,t代表当前深度；dcount[i][t]用来记录连续的相同子串的个数。

bool isok(int dep)//m>=2时的判断
{
	if(v[dep]!= v[dep-1])//连续串长度为1时
	{
		dcount[1][dep]=1;
		value[1][dep]=v[dep];
		
	}
	else
	{
		value[1][dep] = v[dep];//记录长度为1，到t层的值
		dcount[1][dep] = dcount[1][dep-1] + 1;//连续个串个数+1
		if(dcount[1][dep] == k)//达到k，停止，返回false.
		{
			return false;
		}
	}
	for(int i=2;i<=m;i++)//连续串长度大于2时
	{
		value[i][dep]=(value[i-1][dep-1]<<1)+v[dep];//value[i - 1][t - 1]的值右移一位，加上x[t]得到value[i][t]的值。
		if(dcount[i][dep-i]==0)
			dcount[i][dep]=1;
		else 
			if(value[i][dep]==value[i][dep-i])//和value[i][t - i]相比，如果相等则长度为i的相同连续串的个数+1
			{
				dcount[i][dep]=dcount[i][dep-i]+1;
				if(dcount[i][dep]== k)
				{
					return false;
				}
			}
			else dcount[i][dep] = 1;
	}
		return true;
}

bool search1(int dep)//当m=1时候的判断
{
	if(v[dep]!=v[dep-1])
	{
		count[dep]=1;//连续被中断，重新记数。
		if(n-dep<k-1)
			return false;
		if(n-dep==k-1)
		{
			reduct+=1;
			return false;
		}
		
	}
	else 
	{
		count[dep]=count[dep-1]+1;
		if(count[dep]==k)//符合减枝条件，reduct记录减去的串的个数，不需再往下搜索,返回false。
		{
			reduct+=snum[n-dep];
			return false;
		}
		if(n-dep<k-count[dep]) //剩下的层数不够，不需再往下搜索，返回false。
			return false;
	}
	return true;
}


int main()
{
	ifstream inf("input.txt");
	ofstream outf("output.txt");

	int dep;//层数
	__int64 result= 0;//不含k个连续的相同子串；=（总串数）-（被减枝的串数）。
	
	inf>>n>>k;
	m=n/k;//需要搜索的子串的最大长度

//一些特殊情况的特殊处理````	
	if(n<k)
	{
		result= pow(2, n);
		
	}
	else if(n == k)
	{
		result= pow(2, n) - 2;
	}
	else if(n == k + 1)
	{
		result= pow(2, n) - 6;
	}

	else if(k == 1)
	{
		outf<< 0;
		return 0;
	}
	else if(k == 2)
	{
		outf<< 0;
		return 0;
	}
	else
	{ 
		if(m >= 2)//串长大于2时
		{		
			v= new short [n + 1];
			dcount= new int* [m + 1];
			value = new int* [m + 1];
			for(int i = 1; i < m + 1; i ++)
			{
				dcount[i] = new int[n + 1];
				value[i] = new int[n + 1];
				for(int j = 0; j < n + 1; j ++)
					dcount[i][j] = 0;
			}			
			v[1] = 0;
			value[1][1] = 0;
			dcount[1][1] = 1;
			for(i = 2; i <= n; i ++)
				v[i] = -1;			
			dep= 2;
			while(dep> 1)
			{
				v[dep] += 1;
				while((v[dep] < 2) && !(isok(dep))) v[dep] += 1;
				if(v[dep] < 2)
				{
					if(dep== n)
					{
						result++;
					}
					else
					{
					
						dep++;
						v[dep] = -1;
					}
				}
				else dep--;
			}
			result<<= 1;
			delete [] v;
			for(i = 1; i < m + 1; i ++)
			{
				delete [] dcount[i];
				delete [] value[i];
			}
			delete [] dcount;
			delete [] value;
		}
		else//if(m>=2)
		{
			__int64 temp;
			v= new short [n + 1];
			count= new short[n + 1];
			v[1] = 0;
			count[1] = 1;
			for(int i = 2; i <= n; i ++)
				v[i] = -1;
			snum= new __int64[n + 1];
			temp = 1;
			snum[0] = 1;//根下面有几个串
			for(int j = 1; j <= n; j ++)
			{
				temp <<= 1;
				snum[j] = temp;
			}			
			dep= 2;
			while(dep> 1)
			{
				v[dep] += 1;
				while((v[dep] < 2) && !(search1(dep))) v[dep] += 1;
				if(v[dep] < 2)
				{
					if(dep< n)
					{
						dep++;
						v[dep] = -1;
					}
				}
				else dep--;
			}
			result= (snum[n - 1] -reduct) * 2;
			delete [] v;
			delete [] count;
			delete [] snum;
		}
	}
	char str[23]; //将int64转化成字符型输出
	_i64toa(result, str, 10); 
	outf<<str<< endl;
	return 0;
}