Codeforces Round #744 (Div. 3) F. Array Stabilization (AND version) (优先队列)

Codeforces Round #744 (Div. 3) F. Array Stabilization (AND version)  (优先队列)

  • 题意:有一长度为\(n\)的\(01\)序列,每次可以将序列元素右移\(d\)个单位,然后原序列和新序列每个元素取&,问你最少操作多少次使得序列所有元素都为\(0\),或者不存在.

  • 题解:对于大小为\(1\)的位置,它一定只能被某个是\(0\)的位置移动过来变成\(0\),所以我们考虑\(0\)的位置,移动后的新位置为\((i+d)%n\),如果新位置为\(0\),那么我们不操作,如果是\(1\),那么操作一次将其变为\(0\),之后再用新位置的\(0\)去覆盖其他位置的\(1\)(也可能不覆盖),用优先队列维护操作次数,直到没有\(1\)为止

  • 代码:

    #include <bits/stdc++.h>
    #define ll long long
    #define fi first
    #define se second
    #define pb push_back
    #define me memset
    #define rep(a,b,c) for(int a=b;a<=c;++a)
    #define per(a,b,c) for(int a=b;a>=c;--a)
    const int N = 1e6 + 10;
    const int mod = 1e9 + 7;
    const int INF = 0x3f3f3f3f;
    using namespace std;
    typedef pair<int,int> PII;
    typedef pair<ll,ll> PLL;
    ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
    ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
     
     
    int main() {
        int _;
        scanf("%d",&_);
        while(_--){
            int n,d;
            scanf("%d %d",&n,&d);
            vector<int> a(n+1);
            priority_queue<PII,vector<PII>,greater<PII>> h;
            for(int i=0;i<n;++i){
                scanf("%d",&a[i]);
                if(!a[i]) h.push({0,i});
            }
            int ans=0;
            while(!h.empty()){
                auto now=h.top();
                h.pop();
                int cur=(now.se+d)%n;
                if(a[cur]==0) continue;
                a[cur]=0;
                h.push({now.fi+1,cur});
                ans=max(ans,now.fi+1);
            } 
            bool flag=true;
            for(int i=0;i<n;++i){
                if(a[i]){
                    flag=false;
                    break;
                }
            }
            if(flag){
                printf("%d\n",ans);
            }
            else puts("-1");
        }
     
     
     
        return 0;
    }
    
上一篇:pcie Riffa 之注意事项


下一篇:AMBA简介