說實話題目真的不難，但是自己真的垃圾，
第一題簽到過了
第二題腦子只想貪心，過了8個點，后來發現貪心有點問題。又想到了用小根堆。結果TLE。最后發現是二分
第三題想到了求環，想到了用并查集。沒有想到聯通塊的大小就是環。

目錄

• A: AcWing 3577. 選擇數字 【難度: 簡單 / 知識點: 思維】
• B: AcWing 3578. 最大中位數 【難度: 一般 / 知識點: 二分答案】
• C: AcWing 3579. 數字移動 【難度: 中 / 知識點: 并查集】

A: AcWing 3577. 選擇數字 【難度: 簡單 / 知識點: 思維】

https://www.acwing.com/problem/content/3580/

#include<cstdio> #include<iostream> #include<algorithm> #include<map> using namespace std; typedef long long int LL; const int N=1e5+10; int a[110],b[110]; bool st[N]; int main(void) {int m;cin>>m;for(int i=0;i<m;i++) cin>>a[i],st[a[i]]=true;;int n; cin>>n;for(int i=0;i<n;i++) cin>>b[i],st[b[i]]=true;for(int i=0;i<m;i++){for(int j=i;j<n;j++){if(!st[a[i]+b[j]]){cout<<a[i]<<" "<<b[j]<<endl;return 0;}} }return 0; }

其實你會發現，每組數據求最大值，其組合的數據一定不會在這里的集合中出現。

#include<cstdio> #include<iostream> #include<algorithm> #include<map> using namespace std; typedef long long int LL; int main(void) {int m;cin>>m;LL x,a=0,b=0;for(int i=0;i<m;i++) cin>>x,a=max(a,x);int n; cin>>n;for(int i=0;i<n;i++) cin>>x,b=max(b,x);cout<<a<<" "<<b<<endl;return 0; }

B: AcWing 3578. 最大中位數 【難度: 一般 / 知識點: 二分答案】

https://www.acwing.com/problem/content/3581/
用排序后有單調性，故用二分答案，注意開long long .
這道和洛谷二分題單里的跳石頭大同小異

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; typedef long long int LL; const int N=2*1e5+10; LL a[N]; int n,k; bool check(LL mid) {LL res=0;for(int i=n/2;i<n;i++){if(a[i]<mid) res+=mid-a[i];//需要補}if(res<=k) return true;//補的數的和大于kelse return false; } int main(void) {cin>>n>>k;for(int i=0;i<n;i++) cin>>a[i];sort(a,a+n);LL l=0,r=2*1e9;while(l<r){LL mid=l+r+1>>1;if(check(mid)) l=mid;else r=mid-1;}cout<<l<<endl;return 0; }

C: AcWing 3579. 數字移動 【難度: 中 / 知識點: 并查集】

https://www.acwing.com/problem/content/3582/

不難看出這應該是一個圖。
我們以
n=6 ， 4 6 2 1 5 3為例

你會發現每一個都是一個環，而環的大小正好等于連通塊的大小。
故直接套用并查集求連通塊的模板。

#include<bits/stdc++.h> using namespace std; const int N=1e5*2+10; int p[N],cnt[N],a[N],n,t; int find(int x) {if(x!=p[x]) p[x]=find(p[x]);return p[x]; } int main(void) {cin>>t;while(t--){cin>>n;for(int i=1;i<=n;i++) cin>>a[i],p[i]=i,cnt[i]=1;for(int i=1;i<=n;i++){if(find(a[i])!=find(i)){cnt[find(i)]+=cnt[find(a[i])];p[find(a[i])]=find(i);}}for(int i=1;i<=n;i++) cout<<cnt[find(i)]<<" ";cout<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的Acwing第 1 场周赛【完结】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。