CF1383E Strange Operation

一、题目

点此看题

二、解法

大体思路自己想的（独立思考乐趣多??），最后的建图参考了SharpnessV大佬的方法。

类似子序列自动机的方法，我们给每个点找一个后继节点。但是本题的要求显然更高，它要求我们知道子序列自动机的原理：找到最有潜力的后继节点就可以表达所有方案。

所谓“潜力”，也就是以它开始的选择范围更广，所以常规算法我们直接找后面第一个点即可。

但这样做的前提是把局部本质相同的方案用这个后继节点来表达，但由于本题的特殊性，我们考虑区分局部方案的依据就是相邻两个 \(1\) 之间 \(0\) 的个数（你可以理解成把 \(1\) 作为分界点来动态规划），所以对于每一种 \(0\) 的个数我们需要找到一个最有潜力的后继，但由于本题连续的 \(0\) 可以继承，所以我们是把一个代表 \(0\) 个数的区间连到原序列一个区间的第一个点上面去。

如果你完全理解我上面所说，就可以认同下面巧妙的建图方法了：

• 对于原序列中的 \(0\)，如果添上 \(0\)，若是某一段连续 \(0\) 的末尾，需要找到后面第一个长度大于当前段的连续段，连到连续段的第一个点即可，否则直接连到下一个 \(0\)；如果添上 \(1\)，直接连后面第一个 \(1\) 即可。
• 对于原序列中的 \(1\)，直接连向后面第一个 \(0\)、后面第一个 \(1\) 即可。

所以用单调栈就可以很轻易地把图建出来，时间复杂度 \(O(n)\)

三、总结

字符串本质不同计数问题中，匹配思想很重要??

#include 
#include 
#include 
using namespace std;
const int M = 1000005;
const int MOD = 1e9+7;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,l,r,ans,nm[M],p[M],g[M][2],f[M];char s[M];
void add(int &x,int y) {x=(x+y)%MOD;}
signed main()
{
	scanf("%s",s+1),n=strlen(s+1);
	l=1;while(s[l]=='0') l++;
	r=n;while(s[r]=='0') r--;
	if(l>r) {printf("%d\n",n);return 0;}
	for(int i=r,ls=0;i>=l;i--)
	{
		g[i][1]=ls;
		if(s[i]=='1') ls=i;
	}
	for(int i=r,ls=0;i>=l;i--)
	{
		if(s[i+1]=='0' || s[i]=='1') g[i][0]=ls;
		if(s[i]=='0') ls=i;
	}
	for(int i=l,nw=0;i<=r;i++)
	{
		if(s[i]=='0')
		{
			nw++;
			while(m && nm[m]