AtCoder Beginner Contest 350

2024-04-22 07:04
文章标签 350 atcoder beginner contest

本文主要是介绍AtCoder Beginner Contest 350,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

A - Past ABCs

简单的枚举判断即可

#include "bits/stdc++.h"
using namespace std;#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int> 
#define vi vector<int>
#define si set<int> 
#define mi map<int,int>
#define mc map<char,int>
#define YES cout<<"Yes"<<endl;
#define NO  cout<<"No"<<endl;
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
void solve()
{string s;cin>>s;int sum=0;for (int i=3;i<6;i++){sum=sum*10+(s[i]-'0');}string s1=s.substr(0,3);if(s1=="ABC" && sum>=1 && sum<=349 && sum!=316){YES}else {NO}}
signed main()
{IOSint t;t=1;//cin>>t;while(t--){solve();}
}

B - Dentist Aoki

如果一个洞奇数次进,则总数加一偶数次进总数减一。

#include "bits/stdc++.h"
using namespace std;#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int> 
#define vi vector<int>
#define si set<int> 
#define mi map<int,int>
#define mc map<char,int>
#define YES cout<<"Yes"<<endl;
#define NO  cout<<"No"<<endl;
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
void solve()
{int n,q;cin>>n>>q;int sum=n;vector<int> a(n+1,1);for (int i=1;i<=q;i++){int x;cin>>x;if(a[x]==1){a[x]=0;sum--;}else {a[x]=1;sum++;}}cout<<sum;
}
signed main()
{IOSint t;t=1;//cin>>t;while(t--){solve();}
}

C - Sort 

先用一个数组记录第几个输入的数字,然后一个数组记录这个数字的位置,

然后再按照排列从小到大的顺序遍历,如果这个数不在相对应的位置上就和其需要到的位置上的数交换 。时间复杂度(n).

#include "bits/stdc++.h"
using namespace std;#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int> 
#define vi vector<int>
#define si set<int> 
#define mi map<int,int>
#define mc map<char,int>
#define YES cout<<"Yes"<<endl;
#define NO  cout<<"No"<<endl;
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
void solve()
{int n;cin>>n;vi a(n+1);vi b(n+1);for (int i=1;i<=n;i++){cin>>a[i];b[a[i]]=i;}int cnt=0;vector<pi> v;for (int i=1;i<=n;i++){if(b[i]!=i){int j=b[i];swap(a[i],a[j]);swap(b[a[i]],b[a[j]]);v.push_back({i,j});}}cout<<(int)v.size()<<endl;for (int i=0;i<(int)v.size();i++){auto [x,y]=v[i];cout<<x<<" "<<y<<endl;}}
signed main()
{IOSint t;t=1;//cin>>t;while(t--){solve();}
}

D - New Friends

这题考察联通块的知识,每个联通块内都可以有(cnt)*(cnt-1)/2条边。

这题可以用两种做法:

1.图论

因为存在一个点被联通块内多个点连接的情况,所以每次先加上边,最后除以2.

#include "bits/stdc++.h"
using namespace std;#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int> 
#define vi vector<int>
#define si set<int> 
#define mi map<int,int>
#define mc map<char,int>
#define YES cout<<"Yes"<<endl;
#define NO  cout<<"No"<<endl;
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int vis[200010];
void solve()
{int n,m;cin>>n>>m;vector<vector<int>> v(n+1);for (int i=1;i<=m;i++){int x,y;cin>>x>>y;v[x].push_back(y);v[y].push_back(x);}int ans=0;for (int i=1;i<=n;i++){if(vis[i]){continue;}queue<int> q;q.push(i);vis[i]=1;int cnt1=1,cnt2=0;while(q.size()){int u=q.front();q.pop();for (auto x : v[u]){cnt2++;if(vis[x]==0){vis[x]=1;cnt1++;q.push(x);}}}ans+=cnt1*(cnt1-1)-cnt2;}ans/=2;cout<<ans;
}
signed main()
{IOSint t;t=1;//cin>>t;while(t--){solve();}
}

2.并查集

#include "bits/stdc++.h"
using namespace std;#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int> 
#define vi vector<int>
#define si set<int> 
#define mi map<int,int>
#define mc map<char,int>
#define YES cout<<"Yes"<<endl;
#define NO  cout<<"No"<<endl;
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int p[200010],cnt[200010];
int find(int x)
{if(p[x]!=x) p[x]=find(p[x]);return p[x];
}
void solve()
{int n,m;cin>>n>>m;iota(p+1,p+n+1,1);for (int i=1;i<=m;i++){int x,y;cin>>x>>y;p[find(x)]=find(y);}int ans=-m;for (int i=1;i<=n;i++){cnt[find(i)]++;}for (int i=1;i<=n;i++){ans+=cnt[i]*(cnt[i]-1)/2;}cout<<ans;}
signed main()
{IOSint t;t=1;//cin>>t;while(t--){solve();}
}

