F. Array Stabilization (AND version)

题目链接：Problem - 1579F - Codeforces

题目大意：给一个n,d n表示数组的长度，d表示每次将数组向右移动的长度，列入d=2,数组：1 2 3 4 5 ，那么下一次移动过后的数组为 4 5 1 2 3 . 由于数组只包含0与1，要求让移动过后的数组与前一个数组做AND运算，求多少次可以将数组变为全0, 如果不能输出-1，可以输出步数。 1<=n<=1e6, 1<=1<n, ai为0或1.

思路：通过题目的要求，我们可以知道做AND运算，只有两个1才会为1.然后通过数组的移动可以发现  每一次做AND运算，都会将整个数组的状态改变，而该状态是基于上一个数组变化而来的。可以发现要想状态改变，移动过后的数组的那个位置上要为0，与之对应的位置上为1.

做法：可以发现状态的改变而引起的，是基于上一个状态。考虑采用bfs,将当前数组里的0的下标压入队列，然后再对当前状态的所有下标进行d的移动，当发现可以改变时，又压入队列（为下一个状态）。然后记录次数即可。

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
using i64 = long long;

void solve(){
    int n, d;
    cin >> n >> d;
    queue<int> q;
    bool ok = true;
    vector<int> a(n);
    for(int i=0; i<n; i++) {
        cin >> a[i];
        if(a[i])ok = false;
    }
    if(ok) {
        cout << 0 << "\n";
        return;
    }
    int res = 0;
    for(int i=0; i<n; i++) {
        if(a[i]==0) {
            q.push(i);
        }
    }
    while(!q.empty()) {
        int sz =q.size(); //取当前状态
        for(int i=0; i<sz; i++) {
            int x = q.front();
            q.pop();
            int pos = (x+d) % n;
            if(a[pos]==1) { //发现可以改变压队
                a[pos] = 0;
                q.push(pos);
            }
        }
        res++;
    }
    for(int i=0; i<n; i++) {  //看是否成功
        if(a[i]==1) {
            cout << "-1\n";
            return ;
        }
    }
    cout << res-1 << "\n";
}

signed main(){
    IOS;
    int T = 1;
    cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}

py代码：

from collections import deque


def solve() :
    n, d = map(int,input().split())
    a = list(map(int,input().split()))
    q = deque()
    ok = True
    for i in range(n):
        if a[i]==0:
            q.append(i)
        else:
            ok = False
    if ok:
        print(0)
        return
    res = -1
    while q:
        sz = len(q)
        while sz>0:
            x = q.popleft()
            pos = (x+d) % n
            if a[pos]==1:
                a[pos] = 0
                q.append(pos)
            sz-=1
        res+=1
    for i in a:
        if i==1:
            print(-1)
            return
    print(res)
T = int(input())
while T:
    solve()
    T-=1

欢迎大佬纠正，感谢你的收看与点赞。