[luogu] CF165C Another Problem on Strings 类DP

前言

传送门 :

思路

本人太菜,丝毫没感觉是一道模拟QAQ

前置知识 : 子串是连续的

我们先做这题之前,先计算一下如下 : 当 k = = 1 k == 1 k==1的时候,发现都是 3 3 3 100 = 3 100 = 3 100=3 001 = 3 001 = 3 001=3 010 = 3 010 = 3 010=3

也就是说,我们其实对于这种 010 010 010 和 100 100 100

其实都是可以将 0 0 0放在前面统计的

因此这样子 这道题目就变成了一道模拟

我们只需要每次遇到 1 1 1的时候,统计一下前面 0 0 0的个数即可

CODE

const int N  = 1e6+10;
int dp[N];



ll ans ; 
int cnt,k;
string s;
            
int change_int(char a)
{
	return a-'0';
}
void solve()
{
	dp[0] = 1;
		
	cin>>k;
	cin>>s;
	
	int len  =s.size();
	for(int i=0;i=k)
	  ans+=dp[cnt-k];
	
	 dp[cnt]++;	
	}
	cout