Educational Codeforces Round 183 (Rated for Div. 2)

unknown_risk · 2025-10-07 16:41:09 · 个人记录

B: Deck of Cards

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

C: Monocarp's String

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

Code

        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";
        }