目录

• A. Elections【800 / 模拟】
• B. Make it Divisible by 25【900 / 思维】
• C. Save More Mice【1000 / 贪心】
• D1. All are Same【1100 / 数学 最大公约数】
• 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
打表找规律，你会发现只要是'00' ,'25', '75, '50'这四种情况为后缀的必为25的倍数。
故需要枚举这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 / 数学 最大公约数】

https://codeforces.com/contest/1593/problem/D1
求其除了最小数外其它数的公共最大公约数

#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]]++;//统一变成正数，其实不用也可以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; }

总结

以上是生活随笔为你收集整理的Codeforces Round #744 (Div. 3)【A-D E的题解】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。