Codeforces Round #758 (Div.1 + Div. 2)
2021/12/12 23:17:35
本文主要是介绍Codeforces Round #758 (Div.1 + Div. 2),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1608A - Find Array
直接从2-n+1即可
#include<bits/stdc++.h> using namespace std; typedef long long ll; int n,T; int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=2;i<=n+1;i++) printf("%d ",i); printf("\n"); } return 0; }
1608B - Build the Permutation
首先考虑怎样才能有解,设有a个峰b个谷,那么a+b+1<n,并且a和b最多差一个,画一画就能发现,因为两个峰之间必有一个谷
然后考虑构造,直接取最大的a+b+2个,大的作峰,小的作谷,然后剩余的按从小到大放在最前面即可,具体的看代码
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+5; int p[maxn]; int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); int T,n,a,b; scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&a,&b); if(abs(a-b)>1 || a+b+2>n){printf("-1\n"); continue;} int flag=0; if(a<b) swap(a,b),flag=1; int pos=n; if(a==b) { for(int i=0;i<=a;i++) p[n-i*2]=pos--; for(int i=0;i<=b;i++) p[n-i*2-1]=pos--; for(int i=1;i<=pos;i++) p[i]=i; } else { for(int i=0;i<a;i++) p[n-i*2-1]=pos--; for(int i=0;i<=a;i++) p[n-i*2]=pos--; for(int i=1;i<=pos;i++) p[i]=i; } for(int i=1;i<=n;i++) { if(!flag) printf("%d ",p[i]); else printf("%d ",n-p[i]+1); } printf("\n"); } return 0; }
1608C - Game Masterh
个人觉得这道题非常的棒
首先我们要倒着考虑这个问题,如果x最后胜者,那么x一定在最后一轮赢了一个人y,倒数第二轮应该是x或y赢了z,这样依次拓展下去,如果能拓展到所有的人,就意味着x可以最终获胜
显然这个过程可以和图联系起来,考虑每一个人向他能打败的人连一个边,那么要是可以从x出发走到所有的点,就意味着x最终可以取胜,至此我们得到了一个的算法
继续考虑优化,由于这张图已经有级别的边了,所以一定要从这里入手优化,我们分别按照两张地图上的能力作为关键字排序,而后每次仅连接 i 和 i+1 即可,这样就仅仅连 2n-2 条边,又发现能到所有点相当于走到a最大或者b最大的点(因为他们可以战胜任何人),所以我们从amax和bmax两个位置出发遍历整张图即可
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+5; int T,n; struct capability { int val,id; }a[maxn],b[maxn]; vector <int> G[maxn]; bool cmp(capability x,capability y) { return x.val<y.val; } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i].val),a[i].id=i; for(int i=1;i<=n;i++) scanf("%d",&b[i].val),b[i].id=i; sort(a+1,a+n+1,cmp),sort(b+1,b+n+1,cmp); vector <int> ans(n+5,0); for(int i=1;i<=n;i++) G[i].clear(); for(int i=1;i<n;i++) G[a[i].id].push_back(a[i+1].id); for(int i=1;i<n;i++) G[b[i].id].push_back(b[i+1].id); ans[a[n].id]=ans[b[n].id]=1; queue <int> q; q.push(a[n].id),q.push(b[n].id); while(!q.empty()) { int u=q.front(); q.pop(); for(auto to:G[u]) { if(ans[to]) continue; ans[to]=1; q.push(to); } } for(int i=1;i<=n;i++) printf("%1d",ans[i]); printf("\n"); } return 0; }
这篇关于Codeforces Round #758 (Div.1 + Div. 2)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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功能效果提升