【牛客训练记录】牛客周赛 Round 62

https://ac.nowcoder.com/acm/contest/91177#question

赛后反思

一直都不会做期望，对于概率论相关的需要加强

A题

直接模拟字符串字符交换即可

#include <bits/stdc++.h>
#define int long longusing namespace std;void solve(){string s; cin>>s;cout<<s[1]<<s[0]<<s[2]<<s[3]<<s[4];	
}signed main(){// int T; cin>>T; while(T--)solve();return 0;
}

B题

\(x = 0\) 原地不动，直接模拟这个 \(x\) 即可，位于正半轴 \(-a[i]\) 位于负半轴 \(+a[i]\)，更新答案即可

#include <bits/stdc++.h>
#define int long longusing namespace std;void solve(){int n,x; cin>>n>>x;vector<int> a(n + 1);for(int i = 1;i<=n;i++) cin>>a[i];int ans = 0;for(int i = 1;i<=n;i++){if(x==0) continue;ans+=a[i];if(x>0) x-=a[i];else if(x<0) x+=a[i];}cout<<ans<<endl;
}signed main(){// int T; cin>>T; while(T--)solve();return 0;
}

C题

我们设 \(dis(x,y)\) 为点 \((x,y)\) 到原点的距离，我们首先需要找到有多少个圆覆盖到了原点，只要 \(dis(x,y) \le r\) 就是覆盖到了原点，最后我们需要移动的圆的个数为 \(max(0,cnt-k)\) 其中 \(cnt\) 代表有多少个圆覆盖到了原点，最后我们移动的代价就要加上这些需要移动的圆，移动的距离为 \(r - dis(x,y)\)，我们对代价进行排序，每次贪心选择代价最小的圆进行移动。

#include <bits/stdc++.h>
#define int long long
#define pi 3.14159265358979324using namespace std;struct node{int x,y,r;double dj;
};double dis(int x,int y){return sqrt(x*x+y*y);
}bool cmp(node x,node y){return x.dj < y.dj;
}vector<node> a;void solve(){int n,k; cin>>n>>k;for(int i = 1;i<=n;i++){int x,y,r; cin>>x>>y>>r;if(dis(x,y)<=r){double dj = pi*r*r*(r-dis(x,y));a.push_back((node){x,y,r,dj});}}	sort(a.begin(),a.end(),cmp);double ans = 0;int lim = a.size()-k;for(int i = 0;i<lim;i++) ans+=a[i].dj;cout<<fixed<<setprecision(8)<<ans<<endl;
}signed main(){// int T; cin>>T; while(T--)solve();return 0;
}

D题

期望不会

E题 部分分做法

我们对于每次询问直接暴力排序找中位数即可

#include <bits/stdc++.h>
#define int long longusing namespace std;void solve(){int n,q; cin>>n>>q;vector<int> a(n + 1);for(int i = 1;i<=n;i++) cin>>a[i];while(q--){int l,r; cin>>l>>r;vector<int> b;for(int i = l;i<=r;i++){b.push_back(a[i]);}sort(b.begin(),b.end());cout<<b[(b.size() + 1)/2-1]<<endl;}	
}signed main(){// int T; cin>>T; while(T--)solve();return 0;
}

F题 部分分做法

同 E 题

G题 部分分做法

直接大力 \(O(n!)\) 枚举所有的排列，再参照 B 题的方式模拟，更新答案和排列即可

#include <bits/stdc++.h>
#define int long longusing namespace std;const int N = 107;int n,x; 
vector<int> a(N);
int cho[N];
bool vis[N];
int ans = LONG_LONG_MAX;
int ansp[N];void pd(){int tx = x;int tans = 0;for(int i = 1;i<=n;i++){if(tx==0) continue;tans+=a[cho[i]];if(tx>0) tx-=a[cho[i]];else if(tx<0) tx+=a[cho[i]];}if(tans < ans){ans = tans;for(int i = 1;i<=n;i++) ansp[i] = cho[i];}
}void dfs(int x){if(x > n){pd();return;}for(int i = 1;i<=n;i++){if(vis[i]) continue;cho[x] = i;vis[i] = 1;dfs(x + 1);cho[x] = 0;vis[i] = 0;}
}void solve(){cin>>n>>x;for(int i = 1;i<=n;i++) cin>>a[i];dfs(1);cout<<ans<<endl;for(int i = 1;i<=n;i++) cout<<ansp[i]<<" ";
}signed main(){// int T; cin>>T; while(T--)solve();return 0;
}