E - Toward 0

mp[n]是n的期望花费。

cost1=mp[n/a]+x。  

cost2=\sum1~6 mp[n/i] / 6 + y  当i=1时 两边有相同的式子,把它移到左边。

cost2=\sum_{2}^{6}i mp[n/i]/5+\frac{6}{5}*y 

#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int> 
#define vi vector<int>
#define si set<int> 
#define mi map<int,int>
#define mc map<char,int>
#define YES cout<<"Yes"<<endl;
#define NO  cout<<"No"<<endl;
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }void solve()
{int n,a,x,y;cin>>n>>a>>x>>y;map<int,double> mp;auto dfs=[&](auto dfs,int u)-> double{if(u==0){return 0;}if(mp.find(u)!=mp.end()){return mp[u];}double cost1=dfs(dfs,u/a)+x;double cost2=0;for (int i=2;i<=6;i++){cost2+=dfs(dfs,u/i);}cost2=cost2/5+1.0*y*6/5;return mp[u]=min(cost1,cost2);};dfs(dfs,n);cout<<fixed<<setprecision(10)<<mp[n];	}
signed main()
{IOSint t;t=1;//cin>>t;while(t--){solve();}
}

这篇关于AtCoder Beginner Contest 350的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/925094

相关文章

2014 Multi-University Training Contest 8小记

1002 计算几何 最大的速度才可能拥有无限的面积。 最大的速度的点 求凸包, 凸包上的点( 注意不是端点 ) 才拥有无限的面积 注意 :  凸包上如果有重点则不满足。 另外最大的速度为0也不行的。 int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;}struct poin

2014 Multi-University Training Contest 7小记

1003   数学 , 先暴力再解方程。 在b进制下是个2 , 3 位数的 大概是10000进制以上 。这部分解方程 2-10000 直接暴力 typedef long long LL ;LL n ;int ok(int b){LL m = n ;int c ;while(m){c = m % b ;if(c == 3 || c == 4 || c == 5 ||

2014 Multi-University Training Contest 6小记

1003  贪心 对于111...10....000 这样的序列,  a 为1的个数,b为0的个数,易得当 x= a / (a + b) 时 f最小。 讲串分成若干段  1..10..0   ,  1..10..0 ,  要满足x非递减 。  对于 xi > xi+1  这样的合并 即可。 const int maxn = 100008 ;struct Node{int

AtCoder Beginner Contest 370 Solution

A void solve() {int a, b;qr(a, b);if(a + b != 1) cout << "Invalid\n";else Yes(a);} B 模拟 void solve() {qr(n);int x = 1;FOR(i, n) FOR(j, i) qr(a[i][j]);FOR(i, n) x = x >= i ? a[x][i]: a[i][x];pr2(

CF Bayan 2015 Contest Warm Up B.(dfs+暴力)

B. Strongly Connected City time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/475/probl

CF Bayan 2015 Contest Warm Up A.(模拟+预处理)

A. Bayan Bus time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/475/problem/A The fi

AtCoder Beginner Contest 369 D - Bonus EXP 动态规划

原题链接: https://atcoder.jp/contests/abc369/tasks/abc369_d 思路:   这道题为什么要用动态规划呢,其实,对于第i个怪物,我们有打与不打两种处理方式,而对于打,我们是获得两倍的经验值,还是一倍的经验值,与我们打了奇数只怪物还是打了偶数只怪物有关了,因此我们定义dp[i][0] 为前i只怪物总共打了偶数次,dp[i][1] 为前i只怪物总

2015 Multi-University Training Contest 5 1009 MZL#39;s Border

MZL's Border  Problem's Link:  http://acm.hdu.edu.cn/showproblem.php?pid=5351   Mean:  给出一个类似斐波那契数列的字符串序列,要你求给出的f[n]字符串中截取前m位的字符串s中s[1...i] = s[s.size()-i+1....s.size()]的最大长度。 analyse:   过计算

【UVa】10600 ACM Contest and Blackout 次小生成树

类型:次小生成树 题目大意: 为了举办ACM竞赛,市长决定给所有的n(3 <= n <= 100)所学校提供可靠的电力供应。当且仅当一个学校直接连到电站,或者连到另一个有可靠供应的学校时,才有可靠供应。现在给出在不同学校之间的布线成本,找出最便宜的两种连线方案。一个方案的成本等于其中所有学校之间连线的成本的总和。 题目分析: 次小生成树。 先求出最小生成树,然后枚举所有不在

【POJ】3660 Cow Contest floyd(可以拓扑排序?)

Cow Contest Time Limit: 1000MS Memory Limit: 65536KTotal Submissions: 6925 Accepted: 3792 Description N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating i