SMU Spring 2023 Trial Contest Round 4
（^_^）
思路：pi=acos（-1）
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; const int N=1e5+5,M=1e3+5,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; double n; double pi=acos(-1); int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n; double r=n/pi; double s=pi*r*r/2; cout<<fixed<<setprecision(3)<<s; return 0; }
B植树造林
思路：奇偶性
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; const int N=1e5+5,M=1e3+5,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; int n; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n; if(n%2)cout<<1; else cout<<2; return 0; }
思路：排序，加k个最大的数，减k个最小的数
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; const int N=1e5+5,M=1e3+5,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; int n,k; int a[N]; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>k; for(int i=0;i<n;++i)cin>>a[i]; sort(a,a+n); ll s=0; for(int i=n-1;i>n-1-k;--i)s+=a[i]; for(int i=0;i<k;++i)s-=a[i]; cout<<s; return 0; }
思路：列公式
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; const int N=1e5+5,M=1e3+5,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; ll x11,x22,y11,y22; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>x11>>y11>>x22>>y22; ll y= lcm(y11,y22),xx1=x11*y/y11,xx2=x22*y/y22; ll d=gcd(xx1+xx2,y); cout<<(xx1+xx2)/d<<' '<<y/d<<'\n'; bool ok=false; d=gcd(abs(xx1-xx2),y); if(xx1<xx2)ok=true; if(ok)cout<<'-'; cout<<abs(xx1-xx2)/d<<' '; if(xx1==xx2)cout<<0<<'\n'; else cout<<y/d<<'\n'; d=gcd(x11*x22,y11*y22); cout<<x11*x22/d<<' '<<y11*y22/d<<'\n'; d=gcd(x11*y22,x22*y11); cout<<x11*y22/d<<' '<<x22*y11/d; return 0; }
思路：将边按点从大到小排序，用并查集将相连的点合并，当遍历到的边已在一个集合中，说明有环，若点小于等于k则删边
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; const int N=1e6+5,M=1e3+5,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; int n,m,k; int fa[N]; struct E{ int l,r; bool operator<(const E&e)const{ if(e.l==l)return r>e.r; else return l>e.l; } }g[2*N]; int find(int x){ if(x!=fa[x])fa[x]=find(fa[x]); return fa[x]; } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>m>>k; for(int i=1;i<=n;++i)fa[i]=i; for(int i=1;i<=m;++i)cin>>g[i].l>>g[i].r; sort(g+1,g+m+1); int ans=0; for(int i=1;i<=m;++i){ int a=find(g[i].l),b=find(g[i].r); if(a!=b)fa[a]=b; else if(min(g[i].l,g[i].r)<=k)ans++; } cout<<ans; return 0; }
思路：根据要求，需要升序且相邻之间有公因数；先排序，再从小到大将每个数的因数记录下来，f（i）表示最后一个数的质因子包含i的好序列的最大长度
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; const int N=1e6+5,M=1e3+5,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; int t,n,a[N]; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>t; while(t--){ cin>>n; int ans=0; for(int i=0;i<n;++i)cin>>a[i]; sort(a,a+n); vector<int>f(a[n-1]+1); for(int i=0;i<n;++i){ int s=a[i],c=0; vector<int>p; for(int j=2;j*j<=s&s!=1;++j){ if(s%j)continue; p.push_back(j); while(s%j==0)s/=j; } if(s!=1)p.push_back(s); for(auto j:p)c=max(c,f[j]); c++; for(auto j:p)f[j]=c; ans=max(ans,c); } cout<<ans<<'\n'; } return 0; }
思路：当为L时，字符打进光标右侧；当为R时，字符打进光标左侧
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; const int N=1e5+5,M=1e3+5,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; string s,p; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); string a="",b=""; cin>>s>>p; for(int i=0;i<s.size();++i){ if(p[i]=='R')a+=s[i]; else b+=s[i]; } reverse(b.begin(), b.end()); cout<<a<<b; return 0; }