人人好,迎接人人阅读周末算法题专题。

今天我们选择的问题是codeforces上周竞赛的C题,我上周本来想参赛的,都已经报名了。然则厥后由于身体不适,以是早早休息了,没有加入。今天抽闲做了一下上周的问题之后异常庆幸还好上周没加入,否则的话rating一定要掉了。

问题链接:https://codeforces.com/contest/1405/problem/C

这道题有6800多人通过,怎么看也不算是难题,然则我做了一上午都没能AC。最后又苦思冥想了良久,才最终做出来。做出来之后的第一感受就是这道题太牛了,值得一说,算是那种谁都能看懂题意,都能想想设施,然则能做出来很不容易的问题。


照样一如既往的codeforces赛题的气概,不严酷考察算法,你做不出来大概率不是由于知道的算法不够多,而是由于你思维能力不够。

题意


给定一个字符串,字符串当中只包罗三种字符,分别是0,1和?。?示意既可以是0也可以是1。现在呢,给定一个整数k,k示意滑动窗口的长度。我们需要从头最先将一个滑动窗口向字符串末尾移动,很明显,不管我们怎么移动,滑动窗口里的字符的数目应该都是k个。

由于存在?既可以是0也可以是1,我们希望我们能找到一种方案,把一部分?酿成0,另外一部分酿成1。使得在这个窗口滑动的历程当中,窗口里的0的数目和1的数目相等

给定字符串以及k,要求返回YES或NO,YES示意存在这样的方案,NO示意不存在。

这是一道多组测试数据的问题,首先给定一个t示意数据组数。对于每一组数据首先给定n和k两个整数,n示意字符串的长度,k示意滑动窗口的长度。接着给定一个字符串,保证字符串当中只有0,1和?,而且字符串的长度为n。

其中

样例




心路历程


首先通过给定的数据局限我们可以确定一点,就是若是我们一个滑动窗口一个滑动窗口地判断一定会超时。由于最坏情形下,,这时滑动窗口的数目一共也是k个,对于每一个窗口我们需要遍历一遍。以是整体的复杂度是,对于1e5的数据局限来说这一定是不能接受的。

于是我转变思绪,决议从整体入手。怎么入手呢?

整体入手


对于每一个滑动窗口来说都要保证其中0和1的数目相等,我们考察一下会发现,每一个位置的字符一共泛起的次数是差别的。好比10?1?0这个字符串,我们假设k=4。我们会发现第0位的字符1只在1个窗口泛起,第1位的0会在两个滑动窗口泛起。对于每一个窗口我们都要保证0和1的数目一样多,那么也就是说我们要保证这些窗口泛起的0和1的总数累加在一起应该一样多。

以是对于字符串当中的每一位,我们都盘算它们的孝敬度,孝敬度就是总共泛起的次数。这个值实在很好算,就是。好比第0位的1只泛起了一次,以是孝敬度就是1,第1位的0泛起了两次,孝敬度就是2。对于?来说我们是不确定它们孝敬是0照样1的,但可以一定的是孝敬度是确定的。以是我们用一个数组来存储下来它们的孝敬度。

最终我们可以获得两个数,分别是0的所有孝敬度,1的孝敬度以及**?组成的孝敬度数组**。我们要做的就是从?组成的孝敬度数组当中选出一些来酿成0,另外一些酿成1,最后让0和1的孝敬度相等。

实在问题就转酿成了给定一个数组和一个target,要求我们能否从这些数组当中选出一部分来求和之后即是target。我们之前在LeetCode当中做过这样的问题,应该说是异常基础了,只需要用递归就可以实现了。

,

皇冠足球app

www.huangguan.us是一个提供皇冠代理APP下载、皇冠会员APP下载、皇冠体育最新登录线路、新2皇冠网址的的体育平台。新皇冠体育官网是多年来值得广大客户信赖的平台,我们期待您的到来!

,

但很遗憾的是,我把代码写出来之后连样例都过不了。错在了这个样例:

6 2
????00

由于最后泛起了两个0,以是对于最后一个窗口来说,是无论如何也是无法杀青的。这个结论实在不难发现,考察一下样例就可以。

维护区间


