目錄

• A. Elections【800 / 模擬】
• B. Make it Divisible by 25【900 / 思維】
• C. Save More Mice【1000 / 貪心】
• D1. All are Same【1100 / 數(shù)學 最大公約數(shù)】
• E. Gardener and Tree【1600 / 拓撲】

A. Elections【800 / 模擬】

https://codeforces.com/contest/1593/problem/A

#include<bits/stdc++.h> using namespace std; typedef long long int LL; const int N=1e5*2+10; int n,m,t; LL a[N]; int main(void) {cin>>t;while(t--){cin>>a[0]>>a[1]>>a[2];for(int i=0;i<3;i++){LL ans=0;for(int j=0;j<3;j++) if(i!=j) ans=max(ans,a[j]);if(ans<a[i]) cout<<0<<" ";else cout<<ans-a[i]+1<<" ";}cout<<endl;}return 0; }

B. Make it Divisible by 25【900 / 思維】

https://codeforces.com/contest/1593/problem/B
打表找規(guī)律，你會發(fā)現(xiàn)只要是'00' ,'25', '75, '50'這四種情況為后綴的必為25的倍數(shù)。
故需要枚舉這4種情況，貪心的刪除求解，總的求一個min。

#include<bits/stdc++.h> using namespace std; int t; string s; int solve(char a,char b) {int len=0;int k=s.size()-1;for(int i=s.size()-1;i>=0;i--) {if(len&&s[i]==b) return (len-i-1)+(k-len);if(s[i]==a) len=i;}return 1e9; } int main(void) {cin>>t;while(t--){cin>>s;int ans=1e9;ans=min(ans,solve('5','2')); ans=min(ans,solve('5','7')); ans=min(ans,solve('0','5'));ans=min(ans,solve('0','0'));cout<<ans<<endl;}return 0; }

C. Save More Mice【1000 / 貪心】

https://codeforces.com/contest/1593/problem/C
排序，從后到前的判斷，可不可以，然后累加距離和。

#include<bits/stdc++.h> using namespace std; typedef long long int LL; const int N=1e5*5+10; LL t,n,k; LL a[N]; int main(void) {cin>>t;while(t--){cin>>n>>k;for(int i=1;i<=k;i++) cin>>a[i];sort(a+1,a+k+1);LL cnt=0,ans=0;for(int i=k;i>=1;i--){if(cnt>=a[i]) break;cnt+=n-a[i];ans++;}cout<<ans<<endl;}return 0; }

D1. All are Same【1100 / 數(shù)學 最大公約數(shù)】

https://codeforces.com/contest/1593/problem/D1
求其除了最小數(shù)外其它數(shù)的公共最大公約數(shù)

#include<bits/stdc++.h> using namespace std; typedef long long int LL; const int N=1e3*2+10; LL t,n,a[N]; LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;} int main(void) {cin>>t;while(t--){cin>>n;map<LL,LL>mp;for(int i=1;i<=n;i++) cin>>a[i],a[i]+=1e6,mp[a[i]]++;//統(tǒng)一變成正數(shù)，其實不用也可以sort(a+1,a+1+n);if(mp.size()==1) cout<<"-1"<<endl;//全部相等的情況else {vector<LL>ans;for(int i=1;i<=n;i++) if(a[i]-a[1]) ans.push_back(a[i]-a[1]);LL w=ans[0];for(int i=0;i<ans.size();i++) if(i) w=min(w,gcd(ans[i],ans[i-1]));cout<<w<<endl;}}return 0; }

E. Gardener and Tree【1600 / 拓撲】

https://codeforces.com/contest/1593/problem/E
拓撲搞一下

#include<bits/stdc++.h> using namespace std; const int N=1e5*5; int t,n,k; int d[N]={0}; vector<int>ve[N]; int main(void) {cin>>t;while(t--){cin>>n>>k;for(int i=1;i<=n;i++) ve[i].clear();memset(d,0,sizeof 4*(n+1));for(int i=1;i<=n-1;i++){int a,b; cin>>a>>b;ve[a].push_back(b);ve[b].push_back(a);d[a]++,d[b]++;}queue<int>q;for(int i=1;i<=n;i++) if(d[i]<=1) q.push(i);//<=1 的目的是 有孤點int cnt=n;while(q.size()&&k){queue<int>temp;cnt-=q.size();while(q.size()){auto t=q.front(); q.pop();for(int i=0;i<ve[t].size();i++){if(--d[ve[t][i]]==1) temp.push(ve[t][i]);}}q=temp;k--;}cout<<cnt<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Codeforces Round #744 (Div. 3)【A-D E的题解】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。