LCS
#include<iostream> #include<cstring> #include<queue> #include<map> #include<set> #include<algorithm> #include<cmath> #include<vector> #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int,int> pii; const int inf=0x3f3f3f3f; const double eps=1e-8; int a,b,c,n; int x[4]; int main(){ cin>>a>>b>>c>>n; x[1]=a,x[2]=b,x[3]=c; sort(x+1,x+3+1); swap(x[1],x[3]); string s1,s2,s3; if(x[1]+x[2]-n>x[3]) puts("NO"); else{ s1=string(x[3],'a')+string(x[1]-x[3],'b')+string(n-x[1],'d'); s2=string(x[3],'a')+string(x[1]-x[3],'b')+string(x[2]-x[3],'c')+string(n-x[1]-x[2]+x[3],'e'); s3=string(x[3],'a')+string(x[2]-x[3],'c')+string(n-x[2],'f'); if(a>=b&&b>=c) cout<<s1<<endl<<s2<<endl<<s3; else if(a>=c&&c>=b) cout<<s2<<endl<<s1<<endl<<s3; else if(b>=a&&a>=c) cout<<s3<<endl<<s2<<endl<<s1; else if(b>=c&&c>=a) cout<<s3<<endl<<s1<<endl<<s2; else if(c>=a&&a>=b) cout<<s2<<endl<<s3<<endl<<s1; else cout<<s1<<endl<<s3<<endl<<s2; } }
Inverse Pair
#include<iostream> #define ll long long using namespace std; const int N=200010; int q[N],tmp[N]; int n; ll merge_sort(int l,int r){ if(l>=r) return 0; int mid=(l+r)>>1; ll res=merge_sort(l,mid)+merge_sort(mid+1,r); int k=0,i=l,j=mid+1; while(i<=mid&&j<=r){ if(q[i]<=q[j]) tmp[k++]=q[i++]; else{ tmp[k++]=q[j++]; res+=(mid-i+1); } } while(i<=mid) tmp[k++]=q[i++]; while(j<=r) tmp[k++]=q[j++]; for(int i=l,j=0;i<=r;i++,j++) q[i]=tmp[j]; return res; } int vis[N]; int main(){ scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&q[i]); if(vis[q[i]+1]) q[i]++; vis[q[i]]=1; } printf("%lld",merge_sort(0,n-1)); }
Average
#include<iostream> #include<cstring> #include<queue> #include<map> #include<set> #include<algorithm> #include<cmath> #include<vector> #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int,int> pii; const int inf=0x3f3f3f3f; const double eps=1e-6; const int N=100010; int n,m,x,y; double a[N],b[N],c[N]; double s[N]; bool check1(double mid){ for(int i=1;i<=n;i++) c[i]=a[i]-mid; for(int i=1;i<=n;i++) s[i]=s[i-1]+c[i]; double mn=2e9,mx=-2e9; for(int i=x;i<=n;i++){ mn=min(mn,s[i-x]); mx=max(mx,s[i]-mn); } return mx>=0; } bool check2(double mid){ for(int i=1;i<=m;i++) c[i]=b[i]-mid; for(int i=1;i<=m;i++) s[i]=s[i-1]+c[i]; double mn=2e9,mx=-2e9; for(int i=y;i<=m;i++){ mn=min(mn,s[i-y]); mx=max(mx,s[i]-mn); } return mx>=0; } int main(){ scanf("%d%d%d%d",&n,&m,&x,&y); for(int i=1;i<=n;i++) scanf("%lf",&a[i]); for(int i=1;i<=m;i++) scanf("%lf",&b[i]); double l=0.0,r=100000.0; while(r-l>eps){ double mid=(l+r)/2.0; if(check1(mid)) l=mid; else r=mid; } double ans1=l; l=0.0,r=100000.0; while(r-l>eps){ double mid=(l+r)/2.0; if(check2(mid)) l=mid; else r=mid; } double ans2=l; printf("%.6lf",ans1+ans2); }