发现了这个问题之后,于是我最先想设施打补丁,也就是设计一种方式能够解决这个问题。我于是想了一个设施,对于每一个窗口我都维护两个值。分别是应该赋值成1的?的数目和应该赋值成0的?数目,举个例子,好比说照样适才谁人例子,一最先遇到两个??,那么显然应该一个即是0一个即是1。

这样当我们移动窗口的时刻,会移出去一个字符,移进来一个字符。对于每个字符来说都有三种可能,以是一共就有9种可能。这9种情形我们也很容易想明了,首先移出和移入相等的情形,一定是正当的。若是移出的和移入不相等,而且当中没有?的话,那么一定是非法的。

若是移出0,移入?,那么移入的?一定是0,也就是说确定是0的问号数目加一。若是移出的是1,那么说明移入的?是1。若是移出的是?,移入的是1,说明移出的?也是1,也就是消耗了一个确定是1的?,同理若是移入的是0,也是一样的。

这样我们可以维护窗口内确定是0和确定是1的?的数目,在转变的历程当中,只要有一个小于0,那么就说明情形是非法的,否则说明是正当的。

我原本以为这样的方案应该已经很完美了,然则最后照样没有AC。我仔细想了一下,实在这种方案照样存在破绽,由于我们没设施判断是否会泛起前后矛盾的情形。也就是说最好要把每一个?的取值确定下来,而不是模棱两可,由于模棱两可就意味着可能存在矛盾。

正解


然则理论上来说每一个?都有两种可能,我们怎么能确定下来?的取值呢?

若是是单单思索这个问题是很难的,但实在我们适才已经距离正解异常接近了,由于我们在维护区间的时刻发现了一个异常重要的特征。就是当我们移动窗口的时刻,移出的字符必须和移入的一致,否则一定非法。而我们移动的窗口的长度是确定的,我们就可以获得一个性子: s[i] = s[i+k]。


我们看下上图,上图框起来的k个元素代表窗口,当我们窗口移动的时刻会移入一个元素,也会移出一个元素。我们假设现在窗口内的元素是正当的,也就是0和1一样多。那么当我们移动之后若是也是正当的,必须要保证移入的和移出的元素一样,或者其中有一个是?。

我们进一步考察会发现i和i + k,它们关于k同余。说白了就是它们对k取模的余数一样,我们把所有关于k取模之后余数一样的数的聚集称为剩余系。k的剩余系一共有k个,这个也很容易想明了,由于k的余数一共有0到k-1这k个。不管我们怎么移动窗口,窗口内的元素都是k个,而且是每一个剩余系各包罗一个元素。以是我们可以检查每一个剩余系对应下标的元素是否所有相等或者是即是?,若是不满足那么一定非法。

检查完所有的剩余系之后,我们还要统计一下为0的剩余系以及为1的剩余系的数目。若是跨越k的一半,那么也一定是非法的。若是你能把这些点所有想明了,那么这题的代码也就异常简朴了。

t = int(input())

for _ in range(t):
    n, k = list(map(int, input().split(' ')))
    st = input()
    if k % 2 == 1:
        print('NO')
        continue
    
    zero, one = 00
    flag = True
    # 检查所有剩余系
    # 枚举对k取模之后的余数
    for i in range(k):
        # tmp存这个剩余系应该所有相等的字符
        tmp = None
        for j in range(i, n, k):
            if st[j] != '?':
                # 若是tmp是1遇到了0或者是tmp是0遇到了1
                if tmp is not None and st[j] != tmp:
                    flag = False
                    break
                tmp = st[j]
        if not flag:
            break
            
        # 凭据tmp判断是所有为0的剩余系+1,照样所有为1的剩余系+1
        if tmp == '0':
            zero += 1
        elif tmp == '1':
            one += 1

    # 有一种剩余系的数目跨越一半,那么一定无法组成平衡
    if max(one, zero) > (k // 2):
        flag = False

    print('YES' if flag else 'NO')

我以为今天的题挺难的,解题的思绪绕了好几个弯。从一最先的剖析问题到后面实验解决,发现踩了坑,再继续剖析,继续踩坑,最后发现了要害线索从而解出了问题。在问题解决之前百思不得其解是很痛苦的,然则想到了解法之后的成就感照样很令人欣喜的。我们做算法题磨炼自己的能力,实在就是在这两种体验之间往返摇晃,在这历程当中获得发展。从这个角度来说这题的质量简直很高,是我个人认为的高质量算法题。