Codeforces Round #744 (Div. 3) F. Array Stabilization (AND version) (优先队列)
2021/9/30 6:10:56
本文主要是介绍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; }
这篇关于Codeforces Round #744 (Div. 3) F. Array Stabilization (AND version) (优先队列)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升