• AtCoder Beginner Contest 350

    A - Past ABCs

    简单的枚举判断即可

    1. #include "bits/stdc++.h"
    2. using namespace std;
    3.  
    4. #define int long long 
    5. #define endl '\n'
    6. #define IOS ios::sync_with_stdio(0),cin.tie(0);
    7. #define all(x) x.begin(),x.end()
    8. #define pi pair<int,int> 
    9. #define vi vector<int>
    10. #define si set<int> 
    11. #define mi map<int,int>
    12. #define mc map<char,int>
    13. #define YES cout<<"Yes"<<endl;
    14. #define NO  cout<<"No"<<endl;
    15. template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
    16. template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
    17. void solve()
    18. {
    19. 	string s;
    20. 	cin>>s;
    21. 	int sum=0;
    22. 	for (int i=3;i<6;i++){
    23. 		sum=sum*10+(s[i]-'0');
    24. 	}
    25. 	string s1=s.substr(0,3);
    26. 	if(s1=="ABC" && sum>=1 && sum<=349 && sum!=316){
    27. 		YES
    28. 	}
    29. 	else {
    30. 		NO
    31. 	}
    32. 	
    33. }
    34. signed main()
    35. {
    36. 	IOS
    37. 	int t;
    38. 	t=1;//cin>>t;
    39. 	while(t--){
    40. 		solve();
    41. 	}
    42. }

    B - Dentist Aoki

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

    1. #include "bits/stdc++.h"
    2. using namespace std;
    3.  
    4. #define int long long 
    5. #define endl '\n'
    6. #define IOS ios::sync_with_stdio(0),cin.tie(0);
    7. #define all(x) x.begin(),x.end()
    8. #define pi pair<int,int> 
    9. #define vi vector<int>
    10. #define si set<int> 
    11. #define mi map<int,int>
    12. #define mc map<char,int>
    13. #define YES cout<<"Yes"<<endl;
    14. #define NO  cout<<"No"<<endl;
    15. template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
    16. template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
    17. void solve()
    18. {
    19. 	int n,q;
    20. 	cin>>n>>q;
    21. 	int sum=n;
    22. 	vector<int> a(n+1,1);
    23.  
    24. 	for (int i=1;i<=q;i++){
    25. 		int x;
    26. 		cin>>x;
    27. 		if(a[x]==1){
    28. 			a[x]=0;
    29. 			sum--;
    30. 		}
    31. 		else {
    32. 			a[x]=1;
    33. 			sum++;
    34. 		}
    35. 	}
    36. 	cout<<sum;
    37. }
    38. signed main()
    39. {
    40. 	IOS
    41. 	int t;
    42. 	t=1;//cin>>t;
    43. 	while(t--){
    44. 		solve();
    45. 	}
    46. }

    C - Sort 

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

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

    1. #include "bits/stdc++.h"
    2. using namespace std;
    3.  
    4. #define int long long 
    5. #define endl '\n'
    6. #define IOS ios::sync_with_stdio(0),cin.tie(0);
    7. #define all(x) x.begin(),x.end()
    8. #define pi pair<int,int> 
    9. #define vi vector<int>
    10. #define si set<int> 
    11. #define mi map<int,int>
    12. #define mc map<char,int>
    13. #define YES cout<<"Yes"<<endl;
    14. #define NO  cout<<"No"<<endl;
    15. template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
    16. template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
    17. void solve()
    18. {
    19. 	int n;
    20. 	cin>>n;
    21. 	vi a(n+1);
    22. 	vi b(n+1);
    23. 	
    24. 	for (int i=1;i<=n;i++){
    25. 		cin>>a[i];
    26. 		b[a[i]]=i;
    27. 	}
    28. 	int cnt=0;
    29. 	vector<pi> v;
    30.  
    31. 	for (int i=1;i<=n;i++){
    32. 		if(b[i]!=i){
    33. 			int j=b[i];
    34. 			swap(a[i],a[j]);
    35. 			swap(b[a[i]],b[a[j]]);
    36. 			v.push_back({i,j});
    37. 		}
    38. 	}
    39. 	
    40. 	cout<<(int)v.size()<<endl;
    41. 	for (int i=0;i<(int)v.size();i++){
    42. 		auto [x,y]=v[i];
    43. 		cout<<x<<" "<<y<<endl;
    44. 	}
    45. 	
    46. }
    47. signed main()
    48. {
    49. 	IOS
    50. 	int t;
    51. 	t=1;//cin>>t;
    52. 	while(t--){
    53. 		solve();
    54. 	}
    55. }

    D - New Friends

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

    这题可以用两种做法：

    1.图论

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

    1. #include "bits/stdc++.h"
    2. using namespace std;
    3.  
    4. #define int long long 
    5. #define endl '\n'
    6. #define IOS ios::sync_with_stdio(0),cin.tie(0);
    7. #define all(x) x.begin(),x.end()
    8. #define pi pair<int,int> 
    9. #define vi vector<int>
    10. #define si set<int> 
    11. #define mi map<int,int>
    12. #define mc map<char,int>
    13. #define YES cout<<"Yes"<<endl;
    14. #define NO  cout<<"No"<<endl;
    15. template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
    16. template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
    17. int vis[200010];
    18. void solve()
    19. {
    20. 	int n,m;
    21. 	cin>>n>>m;
    22. 	vector<vector<int>> v(n+1);
    23. 	for (int i=1;i<=m;i++){
    24. 		int x,y;
    25. 		cin>>x>>y;
    26. 		v[x].push_back(y);
    27. 		v[y].push_back(x);
    28. 	}
    29. 	int ans=0;
    30. 	
    31. 	for (int i=1;i<=n;i++){
    32. 		if(vis[i]){
    33. 			continue;
    34. 		}
    35. 		queue<int> q;
    36. 		q.push(i);
    37. 		vis[i]=1;
    38. 		int cnt1=1,cnt2=0;
    39. 		while(q.size()){
    40. 			int u=q.front();
    41. 			q.pop();
    42. 			for (auto x : v[u]){
    43. 				cnt2++;
    44. 				if(vis[x]==0){
    45. 					vis[x]=1;
    46. 					cnt1++;
    47. 					q.push(x);
    48. 					
    49. 				}
    50. 				
    51. 			}
    52. 		}
    53. 		
    54. 		ans+=cnt1*(cnt1-1)-cnt2;
    55. 		
    56. 	}
    57. 	ans/=2;
    58. 	cout<<ans;
    59. }
    60. signed main()
    61. {
    62. 	IOS
    63. 	int t;
    64. 	t=1;//cin>>t;
    65. 	while(t--){
    66. 		solve();
    67. 	}
    68. }

    2.并查集

    1. #include "bits/stdc++.h"
    2. using namespace std;
    3.  
    4. #define int long long 
    5. #define endl '\n'
    6. #define IOS ios::sync_with_stdio(0),cin.tie(0);
    7. #define all(x) x.begin(),x.end()
    8. #define pi pair<int,int> 
    9. #define vi vector<int>
    10. #define si set<int> 
    11. #define mi map<int,int>
    12. #define mc map<char,int>
    13. #define YES cout<<"Yes"<<endl;
    14. #define NO  cout<<"No"<<endl;
    15. template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
    16. template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
    17. int p[200010],cnt[200010];
    18. int find(int x)
    19. {
    20. 	if(p[x]!=x) p[x]=find(p[x]);
    21.     return p[x];
    22. }
    23. void solve()
    24. {
    25. 	int n,m;
    26. 	cin>>n>>m;
    27. 	iota(p+1,p+n+1,1);
    28. 	for (int i=1;i<=m;i++){
    29. 		int x,y;
    30. 		cin>>x>>y;
    31. 		p[find(x)]=find(y);
    32. 	}
    33. 	
    34. 	int ans=-m;
    35. 	for (int i=1;i<=n;i++){
    36. 		cnt[find(i)]++;
    37. 	}
    38. 	
    39. 	for (int i=1;i<=n;i++){
    40. 		ans+=cnt[i]*(cnt[i]-1)/2;
    41. 	}
    42. 	
    43. 	cout<<ans;
    44.  
    45.  
    46. }
    47. signed main()
    48. {
    49. 	IOS
    50. 	int t;
    51. 	t=1;//cin>>t;
    52. 	while(t--){
    53. 		solve();
    54. 	}
    55. }

    E - Toward 0

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

    cost1=mp[n/a]+x。  

    cost2=∑" role="presentation">∑1~6 mp[n/i] / 6 + y  当i=1时 两边有相同的式子，把它移到左边。

    cost2=∑26imp[n/i]/5+65∗y" role="presentation">∑26imp[n/i]/5+65∗y 

    1. #define int long long 
    2. #define endl '\n'
    3. #define IOS ios::sync_with_stdio(0),cin.tie(0);
    4. #define all(x) x.begin(),x.end()
    5. #define pi pair<int,int> 
    6. #define vi vector<int>
    7. #define si set<int> 
    8. #define mi map<int,int>
    9. #define mc map<char,int>
    10. #define YES cout<<"Yes"<<endl;
    11. #define NO  cout<<"No"<<endl;
    12. template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
    13. template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
    14.  
    15. void solve()
    16. {
    17. 	int n,a,x,y;
    18. 	cin>>n>>a>>x>>y;
    19. 	map<int,double> mp;
    20. 	
    21. 	auto dfs=[&](auto dfs,int u)-> double{
    22. 		if(u==0){
    23. 			return 0;
    24. 		}
    25. 		if(mp.find(u)!=mp.end()){
    26. 			return mp[u];
    27. 		}
    28. 		
    29. 		double cost1=dfs(dfs,u/a)+x;
    30. 		double cost2=0;
    31. 		for (int i=2;i<=6;i++){
    32. 			cost2+=dfs(dfs,u/i);
    33. 		}
    34. 		cost2=cost2/5+1.0*y*6/5;
    35. 	
    36. 		return mp[u]=min(cost1,cost2);
    37. 	};
    38. 	dfs(dfs,n);
    39. 	cout<<fixed<<setprecision(10)<<mp[n];	
    40. 	
    41. }
    42. signed main()
    43. {
    44. 	IOS
    45. 	int t;
    46. 	t=1;//cin>>t;
    47. 	while(t--){
    48. 		solve();
    49. 	}
    50. }

  • 相关阅读:
    LeetCode 144. 二叉树的前序遍历
    linux文件的隐藏属性、特殊属性和ACL权限
    Flink快速入门
    Java中的值传递与引用传递 含面试题
    Docker笔记-09 Docker Compose
    C++入门笔记
    [附源码]Python计算机毕业设计SSM开放实验室管理系统（程序+LW)
    【AI】《动手学-深度学习-PyTorch版》笔记（二十）：图像增强、微调
    Shell特殊变量(Shell $#、$*、$@、$?、$$)的使用
    mysql中GROUP_CONCAT函数详解
  • 原文地址：https://blog.csdn.net/yrhuadonghui/article/details/138039453