Educational Codeforces Round 183 (Rated for Div. 2)

B: Deck of Cards

Sol: 看成一个双端队列。若队中元素通过0或1的操作出队，状态一定是‘-’。当通过2出队的可能是在队首也可能在队尾，极限情况是均在队尾或均在队首。通过这两种操作出队的元素状态为'?'，剩余仍在队列中的为'+'。模拟即可。

C: Monocarp's String

Sol: 统计字符串A与B个数之差diff，找到最短的连续子串使得A与B的个数之差等于diff。实现的巧妙之处在于利用了map的find和end功能。

Code

CPP

        for(int i=0;i<n;i++)
		{
			if(s[i]=='a')d++;
			else d--;
		}
		if(d==0)puts("0");
		else
		{
			map<int,int>x;
			int d1=d,d2=0,mn=1e9;
			x[0]=-1;
            //d1表示diff+B-A的前缀和
            //d2表示A-B的前缀和
			for(int i=0;i<n;i++)
			{
				if(s[i]=='a')
				{
					d1--;
					d2++;
				}
				else
				{
					d1++;
					d2--;
				}
                //对于右端点i，find(-d1)可以找到A-B个数差为diff的左端点，使得子串满足条件
				if(x.find(-d1)!=x.end())mn=min(mn,i-x[d1]);
                //对于相同的d2,i大的会覆盖小的，即左端点会尽可能靠近右端点，所以每次计算得到的长度会尽可能的小
				x[d2]=i;
			}
			if(mn==n)puts("-1");
			else cout<<mn<<"\n";
		}

Educational Codeforces Round 183 (Rated for Div. 2)

文章操作

B: Deck of Cards

C: Monocarp's String

相关推荐

评论

Educational Codeforces Round 183 (Rated for Div. 2)