AtCoder Beginner Contest 226 (A~E)
2021/11/8 6:10:24
本文主要是介绍AtCoder Beginner Contest 226 (A~E),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
AtCoder Beginner Contest 226
A - Round decimals
给你一个小数让你输出四舍五入后的整数,我直接%.0f输出wa了一个点,用字符串判断过了。。。
B - Counting Arrays
给你\(n\)个数组,问你有多少种数组
直接map输出size就好
C - Martial artist
你需要学习\(n\)个步伐,学习第\(i\)个步伐需要消耗\(t_i\)的时间,并且还要满足必须先学会之前的一些步伐,问你学会第\(n\)个步伐最少需要多长时间
显然倒着跑dfs即可
#include <bits/stdc++.h> using namespace std; #define PII pair<int,int> #define fi first #define se second #define pb push_back #define ll long long #define ull unsigned long long #define PLL pair<ll,ll> const int N=1000010; const int mod=1e9+7; int n; int t[N]; vector<int> a[N]; bool vis[N]; ll res=0; void dfs(int u){ vis[u]=true; for(auto w:a[u]){ if(!vis[w]){ res+=t[w]; dfs(w); } } } int main(){ scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%d",&t[i]); int k; scanf("%d",&k); for(int j=1;j<=k;++j){ int x; scanf("%d",&x); a[i].pb(x); } } dfs(n); printf("%lld\n",res+t[n]); return 0; }
D - Teleportation
二维平面上有\(n\)个点,找到最少的点对集,使得任意一点选择某个点对集后加上任意次后能到达其他所有点
\(n\)范围给了\(500\),那么我们直接\(O(n^2)\)枚举,每个点对集进行约分,保证不重复,用map存一下,然后输出size*2即可
#include <bits/stdc++.h> using namespace std; #define PII pair<int,int> #define fi first #define se second #define pb push_back #define ll long long #define ull unsigned long long #define PLL pair<ll,ll> const int N=1000010; const int mod=1e9+7; int n; PII pt[N]; map<PII,int> mp; int main(){ scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%d %d",&pt[i].fi,&pt[i].se); } for(int i=1;i<=n;++i){ for(int j=i+1;j<=n;++j){ if(i==j) continue; int x=pt[i].fi-pt[j].fi; int y=pt[i].se-pt[j].se; int d=__gcd(x,y); mp[{x/d,y/d}]++; } } printf("%d\n",(int)mp.size()*2); return 0; }
E - Just one
\(n\)个点,\(m\)条无向边,现在给边赋方向,使得每个点有且仅有一条出边,问你有多少种方案
自己在纸上画几个样例后,不难发现对于每个连通块,只要满足点数刚好等于边数即可
#include <bits/stdc++.h> using namespace std; #define PII pair<int,int> #define fi first #define se second #define pb push_back #define ll long long #define ull unsigned long long #define PLL pair<ll,ll> const int N=1000010; const int mod=998244353; int n,m; vector<int> edge[N]; PII pt[N]; int p[N]; int cnt1[N],cnt2[N]; vector<int> v; int find(int x){ if(p[x]!=x) p[x]=find(p[x]); return p[x]; } int main(){ scanf("%d %d",&n,&m); for(int i=1;i<=m;++i){ scanf("%d %d",&pt[i].fi,&pt[i].se); } for(int i=1;i<=n;++i) p[i]=i; for(int i=1;i<=m;++i){ int fu=find(pt[i].fi); int fv=find(pt[i].se); if(fu!=fv) p[fu]=fv; } for(int i=1;i<=n;++i){ int now=find(i); if(!cnt1[now]) v.pb(now); cnt1[now]++; } for(int i=1;i<=m;++i){ int now=find(pt[i].fi); cnt2[now]++; } bool flag=true; for(auto w:v){ if(cnt1[w]!=cnt2[w]) flag=false; } if(!flag){ puts("0"); return 0; } ll ans=1; for(int i=1;i<=(int)v.size();++i){ ans=ans*1ll*2%mod; } printf("%lld\n",ans); return 0; }
这篇关于AtCoder Beginner Contest 226 (A~E)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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功能效果提升