「随笔」HH的题

  1. 1. 「随笔」HH的题
    1. 1.1. Problem
    2. 1.2. 思维解析
    3. 1.3. 题目解法

「随笔」HH的题

记一个脑洞题,晚自习花了半个小时分析了个暴力,这里我就把暴力版本放上来。

Problem

给出$01$序列$A$,每一次操作为选取一个长度为$k$的区间(定义区间的左端点为$l$,右端点为$r$,则$r - l + 1 = k$),将这个区间内所有$0$变成$1$,$1$变成$0$。如果能将这个数列内的元素全都变为$0$,输出最少的操作次数,并且输出操作的所有区间的左右断点。如果不行,请输出NIE。数列长度$n \le 10^3, k \le 10^3$。(其实可以扩大到$10^6$,只是鄙人能力不足)

思维解析

额,首先,对于这种题目,我们要分析:“每一次操作‘究竟’会造成什么影响”。然而,操作仅仅是$01$翻转罢了,于是,我们将相邻两个数看成“一对数”,对于“一对数”,我们需要关注的信息仅仅是“这两个数是否相同”。如果区间中所有的数对都满足“两数相同”,则这个序列不是全$1$序列就是全$0$序列。而对于每一次操作,我们能影响的是两个数对,操作的左区间是$l$,右区间是$r$,则$l - 1, l$和$r, r + 1$这两对数对受到了影响,这两数对的性质被“取反”了。即原本是相同的,会变成不同的,原本是不同的,则会变成相同。而对于区间内的所有数对的内部的相对性质都没有改变。这样,我们的操作就从区间操作变成了点操作。数对不太好描述,我们选取差分,差分数组为$B$,即$a_i = a_{i -1}$时,$b_i = 0$,否则$b_i = 1$。然后呢?如果每次操作两端是$b_l, b_r$,$B$中$1$的个数为$s$,$b_l \wedge b_r = 1$,则$s = s - 2$。$b_l \wedge b_r = 0$,且$b_l \vee b_r = 1$,则$s$不变。即每次操作能减少的$s$数量为$0$或$2$。但这不代表我们不能使距离不为$k$的两个$1$都变成$0$,然而将这样的$1$变成$0$的代价是$\frac{r - l + 1}{k}$次操作。

题目解法

前面都是思维铺垫,如果没有耐心看,可以直接看这里。贪心策略:从数列的第一个向后扫,遇到$1$,假设当前在$i$位置,则对$[i, i + k - 1]$进行操作,这样的操作次数一定最少。为什么?假如这次不操作$i$位置上的$1$,在之后一定会有一次操作的$l$或$r$为$i$。或是$l = i - k + 1$,或是$r = i + k - 1$,而对于本贪心策略而言,如果在$i - k + 1$位置上,那么$i - k + 1$位置一定会有一次被变为$1$,或一开始就是$1$。即在对$i - k + 1, i$进行操作时,当前位置已经被变为$0$。如果是在$i + k - 1$位置上,那这次操作$i, i + k - 1$和在之后的某一次操作$i, i + k - 1$是等效的。即操作次数一定不会减少,即如果这个数列能被全变为$0$,这种操作方法的次数一定最少。假如这次操作了这个$i + k \times t - 1$,并且后面的$i + k \times t - 1$位置上有一个$1$,那么必定会在$k$次操作后处理到$i + k \times t - 1$位置上。因为这一次操作后,$i + k - 1$位置的值会变为$i + k - 1$,直到扫到$i + k - 1$位置时,都不会有任何操作使$i + k - 1$位置变为$i + k - 1$,所以必定会有一次操作在$i + k - 1$上。即如果这个数列能被全变为$0$,这种操作方法一定能使其变为全$0$数列。

思维过程略复杂,我也说的不是很清楚,如有问题欢迎指正。(关于操作位置的问题我懒得改了,太麻烦)