2022.3.4
題目地址：https://codeforces.com/contest/1003

目錄

• A. Polycarp's Pockets【模擬】
• B. Binary String Constructing【構造】
• C. Intense Heat【前綴和】
• D. Coins and Queries【貪心】
• E. Tree Constructing【構造樹】
• F. Abbreviation【DP 未完成】

A. Polycarp’s Pockets【模擬】

按照題意模擬即可。

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; set<int>st[N]; int k,n; int main(void) {cin>>n;for(int i=0;i<n;i++){int x; cin>>x;bool flag=0;for(int j=0;j<=k;j++)if(st[j].find(x)==st[j].end()){st[j].insert(x);flag=1;break;}if(!flag) st[++k].insert(x);}cout<<k+1<<endl;return 0; }

B. Binary String Constructing【構造】

你會發現01010101這種串是 2*4-1種 010101這種串是 2*3-1種
即我們可以先輸出一連串的01，或者一連串的10 這個是根據0多還是1多。

#include<bits/stdc++.h> using namespace std; int a,b,x; int main(void) {cin>>a>>b>>x;char c1,c2;if(a>b) c1='0',c2='1';//0多 01else c1='1',c2='0',swap(a,b);//1多 10for(int i=1;i<=x/2;i++) cout<<c1<<c2,a--,b--;//前面我們已經輸出了奇數個if(x%2) //說明剩余的還有偶數個{while(a) cout<<c1,a--;while(b) cout<<c2,b--;}else //說明剩余的是奇數個{while(b) cout<<c2,b--;while(a) cout<<c1,a--;}return 0; }

C. Intense Heat【前綴和】

#include<bits/stdc++.h> using namespace std; const int N=1e6+10; double a[N],s[N],n,k; int main(void) {cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i];double ans=-1e9;for(int i=k;i<=n;i++){for(int j=1;j+k-1<=n;j++){double temp=(s[j+i-1]-s[j-1])/i;if(temp>ans) ans=temp; }}printf("%.15lf",ans);return 0; }

D. Coins and Queries【貪心】

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; map<int,int>mp; int n,m; int main(void) {cin>>n>>m;for(int i=1;i<=n;i++){int x; cin>>x;mp[x]++;}while(m--){int x; cin>>x;int sum=0,cnt=0;for(int i=30;i>=0;i--){int u=1<<i;if(mp[u]&&sum+u<=x){int t=min(mp[u],(x-sum)/u);//盡可能的多拿cnt+=t;sum=sum+t*u;}if(sum==x) break;}if(sum==x) cout<<cnt<<endl;else puts("-1");}return 0; }

E. Tree Constructing【構造樹】

先弄好直徑，然后除了邊界點，中間加入滿足條件的樹。

#include<bits/stdc++.h> using namespace std; int n,d,k,id;//d直徑 k度數 vector<pair<int,int>>ve; void dfs(int u,int dep,int maxd) {if(dep==maxd) return;for(int i=0;i<k-1-(dep==0) && id<n;i++)//dep==0說明是直徑上的根節點有倆度{ve.push_back({u,++id});dfs(id,dep+1,maxd);} } int main(void) {cin>>n>>d>>k;if((n <= d) || (d > 1 && k < 2))最基本的條件都不滿足{cout << "NO" << endl;return 0;}for(int i=1;i<=d;i++) ve.push_back({i,i+1});id=d+1;for(int i=2;i<=d;i++) dfs(i,0,min(i-1,d-(i-1)));//可以加的最大的深度if(id<n) puts("NO");//說有的點不能全部加入else{puts("YES");for(int i=0;i<ve.size();i++) cout<<ve[i].first<<" "<<ve[i].second<<endl;}return 0; }

F. Abbreviation【DP 未完成】

總結

以上是生活随笔為你收集整理的Codeforces Round #494 (Div. 3)【未完结】的全部內容，希望文章能夠幫你解決所遇到的問題。

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