Google算法题 有限次询问下估算图的边数 Code jam Qualification Round 2022 Q5
2022/4/4 22:19:23
本文主要是介绍Google算法题 有限次询问下估算图的边数 Code jam Qualification Round 2022 Q5,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
https://codingcompetitions.withgoogle.com/codejam/round/0000000000876ff1/0000000000a45fc0#problem
1、利用总边数=度数/2。
2、为了解决度数不平衡的问题,交替使用T(随机传送)和W(邻接传送)操作。
例如,少部分的点的度很高、但是大部分的点度数比较低,使用T操作很难前往度很高的点,但W操作则容易到达。
3、对T得到的样本累计求得平均度数,对W的结果进行记录(不进行累计的原因是W操作和T不是一致的)。
4、求和时,未知的用平均代替,已知的则用记录值。
#include<bits/stdc++.h> using namespace std; void YD() { int N,K; cin>>N>>K; //vector<int> room(N+1,0); int cur,pass_num; long long sum_num=0,sum_degree=0; cin>>cur>>pass_num; //sum_num++; //sum_degree+=pass_num; unordered_map<int,int> index_degree; index_degree[cur]=pass_num; //room[cur]=pass_num; K/=2; while(K--) { int nxt=rand()%(N)+1; cout<<'T'<<' '<<nxt<<endl; cin>>cur>>pass_num; sum_num++; sum_degree+=pass_num; index_degree[cur]=pass_num; cout<<'W'<<endl; cin>>cur>>pass_num; //sum_num++; //sum_degree+=pass_num; index_degree[cur]=pass_num; } double average_degree_div2=double(sum_degree)/sum_num/2; double sum_degree_div2=0.; for(int i=1;i<=N;i++) { if(index_degree.count(i)) sum_degree_div2+=(double)index_degree[i]/2.; else sum_degree_div2+=average_degree_div2; } cout<<"E "<<(long long)(sum_degree_div2+0.5)<<endl; } int main() { int t; cin >> t; while (t--) { YD(); } return 0; }
这篇关于Google算法题 有限次询问下估算图的边数 Code jam Qualification Round 2022 Q5的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-01got an unexpected keyword argument
- 2024-03-30维多利亚的秘密 golang入坑系统
- 2024-03-29mongodb sort by date
- 2024-03-29go swagger
- 2024-03-25mongodb cdc
- 2024-03-25how to use go in vscode
- 2024-03-22mongooseserverselectionerror: connect econnrefused ::1:27017
- 2024-03-21pymongo insert_many
- 2024-03-18projection mongodb
- 2024-03-14clickhouse-go