A 水题,不解释
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int gcd(int x,int y) { return y==0?x:gcd(y,x%y); } int lcm(int x,int y) { return x/gcd(x,y)*y; } int main() { int i,j,n,x,y,a,b; scanf("%d%d%d%d",&x,&y,&a,&b); n=lcm(x,y); printf("%d\n",b/n-(a-1)/n); return 0; }
B 简单计算几何,枚举四边形的对角线,然后分别求出在对角线左边的点和对角线构成的三角形面积的最大值还有右边的点和对角线构成三角形面积的最大值,然后最后相加就行了
#include <stdio.h> #include <string.h> #include <math.h> #include <algorithm> using namespace std; typedef struct { double x,y; }Point; typedef struct { Point x,y; }Vector; Point a[1005]; double xmulti(const Point p1, const Point p2, const Point p0) { return (p1.x - p0.x) * (p2.y - p0.y) - (p1.y - p0.y) * (p2.x - p0.x); } bool side(const Point p1, const Vector vec) { return xmulti(vec.x, p1, vec.y) > 1e-6; } int main() { int i,j,n,x,y,k; double ans=0; scanf("%d",&n); for (i=0;i<n;i++) { scanf("%lf%lf",&a[i].x,&a[i].y); } for (i=0;i<n;i++) { for (j=i+1;j<n;j++) { Vector vec; vec.x=a[i]; vec.y=a[j]; double s1=0,s2=0; for (k=0;k<n;k++) { if (side(a[k],vec)) { // printf("%d 1\n",k); s1=max(s1,fabs(xmulti(a[i],a[j],a[k]))/2); } else { // printf("%d 2\n",k); s2=max(s2,fabs(xmulti(a[i],a[j],a[k]))/2); } } // printf("%lf..%lf %d %d\n",s1,s2,i,j); if (s1!=0 && s2!=0) ans=max(ans,s1+s2); } } printf("%lf\n",ans); return 0; }
C.规律数学题,把长段可以拆成一些小段,其实最后说是约分,算出来的公式有(n-1)!都可以直接约掉的……
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; long long a[100005]; long long num[100005]; long long gcd(long long x,long long y) { return y==0?x:gcd(y,x%y); } int main() { int j,n; long long i; scanf("%d",&n); for (i=0;i<n;i++) { scanf("%I64d",&a[i]); } sort(a,a+n); long long nn=n-1; for (i=0;i<nn;i++) { if (n%2==0 && i==nn/2) num[i]=(1+nn/2)*(nn/2)+nn/2+1; else if (i<nn/2) num[i]=(i+2)*(i+1)+(i+1)*(nn-2*(i+1)); else num[i]=(nn-i-1+2)*(nn-i-1+1)+(nn-2*(nn-i-1+1))*(nn-1-i+1); // printf("%d, %I64d\n",i,num[i]); } long long up=0; for (i=0;i<n-1;i++) { num[i]=num[i]*abs(a[i]-a[i+1]); up+=num[i]; } up=up*2; for (i=0;i<n;i++) { up+=a[i]; } // printf("%I64d\n",up); long long down=n; long long tmp=gcd(up,down); printf("%I64d %I64d\n",up/tmp,down/tmp); return 0; }